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.

The transition table of the NFA is

State | a | b |
---|---|---|

→{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.

State | a | b |
---|---|---|

→{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

**. Thus, we remove**

*q0***,**

*q1***,**

*q2***from the transition table.**

*q3*State | a | b |
---|---|---|

→{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.

- Replace {q0, q1} by {q1}
- Replace {q0, q2} by {q2}
- Replace {q0, q3} by {q3}

State | a | b |
---|---|---|

→{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.

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