Skip to main content

Regular grammar to RE and FA

Short answer

RE: (abb + a + baa)*(aba + ε). NFA: start/final S, states A,B,P1,P2,F; S-ε→B, S-a→P1-b→A, S-b→P2-a→B; A-a→F, A-b→S; B-a→S. 'a' accepted via S-ε→B-a→S; 'aba' via S-a→P1-b→A-a→F.

Consider the regular grammar G = (V, Σ, R, S) where R = {S → abA | B | baB | ε; A → bS | a; B → aS}. [Rest of the question not clearly printed; the solution derives the equivalent regular expression and a finite automaton.]

Grammar. S → abA | B | baB | ε; A → bS | a; B → aS. (The question text is incomplete; we find the equivalent regular expression and a finite automaton.)

Regular expression (Arden's theorem)

Write each variable as an equation and substitute.

S = abA + B + baB + ε
A = bS + a
B = aS

Substitute B and A into S:

S = ab(bS + a) + aS + ba(aS) + ε
  = abbS + aba + aS + baaS + ε
  = (abb + a + baa)S + (aba + ε)

This has the form S = RS + Q with R = abb + a + baa and Q = aba + ε. By Arden's theorem for this right-linear form, S = RQ (for the left-linear form X = XR + Q it gives X = QR):

S = (abb + a + baa) (aba + ε)*

So L(G) = (abb + a + baa)*(aba + ε).

Finite automaton (NFA)

Break long right-hand sides with extra states P1, P2:

  • S → abA: S –a→ P1 –b→ A
  • S → baB: S –b→ P2 –a→ B
  • S → B: S –ε→ B
  • S → ε: S is final
  • A → bS: A –b→ S
  • A → a: A –a→ F (F is a new final state)
  • B → aS: B –a→ S

NFA: states {S, P1, P2, A, B, F}, start S, final {S, F}.

Stateabε
→ *SP1P2B
P1–A–
P2B––
AFS–
BS––
*F–––
          ┌────── a ──────┐
          ▼               │
 ──►((S)) ─ε─► (B) ─a─────┘
   │  │
   a  b───► (P2) ─a─► B
   ▼
  (P1) ─b─► (A) ─b─► S
             │
             a
             ▼
            ((F))

Check

  • "a": S –ε→ B –a→ S (final). Accepted; it matches the RE (a).
  • "aba": S –a→ P1 –b→ A –a→ F. Accepted; matches aba.
  • "abbbaa": S –a→ P1 –b→ A –b→ S –b→ P2 –a→ B –a→ S. It is abb·baa, accepted.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →