Using Kleene's Theorem for Finite Automata State Elimination
When using Kleene's Theorem in order to determine the regular expression represented by a finite automata, are you able to simply immediately eliminate the dead states since they wouldn't be part of the regular expression? If not, how would they factor into the regular expression?
Re: Using Kleene's Theorem for Finite Automata State Elimination
By Kleene's theorem, do you mean the regular theorem about converting finite automata into regular expressions? The one with
=R(i,j,k-1)\cup R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1))
where
is the regular expression for words that go from state
to state
through states no higher than
?
"Are you able" is a little vague. The theorem contains an algorithm that works for all states, dead or not. If you want, you can perform simplifications along the way. If you know that
is a dead state, then
is empty when
, and so
for all
and
. On the other hand, in the middle of the algorithm, it may not be clear which states are dead (they may be accessible through states with higher numbers).