Teoria automatelor

Teoria automatelor  este o ramură a matematicii discrete care studiază automatele abstracte  - calculatoarele reprezentate ca 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 .

Există un tratament algebric al teoriei automatelor folosind semiinele , serii formale de putere , serii formale peste arbori, teoria punctului fix și teoria matricelor [1] .

Terminologie

Un simbol  este orice bloc de date atomic (adică nu mai este indivizibil fără a pierde sensul) care poate avea un efect asupra unei mașini. Cel mai adesea, un simbol este o literă a unui limbaj formal. De exemplu, simbolurile utilizate în multe limbaje de programare includ litere din limbajul obișnuit, separatoare și unele caractere suplimentare. Dar un simbol poate fi, de exemplu, un întreg cuvânt cheie al unui anumit limbaj de programare (dacă, pentru, în timp ce etc.), un element grafic al unei diagrame etc.

Scopul automatelor formale

În teoria automatelor, acest cuvânt este înțeles ca o construcție formală (matematică) care definește un algoritm al cărui scop este să determine dacă un anumit cuvânt aparține limbajului de intrare descris de un automat formal dat. Cuvântul „formal” subliniază diferența dintre un astfel de automat și mașini-unelte automate, transmisii automate și alte dispozitive similare încorporate în metal. Pentru concizie, adjectivul „formal” sau „matematic” este adesea omis în manualele relevante (începând cu numele teoriei - ar fi mai precis „teoria automatelor formale”) atunci când este clar ce este în joc.

Ordinea de funcționare a mașinii

Pentru a-și îndeplini scopul, toate automatele (formale) sunt înzestrate cu proprietatea de a se afla în unele stări admisibile și funcții de tranziție automată, în cel mai simplu caz (automate finite) precizând doar posibilitatea trecerii de la o stare la alta la citirea caracterului următor. din lanțul de intrare. După următoarea tranziție, capul de citire al mașinii este deplasat cu un caracter (este „citește”). Acest lucru se întâmplă până când se ajunge la sfârșitul cuvântului citit sau nu este găsită o funcție de tranziție adecvată.

Setul tuturor stărilor admisibile ale automatului este finit și formează alfabetul stărilor automatului. Din întregul set de stări se distinge un subset al stărilor inițiale ale automatului (într-una dintre care poate începe analizarea cuvântului) și un subset de stări finale (sau finale ) în care automatul (dacă este citit cuvântul ). complet) poate concluziona că cuvântul analizat (de intrare) aparține limbajului mașină. Stările inițiale și finale ale automatului se pot intersecta. Dacă automatul intră în starea finală (sau finală), acesta indică doar posibilitatea finalizării parsării, adică automatul poate trece prin una sau alta stare finală de multe ori în timpul funcționării în timp ce citirea cuvântului continuă.

Pornirea și oprirea mașinii

Începutul funcționării automatului este complet determinat de „configurația sa inițială”, care include cuvântul analizat și starea în care se află automatul. Dacă automatul se află într-una dintre stările inițiale și există o funcție de tranziție pentru această stare și primul simbol al șirului citibil, automatul face tranziția corespunzătoare, deplasează capul de citire pe cuvântul de intrare și (în cel mai simplu caz , automate finite) continuă să examineze următorul simbol de intrare.

Pentru a accepta (sau, după cum se spune, admite) un cuvânt introdus de către un automat, trebuie îndeplinite două condiții:

  1. Cuvântul introdus trebuie citit în întregime
  2. După citirea cuvântului, automatul este (sau poate trece prin tranziții goale, dacă acestea sunt permise pentru tipul corespunzător de automată) la una dintre stările finale. Pentru unele tipuri de automate, acest criteriu poate fi formulat oarecum diferit, iar în teoria automatelor se dovedește echivalența (echivalența) unor astfel de formulări ale opritorului.

Prin „tranziție goală” sau „trecere prin simbol gol” înțelegem aici o trecere de la o stare la alta, când următorul caracter nu este citit din cuvântul de intrare sau, cu alte cuvinte, un caracter gol este „citit”. Vezi mai jos pentru desemnări.

Rețineți că automatul trebuie să accepte toate cuvintele admisibile din limba pe care o descrie și, în același timp, să nu accepte un singur cuvânt care nu este inclus în această limbă.

Dacă cuvântul introdus nu aparține limbii, atunci și automatul

  1. se va opri într-un număr finit de pași fără a fi citit până la sfârșitul cuvântului și fără a avea o funcție de tranziție adecvată pentru a continua citirea
  2. va citi întregul cuvânt, dar nu va fi într-una dintre stările finale (sau un alt criteriu echivalent nu va fi îndeplinit pentru unele tipuri de automate)
  3. intră într-un ciclu infinit de schimbare a stărilor admisibile, în care însă ambele criterii de primire (admitere) a unui cuvânt nu vor fi îndeplinite simultan.

Principalele tipuri de automate

Prin complexitatea limbilor analizate

Automatele formale sunt de obicei împărțite în funcție de caracteristicile funcțiilor lor de tranziție, care determină gradul de complexitate al limbajului pe care îl descrie.

Conform clasificării lui N. Chomsky , sunt cunoscute patru tipuri principale (după varietate, după complexitate) de limbi formale:

  1. Regulat
  2. Fără context
  3. Sensibil de context
  4. Limbi generale (fără restricții suplimentare)

Pentru a analiza cuvinte din limbaje obișnuite, automate formale ale celui mai simplu dispozitiv, așa-numitul. automate finite . Funcția lor de tranziție specifică doar o schimbare de stări și, eventual, o deplasare (citire) a simbolului de intrare.

Pentru a analiza un cuvânt din limbi fără context, trebuie să adăugați o „bandă de cumpărături” sau „stivă” automatului, în care, la fiecare tranziție, este scris un lanț bazat pe alfabetul de magazin corespunzător. Astfel de mașini se numesc „ mașini de magazin ”.

Pentru limbajele sensibile la context, au fost dezvoltate automate și mai complexe delimitate liniar , iar pentru limbajele generale, o mașină Turing [2] .

Cu o cunoaștere mai apropiată a teoriei, devine clar că, cu cât dispozitivul automatului este mai complex, cu atât capacitățile sale de recunoaștere sunt mai mari, dar, în același timp, devine mai dificil și mai consumator de timp să lucrezi cu el. Prin urmare, un matematician competent și un inginer software încearcă să selecteze cel mai simplu tip de automat care rezolvă problema recunoașterii cu calitatea cuvenită.

Rețineți că multe sarcini de căutare a informațiilor pe World Wide Web sunt scrise în termeni de limbaje obișnuite (adică cu cele mai severe restricții), iar majoritatea limbajelor de programare universale utilizate sunt implementate cu destul de mult succes pe baza de gramatici fără context (deși cu unele îmbunătățiri, vezi . „gramatici de atribute”). Printre puținele și foarte ciudate excepții se numără limbajul de programare LISP (LISP), dezvoltat pe baza unor limbaje sensibile la context. Iar Mașina Turing, cu toată universalitatea și puterea sa (în teorie), se dovedește a fi atât de complexă și incomod pentru utilizare în aplicații încât este folosită doar pentru analiză teoretică.

Prin unicitatea funcției de tranziție

Pentru aceeași configurație curentă (starea automatului, simbolul de intrare lizibil și, eventual, câțiva parametri suplimentari pentru tipuri complexe de automate, de exemplu, conținutul stivei într-un automat push-down), funcțiile de tranziție ale unui automat formal. automatul poate specifica ca o singură tranziție (definită, deterministă), deci și câteva diferite. Cu alte cuvinte, pentru aceeași configurație a unui automat, în general, este posibilă existența mai multor funcții de tranziție.

Incertitudinea (non-determinismul) automatului poate apărea și atunci când fiecare dintre configurațiile sale corespunde unei singure funcții de tranziție, dar sunt permise și tranzițiile de-a lungul „lanțului gol” (simbol gol). Este clar că ambiguitatea tranziției aici poate apărea nu într-unul, ci în mai multe cicluri de ceas ale automatului.

Pe această bază, automatele sunt, de asemenea, împărțite în deterministe (definite) și nedeterministe. Importanța acestei împărțiri se explică și prin modul în care proprietatea determinismului afectează interpretarea toleranței unui cuvânt de către un automat.

Deci, dacă avem un automat determinist, atunci dacă nu sunt îndeplinite condițiile de mai sus pentru admiterea unui cuvânt, putem spune imediat că acest cuvânt nu aparține limbajului. Dacă avem un automat nedeterminist, atunci într-un astfel de caz facem această concluzie doar pentru una dintre posibilele ramuri ale parsării cuvântului. De fapt, programatorul trebuie să-și amintească cumva toate bifurcăturile posibile în parsarea unui cuvânt și, dacă una dintre ramuri eșuează, să revină la următoarea bifurcătură și să exploreze o altă ramură de analiză. Și numai după ce examinăm toate opțiunile de analizare posibile (dacă niciuna dintre ramurile intermediare nu îndeplinește condițiile de toleranță), putem concluziona cu încredere că cuvântul dat nu aparține limbajului.

Este clar că urmărirea și contabilizarea posibilelor returnări la analizarea unui cuvânt complică semnificativ munca programatorului. Prin urmare, se pune întrebarea dacă este posibil să se transforme automatul în așa fel încât să devină determinist din nedeterminist și, într-un număr de cazuri, deci mai convenabil pentru a lucra cu el. S-a dovedit în teoria automatelor că acest lucru se poate face întotdeauna pentru limbajele obișnuite și automatele lor finite corespunzătoare. Și pentru alte tipuri de limbi (conform lui N. Chomsky), începând cu fără context și automatele lor corespunzătoare, în cazul general - nu mai.

Pe de altă parte, se observă că automatele nedeterministe au de obicei un volum semnificativ mai mic, logica lor de funcționare este mai ușor de înțeles de către o persoană. Rețineți că atunci când utilizați computere multiprocesor (multi-core), însăși posibilitatea de paralelizare este adesea strâns legată de non-determinismul algoritmului. Un program, din care toate părțile trebuie executate într-o secvență strict definită, nu poate fi paralelizat ... [2] .

Exemple de definiții formale pentru automate finite

Automatele pot fi deterministe sau nedeterministe .

Un automat finit determinist  (DFA)  este o secvență ( tuplu ) de cinci elemente, unde: Un automat finit nedeterminist  (NFA)  este o secvență (tuplu) de cinci elemente, unde: Cuvânt Automatul citește șirul final de caractere a 1 , a 2 , …., a n , unde a i   Σ, care se numește cuvântul de intrare . Setul tuturor cuvintelor este scris ca Σ*. Cuvânt acceptat Cuvântul w   Σ* este acceptat de automat dacă q n  F. 

Se spune că un limbaj L este lizibil (acceptat) de un automat M dacă este format din cuvinte w bazate pe alfabet, astfel încât, dacă aceste cuvinte sunt introduse în M, după terminarea 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ă automate care pot trece la o stare nouă fără a citi un personaj. Funcția de tranziție fără citirea unui caracter se numește -jump (epsilon-jump).

Aplicație

Teoria automatelor stă la baza tuturor tehnologiilor și software-ului digital, de exemplu, un computer este un caz special de implementare practică a unei mașini cu stări finite.

O parte a aparatului matematic al teoriei automatelor este utilizată direct în dezvoltarea analizatoarelor lexicale și sintactice pentru limbaje formale , inclusiv limbaje de programare , precum și în construcția de compilatoare și dezvoltarea limbajelor de programare în sine, descrierilor hardware și marcajului . .

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

Vezi și

Note

  1. ↑ Teoria automatelor moderne , 2013 , p. 5.
  2. ↑ 1 2 Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoria și implementarea limbajelor de programare Copie de arhivă din 3 ianuarie 2022 la Wayback Machine  - M.: MZ-Press, 2006, ed. a 2-a — ISBN 5-94073-094-9

Literatură

Link -uri

  Accesați articolul Wikidata  Dicționare și enciclopedii