Nedeterministický konečný automat (NKA)

  • Každý NKA lze převést do nějakého DKA (ten ale často může mít více stavů)
    • Pokud má NKA stavů, DKA může mít až stavů
  • Často se využívá pro vytvoření návrhu algoritmů, protože vytvoření stavů je intuitivnější než u DKA
  • Nedeterministický konečný automat
    • - konečná množina vnitřních stavů
    • - konečná vstupní abeceda
    • - zobrazení z do množiny všech podmnožin (značíme )
    • - počáteční stav
    • - množina koncových stavů

Konečné automaty s -přechody

  • Jsou vždy nedeterministické
  • Význam -přechodu:
    • Konečný automat vždy provede všechny -přechody před čtením dalšího symbolu
  • K čemu je využít:
    • Vyhledávání v textu s překlepy

-Closure

  • Tzv. uzávěr

  • Funkce pro konečný automat je definována takto:

  • Pro každý stav vytvoříme množinu stavů, do kterých se lze dostat přes přechody (tedy bez "ukrajování" vstupního řetězce)

  • Příklad:

../Attachments/02-epsilon-closure.png

Vztah mezi DKA a NKA

  • Konečné automaty a nazýváme ekvivalentní, jestliže přijímají stejný jazyk, tj.
  • Ke každému nedeterministickému konečnému automatu existuje ekvivalentní deterministický konečný automat

Převod NKA na DKA (determinizace)

  • Vytvořím DKA takový, že každý jeho stav se sestává z množiny stavů NKA
  • Počátečním stavem je množina obsahující počáteční stav NKA
  • Stavy s přechodem pro stejný symbol sjednotím do 1 stavu
  • Velikost výsledného DKA
    • Pokud velikost , pak velikost může být až
    • Pokud je homogenní NKA, pak počet stavů DKA získaného standardní determinizací (podmnožinovou konstrukcí) je omezen vztahem níže, tedy

Příklad 1:

../Attachments/Pasted image 20221004164815.png

Příklad 2:

../Attachments/Pasted image 20221004171703.png

NKA:

Stav a b
-> 0 {2,3} {1,4}
<- 1 {3} {1}
<- 2 {2} {4}
3 {3} {3}
4 {4} {4}

DKA determinizovaný:

Stav a b
-> {0} {2,3} {1,4}
<- {2,3} {2,3} {3,4}
<- {1,4} {3,4} {1,4}
{3,4} {3,4} {3,1}

Úplně určený NKA

  • nazveme úplně určený, když zobrazení
  • Tedy každý přechod má v tabulce přechodů vyplněné políčko ve kterém není prázdná množina

Vytvořeno: 13. 6. 2023, 12:48
Poslední aktualizace: 27. 5. 2026, 16:04