- 2073 Shrawan
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.
Construct an NFA for (aba ∪ baa).
Language. L = L(aba) ∪ L(baa). 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 | – | – | – |
ε 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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Every RE has NFA; ε-NFA for bb(a∪b)*ab · Theory of Computation, chapter 2
- NFA and DFA from grammar σ→aA|bB · Discrete Structure, chapter 2 · asked 2×
- NFA and DFA from grammar with A, B rules · Discrete Structure, chapter 2 · asked 2×
- Language of grammar; grammar for strings not ending in ab · Discrete Structure, chapter 2
- NFA and DFA from grammar σ→bσ|aC · Discrete Structure, chapter 2 · asked 4×