02 Nedeterministický konečný automat
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# 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 $n$ stavů, DKA může mít až $2^n$ 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 $M = (Q, \Sigma, \delta, q_{0,}F)$
- $Q$ - konečná množina vnitřních stavů
- $\Sigma$ - konečná vstupní abeceda
- $\delta$ - zobrazení z $Q \times \Sigma$ do množiny všech podmnožin $Q$ (značíme $2^{Q}$)
- $q_{0}\in Q$ - počáteční stav
- $F \subseteq Q$ - množina koncových stavů
# Konečné automaty s $\Large{\varepsilon}$-přechody
- Jsou vždy nedeterministické
- Význam $\varepsilon$-přechodu:
- Konečný automat vždy provede všechny $\varepsilon$-přechody před čtením dalšího symbolu
- K čemu je využít:
- Vyhledávání v textu s překlepy
# $\huge{\varepsilon}$-Closure
Tzv. $\varepsilon$ uzávěr
Funkce $\varepsilon \textendash Closure: Q \mapsto 2^Q$ pro konečný automat $M$ je definována takto:
$\varepsilon \textendash Closure(q) = {\space p: (q,\varepsilon) \vdash^{*} (p,\varepsilon),\enspace p \in Q \space }$
Pro každý stav vytvoříme množinu stavů, do kterých se lze dostat přes $\varepsilon$ přechody (tedy bez “ukrajování” vstupního řetězce)
Příklad:
Vztah mezi DKA a NKA
- Konečné automaty $M_{1}$ a $M_{2}$ nazýváme ekvivalentní, jestliže přijímají stejný jazyk, tj. $L(M_{1}) = L(M_{2})$
- Ke každému nedeterministickému konečnému automatu $M$ existuje ekvivalentní deterministický konečný automat $M'$
# 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 $|Q_{NKA}| = n$, pak velikost $|Q_{DKA}|$ může být až $2^n$
- Pokud $M$ je homogenní NKA, pak počet stavů DKA $M’$ získaného standardní [determinizací](None#Převod NKA na DKA determinizace) (podmnožinovou konstrukcí) je omezen vztahem níže, tedy $< 2^{n}$ $$ |Q’| \leq \sum_{a \in \Sigma}{(2^{Q(a)})-|\Sigma|+1} $$
# Příklad 1:
# Příklad 2:
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
- $M$ nazveme úplně určený, když zobrazení $\delta(q,a) \neq \emptyset, \forall q \in Q, a \in \Sigma$
- Tedy každý přechod má v tabulce přechodů vyplněné políčko ve kterém není prázdná množina