alex , mylisz skończony automat deterministyczny ze skończonym automatem zupełnym. Przez przebieg (ang. run) automatu definiuje się ciąg s_0, …, s_n, gdzie n jest długością słowa w, taki że: s_0 \in S_0 (zbiór stanów początkowych), a s_i \in \delta(s_{i-1}, w_i) dla i = 1, …, n. Słowo jest akceptowane, jeśli istnieje taki przebieg dla słowa w, że s_n jest w zbiorze stanów końcowych. Dla każdego słowa, automat niedeterministyczny może mieć takich przebiegów dowolną ilość, deterministyczny - co najwyżej jeden, zupełny - dokładnie jeden. Skoro automat “Zawsze jest w jakimś stanie”, to w jakim stanie będzie ten:
--->q0---a--->q1--a, b--+
^ |
| |
+--------+
q1 - stan końcowy
po wczytaniu słowa “baba”?