Converting NFAs to DFAs

Note: to view the symbols on this page correctly, you should be using a PC with the Windows TrueType Symbol font loaded.

Converting a nfa to a dfa

Defn: Theis the set of all states, including S itself, that you can get to via e-transitions. The e-closure of state S is denoted: S Example:e-closure of a state

`The e-closure of state 1: 1 = { 1, 2, 4 }`

`The e-closure of state 3: 3 = { 3, 2, 4 }`

Defn: TheSe-closure of a set of states_{1}, ... S_{n}is S_{1}� S_{2}� ... � S_{n}.

Example: The e-closure for above states 1 and 3 is

{ 1, 2, 4 } � { 3, 2, 4 } = { 1, 2, 3, 4 }

To construct a dfa from a nfa:

Step 1: Let the start state of the dfa be formed from the e-closure of the start state of the nfa.

Subsequent steps: If S is any state that you have previously constructed for the dfa and it is formed from say states t_{1}, ... , t_{r}of the nfa, then for any symbol x for which at least one of the states t_{1}, ... , t_{r}has a x-successor, the x-successor of S is the e-closure of the x-successors of t_{1}, ... , t_{r}.

Any state of the dfa which is formed from an accepting state, among others, of the nfa becomes an accepting state.

Example 1: To convert the following nfa:

we get:

This constructs a dfa that has no epsilon-transitions and a single accepting state.

Example 2: To convert the nfa for an identifier to a dfa

we get:

Minimizing the Number of States in a DFA

Step 1: Start with two sets of states (a) all the accepting states, and (b) all the nonaccepting states

Subsequent steps: Given the sets of states S_{1}, ... S_{r}consider each state S and each symbol x in turn. If any member of S has a x-successor and this x-successor is in say S', then unless all the members of S have x-successors that are in S', split up S into those members whose x-successors are in S' and the others (which don't have x-successors in S').

Example 1. Consider the dfa we constructed for an identifier (with renumbered states):

The sets of states for this dfa are:S1S2Nonaccepting Accepting states: states: 1 2 All states in S2 have the successors 3 letter-successor and digit-successor, and 4 the successor states are all in the set of states S2.Combine all the states of S2 to get:

Example 2. Consider the dfa:

All of the states (1, 2, and 3) are accepting states and all their successors are also accepting states, but state 1 has an a-successor whereas states 2 and 3 do not. So, we split the set of accepting states into two sets S1 and S2 where: S1 consists of state 1, and S2 consists of states 2, 3to get: