Building NFA from Regular Grammars- Examples

 Example:

Grammar

• $A_0 \to aA_1$

• $A_1 \to bA_1 \ \mid\ a \ \mid\ bA_0$

We’ll use the standard construction:

• One NFA state per nonterminal $(A_0, A_1)$ plus a fresh final state $F$.

• For each rule $X \to aY$: add a transition $X \xrightarrow{a} Y$.

• For each rule $X \to a$ (terminal only): add $X \xrightarrow{a} F$.

• Start state is the start nonterminal ($A_0$).

• Accepting states: $\{F\}$ (no $\varepsilon$-rules here, so neither $A_0$ nor $A_1$ is accepting).

---

NFA $N = (Q,\Sigma,\delta,q_0,F)$

• States $Q = \{A_0, A_1, F\}$
  

• Alphabet $\Sigma = \{a,b\}$

  
  

  Start

• $q_0 = A_0$

• Accepting $F=\{F\}$

Transitions $\delta$:

• From $A_0$:

  • on a → $\{A_1\}$ (from $A_0 \to aA_1$)

  • on b → $\varnothing$
    

• From $A_1$:

  • on a → $\{F\}$(from $A_1 \to a$)

  • on b → $\{A_1, A_0\}$ (from $A_1 \to bA_1$ and $A_1 \to bA_0$)

• From $F$:

  • on a → $\varnothing$, on b → $\varnothing$ (no outgoing rules)

---

Transition table

State	a	b
$A_0$	$\{A_1\}$	$\varnothing$
$A_1$	$\{F\}$	$\{A_1, A_0\}$
$F$	$\varnothing$	$\varnothing$

Example

let’s build the NFA for the right-linear grammar:

• $S \to 0S \mid 1A \mid 1$
  

• $A \to 0A \mid 1A \mid 0 \mid 1$
  

Example:

Grammar

• $S \to 0A \;|\; 1B \;|\; 0 \;|\; 1$
  

• $A \to 0S \;|\; 1B \;|\; 1$
  

• $B \to 0A \;|\; 1S$
  

Example:

S → 0A | 1A

A → 0A | 1A | +B | -B

B → 0B | 1B | 0 | 1