2.2.3 Odstranění ε-přechodů

\(\varepsilon\)-přechod

\(\varepsilon\)-přechod je přechod, který může automat provést pro libovolný symbol na vstupu, přičemž při použití tohoto přechodu se ze vstupu žádný symbol nečte (čtecí hlava se neposouvá).

Definice (\(\varepsilon\)-closure)

\(\varepsilon\)-closure

\(\varepsilon\)-closure je funkce, která na vstupu vyžaduje stav automatu, pro nějž vrací množinu všech stavů, které jsou z daného stavu dosažitelné bez nutnosti čtení vstupního symbolu.

Do této množiny tak patří vždy sám stav, pro který \(\varepsilon\)-closure počítáme, a všechny další, které jsou z tohoto stavu dosažitelné pomocí \(\varepsilon\)-přechodů (jednoho i více).

Odstranění \(\varepsilon\)-přechodů

Algoritmicky odstraňujeme \(\varepsilon\)-přechody ve třech krocích:

Vypočteme funkci \(\varepsilon\)-closure pro všechny stavy.
Z automatu odstraníme všechny \(\varepsilon\)-přechody a pomocí \(\varepsilon\)-closure upravíme přechodovou funkci automatu. Pokud máme například \(\varepsilon\text{-closure}(S) = \{S, A, B\}\), pak všechny přechody, které vedou ze stavů \(S, A\) a \(B\), povedou také ze stavu \(S\).
Upravíme množinu koncových stavů. Koncové stavy jsou ty, které ve svém \(\varepsilon\)-closure mají alespoň jeden z původních koncových stavů.