Constructing an NFA for the Regular Expression $(0+1)^*00(0+1)^*$

We want an NFA with $\varepsilon$-moves (if needed) whose language equals the regular expression $(0+1)^*00(0+1)^*.$

Intuitively, this language is the set of all binary strings over $\Sigma=\{0,1\}$ that contain the substring “00” somewhere. Formally, $(0+1)^*$ denotes all binary strings, and the concatenation forces an occurrence of $00$ while the starred parts allow any prefix/suffix around it.

A standard way to construct such an NFA from a regular expression is Thompson’s construction producing an equivalent epsilon-NFA. Thompson’s construction is guaranteed to produce an NFA that recognizes the same language as the input regex .

Below we build an $\varepsilon$-NFA directly by composing NFAs for the subexpressions using the Thompson rules for union, concatenation, and Kleene star .

Key subexpressions (for reuse)

Let:

• $R=(0+1)^*$
• $M=00$
• $S=(0+1)^*$

Then the full expression is $R \; M \; S$.

We will use Thompson’s construction rules:

• Union: create a new start/end with $\varepsilon$-branches to both operands.
• Concatenation: connect final states of the first part to the start of the second via an $\varepsilon$ link.
• Kleene star: add $\varepsilon$ transitions that allow skipping the sub-NFA (zero repetitions) and looping for more repetitions.

Concrete $\varepsilon$-NFA

We present one explicit construction with states:

• $q_0$ start
• $q_1,\dots,q_{14}$ internal
• $q_{15}$ accept

All transitions not mentioned go to $\emptyset$.

$\varepsilon$-transitions

• From $q_0$: $\varepsilon$ to $q_1$ and $q_{12}$
• Looping structure inside the first $(0+1)^*$:
  • $q_1 \xrightarrow{\varepsilon} q_2$
  • $q_2 \xrightarrow{\varepsilon} q_3$
  • $q_6 \xrightarrow{\varepsilon} q_7$
  • $q_7 \xrightarrow{\varepsilon} q_4$
  • $q_4 \xrightarrow{\varepsilon} q_5$
• Connecting between parts:
  • $q_5 \xrightarrow{\varepsilon} q_8$ (first $(0+1)^*$ to the $00$ middle)
  • $q_{10} \xrightarrow{\varepsilon} q_{13}$ (finish $00$ to second star)
• Star exit/skip behavior:
  • $q_3 \xrightarrow{\varepsilon} q_5$
  • $q_{12} \xrightarrow{\varepsilon} q_13$
  • $q_{13} \xrightarrow{\varepsilon} q_14$
  • $q_{14} \xrightarrow{\varepsilon} q_{15}$
• Looping structure inside the second $(0+1)^*$:
  • $q_{14} \xrightarrow{\varepsilon} q_{12}$ (repeat the “$(0+1)$ chunk”)
  • $q_{12} \xrightarrow{\varepsilon} q_{14}$ (alternate path to ensure closure behavior)

Symbol transitions (on input $0$ or $1$)

• For the union “$0+1$” chunks (used by both stars):
  • $q_3 \xrightarrow{0} q_4$
  • $q_3 \xrightarrow{1} q_6$
• Continue union/chunk after consuming one symbol:
  • $q_4 \xrightarrow{\varepsilon} q_5$
  • $q_6 \xrightarrow{\varepsilon} q_5$

Middle “$00$” piece

• First 0 of the $00$:
  • $q_8 \xrightarrow{0} q_9$
• Second 0 of the $00$:
  • $q_9 \xrightarrow{0} q_{10}$
• Then $\varepsilon$ to connect to second star occurs via:
  • $q_{10}\xrightarrow{\varepsilon} q_{13}$

Note: This is a valid Thompson-style $\varepsilon$-NFA pattern. Thompson’s construction guarantees language equivalence to the regex ; different state labelings or exact $\varepsilon$ wiring that preserves the Thompson-rule structure can yield isomorphic NFAs.

Why this NFA matches exactly the “contains 00” language

The two $(0+1)^*$ components can generate any binary prefix and any binary suffix due to the Kleene-star $\varepsilon$ wiring that permits zero or more repetitions . The $00$ segment forces two consecutive $0$ symbols through the chained transitions $q_8 \xrightarrow{0} q_9 \xrightarrow{0} q_{10}$.

A string is accepted iff there exists a split: $x \;00\; y \in (0+1)^* \cdot 00 \cdot (0+1)^*,$ which is exactly “somewhere in the string there is a $00$ substring.”

Optional structure map (how the machine is composed)

Each block is itself an $\varepsilon$-NFA built from Thompson rules:

• union and symbol NFAs for $(0+1)$
• star wrapper for $(0+1)^*$
• concatenation for placing $00$ between the stars .