1
$\begingroup$

I'm trying to understand how to create state diagram of DFA. I found following example. On the first diagram I dont understand why we need fourth state when third state is final and there is no transitive function from fourth state to another state. And one more question about second diagram. Can't this automata take the word aaaa?

state diagram

$\endgroup$
  • 1
    $\begingroup$ The fourth state is a junk state. You need one to take the control of the forbidden words. BtW there is a typo in the exercise, i think, the language must be $\{w | w $ has exactly two a's$\}$. For the second one, no. It stays in the first node, because of the definition of the language, you need two b's. $\endgroup$ – Phicar Nov 1 '14 at 15:58
1
$\begingroup$

"Final state" is a confusing term. It does not mean that the state is actually the last one, or that the automaton stops when it reaches the final state. It means that if the automaton reaches that state at the end of the input, then the automaton will accept the input. The automaton might reach a final state at the end of the input, or it might not. For this reason some people prefer to call final states "accepting states".

The situation is further confused because the answer you are given for the left-hand automaton is wrong. The automaton pictured there accepts strings with exactly two as, not strings with exactly three as. I will suppose that the question was misprinted, and should say $$\{w \mid \text{$w$ has exactly $\bf{two}$ $\mathtt{a}$'s}\}.$$

The left-hand automaton must accept strings with exactly two as, and it must also reject strings with fewer than 2 as or with more than 2 as. After reading any string with zero as, the automaon will be in the leftmost state. After reading any string with exactly one a, it will be in the second state. After reading any string with exactly two as it will be in the third state, which is an accepting state, so it will accept any such string. But what does it do if the input string contains three or more as? It must do something; the definition of an automaton says that there must be a transition function which says what the new state is for any previous state and any input symbol. So there must be transitions out of the third state for both a and b. A third a takes the automaton into the fourth state, and once it is in that state it stays there until the input is completely read. Then it rejects the input, because the input had more than two as.


The second automaton does not accept aaaa, because each a takes it around the loop leading from the initial state back to the initial state. After reading aaaa it finishes in the same state it started in; because this is not an accepting state, the automaton does not accept the state aaaa.

$\endgroup$
0
$\begingroup$

Yes, the second DFA cannot take a word $aaaa$ as it is the language of words with at least two b's with no restriction on the number of $a$'s. Moreover, the first graph is wrong it accepts the language of exactly two $a$'s.

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