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: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25