Constructing an NFA for “0+ then odd number of 1s then 2*” over Σ = {0,1,2}

We want an NFA over $\Sigma=\{0,1,2\}$ that accepts exactly the strings of the form $0^+ \cdot (1(1)^* \text{ with odd number of }1\text{s}) \cdot 2^*.$ Concretely: the string must start with one or more $0$s, then have an odd number of $1$s, and may end with any number of $2$s (including none).

A helpful regex-like characterization is: $0^+ \, 1\,(1\,)^* \, 2^* \quad \text{with the condition that the number of 1s is odd}.$ We’ll encode the “odd number of 1s” requirement by tracking parity using NFA states. This is a standard regular-language pattern, implemented either via DFA parity states or via NFA nondeterminism; here we’ll explicitly build the NFA.

Key ideas:

• NFA: transitions can be nondeterministic.
• Accepting state.
• Start state.
• Epsilon transition.

Language decomposition

Let’s view an accepted string as:

1. Prefix: $0^+$ (at least one $0$)
2. Middle: odd number of $1$s (i.e., $1^1,1^3,1^5,\dots$)
3. Suffix: $2^*$ (any number of $2$s)

We will ensure the NFA does not allow:

• ending the string before the odd-number-of-$1$s portion is completed,
• reading any symbol outside the required structure (e.g., no $0$ after the middle begins).

Proposed NFA (explicit construction)

Let the NFA be $M=(Q,\Sigma,\delta,q_0,F)$ where:

• $\Sigma=\{0,1,2\}$
• $Q=\{q_0,q_{0},q_E,q_O\}$
• Start state: $q_0$
• Accepting states: $F=\{q_O\}$

Interpretation of states:

• $q_0$: before reading the required first $0$ (so empty or leading nonzero is impossible to accept)
• $q_{0}$: have read at least one $0$, still in the $0^+$ prefix
• $q_E$: have read an even number of $1$s (and already transitioned out of the 0-prefix)
• $q_O$: have read an odd number of $1$s; from here you may read $2^*$ and acceptance depends on ending in $q_O$

Now define $\delta$ as a set of transitions (for each state and symbol):

Prefix transitions (enforcing $0^+$)

• From $q_0$:
  • $\delta(q_0,0)=\{q_{0}\}$
  • $\delta(q_0,1)=\emptyset$
  • $\delta(q_0,2)=\emptyset$
• From $q_{0}$:
  • $\delta(q_{0},0)=\{q_{0}\}$ (keep consuming leading zeros)
  • $\delta(q_{0},1)=\{q_E\}$ (on first $1$, parity becomes even? careful: we start counting 1s here)
  • $\delta(q_{0},2)=\emptyset$ (no 2 allowed before 1s)

We must be consistent with parity:

• If we enter the “1-region” on reading the first $1$, then the number of $1$s becomes $1$ which is odd, not even. So we should set:
• $\delta(q_{0},1)=\{q_O\}$

Parity transitions among $1$s

• From $q_E$:
  • $\delta(q_E,1)=\{q_O\}$ (even -> odd after reading another 1)
  • $\delta(q_E,0)=\emptyset$
  • $\delta(q_E,2)=\emptyset$
• From $q_O$:
  • $\delta(q_O,1)=\{q_E\}$ (odd -> even)
  • $\delta(q_O,0)=\emptyset$
  • $\delta(q_O,2)=\{q_O\}$ (2* allowed after odd number of 1s)

Allow 2* suffix

• Already captured by $\delta(q_O,2)=\{q_O\}$
• Note: $q_E$ has no outgoing transition on $2$, so if you’ve read an even number of $1$s, you cannot “skip” to trailing $2$s.

Putting it all together, the transition function is:

This is actually a DFA (no nondeterministic branching needed), but it is a valid NFA since DFA is a special case.

Why it matches the specification

• Begins with one or more 0s: The only way to leave $q_0$ is by reading a $0$, and acceptance is impossible unless you reach $q_O$ later.
• Odd number of 1s: Parity is tracked between $q_E$ and $q_O$; each 1 toggles parity. $q_O$ is accepting.
• Ends with any number of 2s: From $q_O$, you can loop on $2$ staying in $q_O$, so trailing $2$s don’t change acceptance.
• No extra 0s after entering the 1/2 phase: $q_E$ and $q_O$ have no transitions on $0$.