0
$\begingroup$

I am reading a computer theory book and came across the following example converting a NFA to a DFA:

enter image description here

My question is, would you not need an edge labeled $b$ going from the $x_4$ node on the right to the null collection state?

$\endgroup$
1
  • 1
    $\begingroup$ Which book? You need to give attribution for the image! $\endgroup$ – Raphael Jan 24 '16 at 23:33
2
$\begingroup$

The standard definition of DFAs involves a transition function, that is total. That means that, from every state, there should be an arrow for each symbol. So, yes, there is a missing $b$ arrow from $q_4$ to $\emptyset$ and also, missing $a$ and $b$ arrows from $\emptyset$ to itself. While we're at it, the diagram also has no indicated start state.

Note, though, that some authors use the convention that, if there's no transition given for some symbol from some state then, when the automaton reads that symbol in that state, it goes to a "dead" state. The dead state is non-accepting and the automaton cannot leave it (reading any character keeps it in that state). The author of your book might be using that convention inconsistently: the dead state is $\emptyset$ but they've only shown some of the transitions that lead to it. I think that's bad style: in my opinion, it's clearest to either show all the transitions to the dead state, or none of them.

$\endgroup$
3
  • $\begingroup$ The start state in the diagram is marked by a "-", the end states are marked by "+". $\endgroup$ – Thomas Klimpel Jan 24 '16 at 22:47
  • 2
    $\begingroup$ Lesson learned: never trust a book that uses $\phi$ instead of $\emptyset$. $\endgroup$ – Raphael Jan 24 '16 at 23:32
  • $\begingroup$ @ThomasKlimpel Oh, I wondered what those were for. I've never seen that convention before. $\endgroup$ – David Richerby Jan 25 '16 at 0:50
0
$\begingroup$

Indeed, if you really insist on the $\emptyset$ node, then you definitively need an edge labeled 'b' going from the x(sub 4) node to the $\emptyset$ node. In addition, the $\emptyset$ node also needs edges labeled 'a' and 'b' going back to itself.

In my opinion, the insistence on the $\emptyset$ node is misguided anyway, especially if the task is to draw the DFA.

$\endgroup$
2
  • $\begingroup$ The standard definition of a DFA is that the transition function is a total, and that requires a transition to be defined for every symbol, from every state. So I don't think it's at all reasonable to describe the $\emptyset$ node as "misguided". $\endgroup$ – David Richerby Jan 24 '16 at 22:07
  • $\begingroup$ @DavidRicherby The standard definition is good, but to insist on the $\emptyset$ node is misguided nevertheless, especially if the task is to draw the DFA. A graph can often be seen as an appropriate representation of a sparse matrix, but to insist on the $\emptyset$ node means that the corresponding matrix will always be full. (But I'm also thinking of examples like first order logic, where insistence on being single sorted would be regarded as being misguided as well, because it doesn't really change anything.) $\endgroup$ – Thomas Klimpel Jan 24 '16 at 22:45

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.