0
$\begingroup$

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  -

enter image description here

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.imgur.com/4CiHTXR.png

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

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Russel
    Jul 19 at 1:07

1 Answer 1

0
$\begingroup$

Observe that the states of the DFA in question is the powerset of the states of the NFA, while the process of converting the NFA to a DFA you have presented is called subset construction. Since the resulting states of the DFA using subset construction is guaranteed to be a subset of the powerset of the states of the NFA, you can actually define the state of the DFA to be the entire powerset, hence your DFA in question. However, its possible that there will be certain states in the powerset that will be unreachable from the start state and therefore useless (although in the worst-case the resulting DFA might actually have all that exponentially many reachable states).

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Jul 19 at 3:19
  • $\begingroup$ I am actually asking about the transition table of the big DFA. I think the procedure your doing already will give you the reachable states. You can check the link I give for the procedure $\endgroup$
    – Russel
    Jul 19 at 3:27
  • $\begingroup$ However when I tried to use an online converter (joeylemon.github.io/nfa-to-dfa) (I used a JSON file, see EDIT on post), I got a different result (see edit) $\endgroup$ Jul 19 at 5:24
  • $\begingroup$ I checked your given source/JSON file (but you are advised not to post such details in this site since it's very similar to source code) and there seems to be a problem with it. I created your NFA from scratch and it appears that this online converter does not allow conversion of NFA with no alphabet symbol. $\endgroup$
    – Russel
    Jul 19 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.