Converting the Regular Expression $(a+b)^*ab$ into an NFA

The regular expression $(a+b)^*ab$ denotes the language of all strings over the alphabet $\Sigma=\{a,b\}$ that end with the suffix $ab$.2 Here, $(a+b)$ means union between $a$ and $b$, the operator $^*$ is the Kleene star, and juxtaposition means concatenation.2 Therefore, $(a+b)^*ab$ can be read as “any sequence of $a$’s and $b$’s, followed by $a$, then $b$.”

A standard way to convert a regular expression into an NFA is Thompson's construction.2 This method recursively builds small NFAs for symbols and combines them using rules for union, concatenation, and star, while preserving the language of the expression.2

For this expression, there are two useful viewpoints:

1. Formal Thompson construction: build an $\varepsilon$-NFA step by step from $(a+b)^*ab$.2
2. Compact direct NFA: design a smaller NFA that accepts exactly the strings ending in $ab$.

This section presents both, with emphasis on the construction logic and acceptance behavior.2

Footnotes

1. Regular expression to NFA union concatenation Kleene star example (a+b)*ab - Tavily results - Discussion illustrating the language behavior of expressions like $(a|b)^*ab$ as strings ending in ab. ↩ ↩² ↩³ ↩⁴

2. THOMPSON CONSTRUCTION - IITKgp CSE - Lecture notes describing the recursive rules for building NFAs from regular expressions using Thompson construction. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. Regular Expressions - Stanford CS103 Lecture Notes - Notes explaining Thompson's algorithm and its structural properties, including one start and one accept state. ↩ ↩² ↩³

4. From Regular Languages to Finite Automata - University of Waterloo - Slides covering NFA construction for union, concatenation, and Kleene star using ε-transitions. ↩

Parsing the expression structurally

Before constructing the automaton, parse the expression as:

$$((a+b)^*)\cdot a \cdot b$$

This matters because operator precedence in regular expressions treats star as applying to the immediately preceding subexpression, and concatenation then chains the resulting components.2

So the construction proceeds through these subexpressions:

In Thompson construction, each symbol NFA has one start state and one accept state, union introduces a new start and accept state with $\varepsilon$-transitions, concatenation links the first NFA to the second using $\varepsilon$, and star adds new start/accept states plus looping $\varepsilon$-transitions.3

Footnotes

1. THOMPSON CONSTRUCTION - IITKgp CSE - Lecture notes describing the recursive rules for building NFAs from regular expressions using Thompson construction. ↩ ↩²

2. Regular Expressions - Stanford CS103 Lecture Notes - Notes explaining Thompson's algorithm and its structural properties, including one start and one accept state. ↩ ↩²

3. From Regular Languages to Finite Automata - University of Waterloo - Slides covering NFA construction for union, concatenation, and Kleene star using ε-transitions. ↩

Thompson $\varepsilon$-NFA for $(a+b)^*ab$

One valid state labeling is shown below. The labels are arbitrary; the structure is what matters.2

Let the states be:

$$q_0,q_1,\dots,q_{11}$$

• Start state: $q_6$
• Accept state: $q_{11}$

Transitions:

• $q_0 \xrightarrow{a} q_1$
• $q_2 \xrightarrow{b} q_3$
• $q_4 \xrightarrow{\varepsilon} q_0$
• $q_4 \xrightarrow{\varepsilon} q_2$
• $q_1 \xrightarrow{\varepsilon} q_5$
• $q_3 \xrightarrow{\varepsilon} q_5$
• $q_6 \xrightarrow{\varepsilon} q_4$
• $q_6 \xrightarrow{\varepsilon} q_7$
• $q_5 \xrightarrow{\varepsilon} q_4$
• $q_5 \xrightarrow{\varepsilon} q_7$
• $q_7 \xrightarrow{\varepsilon} q_8$
• $q_8 \xrightarrow{a} q_9$
• $q_9 \xrightarrow{\varepsilon} q_{10}$
• $q_{10} \xrightarrow{b} q_{11}$

This follows exactly from the recursive rules of Thompson construction: base NFAs for $a$ and $b$, then union for $(a+b)$, then star for $(a+b)^*$, then concatenation with $a$ and finally with $b$.2

This NFA is an $\varepsilon$-NFA because several transitions consume no input symbol. Such $\varepsilon$-moves are standard in Thompson's method and do not change the recognized language.2

Footnotes

1. THOMPSON CONSTRUCTION - IITKgp CSE - Lecture notes describing the recursive rules for building NFAs from regular expressions using Thompson construction. ↩ ↩² ↩³

2. Regular Expressions - Stanford CS103 Lecture Notes - Notes explaining Thompson's algorithm and its structural properties, including one start and one accept state. ↩ ↩²

3. Thompson's construction - Wikipedia - Overview of Thompson's construction and epsilon-transition-based NFAs for regular expressions. ↩

A smaller direct NFA for the same language

Although Thompson construction is systematic, it often produces more states than necessary. Since $(a+b)^*ab$ means “all strings ending in $ab$,” we can write a much smaller NFA directly.

Let:

• States: $\{q_0,q_1,q_2\}$
• Start state: $q_0$
• Accept state: $q_2$

Transitions:

• From $q_0$ on $a$: to $q_0$ and $q_1$
• From $q_0$ on $b$: to $q_0$
• From $q_1$ on $b$: to $q_2$

No other transitions are needed.

Intuition:

• $q_0$ keeps scanning any prefix in $(a+b)^*$.
• On reading an $a$, the automaton may nondeterministically guess that this $a$ is the beginning of the final suffix $ab$.
• If the next symbol is $b$, it reaches $q_2$ and accepts.

Formally, this NFA accepts exactly the strings whose last two symbols are $ab$.2

This direct NFA is often preferred in exams when the question simply asks to “convert the regular expression into NFA,” unless the instructor explicitly requires Thompson construction.2

Footnotes

1. From Regular Languages to Finite Automata - University of Waterloo - Slides covering NFA construction for union, concatenation, and Kleene star using ε-transitions. ↩

2. Regular expression to NFA union concatenation Kleene star example (a+b)*ab - Tavily results - Discussion illustrating the language behavior of expressions like $(a|b)^*ab$ as strings ending in ab. ↩ ↩² ↩³ ↩⁴

3. Thompson's construction - Wikipedia - Overview of Thompson's construction and epsilon-transition-based NFAs for regular expressions. ↩ ↩²

4. THOMPSON CONSTRUCTION - IITKgp CSE - Lecture notes describing the recursive rules for building NFAs from regular expressions using Thompson construction. ↩

Transition table for the compact NFA

A transition table makes the direct NFA easier to simulate.2

Because the automaton is nondeterministic, the entry for $(q_0,a)$ contains two possible next states. Acceptance occurs if at least one computation path ends in the accepting state after all input is consumed.

A useful characterization is:

$$L((a+b)^*ab)=\{\,w\in\{a,b\}^* \mid w \text{ ends with } ab\,\}$$

which directly explains why strings like $ab$, $aab$, and $bbab$ are accepted, while $a$, $aba$, and $bbb$ are rejected.

Footnotes

1. Regular expression to NFA union concatenation Kleene star example (a+b)*ab - Tavily results - Discussion illustrating the language behavior of expressions like $(a|b)^*ab$ as strings ending in ab. ↩ ↩²

2. Thompson's construction - Wikipedia - Overview of Thompson's construction and epsilon-transition-based NFAs for regular expressions. ↩ ↩² ↩³

Final answer

If the task is to convert $(a+b)^*ab$ into an NFA, a concise correct NFA is:

• $Q=\{q_0,q_1,q_2\}$
• $\Sigma=\{a,b\}$
• Start state $q_0$
• Final state $F=\{q_2\}$

Transition function $\delta$:

$$\delta(q_0,a)=\{q_0,q_1\},\quad \delta(q_0,b)=\{q_0\},\quad \delta(q_1,b)=\{q_2\}$$

and all other transitions go to $\varnothing$.2

This NFA is equivalent to the regular expression because it accepts exactly those strings whose last two characters are $ab$. If the instructor requires Thompson construction specifically, the larger $\varepsilon$-NFA shown earlier is the formal algorithmic construction.2

Footnotes

1. Regular expression to NFA union concatenation Kleene star example (a+b)*ab - Tavily results - Discussion illustrating the language behavior of expressions like $(a|b)^*ab$ as strings ending in ab. ↩ ↩²

2. Thompson's construction - Wikipedia - Overview of Thompson's construction and epsilon-transition-based NFAs for regular expressions. ↩

3. THOMPSON CONSTRUCTION - IITKgp CSE - Lecture notes describing the recursive rules for building NFAs from regular expressions using Thompson construction. ↩

4. Regular Expressions - Stanford CS103 Lecture Notes - Notes explaining Thompson's algorithm and its structural properties, including one start and one accept state. ↩