Reprezentace konečných automatů
Konečný automat můžeme znázornit tabulkou, grafem nebo stavovým stromem.
Následující příklady (zobrazení) jsou pro:
konečný automat A ({S1,S2} , {a,b} , {δ(S1,a)=S2, δ(S1,b)=S1, δ(S2,a)=S1, δ(S2,a)=S2} , S1 , S2).
Slova přijímaná tímto automatem A: {a, ba, aaa, aba, bba, aaba, abba, baaa, ...}
Slova nepřijatá tímto automatem A: {b, ab, aab, abb, baa, bab, aaaa, aaab, ...}
| Tabulka konečného automatu A | ||
| stav \ symbol | a | b |
|---|---|---|
| >> S1 | S2 | S1 |
| << S2 | S1 | S1 |
Reprezentace konečného automatu tabulkou
Tabulka reprezentuje návratovou funkci. Řádky jsou stavy a sloupce symboly abecedy. Konkretní buňka tabulky pak je stav na který se dostanu ze stavu daného řádkem a symbolu daného sloupcem.
Reprezentace konečného automatu grafem
Uzly grafu reprezentují stavy KA, přechodovou funkci vyjadřují hrany označené symboly, koncový stav je vyjádřen zesílením uzlu a počáteční stav označen šipkou.
Reprezentace konečného automatu stavovým stromem
Kořen stromu je počáteční stav konečného automatu. Děti uzlu jsou stavy na které se dostanu z nadřazeného uzlu. Koncové stavy jsou zvýrazněné podobně jako u grafu. Strom se dobře vytvoří z tabulky.