Definition: Let M = (Q, S, R, s, F) be an FA.
A state q Î Q is accessible if there exists w Î S* such that sw |–* q; otherwise, q is inaccessible.
s
q1
a
f
Example:
q2
a
b
b
Note: Each inaccesible state can be removed from FA
Accessible States
 Gist:
State q is accessible if a string takes DFA from s (the start state) to q.
State s   - accesible: w = e : s |–0 s
State q1 - accesible: w = a :  sa |– q1
State f   - accesible: w = ab: sab |– q1b |– f
State q2 - inaccessible (there is no w Î S*
such that sw |–* q2)
21/44