---
title: "NFA and DFA from grammar σ→aA|bB"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:grammar-nfa-dfa-sigma-aa-bb"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/grammar-nfa-dfa-sigma-aa-bb
site: BCT Engineering
---

# NFA and DFA from grammar σ→aA|bB

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2071 Bhadra, 4+4 marks
- Video: [Construct DFA from Right Linear Grammar| Regular Grammar To Finite Automata| TOC|FLAT](https://www.youtube.com/watch?v=-BkGpNNvNZQ) — CSE ACADEMY
- 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-sigma-aa-bb
- 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 σ→aA, σ→bB, A→a, B→a 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

NFA: σ –a→ A, –b→ B; A –a→ F, B –a→ F; F final. Equivalent DFA: {σ} –a→ {A}, –b→ {B}; {A} –a→ {F}; {B} –a→ {F}. Dead state for other moves. Accepts exactly {aa, ba}.

## Answer

Grammar: σ → aA | bB, A → a, B → a. Start symbol σ. The language is L = {aa, ba}.

#### Part 1: NFA
- σ → aA gives σ –a→ A; σ → bB gives σ –b→ B.
- A → a gives A –a→ F; B → a gives B –a→ F, where F is a new final state.

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

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

```text
            a            a
       ┌──────→ ( A ) ──────┐
 ──→ ( σ )                  ↓
       └──────→ ( B ) ──→ (( F ))
            b            a
```

No state of this NFA has two choices on the same symbol, so it is already deterministic apart from the missing transitions.

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

Final states: subsets containing F, i.e. {F}. Rename: S = {σ}, P = {A}, Q = {B}, R = {F}, D = ∅.

```text
 ──→ ( S ) ──a──→ ( P ) ──a──→ (( R ))
       │                          ↑
       b                          a
       ↓                          │
      ( Q ) ─────────────────────┘
```
All other moves (P on b, Q on b, and R on a or b) go to the dead state D, which loops on a and b.

The DFA accepts exactly {aa, ba} (checked 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. What language does σ→aA | bB, A→a, B→a generate?
   A. {aa, bb}
   B. {aa, ba}
   C. {a, b}
   D. {aa, ab}
   Answer: B. σ goes to aA or bB, then A or B gives a, so the strings are aa and ba. (Key point: Language of grammar)

2. Why is a new final state F added when building the NFA?
   A. Because the start symbol must be final
   B. Because every non-terminal needs two outgoing arrows
   C. Productions A→a and B→a have no non-terminal on the right, so they must lead to an accepting state
   D. Because the DFA needs a dead state
   Answer: C. A rule of the form A→a becomes A –a→ F, with F the accepting state. (Key point: New final state F)

3. Why is subset construction easy for this NFA?
   A. Because it has epsilon moves that are removed
   B. Because the start state is also final
   C. Because it has exactly one final state with loops
   D. No state has two choices on the same symbol, so each subset is a single state (plus a dead state for missing moves)
   Answer: D. Every NFA move is single-valued, so the DFA states are just the singletons plus ∅ as dead state. (Key point: NFA already deterministic)

4. Which DFA state(s) are final?
   A. Only {F}, the subset containing F
   B. {A} and {B}
   C. {σ}
   D. The dead state ∅
   Answer: A. In subset construction a subset is final if it contains an NFA final state. (Key point: DFA final states)

## Close variants set in other exams

- [NFA and DFA from grammar with A, B rules](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-with-a-b-productions) — 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×
- [Differentiate DFA and NFA](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adfa-vs-nfa-difference) — Discrete Structure, chapter 2, asked 2×

## Related in other subjects

- [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×
- [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,q1,q2) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-01-q0q2) — Theory of Computation, chapter 2