Skip to main content

NFA and DFA from grammar σ→aA|bB

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

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.

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

Stateab
→ σ{A}{B}
A{F}∅
B{F}∅
*F∅∅
            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 stateab
→ {σ}{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 = ∅.

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →