Skip to main content

NFA and DFA from grammar with A, B rules

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.

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.

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}):

Stateab
→ σ{F}{B}
A{B, F}{A, F}
B∅{F}
*F∅∅
              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 stateab
→ {σ}{F}{B}
{B}∅{F}
*{F}∅∅
∅ (dead)∅∅

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

 ──→ ( 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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →