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