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

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.

EDIT:

Transition table:

   epsilon
1  2, 3
2  -
3  4
4  -


EDIT:

Using this converter: https://joeylemon.github.io/nfa-to-dfa/

With this file:

{"nodes":[

{"label":"1","loc":{"x":200,"y":100},"transitionText":{"2":["ε"],"3":["ε"]}},

{"label":"2","loc":{"x":600,"y":100},"transitionText":{}},

{"label":"3","loc":{"x":400,"y":400},"transitionText":{"4":["ε"]}},

{"label":"4","loc":{"x":600,"y":400},"transitionText":{},"acceptState":true}],

"fsa":{"states":["1","2","3", "4"],"alphabet":["ε"],"transitions":{"1":{"ε":["2"],"ε":["3"]},"2":{},"3":{"ε":["4"]}},"startState":"1","acceptStates":["4"]}}


gives this:

https://i.sstatic.net/Cl9aP.png

So it says the states in DFA are Q' = {{Ø}, {1,3}, {4}, {3,4}}, not

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

• Can you edit your question to include the transition function/table of the DFA in question and the transition function/table of the DFA you have constructed? Jul 19, 2022 at 1:07

What you did on the other hand, is you try to compute only reachable states from the start state. Your computation of $$\varepsilon$$-closure (paths using $$\varepsilon$$ transition only) is correct. However, your process of computing DFA state from each NFA transition will still generate unreachable states. I suggest that you read the link on subset construction I have given above for the step-by-step process. If your familiar with breadth-first search (BFS), the general idea of subset construction is similar. You just have to understand how to determine the reachable (neighbors) states from a given state.
As a hint, the DFA that you should generate must have a single state only $$\{1,2,3,4\}$$ which is both a start and final state.
• I edited the question with the transition table! So the big DFA 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}} is actually the DFA with states many of which are unreachable? How would I calculate only the reachable states correctly? I am not sure I am doing that correctly Jul 19, 2022 at 3:19