How this state set of DFA was retrieved from the given NFA

53 Views Asked by At

I have this NFA:

1,{2, 3}
2,empty
3,{4}
4,empty

All the arrows in this NFA are epsilon-arrows.

I understand that all possible states that can be reached from each of the states, using only epsilon paths are these:

E(1) = {1,2,3,4}
E(2) = {2}
E(3) = {3,4}
E(4) = {4}

However I don't understand how this state set was achieved:

DFA = {empty, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2,
3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}

My understanding is that the transition table that looks like this:

   epsilon   
1  2, 3
2  -
3  4
4  -

is to be used to determine the DFA, along with the E function.

I tried to do it like this:

Start state = 1 => the Result = {E(1)} = {{1, 2, 3, 4}}

T({1, 2, 3, 4}) = E(transitionTable({1, 2, 3, 4})) = E({2, 3, 4}) = {2, 3, 4}

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

T({2, 3, 4}) = E({4}) = {4}

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

T({4}) = E({}) = {}

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

What am I doing wrong here? Any help is appreciated.

0

There are 0 best solutions below