Answer

Language: $L = \{ 0\, 1^{2k+1}\, 2^* \mid k \ge 0 \} = \{ 01\, 2^*,\, 0111\, 2^*,\, 011111\, 2^*, \dots \}$

Structure: starts with 0 → odd number of 1's → any number of 2's.

NFA Design

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

• $\Sigma = \{0,1,2\}$
• $Q = \{q_0, q_1, q_2, q_3\}$
• $q_0$ = start
• $F = \{q_3\}$ (final)

States meaning:

• $q_0$: initial, expecting leading 0
• $q_1$: saw 0, read first 1 (odd count = 1)
• $q_2$: in even number of 1's (after 2nd, 4th, ...)
• $q_3$: in odd number of 1's (after 1st, 3rd, ...) — can transition to 2's

Transition Function $\delta$

No other transitions (missing transitions = dead/implicit reject).

State Diagram

       0
   ┌───────┐
   │       ▼
 (q0)──►(q1)──1──►(q2)
   │    ▲   │    │
   │    │   └────1
   │    2     │
   ▼    │     │
  (q3)◄──2─────┘
    2

How It Works

Equivalent DFA (via Subset Construction)

States = subsets of NFA states:

• $A = \{q_0\}$
• $B = \{q_1\}$
• $C = \{q_2\}$
• $D = \{q_1, q_3\}$
• $E = \{q_3\}$ (accepting)
• Dead = $\emptyset$

But NFA is simpler and sufficient.

Regular Expression

$0(11)^*1\,2^* = 0\,(11)^*\,1\,2^*$

Verification:

• 01 = $0 \cdot (11)^0 \cdot 1 \cdot 2^0$ ✓
• 0111 = $0 \cdot (11)^1 \cdot 1$ ✓
• 011122 = $0 \cdot (11)^1 \cdot 1 \cdot 2^2$ ✓

Final Answer

NFA with 4 states ($q_0,q_1,q_2,q_3$):

• $q_0 \xrightarrow{0} q_1$ (leading 0)
• $q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_1$ (toggle odd/even 1's)
• $q_1 \xrightarrow{2} q_3$ (odd 1's → can start 2's)
• $q_3 \xrightarrow{2} q_3$ (any number of 2's)
• Final = $\{q_3\}$
• Accepts $0(11)^*1 2^*$ exactly.