---
title: "NFA and DFA from grammar with A, B rules"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:grammar-nfa-dfa-with-a-b-productions"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/grammar-nfa-dfa-with-a-b-productions
site: BCT Engineering
---

# NFA and DFA from grammar with A, B rules

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2070 Magh, 4+4 marks
- Video: [Regular Grammar RG to DFA](https://www.youtube.com/watch?v=oQvjgb0EHvw) — Ekeeda
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/grammar-nfa-dfa-with-a-b-productions
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

Consider the regular grammar G = (N, T, P, σ) where N = Set of Non-Terminals = {σ, A, B}, T = Set of Terminals = {a, b} with productions σ→a, σ→bB, A→bA, A→aB, A→b, A→a, B→b and starting symbol σ. Construct a Non-Deterministic Finite State Automata equivalent to the above given regular grammar and convert this into equivalent Deterministic Finite State Automata.

## Short answer

From σ, NFA: σ –a→ F, σ –b→ B; B –b→ F; F final (A is unreachable). Subset construction: {σ} –a→ {F}, –b→ {B}; {B} –b→ {F}. DFA accepting {a, bb}. Missing transitions go to a dead state.

## Answer

Grammar: σ → a | bB; A → bA | aB | b | a; B → b. Start symbol σ.

#### Part 1: NFA
- σ → a: σ –a→ F (F is a new final state).
- σ → bB: σ –b→ B.
- A → bA: A –b→ A; A → aB: A –a→ B; A → b: A –b→ F; A → a: A –a→ F.
- B → b: B –b→ F.

NFA M = ({σ, A, B, F}, {a, b}, δ, σ, {F}):

| State | a | b |
|---|---|---|
| → σ | {F} | {B} |
| A | {B, F} | {A, F} |
| B | ∅ | {F} |
| *F | ∅ | ∅ |

```text
              a
       ┌──────────────→ (( F ))
 ──→ ( σ )                  ↑
       └──b──→ ( B ) ───b──┘
```

The state A cannot be reached from the start symbol σ (no rule of σ or B leads to A), so it is a useless state and does not affect the language. It is shown in the table for completeness.

#### Part 2: DFA by subset construction (from {σ})
| DFA state | a | b |
|---|---|---|
| → {σ} | {F} | {B} |
| {B} | ∅ | {F} |
| *{F} | ∅ | ∅ |
| ∅ (dead) | ∅ | ∅ |

Final state: {F}. Rename: S = {σ}, B' = {B}, R = {F}, D = ∅.

```text
 ──→ ( S ) ──a──────────────→ (( R ))
       │                         ↑
       b                         b
       ↓                         │
     ( B' ) ────────────────────┘
```
Missing moves (B' on a, R on a and b) go to the dead state D.

The DFA accepts L = {a, bb}. I checked this by program on all strings up to length 4.

## Check yourself

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

1. The reachable part of the grammar σ→a | bB, B→b generates which language?
   A. {a, b}
   B. {a, bb}
   C. {a, bb, bbb}
   D. {ab, bb}
   Answer: B. σ→a gives a; σ→bB→bb gives bb. (Key point: Language of grammar)

2. Why does state A not affect the language?
   A. It has no outgoing transitions
   B. It is the only final state
   C. It cannot be reached from the start symbol σ
   D. It has a loop on b
   Answer: C. No rule of σ or B leads to A, so it never takes part in a derivation from σ. (Key point: Useless state A)

3. How is σ→a converted into NFA moves?
   A. σ –a→ F, where F is a new final state
   B. σ –a→ σ
   C. σ –a→ B
   D. σ –ε→ F
   Answer: A. A production with only a terminal on the right ends in the accepting state F. (Key point: Terminal-only production)

4. In the DFA from subset construction, what is the final state?
   A. {σ}
   B. {F}
   C. {B}
   D. ∅
   Answer: B. Only the subset containing the NFA final state F is accepting. (Key point: DFA final state)

## Close variants set in other exams

- [NFA and DFA from grammar σ→aA|bB](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-aa-bb) — Discrete Structure, chapter 2, asked 2×

## Related in Discrete Structure

- [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×

## Related in other subjects

- [Every RE has NFA; ε-NFA for bb(a∪b)*ab](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-to-nfa-bb-aub-ab) — Theory of Computation, chapter 2
- [Convert ε-NFA (q0..q4) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-epsilon-q4) — Theory of Computation, chapter 2, asked 2×
- [Convert NFA (q0..q4, 0/1) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-five-states) — Theory of Computation, chapter 2, asked 2×