Showing that for every NFA with n states, there is a regular expression of length $O(2^n)$

Question

Consider the idea of an extended non-deterministic automation, where transitions can be labelled by regular expressions and not simply by symbols of the input alphabet or $\epsilon$. Such an automaton would work in the obvious way: if there is a transition from state $q$ to state $q′$ labelled with a regular expression $E$, then the automaton can move from $q$ to $q′$ by reading a prefix of the input word that is a string in $L(E)$.

$(a)$ Explain how every non-deterministic automaton with n states can be converted into an equivalent, extended non-deterministic automaton with $n + 2$ states such that

• The initial state has no incoming transitions.

• There is a single accepting state with no outgoing transitions.

• There is at most one transition between any pair of states.

$(b)$ Now show how to obtain a single regular expression denoting the original language by iteratively removing states from the extended non-deterministic automaton obtained in part $(a)$ while maintaining equivalence. As you remove each state, you should maintain the three properties in part $(a)$. At the end, only the initial state and the single accepting state will remain, and there will be one edge labelled with the regular expression to be found. Explain why the size of this expression is $O(2^n)$

For part $(a)$ we can just add 2 new states, make the first 1 a new starting state and add an edge from it to the old starting state, and make the second one a new final state and add an edge from all old final states to it(and then remove the old final states from the set of final states).

If the NFA happens to have more than one transitions between any pair of states, let the the labels be $E$ and $F$ on the edges. Replace it with a single edge with the label $(E+F)$.

I'm unsure about part $(b)$. My idea was that if we're removing node $u$, then for all nodes $(v,u)$ such that there's an edge from $(v,u)$ with label $E$ and for all nodes $(u,x)$ with label $F$, add a label between $(v,x)$ with label $E.F$. If there already exists some label between these 2 nodes, add the old label, $G$ to $E.F$ (making the label $E.F + G$).

Keep doing this till we only have the start and the final node left - but this doesn't seem to work as we end up with self loops at times which i don't know how to deal with?

Answer 1

What you are looking for, the solution to part (b) is the last step of the State Elimination Method that converts a DFA/NFA/$\epsilon$-NFA into regular expression. Here is a short article that explains the method.

---

"If we're removing node $u$, then for all nodes $(v,u)$ such that there's an edge from $(v,u)$ with label $E$ and for all nodes $(u,x)$ with label $F$, add a label between $(v,x)$ with label $E\cdot F$. If there already exists some label between these 2 nodes, add the old label, $G$ to $E.F$ (making the label $E\cdot F + G$)."

The above idea of yours is pretty good. However, it misses the self loop from $u$ to itself, as you have pointed out.

Suppose the label between $(u,u)$ is $H$. Instead of label $E\cdot F$, use $E\cdot H^*\cdot F$ instead. That is all you need to do.

Since $E$, $H$ and $F$ might be the sum of regular expressions, it should be safer to write $(E)(H)^*(F)$ instead of $E\cdot H^*\cdot G$, so that the order of operator precedence is maintained properly. Also, write $(E)(H)^*(F) + G$ instead of $E\cdot F + G$.