Draw a Turing machine that recognizes the language $\{w \in \{0,1\}^*|w \text{ contains even number of 1's}\}$

This is where I am at:

enter image description here

  • $\begingroup$ Can you draw a finite state machine recognizing that language? $\endgroup$ – BrianO Nov 21 '15 at 0:52
  • $\begingroup$ I uploaded a picture to the description $\endgroup$ – Brice Petty Nov 21 '15 at 1:29

You don't need a full blown Turing machine for this. A finite machine (equivalent to a Turing machine that just reads its tape once in one direction) will do.

The required language is given by the regular expression

$$0^* \left( 10^*10^* \right)^*$$

The minimal finite machine that recognises this has two states:

  • an initial accepting state, say $A$;
  • another non-accepting state, say $B$.

The states behave symmetrically:

  • An input of $0$ leaves the machine in the same state, $A$ or $B$.
  • An input of $1$ takes the machine to the other state: $A$ to $B$ or $B$ to $A$.

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.