Přechodový graf můžeme značně zjednodušit tak, že odstraníme některé e-hrany. To můžeme udělat za situace, kdy dvojice stavů spojených e-hranou má právě jednu hranu vedoucí dovnitř a právě jednu hranu vedoucí ven. Případné smyčky mohou být jen u jednoho ze stavů. Nadbytečnou e-hranu v takovém případě odstraníme a dvojici stavů sloučíme.
V našem automatu můžeme odstranit vyznačené e-hrany
Po odstranění e-hran získáme následující přechodový graf
Další úvahy už vyžadují jistou zkušenost. Vidíme, že stavy 2 a 8 jsou vlastně ekvivalentní. Je v nich smyčka pro a, b a vede z nich e-hrana do stavu 4. Mohli bychom je tedy sloučit. Díky e-hraně do výstupního stavu můžeme sloučený stav udělat výstupním. Stav 4 už pak nebude k ničemu, takže ho odstraníme.
Získáme následující přechodový graf
To je pořád NKA. Přikročíme ke známému převodu na deterministický automat. O tabulce e-následníků a jak s ní zacházet si přečtěte na začátku pracného řešení.
| 1 | {1, 5} |
| 2 | {2} |
| 5 | {5} |
| 7 | {7} |
Tabulka pro převod NKA na deterministický vypadá takhle
| a | b | ||
|---|---|---|---|
| →{1, 5} | A | {2, 5, 7} | {5} |
| ←{2, 5, 7} | B | {2, 5, 7} | {2, 5} |
| {5} | C | {5, 7} | {5} |
| ←{2, 5} | D | {2, 5, 7} | {2, 5} |
| {5, 7} | D | {2, 5, 7} | {5} |
A tady je přechodový graf deterministického automatu
Udělejme minimalizaci. Počáteční rozklad množiny stavů je {A, C, E}, {B, D}.
| 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 |
Přechody ze všech stavů jsou stejné.
Nový rozklad množiny stavů tedy bude {A, E}, {C}, {B, D}. 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–.