Automa (informatică)

În teoria sistemelor dinamice , un automat este un sistem dinamic discret (în scanarea timpului și în descrierea stării sale) și invariant în timp (sistemul se comportă în același mod, indiferent de momentul în care acționează).

Când automatul se află într-o stare dată, poate accepta doar un subset de simboluri ale alfabetului său. Evoluția unui automat începe de la o anumită stare numită stare inițială . Un subset privilegiat al stărilor sale se numește un set de stări finale sau marcate .

În general, automatele sunt deterministe , adică, având în vedere o stare și un simbol de intrare, este posibilă o singură tranziție. Cu toate acestea, există și automatele nedeterministe sau stochastice .

Descriere

Automate și limbi

Automatele sunt adesea folosite pentru a descrie limbaje formale în informatică teoretică și, din acest motiv, sunt numite acceptori sau recunoscători ai unei limbi.

Setul de simboluri posibile care pot fi furnizate unui automat constituie alfabetul său.

O secvență de simboluri (numită și șir sau cuvânt ) aparține limbii dacă este acceptată de automatul corespunzător, adică dacă aduce automatul într-o stare validă, indiferent dacă este aceeași sau o altă stare. Un subset al limbii recunoscute, numit limbaj marcat, transportă automatul de la starea sa inițială la o stare finală sau marcată.

Diferite clase de automate corespund diferitelor clase de limbi, caracterizate prin diferite niveluri de complexitate.

Prin urmare, un automat poate recunoaște mai multe limbaje (producerea mai multor secvențe).

Automate cu blocuri

Există în principal două tipuri de încuietori: impasuri și livelock. Primul apare atunci când ajungeți la o stare care nu este inclusă în stările finale și are Γ = {Φ}, adică în care nu există ieșiri. Pe de altă parte, un blocaj viu apare atunci când ajungeți într-un set de stări, dintre care niciuna nu este o stare finală sau o stare bloc, din care nu mai este posibil să ieșiți. Prezența acestor blocuri poate fi identificată cu algoritmi care operează pe digrafele subiacente.

Operațiuni cu automate

Există operațiuni care pot fi efectuate pe un singur automat sau pe mai multe automate. Printre primele putem menționa: accesibilitate, co-accesibilitate, decupare și complement. Printre compozițiile automatelor se află produsul și compoziția în paralel. Acesta din urmă este deosebit de util atunci când doriți să construiți modelul unui sistem foarte complex prin combinarea părților sale individuale.

Clasificarea automatelor

Enumerăm o clasificare a diferitelor tipuri de automate, listate în funcție de creșterea capacității. Un rezumat este prezentat în tabelul de pe pagină.

Automate de stare finită

Același subiect în detaliu: automat cu stare finită .

Automatele cu stări finite au un set finit de stări, scanează un șir de simboluri de intrare (simbol cu ​​simbol) într-un mod ordonat pentru a decide dacă aparține sau nu unei limbi .

În mod oficial, aceste automate sunt cvintupluri, (Q, I, f, q0, F) , formate dintr-un alfabet finit al simbolurilor de intrare (I), un set finit de stări (Q) dintre care se distinge o stare inițială (q0) și un subset de stări, numit final (F) și o funcție de tranziție (f). Această funcție, descrisă prin intermediul unui tabel de tranziție al stării, sau al unui multidigraf, este definită de perechi (starea curentă, simbol scanat) și stabilește tranziția care trebuie făcută, adică starea în care se trece citind simbolul dat.

Funcționarea automatului poate fi descrisă după cum urmează:

• pornind de la starea inițială și primul simbol al șirului de intrare, se decide pe baza funcției să tranziteze într-o anumită stare (ar putea fi, de asemenea, aceeași stare);
• atâta timp cât există un alt simbol în șir de scanat, acesta funcționează în același mod până când se epuizează șirul de intrare;
• se va spune că șirul este acceptat dacă ajunge într-o stare aparținând subsetului stărilor finale.

Astfel de automate sunt capabile să recunoască limbile obișnuite .

Automate cu ieșire

Această clasă de automate de stare finită poate asocia emisia de simboluri aparținând unui alt alfabet numit ieșire . Aceste automate se numesc mașini Moore sau mașini Mealy , în funcție de ieșirea este asociată cu stări (caz mai particular) sau cu tranziții între stări.

ω-automate

Același subiect în detaliu: Ω-automat .

Ω-automatele sunt anumite automate cu stare finită care acceptă intrări de lungime infinită. Acestea reprezintă o abstractizare deosebit de utilă în domeniul metodelor formale , în special pentru tehnicile de verificare a modelelor . Un exemplu binecunoscut de ω-automat este automatul Büchi .

Automate alimentate cu baterii

Același subiect în detaliu: automat stivuit .

Automatele pot fi, de asemenea, echipate cu memorie suplimentară (doar cu privire la stări), de exemplu sub formă de stivă ( împingeți automatele în jos ). Astfel de automate sunt capabile să recunoască o clasă mai largă de limbi decât automatele cu stare finită, cum ar fi cea a limbajelor fără context .

Starea automatelor stivuite constă dintr-un teanc de simboluri. Doar simbolul din partea de sus a stivei la un moment dat este accesibil și poate fi citit.

Tranzițiile în automatele stivuite depind de simbolul de intrare și simbolul de sus al stivei; o tranziție poate presupune plasarea unui simbol nou deasupra stivei și / sau emiterea unui simbol la ieșire.

Automatele stive sunt un superset de automate în stare finită.

Automate liniare delimitate

Același subiect în detaliu: automat liniar delimitat .

Un automat liniar mărginit (în engleză linear bounded automata, LBA) este o mașină specială nedeterministă Turing, în care lungimea benzii este o funcție liniară a dimensiunii intrării. Aceste automate sunt capabile să accepte limbaje dependente de context generate de gramaticile dependente de context (sau de tipul 1 conform ierarhiei Chomsky).

Mașini Turing

Același subiect în detaliu: mașina Turing .

Nivelul maxim de complexitate al unui automat este atins de mașina Turing , un model care generalizează automatele stivei (și, a fortiori, automatele cu stare finită).

Un subansamblu de mașini Turing este constituit de Mașinile care se termină întotdeauna sau decid în terminologia engleză, care sunt mașini pentru care încetarea calculului este întotdeauna garantată, pentru orice intrare.

Automate nedeterministe

Sunt studiate și automatele nedeterministe, adică în care, având în vedere o stare a automatului și un simbol de intrare, este posibilă mai mult de o tranziție. Acestea au utilitate conceptuală în teoria complexității algoritmice .

Bibliografie

• Hopcroft John E., Motwani, Rajeev; Ullman, Jeffrey D., Automate, languages ​​and computability , prima ediție. it., Addison Wesley, ISBN 88-7192-154-2 .

Elemente conexe

• Informatică
• Limbaj formal
• Multidigraf
• Automat cu stare finită
• Mașină secvențială sincronă și asincronă
• Mașină abstractă

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere despre automat

linkuri externe