Recunoscători pentru diferite clase de gramatică
Limba este definită prin specificarea unui set de stări finale valide ale recunoașterii. dacă lanțul alimentat la banda de intrare permite recunoașterii să execute o secvență de pași și să se oprească în starea finală, atunci lanțul aparține limbii.
Se pare că fiecare clasă de gramatici din ierarhia Chomsky corespunde unei clase de recunoașteri. Definirea aceleiași clase de limbi:
- Limba L este dreapta-liniară dacă și numai dacă este definită (printr-un automat determinist unilateral) finit
- Limba L este contextuală dacă și numai dacă este determinată (printr-un automat nedeterminist unilateral) cu memorie de stocare
- Limba L este dependentă de context dacă și numai dacă este determinată (printr-un automat nedeterminist cu două fețe) cu memorie de stocare
- Limba L recursiv enumerable dacă și numai în cazul în care este determinată de o mașină Turing (aceste concepte, nu vom opera, definită în mod oficial în cursul „calculabilitate“ sau un curs de bază „Computer Science“).
Materialul suplimentar al lecției va fi dedicat determinării proprietăților recunoscătorilor. menționate în aceste afirmații, și discutarea aplicabilității lor în practică.
Mașini de stat finit
O mașină de stat finită este una dintre cele mai simple mecanisme utilizate în lucrul cu limbile străine. Acest recunoscător are doar un set fix de celule de memorie, iar dispozitivul de control poate să se deplaseze spre dreapta de-a lungul benzii de intrare și să modifice stările memoriei. Partea principală a mașinii finite este funcția de tranziție. Acesta definește posibile tranziții pentru orice stare curentă și orice simbol de intrare. Se presupune că este permisă trecerea la mai multe stări diferite ale automatului, adică dispozitivul de comandă al dispozitivului de recunoaștere poate fi nedeterminist. Nedeterminarea trebuie înțeleasă după cum urmează: dacă mai multe tranziții dintr-o anumită stare sunt posibile simultan, atunci sunt create mai multe copii ale mașinii noastre, una pentru fiecare stare nouă. Se consideră că o conversație aparține unei limbi dacă cel puțin o secvență de pași este finalizată în starea finală.
După o scurtă explicație a ideilor de bază, putem da o definiție formală a unui automat finit.
Definiția. Mașina de stat finită este de cinci
- Q este un set finit de state
- - set finit de simboluri de intrare admisibile
- - maparea setului în setul P (Q). Comportamentul de control al dispozitivului de control (această funcție este denumită adesea funcția de tranziție)
- - starea inițială a dispozitivului de comandă
- - set de state finale
În principiu, pentru a determina acțiunile ulterioare ale mașinii de stat, este suficientă cunoașterea stării actuale a dispozitivului de comandă, plus secvența de simboluri încă neprocesate pe banda de intrare. Acest set de date se numește configurația automată.
Masini deterministe de stare finita
Definim un automat determinat determinist ca un caz special al unui automat finit (nedeterminist) finit și introducem câteva definiții și convenții suplimentare care ne vor fi utile în viitor:
Definiția. Se spune că un automat este determinist dacă setul conține cel mult o stare pentru orice. Dacă întotdeauna conține exact o stare (adică nu are tranziții nedefinite), atunci automatul este numit complet definit.
Definiția. Un cuvânt deasupra unui alfabet este permis de un automat finit dacă există o secvență de stări astfel încât pentru.
Definiția. Limba L este recunoscută de un automat finit dacă fiecare cuvânt al limbajului L este permis de acest automat finit.
Desemnarea. Automatele finite sunt ilustrate cu ajutorul diagramelor de tranziție. consultați exemplele de mai jos (cercurile duble denotă stările finale):
Automat. recunoașterea limbii: Automatic. recunoașterea limbii: