---
title: "NFA for (ab*a ∪ b*aa)"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:nfa-ab-star-a-union"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/nfa-ab-star-a-union
site: BCT Engineering
---

# NFA for (ab*a ∪ b*aa)

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2073 Shrawan
- Video: [Designing an NFA for a Given Regular Expression by Bharathi Patnala](https://www.youtube.com/watch?v=mLRWDWmYsr4) — Bharathi Patnala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/nfa-ab-star-a-union
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Construct an NFA for (ab*a ∪ b*aa).

## Short answer

Use union construction with a new start state and ε-moves to two branches. Branch 1: p0-a->p1, p1 loops on b, p1-a->p2 (final). Branch 2: r0 loops on b, r0-a->r1, r1-a->r2 (final). Start s-ε->p0, s-ε->r0.

## Answer

**Language.** L = L(ab*a) ∪ L(b*aa). We build an NFA for each part and join them by a new start state with ε-moves (the union construction).

M = ({s, p0, p1, p2, r0, r1, r2}, {a, b}, δ, s, {p2, r2})

- Branch 1, ab*a: p0 –a→ p1; p1 loops on b; p1 –a→ p2 (final).
- Branch 2, b*aa: r0 loops on b; r0 –a→ r1; r1 –a→ r2 (final).
- s –ε→ p0 and s –ε→ r0.

| State | a | b | ε |
|---|---|---|---|
| → s | – | – | p0, r0 |
| p0 | p1 | – | – |
| p1 | p2 | p1 | – |
| *p2 | – | – | – |
| r0 | r1 | r0 | – |
| r1 | r2 | – | – |
| *r2 | – | – | – |

```text
              ε     a      a
        ┌──► p0 ──► p1 ──► ((p2))
        │             ↺b
 ──► s ─┤
        │     b↺   a      a
        └──► r0 ──► r1 ──► ((r2))
              ε
```

#### Test
- "abba" ∈ ab*a: s → p0 –a→ p1 –b→ p1 –b→ p1 –a→ p2. Accepted.
- "baa" ∈ b*aa: s → r0 –b→ r0 –a→ r1 –a→ r2. Accepted.
- "ab": p0 → p1, which is not final, and the other branch dies. Rejected.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How is an NFA for the union of two languages built from the NFAs of each?
   A. Connect the final state of the first to the start of the second
   B. Make all states final
   C. Add a new start state with ε-moves to both original start states
   D. Merge the two start states into one without a new state
   Answer: C. The union construction uses a new start state s with ε-transitions to the start states of both machines. (Key point: Union construction)

2. In the branch for ab*a, which state has a self-loop and on what symbol?
   A. p0 on a
   B. p2 on b
   C. p1 on a
   D. p1 on b
   Answer: D. After the first a, the machine stays in p1 reading any number of b's, then a moves to final p2. (Key point: Branch for ab*a)

3. Which strings does the second branch (r0, r1, r2) accept?
   A. b*aa: any number of b's followed by exactly two a's
   B. a*bb
   C. aab*
   D. b*a
   Answer: A. r0 loops on b, then a goes to r1 and another a goes to final r2. (Key point: Branch for b*aa)

4. Why is the string ab rejected?
   A. The first symbol a is not allowed
   B. Branch 1 ends in p1 which is not final, and branch 2 dies on b after a
   C. Because b is not in the alphabet
   D. Because both branches reach a final state
   Answer: B. In branch 1 the run ends in non-final p1; in branch 2, r1 has no move on b. (Key point: Rejection of ab)

## Related in Theory of Computation

- [Every RE has NFA; ε-NFA for bb(a∪b)*ab](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-to-nfa-bb-aub-ab) — Theory of Computation, chapter 2

## 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×
- [NFA and DFA from grammar with A, B rules](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-with-a-b-productions) — Discrete Structure, chapter 2, asked 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
- [NFA and DFA from grammar σ→bσ|aC](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-bsigma-ac) — Discrete Structure, chapter 2, asked 4×