Definice: Nechť M = (Q, S, R, s, F) je DKA. M je úplný, pokud pro libovolné p Î Q, a Î S existuje právě jedno pravidlo pa ® q Î R pro nějaké q Î Q. Jinak M je neúplný.
S = {a, b, c}
a
s
f
b
c
Převod: Neúplný DKA:
?
a
b
c
?
?
c
a, b
qfalse
a, b, c
Úplný DKA:
b
a
s
f
c
Úplný DKA
32/44
Myšlenka: Úplný DKA se nemůže zaseknout.