Translating Regular Expressions to NFAs

We’ve seen that NFAs and DFAs are weakly equivalent: they both generate exactly the same languages. How do they relate to regular expressions? We’ll answer this question in both directions. First, we’ll turn any regular expression into an NFA. Then we’ll turn any NFA into a regular expression. Since DFAs and NFAs are already known to be equivalent, the two constructions will show that all three formalisms generate exactly the regular languages.

The target in the first direction is $\mathbb{L}(G)=\mathbb{L}(\rho)$ for the machine $G$ constructed from $\rho$. The target in the reverse direction is $\mathbb{L}(\rho)=\mathbb{L}(G)$ for the expression constructed from $G$.

Translating Regular Expressions to NFAs

Given a regular expression $\rho$ on alphabet $\Sigma$, we can construct an NFA $G_\rho = \langle Q_\rho, \Sigma, \delta_\rho, q_0^\rho, F_\rho \rangle$ that recognizes exactly the language $\mathbb{L}(\rho) = \text{eval}(\rho)$.

We’ll build this conversion recursively, following the structure of regular expressions:

Base Cases

Where for each case:

For $\rho = \emptyset$ (the empty language):
- $Q_\rho = \{q_0, q_1\}$
- $\delta_\rho = \emptyset$ (no transitions)
- $q_0^\rho = q_0$
- $F_\rho = \emptyset$ (no final states)
For $\rho = \epsilon$ (the empty string):
- $Q_\rho = \{q_0\}$
- $\delta_\rho = \emptyset$ (no transitions)
- $q_0^\rho = q_0$
- $F_\rho = \{q_0\}$
For $\rho = a$ where $a \in \Sigma$ (a single symbol):
- $Q_\rho = \{q_0, q_1\}$
- $\delta_\rho(q_0, a) = \{q_1\}$
- $q_0^\rho = q_0$
- $F_\rho = \{q_1\}$

Recursive Cases

For the recursive cases, we’ll use the operations we’ve already defined for NFAs:

For $\rho = (\rho_1 \cup \rho_2)$ (union):
- Construct $G_{\rho_1}$ and $G_{\rho_2}$ recursively
- $G_\rho = \text{union}(G_{\rho_1}, G_{\rho_2})$
For $\rho = (\rho_1 \circ \rho_2)$ (concatenation):
- Construct $G_{\rho_1}$ and $G_{\rho_2}$ recursively
- $G_\rho = \text{concatenate}(G_{\rho_1}, G_{\rho_2})$
For $\rho = \rho_1^*$ (Kleene star):
- Construct $G_{\rho_1}$ recursively
- $G_\rho = \text{kleene}(G_{\rho_1})$

Let’s implement this conversion algorithm:

\[ \text{regex2nfa}(\rho) = \begin{cases} \langle \{q_0, q_1\}, \Sigma, \emptyset, q_0, \emptyset \rangle & \text{if } \rho = \emptyset \\ \langle \{q_0\}, \Sigma, \emptyset, q_0, \{q_0\} \rangle & \text{if } \rho = \epsilon \\ \langle \{q_0, q_1\}, \Sigma, \{(q_0, a) \mapsto \{q_1\}\}, q_0, \{q_1\} \rangle & \text{if } \rho = a \in \Sigma \\ \text{union}(\text{regex2nfa}(\rho_1), \text{regex2nfa}(\rho_2)) & \text{if } \rho = (\rho_1 \cup \rho_2) \\ \text{concatenate}(\text{regex2nfa}(\rho_1), \text{regex2nfa}(\rho_2)) & \text{if } \rho = (\rho_1 \circ \rho_2) \\ \text{kleene}(\text{regex2nfa}(\rho_1)) & \text{if } \rho = \rho_1^* \end{cases} \]

Why should this recursive conversion preserve the language? The claim we need is

\[\mathbb{L}(\operatorname{regex2nfa}(\rho))=\operatorname{eval}(\rho)\]

by structural induction on $\rho$. There are three base cases. The machine for $\emptyset$ has no final state, so it accepts no string. The machine for $\epsilon$ begins in its only final state and has no transitions, so it accepts exactly the empty string. And the machine for $a\in\Sigma$ has one $a$-transition from its initial state to its only final state, so it accepts exactly $\{a\}$. Each machine thus agrees with the corresponding evaluation clause.

For the recursive cases, assume that the machines constructed for the immediate subexpressions recognize exactly their evaluated languages. If $\rho=(\rho_1\cup\rho_2)$, the union construction recognizes

\[\mathbb{L}(G_{\rho_1})\cup\mathbb{L}(G_{\rho_2}) =\operatorname{eval}(\rho_1)\cup\operatorname{eval}(\rho_2) =\operatorname{eval}(\rho).\]

The concatenation case replaces union in this equality with language concatenation, and the star case replaces it with Kleene closure. The correctness proofs for the three automaton operations establish those first equalities. So each constructor preserves the induction hypothesis. Every regular expression is built from a base case by finitely many constructors, which gives the desired equality for every $\rho$.

Consider $\rho=a\circ b^*$. The recursive calls build the one-transition machine for $a$ and the one-transition machine for $b$, apply the star construction to the latter, and concatenate the results. An accepting path must first consume one a; it may then take the restarted b path any finite number of times. The resulting language is $\{ab^i\mid i\geq0\}$, exactly $\operatorname{eval}(a\circ b^*)$.

Translating NFAs to Regular Expressions

We’ve seen how to convert a regular expression to an NFA. Now let’s explore the reverse: converting an NFA to an equivalent regular expression.

Given an NFA $G = \langle Q, \Sigma, \delta, q_0, F \rangle$, we can construct a regular expression $\rho$ such that $\mathbb{L}(G) = \mathbb{L}(\rho)$.

The State Elimination Method

The most common approach for this conversion is the state elimination method:

Transform the NFA into a generalized NFA (GNFA) with a single initial state, a single final state, and transitions labeled with regular expressions
Systematically eliminate states one by one, updating the transition labels accordingly
When only the initial and final states remain, the regular expression on the transition between them represents the language of the original NFA

Step 1: Construct the GNFA

First, we transform the NFA into a GNFA:

Add a new initial state $q_{\text{init}}$ with an ε-transition to the original initial state $q_0$
Add a new final state $q_{\text{final}}$ and add ε-transitions from all original final states to $q_{\text{final}}$
Make $q_{\text{final}}$ the only final state
Label each transition with the corresponding symbol from the alphabet (or ε)

Step 2: Eliminate States

For each state $q_k$ (except $q_{\text{init}}$ and $q_{\text{final}}$):

For each pair of states $q_i$ and $q_j$ such that there are transitions from $q_i$ to $q_k$ and from $q_k$ to $q_j$:
- Let $R_{ik}$ be the regular expression on the transition from $q_i$ to $q_k$
- Let $R_{kk}$ be the regular expression on the self-loop at $q_k$ (if any, otherwise $\emptyset$)
- Let $R_{kj}$ be the regular expression on the transition from $q_k$ to $q_j$
- Create or update the transition from $q_i$ to $q_j$ with the regular expression: $R_{ij} \cup (R_{ik} \circ R_{kk}^* \circ R_{kj})$
Remove state $q_k$ and all its incoming and outgoing transitions

Step 3: Extract the Result

After eliminating all states except $q_{\text{init}}$ and $q_{\text{final}}$, the regular expression on the transition from $q_{\text{init}}$ to $q_{\text{final}}$ represents the language of the original NFA.

Formal Definition

We can define this conversion formally as:

\[ \text{nfa2regex}(M) = R_{q_{\text{init}},q_{\text{final}}}^{Q} \]

Where $R_{i,j}^{S}$ represents the regular expression for paths from state $i$ to state $j$ that only pass through states in set $S$ as intermediate states, defined recursively as:

\[ R_{i,j}^{\emptyset} = \begin{cases} \epsilon \cup a_1 \cup a_2 \cup \ldots \cup a_n & \text{if } i = j \text{ and there are direct transitions labeled } a_1, a_2, \ldots, a_n \text{ from } i \text{ to } j \\ \epsilon & \text{if } i = j \text{ and there are no direct transitions from } i \text{ to } j \\ a_1 \cup a_2 \cup \ldots \cup a_n & \text{if } i \neq j \text{ and there are direct transitions labeled } a_1, a_2, \ldots, a_n \text{ from } i \text{ to } j \\ \emptyset & \text{if } i \neq j \text{ and there are no direct transitions from } i \text{ to } j \end{cases} \]

\[ R_{i,j}^{S \cup \{k\}} = R_{i,j}^{S} \cup (R_{i,k}^{S} \circ (R_{k,k}^{S})^* \circ R_{k,j}^{S}) \]

This recursive definition captures the state elimination process, where we consider paths that may pass through state $k$ in addition to paths that don’t.

What does $R_{i,j}^S$ describe at each step? The allowed-intermediate invariant says that it describes exactly the labels of paths from $i$ to $j$ whose intermediate states all belong to $S$.

For $S=\emptyset$, an eligible path has no intermediate state. It is thus either a direct transition from $i$ to $j$ or, when $i=j$, the length-zero path labeled $\epsilon$. The four base clauses list exactly these possibilities, so the invariant holds initially.

For the inductive step, fix a state $k\notin S$ and an arbitrary eligible path from $i$ to $j$ whose intermediate states lie in $S\cup\{k\}$. There are two cases. If the path never visits $k$, its label belongs to $R_{i,j}^S$. If it visits $k$, divide it at its first and last visits to $k$. The first portion has a label in $R_{i,k}^S$, the middle consists of zero or more loops with labels in $R_{k,k}^S$, and the final portion has a label in $R_{k,j}^S$. Its full label thus belongs to

\[R_{i,k}^S\circ(R_{k,k}^S)^*\circ R_{k,j}^S.\]

For instance, consider the path

\[i\xrightarrow{a}k\xrightarrow{b}k\xrightarrow{b}k\xrightarrow{c}j.\]

Its first visit to $k$ follows the entry path labeled $a$, its two returns to $k$ contribute the loop label $bb$, and its final departure contributes $c$. The complete label abbc is thus in $a\circ b^*\circ c$. More generally, a path that visits $k$ repeatedly has one entry segment, zero or more $k$-to-$k$ segments, and one exit segment; this is exactly the decomposition expressed by the starred middle term.

This shows that every eligible path is included by the recurrence. Now check the other direction. Each string in the first union branch labels a path that avoids $k$. Each string in the second branch concatenates a path into $k$, zero or more loops at $k$, and a path out of $k$. All intermediate states in the combined path lie in $S\cup\{k\}$. So the recurrence adds no ineligible string, and the invariant is preserved in both directions.

After all original states have been allowed as intermediates, every path from the new initial state to the new final state is represented. Those paths correspond exactly to the accepting paths of the original NFA, because the two new boundary transitions are labeled $\epsilon$. The final regular expression $\text{nfa2regex}(M)$ thus recognizes exactly $\mathbb{L}(M)$.

--- title: Translating Regular Expressions to NFAs jupyter: python3 --- We've seen that NFAs and DFAs are weakly equivalent: they both generate exactly the same languages. How do they relate to regular expressions? We'll answer this question in both directions. First, we'll turn any regular expression into an NFA. Then we'll turn any NFA into a regular expression. Since DFAs and NFAs are already known to be equivalent, the two constructions will show that all three formalisms generate exactly the regular languages. The target in the first direction is $\mathbb{L}(G)=\mathbb{L}(\rho)$ for the machine $G$ constructed from $\rho$. The target in the reverse direction is $\mathbb{L}(\rho)=\mathbb{L}(G)$ for the expression constructed from $G$. ## Translating Regular Expressions to NFAs Given a regular expression $\rho$ on alphabet $\Sigma$, we can construct an NFA $G_\rho = \langle Q_\rho, \Sigma, \delta_\rho, q_0^\rho, F_\rho \rangle$ that recognizes exactly the language $\mathbb{L}(\rho) = \text{eval}(\rho)$. We'll build this conversion recursively, following the structure of regular expressions: ## Base Cases Where for each case: 1. For $\rho = \emptyset$ (the empty language): - $Q_\rho = \{q_0, q_1\}$ - $\delta_\rho = \emptyset$ (no transitions) - $q_0^\rho = q_0$ - $F_\rho = \emptyset$ (no final states) 2. For $\rho = \epsilon$ (the empty string): - $Q_\rho = \{q_0\}$ - $\delta_\rho = \emptyset$ (no transitions) - $q_0^\rho = q_0$ - $F_\rho = \{q_0\}$ 3. For $\rho = a$ where $a \in \Sigma$ (a single symbol): - $Q_\rho = \{q_0, q_1\}$ - $\delta_\rho(q_0, a) = \{q_1\}$ - $q_0^\rho = q_0$ - $F_\rho = \{q_1\}$ ## Recursive Cases For the recursive cases, we'll use the operations we've already defined for NFAs: 1. For $\rho = (\rho_1 \cup \rho_2)$ (union): - Construct $G_{\rho_1}$ and $G_{\rho_2}$ recursively - $G_\rho = \text{union}(G_{\rho_1}, G_{\rho_2})$ 2. For $\rho = (\rho_1 \circ \rho_2)$ (concatenation): - Construct $G_{\rho_1}$ and $G_{\rho_2}$ recursively - $G_\rho = \text{concatenate}(G_{\rho_1}, G_{\rho_2})$ 3. For $\rho = \rho_1^*$ (Kleene star): - Construct $G_{\rho_1}$ recursively - $G_\rho = \text{kleene}(G_{\rho_1})$ Let's implement this conversion algorithm: $$ \text{regex2nfa}(\rho) = \begin{cases} \langle \{q_0, q_1\}, \Sigma, \emptyset, q_0, \emptyset \rangle & \text{if } \rho = \emptyset \\ \langle \{q_0\}, \Sigma, \emptyset, q_0, \{q_0\} \rangle & \text{if } \rho = \epsilon \\ \langle \{q_0, q_1\}, \Sigma, \{(q_0, a) \mapsto \{q_1\}\}, q_0, \{q_1\} \rangle & \text{if } \rho = a \in \Sigma \\ \text{union}(\text{regex2nfa}(\rho_1), \text{regex2nfa}(\rho_2)) & \text{if } \rho = (\rho_1 \cup \rho_2) \\ \text{concatenate}(\text{regex2nfa}(\rho_1), \text{regex2nfa}(\rho_2)) & \text{if } \rho = (\rho_1 \circ \rho_2) \\ \text{kleene}(\text{regex2nfa}(\rho_1)) & \text{if } \rho = \rho_1^* \end{cases} $$ Why should this recursive conversion preserve the language? The claim we need is $$\mathbb{L}(\operatorname{regex2nfa}(\rho))=\operatorname{eval}(\rho)$$ by structural induction on $\rho$. There are three base cases. The machine for $\emptyset$ has no final state, so it accepts no string. The machine for $\epsilon$ begins in its only final state and has no transitions, so it accepts exactly the empty string. And the machine for $a\in\Sigma$ has one $a$-transition from its initial state to its only final state, so it accepts exactly $\{a\}$. Each machine thus agrees with the corresponding evaluation clause. For the recursive cases, assume that the machines constructed for the immediate subexpressions recognize exactly their evaluated languages. If $\rho=(\rho_1\cup\rho_2)$, the union construction recognizes $$\mathbb{L}(G_{\rho_1})\cup\mathbb{L}(G_{\rho_2}) =\operatorname{eval}(\rho_1)\cup\operatorname{eval}(\rho_2) =\operatorname{eval}(\rho).$$ The concatenation case replaces union in this equality with language concatenation, and the star case replaces it with Kleene closure. The correctness proofs for the three automaton operations establish those first equalities. So each constructor preserves the induction hypothesis. Every regular expression is built from a base case by finitely many constructors, which gives the desired equality for every $\rho$. Consider $\rho=a\circ b^*$. The recursive calls build the one-transition machine for $a$ and the one-transition machine for $b$, apply the star construction to the latter, and concatenate the results. An accepting path must first consume one `a`; it may then take the restarted `b` path any finite number of times. The resulting language is $\{ab^i\mid i\geq0\}$, exactly $\operatorname{eval}(a\circ b^*)$. ## Translating NFAs to Regular Expressions We've seen how to convert a regular expression to an NFA. Now let's explore the reverse: converting an NFA to an equivalent regular expression. Given an NFA $G = \langle Q, \Sigma, \delta, q_0, F \rangle$, we can construct a regular expression $\rho$ such that $\mathbb{L}(G) = \mathbb{L}(\rho)$. ### The State Elimination Method The most common approach for this conversion is the **state elimination method**: 1. Transform the NFA into a generalized NFA (GNFA) with a single initial state, a single final state, and transitions labeled with regular expressions 2. Systematically eliminate states one by one, updating the transition labels accordingly 3. When only the initial and final states remain, the regular expression on the transition between them represents the language of the original NFA #### Step 1: Construct the GNFA First, we transform the NFA into a GNFA: - Add a new initial state $q_{\text{init}}$ with an ε-transition to the original initial state $q_0$ - Add a new final state $q_{\text{final}}$ and add ε-transitions from all original final states to $q_{\text{final}}$ - Make $q_{\text{final}}$ the only final state - Label each transition with the corresponding symbol from the alphabet (or ε) #### Step 2: Eliminate States For each state $q_k$ (except $q_{\text{init}}$ and $q_{\text{final}}$): 1. For each pair of states $q_i$ and $q_j$ such that there are transitions from $q_i$ to $q_k$ and from $q_k$ to $q_j$: - Let $R_{ik}$ be the regular expression on the transition from $q_i$ to $q_k$ - Let $R_{kk}$ be the regular expression on the self-loop at $q_k$ (if any, otherwise $\emptyset$) - Let $R_{kj}$ be the regular expression on the transition from $q_k$ to $q_j$ - Create or update the transition from $q_i$ to $q_j$ with the regular expression: $R_{ij} \cup (R_{ik} \circ R_{kk}^* \circ R_{kj})$ 2. Remove state $q_k$ and all its incoming and outgoing transitions #### Step 3: Extract the Result After eliminating all states except $q_{\text{init}}$ and $q_{\text{final}}$, the regular expression on the transition from $q_{\text{init}}$ to $q_{\text{final}}$ represents the language of the original NFA. ### Formal Definition We can define this conversion formally as: $$ \text{nfa2regex}(M) = R_{q_{\text{init}},q_{\text{final}}}^{Q} $$ Where $R_{i,j}^{S}$ represents the regular expression for paths from state $i$ to state $j$ that only pass through states in set $S$ as intermediate states, defined recursively as: $$ R_{i,j}^{\emptyset} = \begin{cases} \epsilon \cup a_1 \cup a_2 \cup \ldots \cup a_n & \text{if } i = j \text{ and there are direct transitions labeled } a_1, a_2, \ldots, a_n \text{ from } i \text{ to } j \\ \epsilon & \text{if } i = j \text{ and there are no direct transitions from } i \text{ to } j \\ a_1 \cup a_2 \cup \ldots \cup a_n & \text{if } i \neq j \text{ and there are direct transitions labeled } a_1, a_2, \ldots, a_n \text{ from } i \text{ to } j \\ \emptyset & \text{if } i \neq j \text{ and there are no direct transitions from } i \text{ to } j \end{cases} $$ $$ R_{i,j}^{S \cup \{k\}} = R_{i,j}^{S} \cup (R_{i,k}^{S} \circ (R_{k,k}^{S})^* \circ R_{k,j}^{S}) $$ This recursive definition captures the state elimination process, where we consider paths that may pass through state $k$ in addition to paths that don't. What does $R_{i,j}^S$ describe at each step? The **allowed-intermediate invariant** says that it describes exactly the labels of paths from $i$ to $j$ whose intermediate states all belong to $S$. For $S=\emptyset$, an eligible path has no intermediate state. It is thus either a direct transition from $i$ to $j$ or, when $i=j$, the length-zero path labeled $\epsilon$. The four base clauses list exactly these possibilities, so the invariant holds initially. For the inductive step, fix a state $k\notin S$ and an arbitrary eligible path from $i$ to $j$ whose intermediate states lie in $S\cup\{k\}$. There are two cases. If the path never visits $k$, its label belongs to $R_{i,j}^S$. If it visits $k$, divide it at its first and last visits to $k$. The first portion has a label in $R_{i,k}^S$, the middle consists of zero or more loops with labels in $R_{k,k}^S$, and the final portion has a label in $R_{k,j}^S$. Its full label thus belongs to $$R_{i,k}^S\circ(R_{k,k}^S)^*\circ R_{k,j}^S.$$ For instance, consider the path $$i\xrightarrow{a}k\xrightarrow{b}k\xrightarrow{b}k\xrightarrow{c}j.$$ Its first visit to $k$ follows the entry path labeled $a$, its two returns to $k$ contribute the loop label $bb$, and its final departure contributes $c$. The complete label `abbc` is thus in $a\circ b^*\circ c$. More generally, a path that visits $k$ repeatedly has one entry segment, zero or more $k$-to-$k$ segments, and one exit segment; this is exactly the decomposition expressed by the starred middle term. This shows that every eligible path is included by the recurrence. Now check the other direction. Each string in the first union branch labels a path that avoids $k$. Each string in the second branch concatenates a path into $k$, zero or more loops at $k$, and a path out of $k$. All intermediate states in the combined path lie in $S\cup\{k\}$. So the recurrence adds no ineligible string, and the invariant is preserved in both directions. After all original states have been allowed as intermediates, every path from the new initial state to the new final state is represented. Those paths correspond exactly to the accepting paths of the original NFA, because the two new boundary transitions are labeled $\epsilon$. The final regular expression $\text{nfa2regex}(M)$ thus recognizes exactly $\mathbb{L}(M)$.