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