FA → regex: state elimination and Arden’s theorem

1. Thompson states for (a+b)*?
   Stuck? Peek at 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.

   Read lesson 2.2.1

2. Is (r+s)* = r*(sr*)*?
   Stuck? Peek at 2.1.2 Writing regexes, identities and equivalence

   • ∅ + r = r; ∅r = ∅; εr = r; ∅* = ε* = ε; (r*)* = r*; r*r* = r*; ε + rr* = r*; (rs)*r = r(sr)*.
   • (r+s)* = (r*s*)* = (r*+s*)* = r*(sr*)* = (r*s)*r*.
   • ≠: (r+s)* vs r*+s* vs r*s*; (rs)* vs r*s*.
   • No “aa”: (b+ab)*(ε+a). At most one a: b*(ε+a)b*. Even #0: 1*(01*01*)*.
   • Equality: compare shortest strings; counterexample kills; identities or minimal DFAs prove.

   Read lesson 2.1.2

3. What does the ends-with-01 DFA’s state q1 mean?
   Stuck? Peek at 1.1.2 Extended transition function and regular languages

   • δ̂(q, ε) = q; δ̂(q, wa) = δ(δ̂(q, w), a); δ̂(q, xy) = δ̂(δ̂(q, x), y).
   • L(M) = { w : δ̂(q₀, w) ∈ F }. Regular ⇔ accepted by some DFA. All finite languages are regular.
   • From the graph: empty ⇔ no reachable final; Σ* ⇔ all reachable states final; infinite ⇔ cycle on a path start→final.
   • Prove correctness with state meanings + induction on |w|.

   Read lesson 1.1.2

A colleague hands you a 4-state DFA and asks: “what does it accept, as a pattern I can paste into grep?”. You need to turn arrows back into a formula. Two methods exist: state elimination (rip states out one by one, writing regexes on the arrows) and Arden’s theorem (solve equations like algebra). GATE asks for the regex of a given small DFA almost every few years.

A state k has a self-loop labelled c, an arrow in from p labelled a, and an arrow out to q labelled b. If you delete k, what label should the new direct arrow p → q get?

Prediction check

ac*b: go in with a, loop any number of times with c, leave with b. That is the whole state-elimination rule.

Generalized NFA

Allow arrows labelled by whole regexes. Prepare the automaton: add a new start state S with ε to the old start, and a new single accept state E with ε from every old accepting state. Multiple arrows between the same pair are merged with +.

State elimination

Eliminate all old states one by one. The label left on S → E is the regex. Different elimination orders give different-looking but equivalent regexes.

Arden’s theorem

Use it on a DFA by writing one equation per state for “strings that reach this state” (incoming form): q = Σ (p · a) over arrows p ─a→ q, plus ε for the start state. Substitute and apply Arden until each state has a regex; then add up the accepting states.

The condition ε ∉ L(P) matters: with P = ε, R = Q + R has many solutions.

The mirror form R = Q + PR gives R = P*Q.

Worked Arden example (ends with 01)

Arrows: q0 ─1→ q0, q0 ─0→ q1, q1 ─0→ q1, q1 ─1→ q2, q2 ─0→ q1, q2 ─1→ q0.

q0 = ε + q0·1 + q2·1   q1 = q0·0 + q1·0 + q2·0   q2 = q1·1

Substitute q2: q1 = q0·0 + q1·0 + q1·10 = q0·0 + q1(0 + 10) ⇒ (Arden) q1 = q0·0(0 + 10)*.
q0 = ε + q0·1 + q1·11 = ε + q0·1 + q0·0(0+10)*11 = ε + q0(1 + 0(0+10)*11) ⇒ q0 = (1 + 0(0+10)*11)*.
Accepting q2 = q1·1 = (1 + 0(0+10)*11)* 0(0+10)* 1. It is equivalent to (0+1)*01 — longer-looking, same language.

Putting it together

• Eliminate a state with R₄ + R₁R₂*R₃; what is left on S → E is the regex.
• Arden: R = Q + RP with ε ∉ P gives R = QP*.
• Different orders give different-looking but equal regexes.

eliminating k:        R₁         R₃                      R₄ + R₁ R₂* R₃
                 p ───────► k ───────► q        ⇒      p ─────────────────► q
                            ⟲ R₂
             (old direct p→q label R₄)

example: DFA for "odd number of a's" over {a}, plus b loops
   S ─ε→ E0 ⇄ O ─ε→ E      E0 ─a→ O, O ─a→ E0, both have b self-loops
 eliminate E0:  S→O : ε b* a     O→O : b + a b* a
 eliminate O :  S→E : b*a (b + ab*a)*        ← odd number of a's

Kleene’s theorem is complete: regex ⇔ ε-NFA ⇔ NFA ⇔ DFA. A fifth description of regular languages is still missing — rules that generate strings step by step. They are called grammars, and they lead straight into Phase 3.

1. MCQ

   Arden’s theorem solves R = Q + RP (ε ∉ L(P)) as:

   1. R = PQ*
   2. R = QP*
   3. R = P*Q
   4. R = Q*P
2. MCQ

   Eliminating state k with p →(a) k, k ⟲ (b), k →(c) q and no direct p → q gives:

   1. ab*c
   2. a + b* + c
   3. (abc)*
   4. ab*c + ∅*
3. MSQ

   Which regexes describe the GATE example (even number of a’s)?

   1. (b + ab*a)*
   2. b*(ab*ab*)*
   3. (b*ab*a)*b*
   4. (a + b)*
4. MCQ

   Why does Arden require ε ∉ L(P)?

   1. otherwise the solution is not unique
   2. otherwise QP* is empty
   3. P must be a symbol
   4. Q must contain ε

• generalized NFA (regex-labelled arrows)
• state elimination
• Arden’s theorem
• state equations (incoming form)

1. Arden’s theorem?
   Reveal answer

   If ε ∉ L(P), R = Q + RP has the unique solution R = QP*.
2. State-elimination update rule?
   Reveal answer

   R(p,q) ← R(p,q) + R(p,k) R(k,k)* R(k,q)
3. Regex for even number of a’s over {a,b}?
   Reveal answer

   (b + ab*a)* (or b*(ab*ab*)*)