Přechodový graf automatu obsahuje e-hrany, což nám trochu komplikuje situaci. Abychom se lépe orientovali, můžeme si udělat tzv. tabulku e-následníků – pro každý stav si napíšeme, kam se můžeme dostat přes e-hrany (tedy aniž by automat zpracoval nějaký vstupní znak). Přidáme i původní stav, tedy možnost, kdy jsme po žádné e-hraně nepřešli.
| 1 | {1, 5, 6} |
| 2 | {2, 3, 4} |
| 3 | {3, 4} |
| 4 | {4} |
| 5 | {5, 6} |
| 6 | {6} |
| 7 | {7} |
| 8 | {8, 9, 4} |
| 9 | {9, 4} |
Teď se pustíme do převodu na deterministický automat. Pro každý stav přidáme i množinu jeho e-následníků. Rozeberme si první řádek tabulky. Počáteční stav je 1, ale e-následníci jsou ještě 5 a 6.
| a | b | |
|---|---|---|
| →{1, 5, 6} |
Kdyby automat byl ve stavu 1, pro vstup a přejde do stavu 2, odkud může dále do e-následníků 3 nebo 4.
| a | b | |
|---|---|---|
| →{1, 5, 6} | {2, 3, 4 |
Kdyby automat byl ve stavu 5, pro vstup a zůstane ve stavu 5, odkud může e-hranou do 6.
| a | b | |
|---|---|---|
| →{1, 5, 6} | {2, 3, 4, 5, 6 |
Kdyby automat byl ve stavu 6, pro vstup a přejde do stavu 7.
| a | b | |
|---|---|---|
| →{1, 5, 6} | {2, 3, 4, 5, 6, 7} |
Pro vstup b automat ze stavu 1 nikam nemůže; ve stavu 5 může zůstat, případně přejít do 6; ze stavu 6 nikam nemůže.
| a | b | |
|---|---|---|
| →{1, 5, 6} | {2, 3, 4, 5, 6, 7} | {5, 6} |
Stejným způsobem pokračujeme v převodu na deterministický automat. Výsledná tabulka vypadá takto
| a | b | ||
|---|---|---|---|
| →{1, 5, 6} | A | {2, 3, 4, 5, 6, 7} | {5, 6} |
| ←{2, 3, 4, 5, 6, 7} | B | {3, 4, 5, 6, 7, 8, 9} | {3, 4, 5, 6} |
| {5, 6} | C | {5, 6, 7} | {5, 6} |
| ←{3, 4, 5, 6, 7, 8, 9} | D | {3, 4, 5, 6, 7, 8, 9} | {3, 4, 5, 6, 9} |
| ←{3, 4, 5, 6} | E | {3, 4, 5, 6, 7} | {3, 4, 5, 6} |
| {5, 6, 7} | F | {5, 6, 7, 8, 9, 4} | {5, 6} |
| ←{3, 4, 5, 6, 9} | G | {3, 4, 5, 6, 7, 9} | {3, 4, 5, 6, 9} |
| ←{3, 4, 5, 6, 7} | H | {3, 4, 5, 6, 7, 8, 9} | {3, 4, 5, 6} |
| ←{5, 6, 7, 8, 9, 4} | I | {5, 6, 7, 8, 9, 4} | {5, 6, 9, 4} |
| ←{3, 4, 5, 6, 7, 9} | J | {3, 4, 5, 6, 7, 8, 9} | {3, 4, 5, 6, 9} |
| ←{5, 6, 9, 4} | K | {5, 6, 7, 9, 4} | {5, 6, 9, 4} |
| ←{5, 6, 7, 9, 4} | L | {5, 6, 7, 8, 9, 4} | {5, 6, 9, 4} |
Přechodový graf výsledného automatu tedy vypadá takto
Udělejme minimalizaci. Počáteční rozklad množiny stavů je {A, C, F}, {B, D, E, G, H, I, J, K, L}.
| a | b | |
|---|---|---|
| A | II | I |
| C | I | I |
| F | II | I |
Stav C musíme z množiny vyčlenit.
| a | b | |
|---|---|---|
| B | II | II |
| D | II | II |
| E | II | II |
| G | II | II |
| H | II | II |
| I | II | II |
| J | II | II |
| K | II | II |
| L | II | II |
Přechody ze všech stavů jsou stejné.
Nový rozklad množiny stavů tedy bude {A, F}, {C}, {B, D, E, G, H, I, J, K, L}. Prozkoumáním chování stavů bychom zjistili, že takový rozklad už je v pořádku.
Přechodový graf výsledného automatu vypadá takto
Je to vlastně automat, který akceptuje řetězce začínající a– nebo obsahující –aa–.