# Converting an NFA to an equivalent DFA

Both deterministic and non-deterministic finite machines recognize the set of regular languages. This article explores a step by step approach to convert a NFA to a DFA that accepts the same language.

## NFA

Consider the following NFA

This NFA can be converted into an equivalent DFA by following these steps

## Compute -close set

The -close set of a state is defined as the set of all states that can be reached by following or more transitions from that state. The -close set of a state will always contain that state. The -close set of all the states of the NFA are computed

## Start state of DFA

The start state of DFA will be the epsilon closure of start state of NFA. In this case



## Transition on followed by -close

Track the transition for each state in the above set and combine the result.



Thus,



Take the -close of this set



Thus, the final state is given by



## Transition on followed by -close

Track the transition for each state in the above set and combine the result.



Thus,



Take the -close of this set



Thus, the final state is given by



The above process has to be repeated until no more new states are being added and all transitions are accounted for. In this case there is a new state.



## Transition on followed by -close

Track the transition for each state in the above set and combine the result.



Thus,



Take the -close of this set



Thus, the final state is given by



## Transition on followed by -close

Track the transition for each state in the above set and combine the result.



Thus,



Take the -close of this set



Thus, the final state is given by



No new states are added an all transitions are accounted for.

## Final states

If a state in the DFA has any occurrence of a final state in the original NFA, it is marked final. In the above case, and are final in the original NFA. This makes both the states in the DFA final.

## State Diagram

Here is an equivalent transition state diagram