# Using Kleene's Theorem for Finite Automata State Elimination

• Sep 26th 2011, 09:43 AM
LostProjectile
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?
• Sep 26th 2011, 11:53 AM
emakarov
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

\$\displaystyle R(i,j,k)=R(i,j,k-1)\cup R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1)\$

where \$\displaystyle R(i,j,k)\$ is the regular expression for words that go from state \$\displaystyle i\$ to state \$\displaystyle j\$ through states no higher than \$\displaystyle k\$?

"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 \$\displaystyle k\$ is a dead state, then \$\displaystyle R(i,k,k-1)\$ is empty when \$\displaystyle i\ne k\$, and so \$\displaystyle R(i,j,k)=R(i,j,k-1)\$ for all \$\displaystyle i\ne k\$ and \$\displaystyle j\$. 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).