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:
Asked
Active
Viewed 1,026 times
-1
-
Can you draw a finite state machine recognizing that language? – BrianO Nov 21 '15 at 00:52
-
I uploaded a picture to the description – Brice Petty Nov 21 '15 at 01:29
1 Answers
0
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$.
Thumbnail
- 563