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–.