Definice: Nechť M = (Q, S, R, s, F) je DKA. Stav q Î Q je ukončující, pokud existuje řetězec w Î S*, pro který platí: qw |–* f. Jinak q je neukončující.
s
q1
a
f
Příklad:
q2
b
Stav s   - ukončující: w = ab : sab |– q1b |– f
Stav q1 - ukončující: w = b :  q1b |– f
Stav f   - ukončující: w = e : f |–0 f
Stav q2 - neukončující (neexistuje žádné w Î S* takové že: q2w |–* q, q Î F)
Pozn.: Každý neukončující stav může být odstraněn.
Ukončující stavy
Myšlenka: Stav q je ukončující, pokud pro nějaký řetězec „dostane“ DKA z q do koncového stavu
b
a
28/44