--- title: "Every RE has NFA; ε-NFA for bb(a∪b)*ab" subject: "Theory of Computation" chapter: 2 key: "semester_3/theory_of_computation:re-to-nfa-bb-aub-ab" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/re-to-nfa-bb-aub-ab site: BCT Engineering --- # Every RE has NFA; ε-NFA for bb(a∪b)*ab Theory of Computation · Chapter 2: Finite Automata - Asked in: 2070 Chaitra - Video: [Theory of Computation: Conversion of RE to Epsilon-NFA](https://www.youtube.com/watch?v=dyZptpZLwIE) — Anita R - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/re-to-nfa-bb-aub-ab - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2 ## Question Show that for any regular expression R, there is an NFA that accepts the same language represented by R. Construct an ε-NFA for the regular expression bb(a∪b)*ab. ## Short answer Thompson's construction proves every RE has an ε-NFA. For bb(a∪b)*ab: states q0..q12; q0–q2 read 'bb', then ε to a loop (q4–q9) implementing (a∪b)* with ε-returns, then ε to q10–q12 reading 'ab'. Final q12. Example: 'bbab' accepted. ## Answer #### Theorem For every regular expression R there is an NFA (with ε-moves) N with L(N) = L(R). **Proof (structural induction on R; Thompson's construction).** Each NFA built has one start state and one final state. **Basis** - R = ∅: two states, no transitions. - R = ε: start –ε→ final. - R = a ∈ Σ: start –a→ final. **Induction step.** Let N₁, N₂ be NFAs for R₁, R₂ (disjoint states). - R₁ ∪ R₂: new start s with ε-moves to the starts of N₁, N₂; ε-moves from their finals to a new final f. Accepts L(R₁) ∪ L(R₂). - R₁R₂: ε-move from the final of N₁ to the start of N₂. Start = start of N₁, final = final of N₂. - R₁*: new start s and final f; s –ε→ start(N₁), s –ε→ f; final(N₁) –ε→ start(N₁), final(N₁) –ε→ f. By induction every regular expression has an NFA. ∎ #### NFA for bb(a ∪ b)*ab Build the parts: bb, (a ∪ b)*, ab and concatenate. States q0–q12, start q0, final q12. | State | a | b | ε | |---|---|---|---| | → q0 | – | q1 | – | | q1 | – | q2 | – | | q2 | – | – | q3 | | q3 | – | – | q4, q10 | | q4 | – | – | q5, q7 | | q5 | q6 | – | – | | q6 | – | – | q9 | | q7 | – | q8 | – | | q8 | – | – | q9 | | q9 | – | – | q4, q10 | | q10 | q11 | – | – | | q11 | – | q12 | – | | *q12 | – | – | – | ```text →q0 -b→ q1 -b→ q2 -ε→ q3 -ε→ q10 -a→ q11 -b→ ((q12)) │ ▲ ε │ ε ▼ │ q4 │ (star of a|b) ├ε→ q5 -a→ q6 -ε┐ └ε→ q7 -b→ q8 -ε┴→ q9 q9 -ε→ q4 and q9 -ε→ q10 ``` - q0–q2 read "bb". - q3 to q10 is the star of the union: q3 can skip directly to q10 (zero repetitions), or enter q4, pick a (q5→q6) or b (q7→q8), reach q9, then loop back to q4 or leave to q10. - q10 –a→ q11 –b→ q12 reads the final "ab". **Check.** "bbab": q0 b q1 b q2 ε q3 ε q10 a q11 b q12 accepted. "bbaab": the star consumes the first a, then "ab" matches. "bbb" is rejected. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What property does each built NFA have? A. Exactly two transitions B. No ε-moves C. A dead state D. One start state and one final state Answer: D. This enables composition. (Key point: Thompson construction) 2. How is R1 ∪ R2 built? A. Add a loop on the final B. New start with ε to both starts; ε from both finals to new final C. Merge both starts and finals D. ε from final of N1 to start of N2 Answer: B. Union adds a new start and final. (Key point: Union) 3. How is R1* built? A. Only ε from final to start B. Only ε from s to f C. A self-loop on the start D. New s and f with ε s→start, s→f, final→start, final→f Answer: D. The ε s→f allows zero repetitions. (Key point: Star) 4. How is R1R2 built? A. ε from start of N1 to start of N2 B. ε from final of N1 to start of N2 C. Merge final of N2 into start of N1 D. New final state with ε from both starts Answer: B. Start is N1's start and final is N2's. (Key point: Concatenation) ## Related in Theory of Computation - [Regular expression with substring 0101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-substring-0101) — Theory of Computation, chapter 2 - [NFA for (ab*a ∪ b*aa)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-ab-star-a-union) — Theory of Computation, chapter 2 - [Regular grammar to RE and FA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-grammar-to-re-fa) — Theory of Computation, chapter 2 - [Recursive iff language and complement are RE](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-iff-complement-re) — Theory of Computation, chapter 4, asked 2× - [RE: no more than 3 a's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-at-most-3-as) — Theory of Computation, chapter 2 - [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5× ## Related in other subjects - [NFA and DFA from grammar σ→aA|bB](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-aa-bb) — Discrete Structure, chapter 2, asked 2× - [Regular expression and FSA: at least three b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-at-least-three-b) — Discrete Structure, chapter 2 - [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2 - [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2