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
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).