Decompiling NFA to Regular Expressions

Goal

Given an NFA $M$, construct a regular expression $R$ with $L(R) = L(M)$.

The State Elimination Method

Setup

Given NFA $M = (Q, \Sigma, \Delta, s, F)$, we compute a regex for paths through $M$.

Normalisation

First, transform $M$ to have:

1. A single start state (with no incoming edges)
2. A single accepting state (with no outgoing edges)

Add new start $s_{\text{new}}$ with $\varepsilon$-edge to $s$.

Add new accept $f_{\text{new}}$ with $\varepsilon$-edges from all states in $F$.

Regional Languages

Definition

A region $(p, S, q)$ specifies:

• Source state $p$
• Target state $q$
• Set $S$ of states allowed as intermediate

The regional language $R(p, S, q)$ is the set of strings labelling paths from $p$ to $q$ using only states in $S$ as intermediate nodes.

Base Case: $S = \emptyset$

$R(p, \emptyset, q) = \begin{cases} \varepsilon \cup a_1 | \cdots | a_k & p = q \text{ and } p \xrightarrow{a_i} p \\ a_1 | \cdots | a_k & p \xrightarrow{a_i} q \\ \emptyset & \text{no direct path} \end{cases}$

Where $a_1, \ldots, a_k$ label the direct edges from $p$ to $q$.

Inductive Step

For $S = S' \cup \{r\}$ where $r \notin S'$:

$R(p, S, q) = R(p, S', q) \cup R(p, S', r) \cdot R(r, S', r)^* \cdot R(r, S', q)$

Interpretation

Paths from $p$ to $q$ through $S$ either:

1. Don’t visit $r$ at all (stay in $S'$): $R(p, S', q)$
2. Visit $r$ at least once:
   • Go $p \to r$ staying in $S'$: $R(p, S', r)$
   • Loop at $r$ zero or more times: $R(r, S', r)^*$
   • Go $r \to q$ staying in $S'$: $R, S', q)$

Algorithm

1. Normalise: single start $s$, single accept $f$
2. Compute $R(s, Q \setminus \{s, f\}, f)$ by eliminating states one by one
3. The result is $L(M)$

Order of Elimination

The order in which states are eliminated does not affect correctness, but can affect the size of the resulting regex.

Common strategies:

• Eliminate states with few transitions first
• Eliminate “middle” states before endpoints

Example

Automaton

Two-state NFA: $q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0$, with $q_1$ accepting.

Computation

We want $R(q_0, \{q_0, q_1\}, q_1)$.

Let $S = \{q_0, q_1\}$.

Eliminate in some order. Suppose we eliminate $q_0$ first.

Actually, with normalisation, we have start $s$ and accept $f$. The internal states are $\{q_0, q_1\}$.

Compute $R(s, \{q_0, q_1\}, f)$:

• Paths: $s \xrightarrow{\varepsilon} q_0 \xrightarrow{a} q_1 \xrightarrow{\varepsilon} f$, or
• $q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0 \xrightarrow{a} q_1 \xrightarrow{\varepsilon} f$, etc.

After elimination: the language is $a(ba)^*$ plus accounting for $\varepsilon$-transitions.

Size Considerations

Worst Case

The regex may grow exponentially as states are eliminated due to the union and concatenation operations.

Optimisation

• Factor common subexpressions
• Use algebraic simplifications (e.g., $\emptyset \cdot R = \emptyset$, $\varepsilon \cdot R = R$)
• Choose good elimination order

Closure under Complement

Using automaton-to-regex conversion:

1. Convert regex to DFA (via NFA)
2. Swap accepting and non-accepting states
3. Convert back to regex

This shows regular languages are closed under complement.

---

Summary

• Compute regex $R(p, S, q)$ for paths through region
• Base case: direct transitions
• Inductive step: $R(p, S, q) = R(p, S', q) \cup R(p, S', r) \cdot R(r, S', r)^* \cdot R(r, S', q)$
• Eliminate all internal states to get the full language