Deterministický TS (DTS)
Myšlenka: Deterministický TS může provést z každé konfigurace maximálně jeden přechod
Definice: Nechť M = (Q, S, G, R, s, F) je TS. M je deterministický TS, pokud pro každé pravidlo tvaru pa ® qbt Î R platí, že množina R – {pa ® qbt} neobsahuje žádné pravidlo s levou stranou pa.
19/45
Tvrzení: Pro každý TS M existuje ekvivalentní DTS Md.
Důkaz: Viz. str. 634 v knize [Meduna: Automata and Languages]