Teoria automatelor

Teoria automatelor- o secțiune de matematică discretă, care studiază automatele abstracte - calculatoare prezentate sub formă de modele matematice - și problemele pe care le pot rezolva.

Teoria automatelor este cel mai strâns legată de teoria algoritmilor: automatul transformă informația discretă în pași în momente discrete de timp și generează rezultatul în pași ai unui algoritm dat.

Terminologie

Simbol- orice bloc atomic de date care poate avea un efect asupra mașinii. Cel mai adesea, un simbol este o literă într-o limbă comună, dar poate fi, de exemplu, un element grafic al unei diagrame.

• Cuvânt- un șir de caractere creat prin concatenare (conexiune).
• Alfabet- un set finit de caractere diferite (multe caractere)
• Limba- setul de cuvinte format din simbolurile alfabetului dat. Poate fi finit sau infinit.

Mașinărie Mașinărie- o secvență (tuplu) de cinci elemente, unde: Cuvântul Automat citește șirul final de caractere a 1 ,a 2 ,…., a n , unde a i ∈ Σ și se numește cuvânt.Setul tuturor cuvintelor este scris ca Σ*. Cuvânt primit Un cuvânt w ∈ Σ* este acceptat de automat dacă q n ∈ F.

Se spune că limbajul este L citit (primit) de un automat M dacă este format din cuvinte w bazate pe alfabet, astfel încât dacă aceste cuvinte sunt introduse în M, la sfârșitul procesării se ajunge la una dintre stările de acceptare F:

De obicei, un automat trece de la stare la stare folosind o funcție de tranziție, în timp ce citește un caracter din intrare. Există, de asemenea, automate care pot trece la o stare nouă fără a citi un personaj. Este apelată funcția de salt fără a citi un caracter -tranziție(tranziție epsilon).

Aplicație

În practică, teoria automatelor este utilizată în dezvoltarea de lexer și parseri pentru limbaje formale (inclusiv limbaje de programare), precum și în construcția de compilatoare și dezvoltarea limbajelor de programare în sine.

O altă aplicație importantă a teoriei automatelor este determinarea riguroasă din punct de vedere matematic a solubilității și complexității problemelor.

Sarcini tipice

• Construcția și minimizarea automatelor- construirea unui automat abstract dintr-o clasă dată care rezolvă o problemă dată (acceptând un limbaj dat), eventual cu minimizarea ulterioară din punct de vedere al numărului de stări sau al numărului de tranziții.
• Sinteza automatelor- construirea unui sistem din „automate elementare” date, echivalente cu un automat dat. Un astfel de automat se numește structural. Este utilizat, de exemplu, în sinteza circuitelor electrice digitale pe o bază de element dat.

Vezi si

Literatură

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman Introducere în teoria automatelor, limbaje și calcul. - M .: Williams, 2002. - S. 528. - ISBN 0-201-44124-1
• Kasyanov V. N. Prelegeri despre teoria limbajelor formale, automate și complexitate computațională. - Novosibirsk: NSU, 1995. - C. 112.

Legături

Fundația Wikimedia. 2010 .

Vedeți ce este „Teoria automatelor” în alte dicționare:

Teoria automatelor

Teoria automatelor- o secțiune de cibernetică teoretică care studiază modele matematice (numite aici automate sau mașini) ale dispozitivelor reale sau posibile care procesează informații discrete în cicluri discrete. Principalul ... ... Dicţionar economic şi matematic

teoria automatelor- O ramură a ciberneticii teoretice care studiază modele matematice (numite aici automate sau mașini) ale dispozitivelor reale sau posibile care procesează informații discrete în cicluri discrete. Conceptele principale ale acestei teorii ...... Manualul Traducătorului Tehnic

Exist., număr de sinonime: 1 tavt (1) Dicţionar de sinonime ASIS. V.N. Trishin. 2013... Dicţionar de sinonime

teoria automatelor- automatų teorija statusas T sritis automatika atitikmenys: angl. teoria automatelor vok. Automatentheorie, f rus. teoria automatelor, f pranc. theorie des automates, f … Automatikos terminų žodynas

Acest termen are alte semnificații, vezi Diagrama de stare. O diagramă de stări este un grafic direcționat pentru un automat finit, în care vârfurile indică stările arcului arată tranziții între două stări În practică ... ... Wikipedia

Teoria mașinilor și mecanismelor (TMM) este o disciplină științifică despre metodele generale de cercetare, construcție, cinematica și dinamica mecanismelor și mașinilor și despre fundamentele științifice ale proiectării acestora. Cuprins 1 Istoria dezvoltării disciplinei 2 Concepte de bază ... Wikipedia

TEORIE- (1) un sistem de idei și principii științifice care rezumă experiența practică, reflectând legile și reglementările naturale obiective care formează (vezi) sau o secțiune a oricărei științe, precum și un set de reguli în domeniul oricărui fel de cunoștințe milioane ...... Marea Enciclopedie Politehnică

Teoria algoritmilor Dicţionar economic şi matematic

Teoria algoritmilor- o ramură a matematicii care studiază proprietățile generale ale algoritmilor. Problema construcției unui algoritm cu anumite proprietăți se numește problemă algoritmică, imposibilitatea lui de rezolvare înseamnă absența unui algoritm adecvat; Dacă… … Dicţionar economic şi matematic

Cărți

• Teoria automatelor. Manual pentru studii universitare și postuniversitare, Kudryavtsev V.B. Manualul conține material extins despre teoria automatelor. Introduce conceptul de automat, oferă teorii...

Agenția Federală pentru Educație

Stat instituție educațională studii profesionale superioare

„UNIVERSITATEA DE STAT MOSCOVA

INSTRUMENT ȘI INFORMATICĂ»

Departamentul IT-4 „Calculatoare și rețele personale”

"APROBA"

Şef Departament IT-4

Mihailov B.M.

„___” __________________ 2007

PRELEGII

La disciplina 1425 „Teoria automatelor”

Pentru studenții din anul II ai Facultății de IT

Specialități 230101

„Calculatoare, complexe, sisteme și rețele”

Se discută în ședința departamentului

„___” ________________2007

Protocol nr. _____

Moscova 2007

^ Dispoziții generale

Scopurile si obiectivele disciplinei

Scopul disciplinei este de a prezenta principiile de organizare a software-ului și hardware-ului în cadrul computerelor personale folosind teoria automatelor, stăpânirea abilităților de dezvoltare a software-ului și hardware-ului computerelor.

^ Cerințe pentru nivelul de stăpânire a conținutului disciplinei

Cunoștințe dobândite ca urmare a stăpânirii disciplinei:

• 
  Principii și concepte de bază ale teoriei automatelor;
• 
  Aplicarea teoriei automatelor pentru construirea de traducători de limbaje algoritmice;
• 
  Aplicarea teoriei automatelor în dezvoltarea de dispozitive și echipamente discrete în cadrul computerelor personale;

Abilități și aptitudini dobândite ca urmare a stăpânirii disciplinei:

• 
  Aplicarea teoriei automatelor pentru rezolvarea problemelor aplicate;
• 
  Proiectare de dispozitive discrete;
• 
  Design translator;

Literatura principală

1. Saveliev A.Ya. Fundamentele informaticii: un manual pentru universități.-M.: Editura MSTU im. N. Bauman, 2001.-328s.

2. Karpov Yu.G.

3. Zaitsev E.I. Teoria automatelor: Manual.-M.: MGAPI, 2002.-59s.

literatură suplimentară

1. Hopcroft D., Motwani R., Introducere în teoria automatelor, limbi și calcule: traducere din engleză-M.: Izdat. Dom Williams, 2002.-528p.

Cursul numărul 1.

Concepte de bază și definiții

Durată: 2 ore (90) minute

1.1. Probleme cheie (principale) (momente)

Locul disciplinei „Teoria automatelor” într-o serie de discipline citite la catedră

Teoria obiectelor automatelor

Probleme ale teoriei automatelor

Concepte de bază și definiții.

^ TEORIA AUTOMATICELOR.

1.2.1. Fundamentele teoriei automatelor. Până la 20 de minute

Mașinărie (din limba greacă   - cu acțiune proprie) - sistem de control, care este mașină cu stări finite sau vreo modificare a acestuia obţinută prin schimbarea componentelor sau a funcţionării sale. Conceptul principal - un automat finit - a apărut la mijlocul secolului al XX-lea în legătură cu încercările de a descrie în limbaj matematic funcționarea sistemelor nervoase, a calculatoarelor universale și a altor automate reale. trăsătură caracteristică o astfel de descriere este discretie modelele matematice corespunzătoare și caracterul finit al intervalelor parametrilor acestora, ceea ce duce la conceptul de automat finit.

Teoria automatelor este secțiunea de teorie sistem de control, care studiază modele matematice ale convertoarelor de informații discrete, numit mitraliere. Dintr-un anumit punct de vedere, astfel de convertoare sunt atât dispozitive reale (calculatoare, automate, organisme vii etc.), cât și sisteme abstracte (de exemplu, un sistem formal, teorii axiomatice etc.). Cel mai strâns asociat cu teoria algoritmilor.

Majoritatea problemelor din teoria automatelor sunt comune principalelor tipuri de sisteme de control. Acestea includ probleme de analiză și sinteză a automatelor, probleme de completitudine, minimizare, transformări echivalente ale automatelor și altele. Sarcina de analiză constă în descrierea comportamentului acestuia pe baza unui automat dat sau, pe baza unor date incomplete despre automat și funcționarea acestuia, stabilirea uneia sau alteia dintre proprietățile acestuia. Sarcina de sinteză automata consta in construirea unui automat cu comportament sau functionare predeterminata. Provocarea completității este de a afla dacă setul are M"  M automate cu proprietatea de completitudine, i.e. se potriveste cu M multimea tuturor automatelor care sunt obtinute printr-un numar finit de aplicatii ale unor operatii la automate dintr-un subset dat de automate M" . Problema transformărilor echivalente în vedere generala este de a găsi un sistem de reguli de transformare (așa-numitele sistem complet reguli) de automate care satisfac anumite condițiiși permiteți unuia să transforme un automat arbitrar în orice automat echivalent cu acesta (două automate sunt echivalente dacă au același comportament de automat. Comportamentul unui automat este un concept matematic care descrie interacțiunea unui automat cu mediul extern. Un exemplu de mediu al unui automat finit este un set de cuvinte de intrare, iar un comportament este o funcție de dicționar implementată de automat sau un eveniment reprezentat de automat.)

Pe lângă cele enumerate mai sus, există probleme specifice în teoria automatelor care sunt caracteristice automatelor. Deci, în funcție de condițiile problemei, este convenabil să se precizeze comportamentul automatului în diferite limbi, în legătură cu care sarcinile importante sunt alegerea unui limbaj adecvat suficient de convenabil și traducerea dintr-o limbă în alta. În strânsă legătură cu problemele sintezei și transformărilor echivalente este problema de minimizare numărul de stări ale automatului, precum și obținerea estimărilor corespunzătoare. Un cerc strâns de întrebări apare în legătură cu modelarea comportamentului automatelor unei clase de către automatele unei alte clase. Aici sunt de asemenea de interes problemele minimizării automatelor de modelare și estimarea complexității acestora. O ramură specială a teoriei automatelor este conectată numite experimente cu automate(adică modalități de obținere a informațiilor despre structura internă a automatelor prin comportamentul lor). Sarcina principală aici este de a obține anumite informații despre structura automatului prin observarea reacției acestuia la anumite influențe externe. În acest caz, apare o gamă largă de probleme legate de clasificarea experimentelor și de rezolvarea problemelor prin anumite tipuri de experimente, precum și de estimări ale lungimii experimentelor minime suficiente pentru a rezolva anumite probleme. Conceptul de experiment cu automate este folosit și în probleme fiabilitate si control sisteme de control, în special controlul automatelor. Multe dintre problemele enumerate mai sus pot fi văzute ca probleme algoritmice. Pentru automatele finite, majoritatea au o soluție pozitivă.

Teoria automatelor își găsește aplicare atât în ​​alte domenii ale matematicii, cât și în rezolvarea problemelor practice. De exemplu, solvabilitatea unor calcule formale este dovedită prin intermediul teoriei automatelor. Aplicarea metodelor și conceptelor teoriei automatelor la studiul limbajelor formale și naturale a condus la apariția lingvisticii matematice (lingvistica matematică este o disciplină matematică al cărei subiect este dezvoltarea unui aparat formal de descriere a structurii naturale și naturale). unele limbaje artificiale.) Conceptul de automat poate servi ca obiect model într-o mare varietate de probleme, ceea ce face posibilă utilizarea teoriei automatelor în diferite cercetări științifice și aplicate.

^ 1.2.2. Probleme și sarcini rezolvate prin teoria automatelor. Până la 30 de minute

Teoria automatelor- o secțiune de matematică discretă care studiază modele matematice ale dispozitivelor reale (tehnice, biologice, economice) sau posibile care procesează informații discrete în pași de timp discreti.

În această teorie, direcțiile sale sunt destul de clar identificate, datorită:

1. 
   selectarea tipurilor de automate studiate (finite, infinite, deterministe, probabiliste, autonome, combinaționale, fără ieșire)
2. 
   nivel acceptat de abstractizare (automate abstracte și structurale)
3. 
   specificul matematicii aplicate (teoria algebrică a automatelor)

În același timp, în modelele discrete ale obiectelor luate în considerare, se ia în considerare doar logica proceselor în desfășurare de modificări ale automatului, fără a lua în considerare caracteristicile cantitative.

Problemele centrale ale unei teorii lizibile sunt problemele de sintaxă și analiză (adică dezvoltarea unei scheme funcționale a unui automat în funcție de comportamentul său dat și descrierea comportamentului unui automat conform structurii sale cunoscute). Aceste probleme sunt strâns legate de problemele de completitudine, echivalență și minimizare a numărului de stări ale automatelor.

Mai mult, automatul, ca dispozitiv conceput pentru a efectua acțiuni cu scop fără intervenția umană, este considerat fie ca implementând una sau alta gramatică formală (automat abstract), fie ca un set de elemente și o schemă pentru conectarea lor (automat structural).

Cauta materiale:

Numărul materialelor dvs.: 0.

Adăugați 1 material

Certificat
despre crearea unui portofoliu electronic

Adăugați 5 materiale

Secret
prezent

Adăugați 10 materiale

Diploma pentru
informatizarea educatiei

Adăugați 12 materiale

Revizuire
pe orice material gratuit

Adăugați 15 materiale

Lecții video
pentru a crea rapid prezentări impresionante

Adăugați 17 materiale

În ultimele decenii, s-a desfășurat și se lucrează intens pentru a crea
și utilizarea diferitelor sisteme și dispozitive pentru prelucrarea discretelor
informație. Convertoarele de informații discrete sunt utilizate pe scară largă ca
diverse tipuri de automate tehnice, dispozitive de calcul și funcționalitatea acestora
blocuri, dispozitive de control roboți care controlează obiecte conform unui dat
algoritm. O clasă largă de astfel de convertoare este unită sub numele general
automate. Aceste dispozitive au un număr finit de intrări care primesc informații,
și un număr finit de ieșiri pentru emiterea de informații procesate. Relație între
intrările și ieșirile sunt date de algoritmul de procesare a informațiilor prescris.
Informațiile de intrare și de ieșire sunt reprezentate prin simboluri, medii fizice
care sunt semnale cuantificate în timp.
Dacă caracterele „K” urmează simultan intrarea sau ieșirea paralelă
canale, să fie tratate ca un singur caracter din alfabetul corespunzător următor
la un singur canal „lipit”, atunci un astfel de automat poate fi reprezentat ca un dispozitiv cu
o intrare și o ieșire (Fig. 1).
Fig.1 - Model funcțional general al convertorului de informații discrete
Există două abordări ale definiției termenului de automat. La început se interpretează
ca un dispozitiv care, fără participarea directă a unei persoane, îndeplinește funcțiile
primirea, convertirea și transmiterea energiei, informațiilor etc. în conformitate cu
programul încorporat în el, cu al doilea ca model matematic al realului
convertoare de informaţii discrete. Funcționarea lui este
succesiunea z1,z2,... de simboluri de finit sau, în general, infinit
al alfabetului Z, ajungând la intrare, provoacă la ieșire un anumit
secvența w1,w2,... de caractere din același sau alt alfabet. Prin urmare,
cel mai general model matematic al unui convertor de informații discrete este
funcția de secvență care afișează setul Z al tuturor secvențelor
simboluri ale alfabetului Z într-un alt set W* de secvențe de simboluri ale alfabetului W.
Această interpretare ne permite să reprezentăm schematic convertorul ca un dispozitiv,
realizând maparea unui set la altul (Fig. 2a).

Fig.2a - Modelul formal al convertorului
Această mapare se numește mapare alfabetică sau alfabetică
operator.
Teoria automatelor este o ramură a teoriei sistemelor de control care studiază matematica
modele de convertoare de informații discrete, numite automate. CU
dintr-un anumit punct de vedere, astfel de convertoare sunt ca niște dispozitive reale
(calculatoare, organisme vii) și sisteme abstracte
(de exemplu, un sistem formal este o colecție de obiecte abstracte care nu sunt legate
cu lumea exterioară, care prezintă regulile de operare cu un set de personaje în
interpretare strict sintactică fără a ține cont de conținutul semantic, adică.
semantică; teorii axiomatice care descriu un anumit set de fenomene
în relaţia lor cauzală între ele).
Teoria automatelor este cel mai strâns legată de teoria algoritmilor. Acest lucru se explică prin fapt
că automatul convertește informația discretă în pași în momente discrete
timp și generează informațiile rezultate despre pașii unui algoritm dat. Aceste
transformările sunt posibile cu ajutorul instrumentelor tehnice și/sau software. Mașinărie
poate fi reprezentat ca un dispozitiv (cutie neagră) la care
sunt luate intrări și ieșiri și care pot avea unele interne
state. În analiza automatelor, comportamentul lor este studiat sub diferite perturbații.
influenţează şi minimizează numărul de stări automate pentru lucrul conform unui dat
algoritm. Un astfel de automat se numește abstract, deoarece abstrasă de real
semnale fizice de intrare și ieșire, considerându-le pur și simplu ca litere ale unora
alfabet și în legătură cu timpul discret idealizat. La sintetizarea automatelor
(procesul de conectare sau asociere) formează un sistem de automate elementare,
echivalent cu automatul abstract dat. Un astfel de automat
numite structurale. Un loc special în teoria automatelor îl ocupă conceptul de finit
mașinărie.
Rezultatul transformării input => output (Fig. 2a) depinde adesea nu numai de input to
acest moment timp, dar și din ceea ce a fost mai devreme la intrare, din istoricul de intrare, i.e.
din istoria transformării. Numărul de istorice posibile de intrare este infinit (numărabil),
chiar dacă automatul are un număr finit de elemente de informații de intrare diferite (ca în

convertor funcţional final). Pentru a ne aminti cumva aceste povești de fundal și
Pentru a se distinge unul de celălalt, convertorul trebuie să aibă o memorie. Pentru aceasta, dispozitivul
(Fig. 1.1,6) se introduce alfabetul stărilor Q = (qx,q2,...qm).
Conceptul de stat q joacă un rol foarte important în acest sens. În stările lor, mașina
își amintește trecutul concentrat. Pentru aceeași intrare
invertorul poate reacționa diferit în funcție de starea în care
el este in acest moment.
Automat finit (Fig. 2b) - o abstractizare matematică care vă permite să descrieți căi
schimbarea stării unui obiect în funcţie de acesta starea curentași date de intrare
cu condiția ca totalul număr posibil stările Q și un set de semnale de intrare
Z sunt finite. Un automat finit este un caz special al unui automat abstract.
Fig. 2b - Mașină de stat
Mașina de stat este unul dintre cele mai importante tipuri de sisteme de control.
Principalul avantaj al automatelor finite este că acestea sunt în mod natural
sistemele controlate de evenimente externe sunt descrise în acest fel.
Teoria automatelor se ocupă cu studiul proceselor care au loc în automate de diverse
fel și tiparele generale la care sunt supuși, folosind pe scară largă pentru aceasta
aparat algebric, logică matematică, analiză combinatorie și teorie
probabilități.
Când proiectați automate fiabile, care funcționează bine, trebuie să rezolvați lucruri extraordinare
sarcini dificile. De exemplu, este necesar să se determine stabilitatea sistemelor pentru a reduce
diverse abateri în funcționarea mașinilor automate. Nevoie de studiu și sensibilitate
automate, deoarece în procesul de funcționare proprietățile sistemelor de control nu rămân
permanent.
Teoria automatelor își găsește aplicație atât în ​​matematică, cât și în rezolvarea problemelor practice.
sarcini. De exemplu, prin intermediul teoriei automatelor se demonstrează solvabilitatea unora
calcul formal. Aplicarea metodelor și conceptelor teoriei automatelor la studiu
limbajele formale și naturale au dus la apariția matematicii
lingvistică (lingvistica matematică este o disciplină matematică, subiectul
care este dezvoltarea unui aparat formal de descriere a structurii naturale
și unele limbaje artificiale.) Conceptul de automat poate servi drept model

obiect într-o mare varietate de sarcini, ceea ce face posibilă aplicarea teoriei
automate în diverse cercetări științifice și aplicate.
Relevanța teoriei automatelor
Există multe obiecte de control asociate cu un mare
responsabilitate: reactoare nucleare și chimice, complexe industriale,
apărare, spațiu, minerit. Succes în a trata direct cu ei
depinde de claritatea și coerența acțiunilor, de capacitatea de a lua decizii corecte și
analizează cu competență situația, din posibilitatea unei interpretări lipsite de ambiguitate
informație. Natura diferită a proceselor fizice care au loc în obiecte, complexă
natura interacţiunii dintre acestea şi sistemele de control determină
dificultăți în dezvoltarea, algoritmizarea și programarea sarcinilor de control. Apărea
dificultăţi asociate cu necesitatea realizării vizibilităţii şi structurii.
Pentru a rezolva aceste probleme, se folosește aparatul matematic dezvoltat al teoriei automatelor.
Descrierea logicii comportamentului (în ce condiții este necesar să se efectueze anumite
acţiuni) în abordarea automată este structurată. Această proprietate face automat
descriind un comportament complex într-o manieră clară și concisă. Corectitudinea lucrării
utilizarea mașinilor automate este prevăzută în faza de proiectare, datorită
reprezentare grafică, adică
 reprezintă vizual comportamentul automatelor de control (grafic, tabelar)
și compoziții din ele;
 Sunt afișate stările dorite;
 reflectă dinamica şi condiţiile tranziţiilor automatului de la stare la stare;
 ușor de văzut posibile greșeliîn design, cum ar fi absența
unele tranziții, stare indisponibilă etc.
Toate acestea duc la o înțelegere clară a funcționării dispozitivului. procese de management,
desenele pot fi reprezentate ca elemente cu comportament previzibil.
Exemplu: unul dintre cei mai mari producători din lume de aviație, spațiu și
echipament militar - corporația americană Boeing este angajată în sisteme de stabilizare
aeronave folosind teoria automatelor pure. O mare parte din teoria automatelor
a fost utilizat cu succes în programele de sistem și filtrele de text în sistemul de operare UNIX.
Acest lucru permite multor oameni să lucreze la un nivel înalt și să se dezvolte foarte
programe eficiente.

Domeniile de aplicare a AT sunt uimitoare în domeniul lor de aplicare și nu se limitează la un îngust
concentrare și specializare. Să luăm în considerare unele dintre ele.
Programare
Se pune întrebarea de ce modelul automat finit al teoriei automatelor este în special
relevante acum, când există un număr mare de limbi
medii de programare și dezvoltare software? Există două probleme:
 comportamentul imprevizibil al codului unui program dezvoltat exclusiv
Instrumente RAD (Rapid Application Development - instrumente de dezvoltare rapidă
aplicații);
 „decolorarea” a „culturii de programare”.
Exemple RAD: Borland Delphi și C++ pentru dezvoltare accelerată
aplicații prin utilizarea orientate pe obiecte și vizuale
programare. Ele permit nu numai programarea în sensul obișnuit al cuvântului,
dar și pentru a desena efectiv programe (atât interfața cât și implementarea) folosind
componente vizuale VCL.
Orice obiect VCL vizual este caracterizat printr-un număr de proprietăți, metode și evenimente.
S-ar părea că prin simpla manipulare a atributelor enumerate este posibilă forțarea
programul fiind dezvoltat pentru a face ceea ce programatorul-dezvoltatorul cere de la el. Dar
acest lucru este departe de a fi adevărat.
De mult timp a fost clar că VCL tinde să ascundă implementarea exactă a anumitor
obiecte, împiedicând astfel persoanele din afară să modifice comportamentul implicit al codului. Cum
practica arată că comportamentul codului unui program creat folosind instrumente RAD nu
întotdeauna previzibil chiar și pentru un programator foarte experimentat, darămite un începător.
Programul, în ciuda „evidentității” codului autorului, se străduiește întotdeauna să meargă pe propriul său drum.
într-un fel, intrând în astfel de instrumente de gestionare a evenimentelor complicate, a căror existență
poate nici măcar nu ghiciți.
ÎN lumea modernă Volumul și complexitatea aplicațiilor dezvoltate crește odată cu creșterea
în fiecare zi, astfel încât această abordare crește dramatic timpul pentru testarea și depanarea software-ului.
Mecanismul teoriei automatelor face posibilă controlul comportamentului codului.
acum patruzeci de ani.
Stilurile de programare diferă în concepte de bază, care sunt
sunt folosite concepte precum „eveniment”, „subrutină”, „funcție”, „clasă”.

("obiect"), etc. Stilul de programare bazat pe alocare explicită a stării
și utilizarea automatelor pentru a descrie comportamentul programelor, numite „automate
programare”, și stilul corespunzător de proiectare a programului -
„proiectare automatizată”. Programarea automată poate fi considerată ca nu
doar ca stil independent de programare, dar și ca un plus față de altele
stiluri, de exemplu, la orientate pe obiecte, deoarece vorbim nu numai și nu atât
folosind mașini cu stări finite în programare, cât despre metoda de creație
programe în general, al căror comportament este descris de automate. Acestea. ca separat
componentă, iar programul în ansamblu poate fi implementat ca un automat.
Există două direcții în programarea automată: tehnologia SWITH și
Tehnologia KA (finite-automatic). Tehnologia comutatorului - tehnologie de dezvoltare a sistemelor
control logic bazat pe automate finite, acoperind procesul
proiectare, implementare, depanare, verificare (verificare), documentare și
escorte.
Codarea/programarea automatelor în cadrul tehnologiei KA se bazează pe
urmatoarele principii:
 a introdus conceptul de obiect dinamic, care poate fi dotat cu un algoritm
comportament în timp;
 algoritmul comportamentului obiectului este dat de modelul de automat finit;
 limbajul de descriere a automatelor se bazează pe reprezentarea tabelară a automatelor;
 logica comportamentului obiectului (tabelul de tranziție automată) este separată de metode
obiect automat (predicate și acțiuni) asociat cu implementarea acestuia
comportament în timp;
 Orice obiect dinamic poate fi executat în paralel.
Să aruncăm o privire mai atentă la aceste tehnologii:
1) Tehnologia WITH. Principalele prevederi: se propune realizarea conceptului de „stat”
primar, iar algoritmii sunt prezentați sub formă de grafice de tranziție (diagrame de stare), i.e.
reprezintă programul ca un sistem de automate finite care interacționează,
descrise prin grafice de tranziție. Stările sunt codificate pentru a distinge între ele.
Graficele într-o formă vizuală pentru o persoană reflectă tranzițiile între stări, precum și
„legarea” acțiunilor de ieșire și a altor automate la stări și/sau tranziții.
În cadrul programului, automatele pot interacționa:

 prin imbricare (un automat este cuibărit într-una sau mai multe stări ale altuia
mașinărie)
 prin apelabilitate (un automat este apelat cu un anumit eveniment de la ieșire
influența formată în timpul tranziției unui alt automat)
 mesagerie (un automat primește mesaje de la altul)
 după numere de stare (un automat verifică starea
altă mașină).
Nici numărul de automate imbricate într-o stare și nici adâncimea de cuibărire nu sunt limitate.
Principalul criteriu pentru implementarea optimă a automatelor de control este posibilitatea
conversia graficului de tranziție în cod de program.<><><>Se cunosc un număr mare
instrumente pentru generarea de programe care implementează grafice de tranziție:
 Instrumentul Visio2Switch Visio2Switch permite grafic
tranziții create automat cu editorul Microsoft Visio
implementați-l ca program izomorf C. Visio2Switch Converter
este utilizat în prezent în crearea de software pentru un număr de
sisteme responsabile în timp real.
 MetaAuto Instrumentul MetaAuto permite, conform graficului de tranziție,
construit cu același editor, implementați-l automat în formular
program izomorf în orice limbaj de programare pentru care
șablon pre-construit (C, C#, Turbo Assembler etc.).
 Instrumentul UniMod UniMod este proiectat să sprijine
programarea automată și construcția și implementarea nu numai a automatelor, ci și
programe în general.
Practica a arătat că pentru multe clase de programe, doar 20-30% din software
codul este construit manual.
Pe baza tehnologiei SWITCH au fost deja dezvoltate aplicații pentru: dispozitive de vending
apă gazoasă, bancomat (vezi exemplul 1), semafoare, sisteme de control
lift pentru pasageri, sistem de control al alarmei auto (vezi exemplul 2),
sistem de plată automatizat telefon mobil, dispozitive de schimb valutar,
aparate pentru vânzarea biletelor etc.
2) Tehnologia KA permite realizarea ideii de paralelism. Tehnologii de dezvoltare
programe de sus în jos, de jos în sus, abordarea structurală a unor astfel de oportunități sau nu

au sau sunt limitate. Chiar și în tehnologia orientată pe obiecte
programare (OOP), problemele funcționării în paralel a obiectelor sunt scoase din domeniul său.
Utilizarea altor tehnologii bazate pe modele paralele bine-cunoscute,
este plin de dificultăți asociate, dacă nu cu restricții privind domeniul de aplicare a acestora, atunci
cu probleme de implementare ulterioară la nivel de software și/sau hardware.
Modelele paralele sunt unul dintre principalele și direcții promițătoareîn dezvoltare
programare și hardware. Ideea de paralelism este foarte atractivă. Dar
pentru a-l folosi, este necesar, mai întâi, să se rezolve problema descrierii, adică. alegere
modelul paralel formal și, în al doilea rând, problema implementării modelului. KA
tehnologia folosește un model cu mijloace de reprezentare și descriere a paralelismului,
care, prin capacitățile lor, nu sunt inferioare altor modele paralele și ei
implementarea este mult mai ușoară. În plus, folosind tehnici standard, este ușor
trece de la o reprezentare paralelă de automată finită la una secvenţială
Descriere.
Exemple de aplicații ale tehnologiei KA: program de contabilitate tip de calcul
salariile sau contabilitate pentru chirie, sistem de management al proiectelor
proces tehnologic cristale în creștere cu multe dinamic
generate în paralel obiecte funcționale care implementează procesele de îndepărtare
date de la senzori, emiterea de acțiuni de control asupra obiectului, algoritmi de automatizare
operarea șoferilor cu diverse echipamente, procese de afișare și calcul.
3) Principala diferență între tehnologiile luate în considerare este implementarea logicii
programe automate. În tehnologia SWITCH, aceasta este implementată prin transfer automat
descrieri în codul de program al limbajului de programare, în tehnologia KA este implementată
execuția directă a automatelor prin interpretarea tabelului său original
reprezentare. Acesta este un mod mai scurt și mai clar de a implementa automate, deși mai multe
lent, dacă luăm în considerare nivelul unui automat component separat al rețelei
masini.
Concluzie: Programarea automată este utilizată în prezent în
proiectare software pentru sisteme de automatizare a instalațiilor critice
control (control automat al unității criogenic-vacuum, generator diesel).
Mașina de stat funcționează pe principiul „pas în lateral - inacceptabil”. Implementează
mașina de stări nu va oferi utilizatorului acțiuni neintenționate (original
varianta de cod), nici programul în sine (varianta de cod modificat).

În prezent, există un boom în domeniul creării de jocuri pe calculator. Mai des
logica de control al jocului în care personajele care se mișcă în zona de joc pot
acționează în diferite moduri (de exemplu, personajul aleargă înainte sau înapoi, urcă
scări, căderi etc.) este implementat ca o mașină de stat.
Implementarea de vizualizatoare pentru matematică discretă și algoritmi de programare
La studierea algoritmilor de prelucrare a informaţiei reprezentate de diverse
structurilor de date, un rol important îl au vizualizatorii algoritmilor care permit
forma vizuală afișează în mod dinamic detaliile muncii lor.
Un vizualizator este un program care, în timpul funcționării sale, pe ecranul computerului
demonstrează dinamic aplicarea algoritmului la setul de date selectat.
Vizualizatoarele vă permit să studiați funcționarea algoritmilor într-un mod pas cu pas, similar cu
modul de urmărire a programului. Ele permit urmărirea dacă este necesar.
pași lărgiți, ignorând partea de rutină a procesului de calcul, care
esențial, de exemplu, pentru algoritmii de enumerare.
Pentru unii algoritmi, o versiune dinamică a demonstrației muncii sale este
mai natural decât un set de ilustrații statice.
Când învățați majoritatea algoritmilor, împreună cu modul „pas înainte”, este foarte util
precum și modul „pas înapoi”, care vă permite să înțelegeți mai rapid și mai complet algoritmul.
De exemplu, în algoritmii de backtracking, poate fi necesar să se facă mai mulți pași
înapoi pentru a înțelege de ce a fost respinsă cutare sau cutare ramură a căutării.
Exemple de vizualizatoare: traversarea arborelui binar, algoritmi de planificare,
sortare etc. Acestea. algoritmi complecși cu un număr mare de tranziții, condiții și
ramurile pot fi reprezentate mai compact si mai clar: sub forma unui automat finit cu
comportament previzibil și vizibil.
Inteligenţă artificială
Rețele neuronale artificiale (ANN) - modele matematice, precum și software-ul acestora
sau implementări hardware construite pe principiul organizării și funcționării
rețele neuronale biologice - rețele de celule nervoase ale unui organism viu. Această noțiune
au apărut atunci când se studiază procesele care au loc în creier și când se încearcă modelarea acestora
proceselor.
Rețelele neuronale sunt o tehnică de modelare excepțional de puternică care permite
reproduce dependențe extrem de complexe. ANN-urile sunt configurabile și

învăţare. Utilizarea automatelor pentru a crea rețele neuronale artificiale
vă permite să excludeți apariția unor stări neprevăzute în lucrare.
Tehnologiile neuronale sunt utilizate în mod deosebit intens în sistemele expert.
previzionarea depozitelor și a afacerilor financiare în evaluarea investițiilor.
Exemplu: în motoarele cu rachete lichide (LRE), care sunt un complex
sistem tehnic format din mai multe unități care interacționează între
în sine, este necesară o reacție rapidă a sistemului de control la procesele care au loc.
într-una dintre cele mai critice și stresante unități - o unitate de turbopompă
(TNA). Atunci când utilizați rețele neuronale și automate, devine posibil
diagnosticarea precoce a urgențelor, ceea ce reduce consecințele unui accident
și preveniți distrugerea motorului în timpul testelor de incendiu (vezi exemplul 3).
Când funcționează, TNA este reprezentat ca o mașină cu stări finite. State, în
care poate fi: Standby, Start, Main mode, Stop, Emergency
stare (împărțită într-un număr de stări care clasifică natura defecțiunii).
Valoarea abaterii limită este selectată astfel încât să fie
minime și în același timp permit mici variații. În caz de refuz (ieșire
oricare dintre cele patru rețele este egală cu una), rețele neuronale antrenate
tipic pentru eșecurile TNA, conform mărturiei căreia este posibil să se determine ce a servit
motivul defecțiunii (ieșirea rețelei este egală cu unu). Dacă acest lucru eșuează (mai multe
ieșirile din rețea sunt egale cu unu), atunci se consideră că eșecul este combinat - în același timp
au existat mai multe defecțiuni și, în caz de incertitudine (toate ieșirile din rețea sunt egale
zero), mașina trece la starea de defecțiune nouă.
Tehnica dezvoltată face posibilă detectarea defecțiunilor unei unități de turbopompe. Deoarece
acest dispozitiv este foarte complex, apoi după declanșarea unei urgențe
este problematic să se determine tipul de avarie, în ce stare de lucru în acest moment
se află unitatea și cum se pune din nou în stare de funcționare. Retea neurala
vă permite fie să preveniți un accident, fie să fixați ora la care a avut loc defecțiunea și
determină tipul defecțiunii. Aplicarea tehnologiei SWITCH în dezvoltarea controlului
Software-ul vă permite să obțineți un protocol complet pentru funcționarea mașinii de diagnosticare - la orice
la momentul funcționării sale, puteți afla în ce stare se află mașina și în ce
starea sa poate fi tradusă.
Crearea de aplicații software pentru dispozitive mobile și microcontrolere

Atunci când se construiesc aplicații server care răspund solicitărilor, un rol important îl joacă
„apatrid” - nu este nevoie să stocați stări între două
cereri consecutive.
Când construiți o aplicație interactivă de succes, bazată pe evenimente, mult
depinde dacă modelul de management al statului este bine gândit.
Mașina de stat este un concept foarte convenabil, care este util pentru
structurarea aplicatiilor.
Deoarece aplicatii mobile ar trebui să folosească spațiul de pe ecran și sistemul
resurse în mod eficient, mașinile de stat sunt deosebit de utile atunci când
dezvoltare software pentru astfel de aplicații.
Programul este un set de automate finite care interacționează
unul cu celălalt și cu lumea exterioară. Diagrama de tranziție KA descrie tranzițiile între
forme de ecran, arcuri de tranziție de la stare la stare descriu acțiuni
utilizator. Fiecare dintre formele construite trebuie să fie asociată cu o mașină de stări,
controlând comportamentul vizual al formei. Dacă forma în sine conține mai multe
pagini, de exemplu, casete de dialog cu file, apoi este furnizat pentru fiecare dintre
subpagini propria mașină de stat.
Mașinile de stat îmbunătățesc foarte mult controlul execuției
sarcini de fundal. Utilizarea lor face posibilă furnizarea de fire de fundal
informații despre starea de execuție, precum și apelul altor fire cu solicitări către
fir de fundal pentru a efectua anumite acțiuni, de exemplu, cu o solicitare pentru
opriți executarea lucrărilor de fundal. În același timp, într-o formă grafică vizuală
atât conexiunile dintre automate cât şi cele interne ale acestora
structura. Avantajul principal: reutilizarea codului, rapidă
modificarea, vizibilitatea, care este importantă în cazul aplicațiilor pentru dispozitive mobile,
care necesită utilizarea economică a spațiului ecranului, memoriei, calculelor
putere și alte resurse.
Construirea de modele de flux de lucru bazate pe modelul automatizat finit al teoriei
mitraliere
În societatea modernă, există un proces de intensificare a calculului și
tehnologii informaţionale în toate ramurile de activitate.
Fluxul documentelor - mișcarea documentelor într-o organizație din momentul în care sunt create sau
primire înainte de finalizarea executării: trimitere și/sau trimitere în cauză. Implementarea

gestionarea documentelor electronice este o sarcină urgentă societate modernă, deoarece
vă permite să faceți procesul de mișcare a documentelor gestionabil și controlat, ceea ce
oferă servicii de management mai bune. Întreprinderi și organizații pentru
Rezolvarea acestei probleme necesită mult timp și bani. În același timp, fiecare
dezvoltarea unui sistem de management al documentelor este unică și posibilitatea de repetare
utilizarea experienței acumulate în în întregime practic absent. Corect
organizarea acestui proces determină calitatea și stabilitatea muncii oricărui
întreprinderilor.
Utilizarea modelului automat în elaborarea specificațiilor fluxului de documente și
produsul software vă permite să creați sisteme mai adecvate cerințelor
utilizatorilor și oferă posibilitatea de a realiza compatibilitatea aplicațiilor.
Teoria automatelor vă permite să implementați logica de ramificare a mișcării documentelor între
participanții la procesele de gestionare a documentelor. Aparatul vă permite să setați reacția
elemente ale sistemului de flux de lucru pentru modificări în sistem.
Așa-numitul obiect compozit este considerat ca obiect modelat.
flux de documente, adică un astfel de flux de documente la care participă, atât electronic,
precum și depunerile pe hârtie. Flux de lucru compozit
reprezentată printr-un triplu: Dm = (U, D, F), unde
 Дт – model formal de flux de lucru;
 Y – set de participanți;
 D - set de acţiuni;
 F este mulţimea stărilor documentului.
Setul de stări de document S se obține prin analiza ciclului de viață
document. Acesta este setul tuturor stărilor care pot fi acceptate de document în
în cadrul fluxului de lucru simulat, unde fiecare valoare este unică: (S)=(Ф).
Starea inițială este starea inițială în care
document după inițializarea procesului. La prezentarea unui flux de documente în formular
set de procese, starea inițială reprezintă primul pas, după care
putem spune că documentul există și procesul este activat. Prin urmare,
stările inițiale sunt obiecte, elemente ale mulțimii Ф, care au una sau
mai multe conexiuni de ieșire și niciuna de intrare.

Fluxul de lucru constă dintr-un set de procese, fiecare dintre ele procesând
unul sau mai multe documente. Ciclu de viață proces de flux de lucru
este determinată de mișcarea documentelor din stările inițiale în stările finale.
În modelul luat în considerare, stările finale ale automatului sunt definite ca stări
documente, după apariția cărora funcționarea mașinii se oprește, i.e.
fluxul de lucru încetează să mai existe. Astfel, finala
stările pot fi definite ca obiecte ale mulţimii Ф, care au una sau
mai multe conexiuni de intrare și niciuna de ieșire.
În fluxul de lucru, documentul ia următoarea stare, în funcție de
rezultatul acțiunii întreprinse asupra acestuia. functie de tranzitie automata
Modelele de flux de lucru pot fi definite ca al i-lea element al setului de acțiuni (D)
flux de lucru, după care starea se schimbă în
stat. (F)=(D)
Alfabetul unui automat este un set de simboluri, ale căror seturi vin sau pot
actioneaza automat. Ca alfabet al automatului, ar trebui să luăm în considerare lista
participanții.
Este posibil să se definească în mod unic un automat care va implementa în mod adecvat modelul
fluxul de lucru. Un model construit pe automate deterministe permite
construiți modele care sunt mai ușor de perceput vizual. Le este mai ușor să construiască
implementare software. În același timp, la crearea modelelor de proces care au
structură complexă de ramificație, model automat pe automate deterministe
devine mare și voluminos.
Automatele nedeterministe vă permit să specificați procese complexe folosind
material mai puțin descriptiv. Cu toate acestea, pentru claritate, ei
mult mai dificil.
Concluzie: pentru procese mici, ușor ramificate, este mai bine să utilizați
automatele deterministe, în timp ce cele nedeterministe sunt mai convenabile pentru
specificarea proceselor cu un număr mare de pași și ramuri.
După dezvoltarea bazei teoretice, software-ul este implementat,
aplicarea în practică a modelelor automate și grafice ale fluxului de lucru. Fiecare dintre
participanții au capacitatea de a accesa anumite tipuri de documente și
efectuează asupra lor acțiuni strict definite.

Implementarea sistemelor compozite de flux de lucru vă permite să faceți munca de birou
mai transparent și previzibil, reduce influența personală a interpretului
personal pentru rezultatul final.
Industria considerată se dezvoltă în prezent rapid. Mai departe
cercetare în această direcţie, mai ales în ceea ce priveşte utilizarea CSgramaticii şi
crearea de software care implementează modelul de automat descris
flux de lucru compozit în întregime.
Găsirea șirurilor de caractere în text
Potrivit statisticilor oficiale, aproximativ 85% dintre utilizatorii de Internet în mod constant
contactați motoarele de căutare
(Google, Yandex, Rambler, Yahoo!, Aport, [email protected] etc.) pentru a găsi
informațiile de care au nevoie despre bunuri sau servicii.
Prevederile teoriei automatelor sunt excelente pentru a descrie un astfel de real
sarcini care apar în aplicații, cum ar fi căutarea pe Internet și extragerea
informații din text. Multe motoare de căutare moderne pe Internet folosesc
program special- un robot de căutare, care este un automat.
În era Internetului și biblioteci electronice cu acces continuu este obisnuit
următoarea problemă. Vi se oferă un set de cuvinte și doriți să le găsiți pe toate
documente care conțin unul (sau toate) dintre ele. Un exemplu popular în acest sens
procesul este opera unui motor de căutare care utilizează o tehnologie specială
căutare, numită indecși inversați (indexuri inversate). Pentru fiecare cuvânt
găsite pe Internet (și există aproximativ 100.000.000 dintre ele), o listă de adrese ale tuturor locurilor în care
se intalneste. Mașinile cu cantități foarte mari de memorie RAM oferă
acces permanent la cele mai solicitate dintre aceste liste, permițând multor persoane
caută simultan documente.
Metoda indexului invers nu folosește mașini de stări, ci această metodă
necesită o perioadă semnificativă de timp pentru a copia conținutul rețelei și a rescrie
indici. Există multe aplicații înrudite în care să aplicați tehnica
indexurile inversate nu sunt posibile, dar puteți utiliza cu succes metode bazate pe
masini. Acele aplicații pentru care tehnologia de căutare bazată pe automate este potrivită,
au următoarele caracteristici distinctive:
1. Conținutul magazinului de text căutat este rapid
se schimba.

Iată două exemple:
o în fiecare zi, analiștii caută articole cu cele mai recente știri
subiecte relevante. De exemplu, analist financiar pot căuta
articole cu anumite abrevieri hârtii valoroase sau nume
companii;
o "robotbuyer" la cererea clientului monitorizeaza preturile curente pt
anumite nume de produse. Preia paginile de pe web,
care conțin directoare și apoi scanează acele pagini căutând
informații despre preț pentru un anumit articol.
2. Documentele căutate nu pot fi catalogate.
De exemplu, este foarte dificil să găsești toate paginile de pe web care conțin informații despre
toate cărțile vândute de Amazon.com deoarece aceste pagini
sunt generate ca și cum ar fi „în mișcare” ca răspuns la o solicitare. Cu toate acestea, putem trimite o cerere către
cărți despre un anumit subiect, spuneți „mașini de stat” și apoi căutați în acea parte
text care este conținut pe paginile care apar, un anumit cuvânt, de exemplu
cuvântul „frumos”.
Simularea funcționării ATM
Un bancomat este un dispozitiv automat care vă permite să efectuați de la distanță
operațiuni legate de autentificarea utilizatorului (titular de cont bancar),
vizualizarea stării curente a contului, retragerea banilor din cont și realizarea
diverse plăți. În acest exemplu, se ia în considerare funcționarea bancomatului, inclusiv
doar partea client, dar și partea server care procesează cererile, precum și
subsistem de autorizare.
Sarcina principală în implementarea unor astfel de sisteme este garanția nivel inalt fiabilitate
clienții, utilizatorii băncii și Sistem informatic borcan.

În ciuda lipsei de comunicare între automate, AServer este imbricat în AClient. La
când automatul AClient se află în stările „Autorizare”, „Solicitare sold” și
Controlul programului „Cerere de bani” este transferat la mașina AServer , care
trimite o cerere către server, primește un răspuns și returnează controlul mașinii

Un client. Serverul în sine este proiectat în mod tradițional și implementat ca
aplicație de consolă.
Interfata programului:
Exemplul arată că instrumentul UniMod simplifică procesul
crearea unui program, în comparație cu abordarea tradițională. În același timp, majoritatea
Timpul dezvoltatorului este cheltuit cu proiectarea sistemului. Din moment ce partea principală
codul este generat automat, fiabilitatea programului este crescută.
Sistem de control al alarmei auto faruri, sirena si LED ca obiecte de control. Utilizarea stării complexe
„2. Pornit” (conține 3 stări) oferă posibilitatea de a opri
indiferent în ce stare se află mașina.
Generatoare de evenimente de sistem
Generator de evenimente p1. Acest obiect descrie evenimentele produse de consolă.
managementul alarmelor. Evenimente:
 e11 - apăsarea butonului „1”;
 e12 - apăsarea butonului „2”;
 e13 - apăsarea butonului „3”.
generator de evenimente p2. Acest obiect corespunde senzorului de șoc. El poate da două
evenimente:
 e21 - fixarea unei lovituri slabe;
 e22 - fixarea unei lovituri puternice.
generator de evenimente p3. Acest obiect pornește unul dintre cele trei temporizatoare. Când numărătoarea inversă
completează, generează evenimentul corespunzător. Cronometrul pornește la cerere
obiect de control „o2” indicând numărul și timpul necesar.
 e31 - temporizatorul „1” a terminat de numărat (temporizator pentru numărarea timpului în starea „3.
Alarma" a mașinii A1);

 e32 - cronometrul „2” a terminat de numărat (temporizator pentru numărarea timpului în starea „2.
Stare de pericol" a mașinii A1);
• e33 - cronometrul „3” a terminat de numărat (temporizator pentru controlul sunetului).
Obiecte de control al sistemului
Obiect de control o1. Acest obiect descrie acțiunile efectuate de faruri
mașină.
 z1 – clipește o dată;
• z2 – clipește de două ori;
• z3 – clipește de trei ori;

 z5 - întrerupe orice acţiune.
Obiect de control o2. Acest obiect este folosit pentru a porni temporizatorul „p3”.
 z1 – pornirea temporizatorului „1” timp de 15 s;
 z2 – pornirea temporizatorului „2” timp de 5 s;
 z3 – pornirea temporizatorului „3” timp de 3 s;
z4 - opriți toate temporizatoarele.
Obiect de control o3. Acest obiect controlul reflectă funcționarea sirenei. A lui
acțiunile de ieșire aproape coincid cu acțiunile de ieșire ale farurilor.
 x1 este o variabilă logică care indică că sunetul este pornit (adică se poate
semnale) sau nu;
 z1 – generarea sunetului corespunzător setarii autoturismului pe sistemul de alarma;
 z2 – generarea sunetului corespunzător scoaterii autoturismului din alarmă;
 z3 – generarea sunetului corespunzător reacţiei la o lovitură slabă;
 z4 – începe să dea un semnal de alarmă;
 z5 - întrerupe sunetul;
 z6 – pornește sunetul (permite să dea semnale);

• z7 – stinge sunetul (interzice darea de semnale).
Obiect de control o4. Acest obiect de control descrie funcționarea LED-ului,
situat în mașină. Acesta arată starea curentă a alarmei.
 z1 – începe să clipească;
 z2 – nu mai clipește.
Obiect de control o5. Acest obiect de control este folosit pentru ieșire

TEORIA AUTOMATOV, o secțiune de matematică discretă care studiază modele matematice ale convertoarelor de informații discrete numite automate. Exemple de astfel de convertoare sunt atât sistemele reale (calculatoare, automate tehnice, organisme vii), cât și sistemele abstracte (calculatoare abstracte, teorii axiomatice). Teoria automatelor a apărut la mijlocul secolului al XX-lea în legătură cu studiul automatelor ca modele matematice ale sistemelor biologice și computerelor. În viitor, problema teoriei automatelor s-a extins semnificativ.

Teoria automatelor este strâns legată de teoria algoritmilor, în special de teoria computerelor abstracte, deoarece automatele pot fi considerate ca un caz de aproximare a acestora.

Un automat poate fi caracterizat ca un dispozitiv care are canale de intrare și ieșire și se află într-una dintre stările interne la fiecare moment discret de timp. Semnale-influențe ajung la canalul de intrare într-un astfel de moment. În aceleași momente, dispozitivul generează semnale de reacție prin canalul de ieșire. Stările automatului, semnalele-acțiuni și semnalele-reacții sunt date de literele alfabetelor corespunzătoare: alfabetul stărilor, precum și alfabetul semnalelor de intrare și de ieșire. Legile interacțiunii dintre literele acestor alfabete sunt date de două funcții - funcția de tranziție și funcția de ieșire, care mapează perechi (stare - literă de intrare) la stări și, respectiv, litere de ieșire. Mediul de intrare pentru automat este setul de cuvinte din alfabetul de intrare, iar mediile sale interne și de ieșire sunt seturile de cuvinte din alfabetul de stare și alfabetul de ieșire. Automatul procesează cuvintele din mediul de intrare literă cu literă în cuvinte din alte două medii. Acest proces se numește comportamentul automatului. Proprietățile alfabetelor și ale funcțiilor determină diferite tipuri de automate. În cazul în care toate alfabetele sunt finite, se obține un automat finit, altfel automatul se numește infinit. Înlocuirea funcțiilor cu relații duce la automate parțiale și nedeterministe; utilizarea funcţiilor aleatoare conduce la un automat probabilist. Când interpretăm mediul de intrare prin termeni sau grafice, se ajunge la automate peste termeni și automate în labirinturi.

Cele mai multe probleme ale teoriei automatelor sunt comune principalelor tipuri de sisteme de control, ele includ probleme de analiză și sinteză a automatelor, probleme de completitudine, minimizare, precum și probleme asociate transformărilor echivalente ale automatelor. Sarcina analizei este de a descrie comportamentul acestuia de la un automat dat sau, din date incomplete despre automat și funcționarea acestuia, de a stabili una sau alta dintre proprietățile acestuia. Sarcina sintezei este de a construi un automat cu un anumit comportament sau operație. Adiacente acestei probleme sunt probleme asociate cu estimarea complexității automatelor cu un comportament dat, precum și cu construirea de automate care sunt optime într-un anumit sens. Problema completității este de a afla dacă un anumit set de automate poate fi obținut dintr-un set mai mic folosind unele operații pe automate. Sarcina de minimizare a automatelor constă în minimizarea valorilor parametrilor automatului (de exemplu, numărul de stări), ceea ce are ca rezultat un automat care este echivalent într-un sens sau altul cu cel original. Pe lângă sarcinile comune principalelor tipuri de sisteme de control, teoria automatelor se ocupă de probleme specifice caracteristice automatelor. Deci, în funcție de condițiile problemei, este convenabil să se precizeze comportamentul automatelor în diferite limbi (expresii regulate, ecuații canonice, limbajul logicii predicatelor etc.), în legătură cu care sarcinile importante sunt alese a unei limbi adecvate suficient de convenabile și a traducerii dintr-o limbă în alta. Problema minimizării numărului de stări automate este legată de problemele de sinteză și transformări echivalente. În legătură cu simularea comportării automatelor unei clase de către automatele unei alte clase, apar problemele de minimizare a modelării automatelor și estimarea complexității acestora. O secțiune specială a teoriei automatelor este legată de așa-numitele experimente cu automate. Sarcina principală a acestei secțiuni este de a obține anumite informații despre structura automatului prin observarea reacției acestuia la anumite influențe externe. În acest caz, apar probleme legate de clasificarea experimentelor și de rezolvarea problemelor prin anumite tipuri de experimente, precum și de estimări ale lungimii experimentelor minime suficiente pentru a rezolva anumite probleme. Conceptul unui experiment cu automate este folosit și în problemele de control al automatelor. Secțiuni speciale ale teoriei automatelor sunt jocurile automate și comportamentul automatelor într-un mediu aleatoriu, care iau în considerare interacțiunea automatelor între ele și cu anumite medii externe. Multe dintre problemele enumerate mai sus pot fi considerate probleme de masă (vezi problema algoritmică). Pentru automatele finite, majoritatea au o soluție pozitivă.

Teoria automatelor își găsește aplicare în multe domenii. De exemplu, solvabilitatea unor calcule formale este demonstrată folosind automatele teoriei. Metodele și conceptele teoriei automatelor sunt utilizate în esență în lingvistica matematică. Conceptul de automat poate servi ca obiect model în diverse probleme, ceea ce face posibilă utilizarea automatelor teoriei în diverse cercetări aplicate.

Lit .: Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S. Introducere în teoria automatelor. M., 1985.

Toate dispozitivele discutate mai sus aparțin clasei de circuite combinaționale, adică dispozitive discrete fără memorie. Odată cu acestea, automatele secvenţiale, sau, cu alte cuvinte, circuitele combinaţionale combinate cu elemente de memorie, au devenit larg răspândite în tehnologia digitală.

Sub termen mașinărie se poate înțelege funcționarea unui dispozitiv din viața reală pe baza atât a semnalelor despre starea mediului extern, cât și a semnalelor interne despre starea automatului în sine. În acest sens, computerul poate fi considerat o mașină digitală. O mașină digitală este un dispozitiv conceput pentru a converti informații digitale. Pe de altă parte, sub termenul mașinărie puteți înțelege modelul matematic al unui dispozitiv. Teoria generală a automatelor este împărțită în două părți: abstractȘi structural teoria automatelor. Diferența dintre ele este că teoria abstractă face abstracție atât din structura automatului în sine, cât și din semnalele de intrare și de ieșire. Teoria abstractă analizează tranzițiile automate sub influența cuvintelor abstracte de intrare și a cuvintelor abstracte de ieșire formate pe aceste tranziții.

Teoria structurală are în vedere atât structura automatului în sine, cât și semnalele sale de intrare și ieșire, metode de construire a automatelor din automate elementare, metode de codificare a semnalelor de intrare și de ieșire, stări ale automatului.

În conformitate cu aceasta, se obișnuiește să se facă distincția între două modele de automate: structural și abstract. Modelul abstract este utilizat în considerarea teoretică a automatelor. Modelul structural este utilizat pentru a construi circuitul automatului din elemente logice și declanșatoare și este conceput pentru a îndeplini funcția de control.

Automat abstract este un model matematic al unui automat digital definit de un vector cu șase componente S=(A,Z,W,d,l,a 1), unde А=(a a ,…,am ) este un set de stări interne ale unui automat abstract; Z=)