4
$\begingroup$

Why does the following DFA have (to have) the state $b_4$?

Shouldn't states $b_1,b_2,b_3$ already cover "exactly two 1s"? Wouldn't state $b_4$ mean "more than two 1s", even if it doesn't trigger an accept state?

enter image description here

$\endgroup$
7
$\begingroup$

$b_4$ is what is called a trap state, that is, a state that exists just so that all possible transitions are explicitly represented, even those that do not lead to a final state.

It doesn't change the language that is being defined, and can be omitted for the sake of brevity.

$\endgroup$
  • 3
    $\begingroup$ It can not be omitted in most definitions of DFAs I've seen. They require a transition to be defined for every state on every input symbol. $\endgroup$ – reinierpost Nov 11 '15 at 9:21
  • $\begingroup$ Omitted as in "implied", not as in "assumed to not exist". Sometimes we are just talking about convenient representations here, not always about formal definitions. In my view, this entire kerfuffle is unnecessary. $\endgroup$ – André Souza Lemos Nov 11 '15 at 13:59
  • $\begingroup$ In my view, it isn't. I've been confused about this myself, assuming the "convenient" notion of DFA was the same as the usual one in cases where the difference matters. The difference should be explained when explaining DFAs. I have added a paragraph to Wikipedia to explain the difference. $\endgroup$ – reinierpost Nov 11 '15 at 14:44
2
$\begingroup$

b4 exists to cover the entire alphabet ([0,1], in this case) for each state. While this is not strictly necessary, it is a hot topic of discussion in the field.

By showing the complete graph, it is more obvious that a third '1' in your input string permanently moves you out of the 'accept' state b3.

$\endgroup$
  • 2
    $\begingroup$ Rather than call it a "hot topic" I'd rather call it "one of those many cases in which the same name is used for slightly different concepts and you have to look at the definitions to figure out what exactly the present author is referring to". $\endgroup$ – reinierpost Nov 11 '15 at 9:24
2
$\begingroup$

The formal definition of a DFA is $M = (Q, \Sigma, \delta, q_0, F)$, were $Q$ is the finite set of states, $\Sigma$ is the alphabet, $\delta$ is the transition function, $q_0 \in Q$ is the start state, and $F \subseteq Q$ is the set of final states. Note that $\delta \colon Q \times \Sigma \to Q$ is specified to be a function, i.e., it has to be defined for all states and symbols. The graphical depiction of the DFA is complete in this sense with $b_4$. Often such dead states are just omitted in the sake of clarity of the diagram, the reader is surely capable of adding them if required.

$\endgroup$
0
$\begingroup$

Answering your question I have to say(sadly) that it depend. It depends on the definition of DFA that you are using because it appears to not be concensus in a unique definition.

For example I use the definition of the DFA where $\delta$ is a function. The next question is: Is $\delta$ a total function or a partial function?

Personally when I use the term function I am refering to total functions by default. But someone can disagree with me. More importantly when I studied the definition of a DFA my teacher told me that $\delta$ is a total function.

Summarizing I use a particular definition of a DFA where the $b_4$ state have to exist. I can skip drawing it for the sake of laziness or clarity, but I know it exist.

Finally to answer your question more precisely we have to know what definition of DFA you use.

Wouldn't state b4 mean "more than two 1s", even if it doesn't trigger an accept state?

The state $b_4$ means that if a word $\sigma$ have more than two "1" it will never reach an accepting state so $\sigma\notin L = \{w\,|\, \text{contains exactly two ones}\}$.

$\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.