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

# NFA and DFA from grammar σ→bσ|aC

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2074 Bhadra, 3+5 marks; 2073 Magh, 4+4 marks; 2072 Asoj, 4+4 marks; 2069 Bhadra, 4+4 marks (asked 4 times)
- 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-sigma-bsigma-ac
- 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-terminal symbols = {σ, C}, T = set of terminal symbols = {a, b}, P is the set of production rules = {σ→bσ, σ→aC, C→bC, C→b} and σ being the starting symbol. Construct a non-deterministic finite state automaton equivalent to the given regular grammar. Use this non-deterministic finite state automaton to generate equivalent deterministic finite state automaton.

## Short answer

NFA: states σ, C, F; start σ, final F. Transitions: σ –a→ C, σ –b→ σ; C –b→ C, C –b→ F. Subset construction gives DFA: {σ} –a→ {C}, –b→ {σ}; {C} –b→ {C,F}; {C,F} –b→ {C,F}. Final state {C,F}. Language b*ab⁺.

## Answer

Grammar: σ → bσ | aC, C → bC | b. Start symbol σ.

The language is L = b*ab⁺ (any number of b's, then one a, then one or more b's).

#### Part 1: NFA from the grammar
Rules for converting a right-linear grammar:
- Each non-terminal becomes a state; the start symbol is the start state.
- A rule X → aY gives a transition X –a→ Y.
- A rule X → a (terminal only) gives a transition X –a→ F, where F is a new final state.

Here: σ → bσ gives σ –b→ σ; σ → aC gives σ –a→ C; C → bC gives C –b→ C; C → b gives C –b→ F.

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

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

(→ marks the start state, * marks a final state. C on b goes to both C and F, so this is non-deterministic.)

```text
        b           b
       ┌─┐         ┌─┐
       ↓ │         ↓ │
 ──→ ( σ ) ──a──→ ( C ) ──b──→ (( F ))
```
(σ loops on b; C loops on b and also goes to F on b.)

#### Part 2: DFA by subset construction
Start state = {σ}. Compute the move for each new subset until no new subset appears.

| DFA state | a | b |
|---|---|---|
| → {σ} | {C} | {σ} |
| {C} | ∅ | {C, F} |
| *{C, F} | ∅ | {C, F} |
| ∅ (dead) | ∅ | ∅ |

- {σ} on a: δ(σ, a) = {C}; on b: {σ}.
- {C} on a: ∅; on b: δ(C, b) = {C, F}.
- {C, F} on a: δ(C, a) ∪ δ(F, a) = ∅; on b: δ(C, b) ∪ δ(F, b) = {C, F}.
- Final states: those containing F, so {C, F}.

Rename A = {σ}, B = {C}, D = {C, F}, and E = dead state:

```text
         b                 b
        ┌─┐               ┌─┐
        ↓ │               ↓ │
 ──→ ( A ) ──a──→ ( B ) ──b──→ (( D ))
                    │            │
                    a            a
                    ↓            ↓
                   ( E ) ←───────┘   (E loops on a, b)
```

The DFA M' = ({A, B, D, E}, {a, b}, δ', A, {D}) accepts exactly b*ab⁺. I checked this with a program on all strings up to length 8.

## Check yourself

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

1. A rule X → aY becomes?
   A. A transition Y –a→ X
   B. An ε-move
   C. A final state
   D. A transition X –a→ Y
   Answer: D. Each non-terminal is a state and X → aY gives X –a→ Y. (Key point: Grammar to NFA)

2. C → b is converted to?
   A. C –b→ C
   B. F –b→ C
   C. An ε-move to σ
   D. C –b→ F where F is a new final state
   Answer: D. A rule with only a terminal goes to a new final state. (Key point: Terminal-only rule)

3. Why is the NFA non-deterministic?
   A. σ has no transitions
   B. There are two start states
   C. It has ε-moves
   D. C on b goes to both C and F
   Answer: D. δ(C, b) = {C, F}. (Key point: Source of non-determinism)

4. The language accepted is?
   A. a*bb*
   B. b*a*b
   C. (ab)*
   D. b*ab⁺
   Answer: D. Any b's, one a, then one or more b's. (Key point: Language)

## Related in Discrete Structure

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

- [Regular grammar to RE and FA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-grammar-to-re-fa) — Theory of Computation, chapter 2
- [Difference between DFA and NFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-nfa-difference) — Theory of Computation, chapter 2, asked 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×