The idea is to group several NFA states into one DFA state, check the possible next NFA states, group them together into new DFA states, and repeat until all DFA states have been completed.

You start with the initial state(s) of the NFA, and add one state to the DFA that corresponds to that set of states.

For each next symbol of those states (in the NFA), you add an outgoing arrow to the DFA state, and determine the target states for each of them (each of these new DFA states will again correspond to a collection of NFA states).

Repeat this for each of the DFA states identified.

For example, if you have this NFA :

_0

/ \

| \/

----- 1 ----- 0 ------

---->| A |---->| B |---->|*C*|

----- ----- ------

| /\

\_/

1

(I hope that's clear, but A is the initial state, with 0 and 1 looping back to it, and 1 going to B. From B, 0 is going to C, which is the end state (marked by *'s).

To construct the DFA, you start with the initial state (A) in the NFA, and create a state for it in the DFA : {A} :

---------

---->| {A} |

---------

In the NFA, the state A allows two next symbols (0 and 1), so in the DFA, we add two outgoing arrows (one for symbol 0, and one for symbol 1). In case of symbol 0, the next state is always A, so in the DFA, that becomes a loopback. In case of symbol 1, the next state is either A or B, so in the DFA, we add a new state {A,B} :

_0

/ \

| \/

--------- 1 -----------

---->| {A} |---->| {A,B} |

--------- -----------

State {A} in the DFA is now complete, so we move to state {A,B}. From the states A and B in the NFA, we again recognize two next symbols 0 and 1. In case of symbol 1, the next state is always A, so in the DFA, we add a pointer back to state {A}. In case of symbol 0, the next state is either A or C, so in the DFA, we add a new state {A,C} :

_0

/ \

| \/

--------- 1 ----------- 0 -----------

---->| {A} |---->| {A,B} |---->| {A,C} |

--------- ----------- -----------

/\ |

\_______/

1

State {A,B} in the DFA is now complete, so we move to state {A,C}. From the states A and C in the NFA, we again recognize two next symbols 0 and 1. In case of symbol 0, the next state is always A, so in the DFA, that becomes a pointer to state {A}. In case of symbol 1, the next state is either A or B, so in the DFA, that becomes a pointer to state {A,B} :

_0 ________________0

/ \ / \

| \/ \/ |

--------- 1 ----------- 0 -----------

---->| {A} |---->| {A,B} |---->| {A,C} |

--------- ----------- -----------

/\ | /\ |

\_______/ \_______/

1 1

State {A,C} in the DFA is now complete, and there are no more states to process. All we have to do now, is mark one or more states in the DFA as end states. In this case, there's only one : {A,C} :

_0 ________________0

/ \ / \

| \/ \/ |

--------- 1 ----------- 0 ------------

---->| {A} |---->| {A,B} |---->|*{A,C}*|

--------- ----------- ------------

/\ | /\ |

\_______/ \_______/

1 1

If the sketches in the post aren't clear, here they are again in a fixed width font :

You start with the initial state(s) of the NFA, and add one state to the DFA that corresponds to that set of states.

For each next symbol of those states (in the NFA), you add an outgoing arrow to the DFA state, and determine the target states for each of them (each of these new DFA states will again correspond to a collection of NFA states).

Repeat this for each of the DFA states identified.

For example, if you have this NFA :

_0

/ \

| \/

----- 1 ----- 0 ------

---->| A |---->| B |---->|*C*|

----- ----- ------

| /\

\_/

1

(I hope that's clear, but A is the initial state, with 0 and 1 looping back to it, and 1 going to B. From B, 0 is going to C, which is the end state (marked by *'s).

To construct the DFA, you start with the initial state (A) in the NFA, and create a state for it in the DFA : {A} :

---------

---->| {A} |

---------

In the NFA, the state A allows two next symbols (0 and 1), so in the DFA, we add two outgoing arrows (one for symbol 0, and one for symbol 1). In case of symbol 0, the next state is always A, so in the DFA, that becomes a loopback. In case of symbol 1, the next state is either A or B, so in the DFA, we add a new state {A,B} :

_0

/ \

| \/

--------- 1 -----------

---->| {A} |---->| {A,B} |

--------- -----------

State {A} in the DFA is now complete, so we move to state {A,B}. From the states A and B in the NFA, we again recognize two next symbols 0 and 1. In case of symbol 1, the next state is always A, so in the DFA, we add a pointer back to state {A}. In case of symbol 0, the next state is either A or C, so in the DFA, we add a new state {A,C} :

_0

/ \

| \/

--------- 1 ----------- 0 -----------

---->| {A} |---->| {A,B} |---->| {A,C} |

--------- ----------- -----------

/\ |

\_______/

1

State {A,B} in the DFA is now complete, so we move to state {A,C}. From the states A and C in the NFA, we again recognize two next symbols 0 and 1. In case of symbol 0, the next state is always A, so in the DFA, that becomes a pointer to state {A}. In case of symbol 1, the next state is either A or B, so in the DFA, that becomes a pointer to state {A,B} :

_0 ________________0

/ \ / \

| \/ \/ |

--------- 1 ----------- 0 -----------

---->| {A} |---->| {A,B} |---->| {A,C} |

--------- ----------- -----------

/\ | /\ |

\_______/ \_______/

1 1

State {A,C} in the DFA is now complete, and there are no more states to process. All we have to do now, is mark one or more states in the DFA as end states. In this case, there's only one : {A,C} :

_0 ________________0

/ \ / \

| \/ \/ |

--------- 1 ----------- 0 ------------

---->| {A} |---->| {A,B} |---->|*{A,C}*|

--------- ----------- ------------

/\ | /\ |

\_______/ \_______/

1 1

If the sketches in the post aren't clear, here they are again in a fixed width font :

```
NFA :
_0
/ \
| \/
----- 1 ----- 0 -----
---->| A |---->| B |---->|*C*|
----- ----- -----
| /\
\_/
1
DFA :
_0 ____________________0
/ \ / \
| \/ \/ |
------- 1 --------- 0 ---------
---->| {A} |---->| {A,B} |---->| {A,C} |
------- --------- ---------
/\ | /\ |
\_______/ \_______/
1 1
```