Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 08

User Rating:  / 0
PoorBest 

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

NFA ? DFA Construction

The algorithm is called subset construction. In the transition table of an NFA, each entry is a set of states. In DFA, each entry is a single state. The general idea behind NFA-to- DFA construction is that each DFA state corresponds to a set of NFA states. The DFA uses its state to keep track of all possible states the NFA can be in after reading each input symbol.

We will use the following operations.

 

  • e-closure(T):
    set of NFA states reachable from some NFA state s in T on ? -transitions alone.
  • move(T,a):
    set of NFA states to which there is a transition on input a from some NFA state s in set of states T.

Before it sees the first input symbol, NFA can be in any of the state in the set e-closure(s0), where s0 is the start state of the NFA. Suppose that exactly the states in set T are reachable from s0 on a given sequence of input symbols. Let a be the next input symbol. On seeing a, the NFA can move to any of the states in the set move(T,a). Let a be the next input symbol. On seeing a, the NFA can move to any of the states in the set move(T,a). When we allow for e-transitions, NFA can be in any of the states in e-closure(move(T,a)) after seeing a.

Subset Construction

Algorithm:

Input: NFA N with state set S, alphabet S, start state s0, final states F
Output: DFA D with state set S’, alphabet S, start states,
s0’ = e-closure(s0), final states F’ and transition table: S’ x S? S’

// initially, e-closure(s0) is the only state in D states S’ and it is unmarked
s0’ = e-closure(s0)
S’ = {s0’ } (unmarked)

while (there is some unmarked state T in S’)
mark state T
for all a in S do
U = ? eclosure( move(T,a) );
if U not already in S’
add U as an unmarked state to S’
Dtran(T,a) = U;
end for
end while

F’:
for each DFA state S
if S contains an NFA final state
mark S as DFA final state

end algorithm

Example

Let us apply the algorithm to the NFA for (a | b )*abb. S is {a,b}.

algorithm to the NFA

The start state of equivalent DFA is e-closure(0), which is A = {0,1,2,4,7}; these are exactly the states reachable from state 0 via e-transition. The algorithm tells us to mark A and then compute e-closure(move(A,a))

move(A,a)), is the set of states of NFA that have transition on ‘a’ from members of A.
Only 2 and 7 have such transition, to 3 and 8. So, e-closure(move(A,a)) =
e-closure({3,8}) = {1,2,3,4,6,7,8}. Let B = {1,2,3,4,6,7,8}; thus Dtran[A,a] = B

For input b, among states in A, only 4 has transition on b to 5. Let C = e-closure({5}) = {1,2,4,5,6,7}. Thus, Dtran[A,b] = C

We continue this process with the unmarked sets B and C, i.e., e-closure(move(B,a)), e-closure(move(B,b)), e-closure(move(C,a)) and e-closure(move(C,b)) until all sets and states of DFA are marked. This is certain since there are only 211 (!) different subsets of a set of 11 states. A set, once marked, is marked forever. Eventually, the 5 sets are:

  1. A={0,1,2,4,7}
  2. B={1,2,3,4,6,7,8}
  3. C={1,2,4,5,6,7}
  4. D={1,2,4,5,6,7,9}
  5. E={1,2,4,5,6,7,10}

A is start state because it contains state 0 and E is the accepting state because it contains state 10.

The subset construction finally yields the following DFA

subset construction

The Resulting DFA can be encoded as the following transition table

State Input symbol
a b
A B C
B B D
C B C
D B E
E B C