1
$\begingroup$

I have the following question

enter image description here

I have designed the following

enter image description here

A Binary String is even if it is ending with 0 and odd if its ending with 1.I have applied this.Im i right ?

UPDATE:

enter image description here

$\endgroup$
  • $\begingroup$ First, this isn’t a DFA: there’s no $0$ transition from $q_2$. Secondly, it accepts the input $1$, which is odd. $\endgroup$ – Brian M. Scott Dec 2 '15 at 12:47
  • $\begingroup$ @BrianM.Scott Okay.So for a DFA there should be a transition from every state for each input symbol. $\endgroup$ – techno Dec 2 '15 at 12:48
  • $\begingroup$ Yes, that’s correct. $\endgroup$ – Brian M. Scott Dec 2 '15 at 12:48
  • $\begingroup$ @BrianM.Scott well i made a blunder.I thought it should end with a 1 to be even when creating the DFA in that case is the diagram partially correct. $\endgroup$ – techno Dec 2 '15 at 12:50
  • $\begingroup$ But if you’re testing for even numbers, you want to accept the inputs that end in $0$, not $1$. $\endgroup$ – Brian M. Scott Dec 2 '15 at 12:53
1
$\begingroup$

Your answer is incorrect. It rejects strings that are even and therefore should be accepted, like $1100$, and accepts strings that are odd and therefore should be rejected, like $1$.

The correct automaton needs to remember whether the last character read was $1$ or $0$, so we need two states: the initial state and an accepting state. When a $0$ is read, transfer to the accepting state or remain there if we were in the accepting state already. When a $1$ is read, transfer to the initial state or remain there if we were in the initial state already.

When the entire string has been read, if the last character was $0$, we'll be in the accepting state and we'll accept the string as even. If the last character was $1$, we'll be in the initial state and reject the string as odd.

UPDATE: apart from the missing initial state annotation, it looks correct after your update. Well done!

$\endgroup$
  • $\begingroup$ Please see the updated question. $\endgroup$ – techno Dec 2 '15 at 12:56

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.