2
$\begingroup$

In computational theory, I came across both deterministic and non-deterministic finite state machines but I heard someone said there are no dead states in deterministic machines. I thought dead and empty states were the same. What I noticed is that empty states are represented by a special symbol called an empty set ∅. What's exactly the difference?

$\endgroup$
  • 1
    $\begingroup$ I'm not familiar with the term “empty state” for a deterministic or non-deterministic finite automaton. I could imagine several concepts that could plausibly be called “empty state”, of which a dead state is one. Could you point to a reference that defines it? $\endgroup$ – Gilles 'SO- stop being evil' Oct 30 '15 at 22:04
  • $\begingroup$ For example: this figure on wiki page which has empty set symbol. $\endgroup$ – cpx Oct 30 '15 at 22:26
2
$\begingroup$

That ∅ in the figure is just the name of that particular state in that machine.You could name it "cpx" if you want.

The figure is an example showing conversion from NFA to DFA. The conversion algorithm builds the DFA states from subsets of NFA states.The state named ∅ indicates that this state represents a particular subset of the states of the NFA, namely the empty set.

So, the symbol is just for the viewer to understand the significance of that particular state in the machine.

$\endgroup$
1
$\begingroup$

As calmyoursenses writes, in one sense, the state labelled $\emptyset$ in the output of the powerset conversion is just a particular state in the DFA it outputs.

On the other hand... It's also true that this particular state has some special properties. $\emptyset$ always has the special property that every outgoing transition from it goes back to itself, and that it is a non-accepting state. Therefore, one could plausibly say that the state labelled $\emptyset$ (in the output of the powerset construction) will always be a dead state. In other words, one could plausibly argue that the state labelled $\emptyset$ in the output of the powerset construction will always be a dead state. However, the converse need not hold: there can be other dead states in the output of the powerstate construction.

Note that all of this is specific to the kind of DFA output by the powerset construction. If you take some other DFA, there need not be any set labelled $\emptyset$ (there's no reason to expect such a label to exist, or to expect states to be labelled by sets).

$\endgroup$
-2
$\begingroup$

An empty state is the state of a list with zero items in it. A dead state refers to an error in the machine itself. An example would be a job queue being empty vs a computer being dead.

$\endgroup$

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.