Deterministický konečný automat (DKA)

  • Patří do regulárních jazyků
  • Deterministický konečný automat
    • - konečná množina vnitřních stavů
    • - konečná vstupní abeceda
    • - zobrazení z do
    • - počáteční stav
    • - množina koncových stavů

Komponenty

Vstupní páska

  • Je na ní zapsaný řetězec (sekvence symbolů) - vstup
  • Read-only

Hlava

  • Čte jeden symbol a posune se vpravo

Tělo

  • Má nějaký stav, ten je z nějaké množiny stavů, která je konečná
  • Chování podle přechodové funkce
  • Skončí po přečtení celého vstupu, podívá se v jakém stavu skončil
    • pokud v koncovém, přijme vstup - tedy vstup je věta z jazyka generovaného tou gramatikou
    • pokud v jiném, nepřijme vstup

Konfigurace

  • Dvojice
    • - dosud přečtený vstup
    • - zbytek vstupu, zatím nepřečtený
  • Počáteční konfigurace -
  • Přijímací konfigurace (na konci po přijetí validního vstupu) -

Přechod DKA

  • Značíme
    • - tranzitivní uzávěr - množina všech konfigurací, do kterých se automat může dostat po libovolném množství přechodů
    • - reflexivní uzávěr - to samé, ale i včetně počáteční konfigurace bez žádného přechodu
  • Mezi dvěma konfiguracemi,

Jazyk přijímaný DKA

  • Řetězec je přijat konečným deterministickým automatem , jestliže pro nějaké
    (existuje posloupnost přechodů z počáteční do přijímací konfigurace)
  • je jazyk přijímaný automatem

Zapsání konfigurace

Definicí

Tabulkou

../Attachments/02-konfigurace-dka-tabulkou.png

Grafem

../Attachments/02-konfigurace-dka-grafem.png

Regulární jazyk / problém

  • Takový problém, který lze vyřešit konečným automatem

Úplně určený DKA

  • Všechny chybné / neurčené vstupy vedou do jednoho stavu
    • Ten není konečný - nelze ty přijmout vstup
    • Má smyčku sám na sebe
  • Každý stav reprezentující řetězec, který nepatří do jazyka, musí být v tom automatu

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25