Definition: Let M = (Q, S, R, s, F) be a DFA. A state q Î Q is terminating if there exists w Î S* such that qw
|–* f
with f Î F; otherwise, q is nonterminating.
s
q1
a
f
Example:
q2
b
State s
- terminating: w = ab : sab |–
q1b |– f
State q1 - terminating: w = b : q1b |– f
State f
- terminating: w = e : f |–0 f
State q2 - nonterminating (there is no w Î S* such that q2w |–*
q, q Î F)
Note: Each nonterminating state can be removed from DFA
Terminating States
Gist:
State q
is terminating if a string takes DFA from q
to a final state.
b
a
28/44