Thompson's Construction: Regex to NFA-ε

The Algorithm: Building NFAs from Regular Expressions

Regular expressions are defined recursively. They have simple base cases (ε, ∅, and single symbols like a) and recursive cases that build larger expressions from smaller ones using operators (union, concatenation, and star).

Thompson's construction is an elegant algorithm that mirrors this recursive structure. We will:

1. Define simple "atomic" NFAs for the base cases.
2. Define rules for combining these atomic NFAs to handle the recursive cases.

A key feature of the NFAs produced by this algorithm is that they are highly composable: each NFA will have exactly one start state and exactly one final state, and the final state will have no outgoing transitions. This modularity is what makes the algorithm work so well.

The Building Blocks: Thompson's Construction Rules

Let's dive into the specific rules for the construction. We'll start with the base cases and then move to the operations that combine them.

To reinforce this, let's watch a video that walks through these same constructions. The presenter links these constructions back to the closure properties we discussed for regular languages, which is a powerful insight.

Let's summarize the rules you've just reviewed. For any regular expression $R$, we are building an NFA we can represent as a box with a start and final state: $\stackrel{start}{\to }\boxed{N(R)}\stackrel{final}{\to }$.

1. Base Cases:

   • For ε: A start state with an ε-transition to a final state.
     start --ε--> final
   • For a symbol a in Σ: A start state with an a-transition to a final state.
     start --a--> final
   • For ∅: A start state and a final state with no path between them.

2. Recursive Cases: (Assuming we have already constructed $N(s)$ and $N(t)$)

   • Union (s | t): Create a new start state with ε-transitions to the start states of $N(s)$ and $N(t)$. Create a new final state, and add ε-transitions from the final states of $N(s)$ and $N(t)$ to it.
   • Concatenation (st): The start state of $N(s)$ becomes the overall start state. The final state of $N(t)$ becomes the overall final state. Connect the final state of $N(s)$ to the start state of $N(t)$ with an ε-transition.
   • Kleene Star (s*): Create a new start and a new final state.
     • Add an ε-transition from the new start state to the new final state (this handles the "zero occurrences" case, i.e., the empty string).
     • Add an ε-transition from the new start state to the start state of $N(s)$.
     • Add an ε-transition from the final state of $N(s)$ to the new final state.
     • Add an ε-transition from the final state of $N(s)$ back to the start state of $N(s)$ (this allows for one or more repetitions).

A Worked Example: (a|b)*abb

Now, let's apply these rules to a more complex regular expression: (a|b)*abb. The structure of this expression is CONCAT(CONCAT(CONCAT(STAR(UNION(a, b)), a), b), b). We build the NFA from the inside out.

1. NFA for a and b: We start with the atomic NFAs for a and b.

   • N(a): (q_a_start) --a--> (q_a_final)
   • N(b): (q_b_start) --b--> (q_b_final)

2. NFA for a|b: Apply the union rule to N(a) and N(b). We create a new start state with ε-moves to q_a_start and q_b_start, and a new final state that is the target of ε-moves from q_a_final and q_b_final.

3. NFA for (a|b)*: Apply the star rule to our NFA for a|b. This involves adding another new start and final state and the four required ε-transitions for looping and bypass.

4. NFA for (a|b)*a: Apply the concatenation rule. We connect the final state of N((a|b)*) to the start state of a new NFA for a with an ε-transition.

5. NFA for (a|b)*ab and (a|b)*abb: We repeat the concatenation step twice more, first for b, and then for a final b.

The final result is a large but systematic NFA-ε that accepts exactly the language described by (a|b)*abb.

Conclusion

Today we explored Thompson's construction, a powerful and systematic algorithm for converting any regular expression into an equivalent NFA-ε. This process is not just a theoretical exercise; it's the basis for how many real-world regular expression engines are implemented. By providing a constructive proof, we have solidified one direction of a major theorem in this field.

Key Takeaways:

• Thompson's construction is a recursive algorithm that builds an NFA-ε from a regular expression.
• The algorithm defines simple NFAs for the base cases (ε, ∅, a) and provides rules for combining them to handle the recursive cases (union, concatenation, Kleene star).
• The NFAs produced are modular, each with a single start and final state, making them easy to compose into larger machines.
• This construction proves that every language describable by a regular expression is a regular language.

Preview of the Next Lesson:
We have successfully built a bridge from regular expressions to finite automata. But is the bridge a two-way street? Can we go in the other direction? In the next lesson, we will answer that question by learning the state elimination method, an algorithm for converting any DFA back into an equivalent regular expression. By proving this, we will complete the proof of Kleene's Theorem, which states that regular expressions and finite automata are equivalent in their descriptive power.