Construct finite automata for the regular expression (a+b)*abb

In this post, we will learn how to construct deterministic finite automata for the regular expression (a+b)*abb.

The given regular expression is rather simple. It is possible to draw its deterministic finite automata directly. But we will start by constructing non-deterministic automata then convert it to deterministic automata.

The NFA of the regular expression (a+b)*abb is given below.

non-deterministic finite automata of  regular expression (a+b)*abb

The transition table of the NFA is

Stateab
→{q0}{q0, q1}{q0}
{q1}{q2}
{q2}{q3}
*{q3}

We will convert the above NFA to DFA by expanding the transition table. We start by adding new states to the transition table.

Stateab
→{q0}{q0, q1}{q0}
{q1}{q2}
{q2}{q3}
*{q3}
{q0, q1}{q0, q1}{q0, q2}
{q0, q2}{q0, q1}{q0, q3}
*{q0, q3}{q0, q1}{q0}

We know that q0 is our start state. It is impossible to reach q1, q2, q3 from q0. Thus, we remove q1, q2, q3 from the transition table.

Stateab
→{q0}{q0, q1}{q0}
{q0, q1}{q0, q1}{q0, q2}
{q0, q2}{q0, q1}{q0, q3}
*{q0, q3}{q0, q1}{q0}

Now we rename the states to make things simpler.

  1. Replace {q0, q1} by {q1}
  2. Replace {q0, q2} by {q2}
  3. Replace {q0, q3} by {q3}
Stateab
→{q0}{q1}{q0}
{q1}{q1}{q2}
{q2}{q1}{q3}
*{q3}{q1}{q0}

The above transition table represents a deterministic automata. We can construct DFA of (a+b)*abb using above transition table.

non-deterministic finite automata of  regular expression (a+b)*abb

We can use this method to convert any NFA to DFA.

Leave a Comment

Your email address will not be published. Required fields are marked *