Conversion of an NFA to a DFA using Subset Construction Algorithm

Conversion of an NFA to a DFA
using
Subset Construction Algorithm
Algorithm of Subset construction`
Operations on NFA States
Example:
By using subset construction algorithm convert the following NFA
N for (alb) * abb to DFA
Example: To apply subset construction
we need to remove :
1. ε – transition
• That require to construct ε – closure (s)
2. A multiple transition on input symbol from some state s in T:
Mov(T,a)
Example: First step: construct ε – closure (s)
{0} =
{1} =
{2} =
{3} =
{4} =
{5} =
{6} =
{7} =
{8} =
{9} =
{10} =
{0 , 1, 2, 4, 7}
{1, 2, 4}
{2}
{1, 2, 3, 4, 6, 7}
{4}
{1, 2, 4, 5, 6, 7}
{1, 2, 4, 6, 7}
{7}
{8}
{9}
{10}
Example: Second step: Looking for the start state for the DFA
The start state A of the equivalent DFA is ε – closure (0)
The ε – closure (0) = {0, 1, 2, 4, 7}
Then the starting state
A = {0, 1, 2, 4, 7}
b
{0, 1, 2, 4, 7}
A
a
Example: Third step: Compute U = ε -closure(move(T,a)
• First determine the input alphabet
here input alphapet = {a,b}
• Second compute:
1. Dtran[A,a] = ε -closure(move(A,a))
2. Dtran[A,b] = ε -closure(move(A,b))
Remember:
A = {0, 1, 2, 4, 7}
1. Dtran[A,a] = ε -closure(move(A,a))
• Among the state 0, 1, 2, 4, 7, only 2 and 7 have transitions on a to 3 and 8,
respectively.
Thus move(A,a)
= {3, 8}
Also, ε- closure ({3,8} = {1, 2, 3, 4, 6, 7, 8}
So we conclude:
Dtran[A,a] = ε -closure(move(A,a)) = ε- closure ({3,8} = {1, 2, 3, 4, 6, 7, 8}
Let us call this set B so:
Dtran[A,a] = B
A
a
{1, 2, 3, 4, 6, 7, 8}
B
2. Dtran[A,b] = ε -closure(move(A,b))
Among the states in A, only 4 has a transition on b, and it goes to 5
Thus:
Dtran[A,b] = ε -closure(move(A,b)) = ε- closure ({5} = {1, 2, 4, 5, 6, 7 }
Let us call this set C so:
Dtran[A,b] = C
A
b
{1, 2, 4, 5, 6, 7 }
C
• Third compute:
3. Dtran[B,a] = ε -closure(move(B,a))
4. Dtran[B,b] = ε -closure(move(B,b))
3. Dtran[B,a] = ε -closure(move(B,a))
Among the states in B, only 2, 7 has a transition on a, and it goes to {3, 8}
respectively
Thus:
Dtran[B,a] = ε -closure(move(B,a)) = ε- closure ({3,8} = {1, 2, 3, 4, 6, 7, 8 }
Dtran[B,a] = B
A
a
{1, 2, 3, 4, 6, 7, 8 }
B
a
4. Dtran[B,b] = ε -closure(move(B,b))
Among the states in B, only 4, 8 has a transition on b, and it goes to {5, 9}
respectively
Thus:
Dtran[B,b] = ε -closure(move(B,b)) = ε- closure ({5,9} = {1, 2, 4, 5, 6, 7,9}
a
Dtran[B,b] = D
A
a
B
B
b
{1, 2, 4, 5, 6, 7,9}
D
• Fourth compute:
5. Dtran[C,a] = ε -closure(move(C,a))
6. Dtran[C,b] = ε -closure(move(C,b))
5. Dtran[C,a] = ε -closure(move(C,a))
Among the states in C, only 2, 7 has a transition on a, and it goes to {3, 8}
respectively
Thus:
Dtran[C,a] = ε -closure(move(C,a)) = ε- closure ({3,8} = {1, 2, 3, 4, 6, 7, 8 }
Dtran[C,a] = B
A
b
{1, 2, 4, 5, 6, 7 }
C
a
B
6. Dtran[C,b] = ε -closure(move(C,b))
Among the states in C, only 4 has a transition on b, and it goes to {5}
respectively
Thus:
Dtran[C,b] = ε -closure(move(C,b)) = ε- closure ({5} = {1, 2, 4, 5, 6, 7}
Dtran[C,b] = C
A
b
b
{1, 2, 4, 5, 6, 7}
C
• Fifth compute:
7. Dtran[D,a] = ε -closure(move(D,a))
8. Dtran[D,b] = ε -closure(move(D,b))
7. Dtran[D,a] = ε -closure(move(D,a))
Among the states in D, only 2, 7 has a transition on a, and it goes to {3, 8}
respectively
Thus:
Dtran[D,a] = ε -closure(move(D,a)) = ε- closure ({3,8} = {1, 2, 3, 4, 6, 7, 8 }
Dtran[D,a] = B
B
b
a
{1, 2, 4, 5, 6, 7,9}
D
8. Dtran[D,b] = ε -closure(move(D,b))
Among the states in D, only 4 and 9 has a transition on b, and it goes to {5,
10} respectively
Thus:
Dtran[D,b] = ε -closure(move(D,b)) = ε- closure ({5,10} = {1,2, 4, 5, 6, 7, 10}
Dtran[D,b] = E
B
b
a
{1, 2, 4, 5, 6, 7, 9}
D
b
{1, 2, 4, 5,6, 7, 10}
E
• Finally compute:
9. Dtran[E,a] = ε -closure(move(E,a))
10. Dtran[E,b] = ε -closure(move(E,b))
9. Dtran[E,a] = ε -closure(move(E,a))
Among the states in E, only 2, 7 has a transition on a, and it goes to {3, 8}
respectively
Thus:
Dtran[E,a] = ε -closure(move(E,a)) = ε- closure ({3,8} = {1, 2, 3, 4, 6, 7, 8 }
Dtran[E,a] = B
D
b
{1, 2, 4, 5, 6, 7,9}
E
a
B
10. Dtran[E,b] = ε -closure(move(E,b))
Among the states in E, only 4 has a transition on b, and it goes to {5}
respectively
Thus:
Dtran[E,b] = ε -closure(move(E,b)) = ε- closure ({5} = {1,2, 4, 5, 6, 7}
Dtran[E,b] = C
D
b
{1, 2, 4, 5,6, 7, 10}
E
b
C
Transition table Dtran for DFA D
Result of applying the subset Construction NFA
for (alb) * abb

Download Report