Mașină de stat

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 august 2022; verificările necesită 6 modificări .

Un automat finit (KA) în teoria algoritmilor  este o abstractizare matematică , un model al unui dispozitiv discret care are o intrare, o ieșire și se află într-o stare din multe posibile la un moment dat. Este un caz special al unui automat discret abstract , al cărui număr de stări interne posibile este finit .

În timpul funcționării, acțiunile de intrare sunt recepționate secvențial la intrarea SC, iar la ieșire, SC generează semnale de ieșire. De obicei, sub influențe de intrare, intrarea automatului este acceptată ca intrare a simbolurilor unui alfabet , iar ieșirea KA în procesul de operare dă simboluri în cazul general al unui alt, poate chiar fără intersectare cu intrare, alfabet.

Pe lângă automatele finite, există și automate discrete infinite - automate cu un număr infinit de stări interne, de exemplu, o mașină Turing .

Trecerea de la o stare internă a navei spațiale la alta poate avea loc nu numai din influențe externe, ci și spontan.

Există KA  - automate deterministe, în care următoarea stare este determinată în mod unic de starea curentă, iar ieșirea depinde numai de starea curentă și de intrarea curentă și KA nedeterministe , a căror stare următoare este în general nedeterminată și, în consecință , semnalul de ieșire nu este definit. Dacă trecerea la stările ulterioare are loc cu anumite probabilități, atunci un astfel de CA se numește CA probabilistic .

Orice sisteme digitale, de exemplu, computere sau unele noduri logice ale computerelor cu declanșatoare de memorie și alte dispozitive , pot servi ca exemple de implementare fizică a KA . Logica secvențială combinațională nu poate fi un CA, deoarece nu are stări interne (nu are memorie).

Dintr-un punct de vedere abstract, CA studiază o secțiune de matematică discretă  - teoria automatelor finite .

Teoria automatelor finite este utilizată practic pe scară largă, de exemplu, în analizatoare și lexeri , testarea software -ului bazată pe modele .

Descrierea oficială a mașinii de stat

Descriere formală generală

În mod formal, CA este definită ca cinci elemente ordonate ale unor mulțimi:

unde  este un set finit de stări automate;  sunt alfabetele finale de intrare și respectiv de ieșire din care se formează șiruri care sunt citite și scoase de automat;  - functie de tranzitie;  este funcția ieșirilor.

Un automat abstract cu o stare selectată (această stare se numește stare inițială ) se numește automat inițial . Deoarece fiecare KA are un număr finit de stări și oricare dintre stările sale poate fi atribuită ca stare inițială, același automat corespunde automatelor inițiale, adică  numărul de stări interne ale KA. Astfel, un CA abstract definește o familie de automate inițiale. Dacă starea inițială nu este specificată, atunci comportamentul automatului este întotdeauna nedeterminist, cuvântul de ieșire al automatului depinde de starea inițială, deci descrierea deterministă completă a automatului va fi [1] :

Există două clase de KA: automate Moore  - KA, în care semnalul de ieșire depinde numai de starea internă, conform figurei, automatul Moore nu are nicio conexiune de la intrare la funcția de ieșire și automatele Mealy  - semnalul de ieșire depinde atât de starea internă cât și de starea intrării.

Descriere generală

Există diferite moduri de a specifica algoritmul pentru funcționarea unui automat finit. De exemplu, un automat finit poate fi definit ca cinci elemente ordonate ale unor mulțimi :

unde  este alfabetul de intrare (un set finit de simboluri de intrare ), din care sunt formate cuvintele de intrare , percepute de automatul finit;  este ansamblul stărilor interne ;  — starea inițială ;  - un set de stări finale sau finale ;  este o funcție de tranziție definită ca o mapare astfel încât , adică valoarea funcției de tranziție pe o pereche ordonată (stare, simbol de intrare sau șir gol de simboluri) este mulțimea tuturor stărilor în care o tranziție dintr-o stare dată este posibilă pentru un simbol de intrare dat sau un șir gol de simboluri, de obicei notat cu literă

Când se analizează CA, se obișnuiește să presupunem că automatul finit începe într-o stare inițială , primește secvențial un caracter de la cuvântul de intrare (un lanț de caractere de intrare). Caracterul citit poate transfera automatul într-o stare nouă sau să nu se transfere într-o stare nouă în conformitate cu funcția de tranziție.

Primind un șir de caractere de intrare și face tranziții de la stare la stare, automatul după primirea ultimului caracter[ clarifica ] cuvântul de intrare va fi într - o anumită stare .

Dacă această stare este finală, atunci se spune că automatul a acceptat cuvântul[ clarifica ]

Alte modalități de a seta funcționarea navei spațiale


Stare initiala
urmatoarea stare

Caracter de intrare a
Caracter de intrare
b
Orice
alt
personaj
p0 p1 p0 p0
p1 p1 p2 p1
p2 p3 p4 p2
p3 p3 p5 p3
p4 p4 p4 p4
p5 p3 p5 p5
  1. O diagramă de stări (sau uneori un grafic de tranziție ) este o reprezentare grafică a unui set de stări și a unei funcții de tranziție. Este un grafic direcționat etichetat , ale cărui vârfuri sunt stările KA, arcele sunt tranzițiile de la o stare la alta, iar etichetele arcurilor  sunt simbolurile prin care se realizează tranziția de la o stare la alta. . Dacă trecerea de la starea q 1 la q 2 poate fi efectuată prin unul dintre mai multe simboluri, atunci toate acestea trebuie etichetate deasupra arcului diagramei.
  2. Tabelul de tranziție  este o reprezentare tabelară a funcției δ . De obicei, într-un astfel de tabel, fiecare rând corespunde unei stări, iar fiecare coloană corespunde unui caracter de intrare valid. Celula de la intersecția rândului și coloanei conține starea în care trebuie să treacă automatul dacă citește simbolul de intrare dat în această stare. Un exemplu de tabel de salt pentru un automat dat ca grafic în Figura 1 este prezentat în dreapta.

Determinare

Mașinile de stări sunt împărțite în deterministe și nedeterministe .

Dacă luăm în considerare cazul când automatul este specificat formal astfel: , unde  este mulțimea stărilor inițiale ale automatului, astfel încât , atunci apare al treilea semn de nondeterminism - prezența mai multor stări inițiale (de pornire) pentru automat .

Teorema determinării afirmă că pentru orice mașină cu stări finite poate fi construită o mașină cu stări finite deterministă echivalentă (se spune că două mașini cu stări finite sunt echivalente dacă limbajele lor sunt aceleași[ clară ] ). Cu toate acestea, deoarece numărul de state din DFA echivalent în cel mai rău caz crește exponențial odată cu creșterea numărului de state din NFA original, în practică o astfel de determinare nu este întotdeauna posibilă. În plus, automatele finite cu ieșire sunt în general indeterministe.

Datorită ultimelor două observații, în ciuda complexității mai mari a automatelor finite nedeterministe, NFA-urile sunt utilizate în principal pentru sarcini legate de procesarea textului. .

Automate și limbaje obișnuite

Pentru un automat finit, este posibil să se definească un limbaj (un set de cuvinte) în alfabetul pe care îl permite , adică cuvintele sunt numite, a căror citire transferă automatul din starea inițială într-una dintre stările finale.

Teorema lui Kleene afirmă că o limbă este obișnuită dacă și numai dacă este permisă de o mașină de stat folosită în limba respectivă.

Minimizarea automatelor

Pentru orice limbaj obișnuit, există un automat unic, până la izomorfism , care acceptă acest limbaj și are cel mai mic număr posibil de stări. Automatul minim pentru un limbaj dat de un automat finit determinist poate fi implementat în timp polinomial, ceea ce vă permite să optimizați consumul de memorie necesar lucrului cu automatul, precum și să rezolvați probleme precum verificarea echivalenței a două automate în timp polinomial .

Limbaje de programare specializate

În limbajul grafic SFC, un program este descris ca o secvență schematică de pași conectați prin tranziții.

Dezvoltarea modelului folosind mașini cu stări finite

Automatele finite vă permit să construiți modele de sisteme de procesare paralelă, cu toate acestea, pentru a modifica numărul de procese paralele într-un astfel de model, trebuie să faceți modificări semnificative modelului în sine. În plus, o încercare de a dezvolta un model complex implementat de un automat finit duce la o creștere rapidă a numărului de stări ale automatului, ceea ce va face în cele din urmă dezvoltarea unui astfel de model extrem de consumatoare de timp. După cum sa menționat mai sus, această din urmă problemă poate fi rezolvată prin utilizarea unui automat nedeterminist.

Ce pot „face” o mașină cu stări finite și o mașină secvențială?

Răspunsul este dat în termeni diferiți în funcție de dacă automatul (respectiv, mașina P) este autonom sau nu [2] . Un automat autonom finit, pornind de la un anumit ciclu, poate genera doar o succesiune periodică de stări x (respectiv, o mașină P este o secvență de simboluri de ieșire y ). Dacă această secvență constă dintr-un singur simbol, atunci aceasta înseamnă că automatul ajunge la o stare de echilibru într-un număr finit de cicluri. Dacă această secvență conține mai multe simboluri, aceasta înseamnă că automatul trece succesiv prin stările corespunzătoare acestor simboluri, iar atunci funcționarea automatului se repetă periodic la nesfârșit. Mai mult, oricare ar fi succesiunea periodică de stări de lungime finită, se poate construi oricând un automat finit autonom, care, începând din al doilea ciclu, generează această secvență. Nimic altceva, în afară de repetarea periodică a aceleiași stări sau a unei secvențe finite de stări, automatul autonom poate „face”. Cu toate acestea, datorită faptului că execuția secvențială a unui anumit ciclu de operații este tipică pentru multe domenii ale tehnologiei moderne, sistemele dinamice, care, într-o idealizare acceptabilă, pot fi considerate ca un automat autonom, sunt utilizate pe scară largă.

Un exemplu clasic sunt automatele păpuși care execută secvențe complexe de acțiuni, de exemplu: scrierea unui anumit text pe hârtie, interpretarea unor piese prestabilite la pian etc.

Un exemplu modern sunt multe mașini automate, linii automate și sisteme automate de control pentru producția ciclică. Dacă automatul nu este autonom, adică starea intrării se schimbă de la ciclu la ciclu, atunci răspunsul la întrebarea ce poate „face” un automat finit și ce nu poate „face” poate fi dat în termeni diferiți. De exemplu, răspunsul poate fi formulat într-un limbaj de reprezentare a evenimentelor. Într-adevăr, un automat finit neautonom sau o mașină secvențială transformă doar secvențe de caractere de intrare în secvențe de caractere de stare sau de ieșire și a spune ce poate și nu poate „face” un automat finit înseamnă să afli ce transformări de secvență sunt posibile într-un automat finit și care sunt imposibile. Dar, deoarece numărul de stări (respectiv, simboluri de ieșire) este finit, această întrebare este echivalentă cu următoarea întrebare: la ce secvențe de intrare are loc fiecare dintre stările posibile (sau fiecare dintre simbolurile de ieșire)? Această ultimă întrebare, în termeni acceptați în teoria automatelor finite, este formulată astfel: ce evenimente pot și ce nu pot fi reprezentate în automatul finit prin fiecare dintre stările posibile (sau prin fiecare dintre simbolurile de ieșire).

Răspunsul este dat de teoremele lui Kleene . Acest răspuns este corect, deoarece teoremele lui Kleene stabilesc condiții necesare și suficiente pentru reprezentabilitatea unei secvențe de evenimente într-un automat, și anume: se disting seturi speciale de secvențe de simboluri de intrare - mulțimi regulate . Faptul că dintr-un astfel de set apare o secvență de intrare se numește eveniment regulat corespunzător. Teoremele lui Kleene stabilesc că numai evenimentele regulate pot fi reprezentate într-un automat finit. Astfel, în limbajul reprezentării evenimentelor, răspunsul la întrebarea ce poate „face” un automat finit este dat fără echivoc: un automat finit poate reprezenta doar evenimente regulate. O serie de seturi importante de secvențe de intrare, cu care trebuie adesea să se ocupe în practică, sunt în mod evident regulate. Deci, de exemplu, se știe că o mulțime constând din orice număr finit de secvențe de intrare de lungime finită este regulată; setul oricăror secvențe periodice de intrare; un set de secvențe infinite care conține secvențe finite date în ultimele câteva cicluri etc.

În cazul general, dacă un set infinit de secvențe de intrare este dat într-un mod arbitrar, atunci întrebarea dacă această mulțime este regulată rămâne deschisă. Ideea este că conceptul de mulțime regulată este introdus inductiv, adică se stabilește un algoritm pentru construirea oricăror mulțimi regulate. Cu toate acestea, nu există o modalitate suficient de eficientă de a rezolva problema inversă, adică de a determina dacă fiecare mulțime dată este regulată.

Deși teoremele lui Kleene răspund la întrebarea ce poate face o mașină de stat, ele răspund la această întrebare în mod ineficient. Au fost făcute primele încercări de a construi alte limbaje în care răspunsul să poată fi dat eficient. Această problemă a limbajului, care joacă un rol cardinal în obținerea unui răspuns eficient la întrebarea ce poate și ce nu poate „face” un automat finit, este crucială și pentru primele etape ale sintezei automatelor, adică pentru a răspunde celei de-a doua dintre întrebările de mai sus. Dacă extindem clasa sistemelor dinamice, pe care le-am definit prin termenii „automat finit” și „mașină secvențială”, prin includerea memoriei infinite (modelul memoriei infinite poate fi, de exemplu, o bandă infinită pentru stocarea simbolurilor sau un număr infinit de stări), atunci pentru sistemele dinamice din această clasă mai largă (sistemele abstracte din această clasă se numesc mașini Turing ) răspunsul la întrebarea „ce pot face?” mult mai simplu - pot implementa orice algoritm predefinit . În același timp, însuși conceptul de algoritm este interpretat în matematica modernă ca o implementare a calculării valorilor oricărei funcții recursive . Un răspuns atât de clar și clar la întrebarea „ce poate face o mașină Turing?” face posibilă punerea conceptului de mașină Turing ca bază pentru definirea conceptului de algoritm: un algoritm este orice proces care poate fi efectuat pe un automat finit suplimentat cu memorie infinită, adică mașini complete din punct de vedere algoritmic, pe o mașină Turing, pe o mașină poștală etc.

Vezi și

Note

  1. Kuznetsov O. P., Adelson-Velsky G. M. Automata // Matematică discretă pentru un inginer. - M . : Energie, 1980. - 344 p.
  2. Aizerman M. A., Gusev L. A., Rozonoer L. I., Smirnova I. M., Tal A. A. Logic. Automate. Algoritmi. Stat. ed. Fiz.-Matematică. Literatură 1963, 556 pagini.

Literatură

Link -uri