NFA and DFA from grammar σ→bσ|aC

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

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

        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.

• {σ} 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:

         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.