2.2.5 Determinizace

Determinizace

Determinizace je metoda sloužící k převodu nedeterministického automatu na deterministický.

NKA se během výpočtu v jedné chvíli může nacházet v libovolné podmnožině svých stavů. Determinizace funguje na principu podmnožinové konstrukce, neboť postupně vytváří všechny možné podmnožiny stavů, ve kterých se daný NKA může během výpočtu nacházet. Tyto podmnožiny následně prohlásíme za stavy ekvivalentního deterministického automatu.

Vlastnosti determinizace

V nejhorším možném případě se může NKA během výpočtu vyskytovat ve všech možných podmnožinách svých \(n\) stavů. Příslušný DKA by tak měl \(2^n\) stavů.
Na svém vstupu předpokládá metoda determinizace nedeterministický automat (tj. bez \(\varepsilon\)-přechodů a s jedním počátečním stavem).
Každý nedeterministický konečný automat může být převeden na ekvivalentní deterministický.

Algoritmus determinizace

Mějme NKA \(M = (Q, \Sigma, \delta, q_0, F)\). Vytvoříme ekvivalentní DKA \(M' = (Q', \Sigma, \delta', q_0', F')\) takto:

Počáteční stav: Novým počátečním stavem \(q_0'\) bude podmnožina obsahující pouze počáteční stav původního automatu, tj. \(\{q_0\}\).
Přechodová funkce: Pro každý stav \(X \in Q'\) (kde \(X\) je množina původních stavů) a každý symbol \(a \in \Sigma\) určíme přechod \(\delta'(X, a) = Y\), kde \(Y = \bigcup_{q \in X} \delta(q, a)\). Pokud stav \(Y\) ještě není v \(Q'\), přidáme ho tam.
Koncové stavy: Množina koncových stavů \(F'\) bude obsahovat všechny stavy \(X \in Q'\), které obsahují alespoň jeden původní koncový stav (tj. \(X \cap F \neq \emptyset\)).

Poznámka: Pokud má nedeterministický automat na vstupu více počátečních stavů, lze použít modifikovaný algoritmus determinizace. Ten se liší od standardního tím, že počáteční stav DKA není podmnožina tvořená jedním počátečním stavem NKA, ale podmnožina obsahující všechny počáteční stavy NKA.