---
title: "Regular grammar to RE and FA"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:regular-grammar-to-re-fa"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/regular-grammar-to-re-fa
site: BCT Engineering
---

# Regular grammar to RE and FA

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2070 Chaitra
- Video: [Converting  Regular Grammar to Finite Automata || Procedure || 2 Examples || Construction || TOC](https://www.youtube.com/watch?v=frzs_IWiiqQ) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/regular-grammar-to-re-fa
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

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.]

## 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.

## Answer

**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.

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

Substitute B and A into S:

```text
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 = R*Q (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}.

| State | a | b | ε |
|---|---|---|---|
| → *S | P1 | P2 | B |
| P1 | – | A | – |
| P2 | B | – | – |
| A | F | S | – |
| B | S | – | – |
| *F | – | – | – |

```text
          ┌────── 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.

## Check yourself

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

1. Which theorem finds the RE from the grammar equations?
   A. Arden's theorem
   B. Rice's theorem
   C. Myhill-Nerode theorem
   D. Pumping lemma
   Answer: A. It solves S = RS + Q as S = R*Q. (Key point: Method)

2. What is the RE?
   A. (ab + ba)*
   B. (abb + a + baa)*(aba + ε)
   C. abb + a + baa + aba
   D. (abb + a + baa)(aba + ε)*
   Answer: B. Substituting A and B into S gives S = (abb + a + baa)S + aba + ε. (Key point: Result)

3. How are productions like S → abA handled in the NFA?
   A. Replaced by ε-moves
   B. Labelled with strings directly
   C. They are ignored
   D. Extra states break them into single symbol moves (S –a→ P1 –b→ A)
   Answer: D. NFA edges read one symbol. (Key point: Long productions)

4. Which states are final in the NFA?
   A. A and B
   B. Only S
   C. S and F
   D. Only F
   Answer: C. S → ε makes S final, and F ends A → a. (Key point: Final states)

## Related in Theory of Computation

- [Regular expression with substring 0101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-substring-0101) — Theory of Computation, chapter 2
- [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5×
- [Pumping lemma: aⁿb²ⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-an-b2n-not-regular) — Theory of Computation, chapter 2, asked 3×
- [Pumping lemma: aⁿbaⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-anban-not-regular) — Theory of Computation, chapter 2
- [CNF conversion (grammar with S→A|B)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acnf-conversion-s-a-b) — Theory of Computation, chapter 3
- [Compare TM with FA and PDA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-compare-fa-pda) — Theory of Computation, chapter 4

## Related in other subjects

- [Regular expression and FSA: at least three b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-at-least-three-b) — 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×
- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Find K and b for K(s+1)/(s³+bs²+3s+1)](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Arh-k-b-oscillate) — Control Systems, chapter 4