L2.2 · Conversions

Chapter recap

Thompson converts any regex into an ε-NFA with one start and one accept state, using 2 new states per symbol, union and star. State elimination converts any automaton back: add S and E, then remove states using R₄ + R₁R₂*R₃. Arden’s theorem (R = Q + RP, ε ∉ P ⇒ R = QP*) solves state equations. Together: regex ⇔ ε-NFA ⇔ NFA ⇔ DFA (Kleene’s theorem).

Merged rule card

From 2.2.1 Regex → ε-NFA (Thompson construction)

Invariant: one start (no in-moves), one accept (no out-moves).
∅, ε, a: 2 states. r+s: +2 states, 4 ε. rs: ε from accept(r) to start(s). r*: +2 states, 4 ε (enter, skip, loop back, exit).
States ≤ 2 × (symbols + operators). Regex → ε-NFA → DFA proves regex ⇒ regular.

From 2.2.2 FA → regex: state elimination and Arden’s theorem

Prep: new start S (ε to old start), new accept E (ε from old accepting). Merge parallel arrows with +.
Eliminate k: R(p,q) ← R₄ + R₁R₂*R₃ (no loop ⇒ R₂* = ε).
Arden: R = Q + RP, ε ∉ P ⇒ R = QP*. Mirror: R = Q + PR ⇒ R = P*Q.
Incoming equations: q = Σ p·a (+ ε for start); answer = sum over accepting states.

Practice questions

NAT
Strict Thompson states for ab?
Write your answer before opening the key.
MCQ
Solution of R = a + Rb (Arden) is:
1. ab*
2. b*a
3. (ab)*
4. a*b
MCQ
DFA: A (start) ─0→ B, A ─1→ A, B ─0→ B, B ─1→ A; F = {B}. Regex?
1. (0 + 1)*0
2. (0 + 1)*1
3. 0(0 + 1)*
4. 1*0
MSQ
Which conversions always exist?
1. regex → ε-NFA
2. DFA → regex
3. NFA → DFA
4. ε-NFA → NFA with same states
NAT
Strict Thompson states for (a + b)*b?
Write your answer before opening the key.
MCQ
q = ε + q·0 + q·1 (start, accepting) gives:
1. (0 + 1)*
2. 0*1*
3. (01)*
4. ε
MCQ
In state elimination, R₂ (the self-loop on k) is absent. We use:
1. R₂* = ∅
2. R₂* = ε
3. skip the update
4. R₂ = ε, R₂* = ∅
MSQ
Which regexes are equal to the result (1 + 0(0+10)*11)*0(0+10)*1 from the Arden example?
1. (0 + 1)*01
2. (0 + 1)*0 1
3. 0*1
4. (1 + 0)*01

Answer key

Reveal answers when you’re ready

4 — 2 + 2, concatenation adds none.
A — Q = a, P = b.
- B: Mirror form.
- C: Wrong.
- D: Wrong.
A — B means “last symbol 0”.
- B: Strings ending in 1 end in A, which is not accepting.
- C: Starts with 0.
- D: Too few strings.
ABCD — All are standard constructions.
10 — 8 for (a+b)*, +2 for b.
A — q = ε + q(0+1) ⇒ (0+1)*.
- B: Too restrictive.
- C: Too restrictive.
- D: Too small.
B — ∅* = ε.
- A: ∅* = ε, not ∅.
- C: The bypass is still needed.
- D: ε* = ε.
ABD — All are “ends with 01”.
- C: Misses 1101.