State elimination for finite automata
= State elimination for finite automata
{title2=$R_{ij}\gets R_{ij}\cup R_{ik}R_{kk}^*R_{kj}$}
To remove an internal state $k$, replace each surviving label by $R_{ij}\cup R_{ik}(R_{kk})^*R_{kj}$. The added term accounts for entering $k$, traversing its loop any number of times, and leaving it. Fresh initial and final states allow all old states to be eliminated, producing a <regular expression> for the same language.