0

Give the diagram of transitions of a Turing machine to a ribbon which accepts the language on the alphabet $\{0, 1\}$ of the words which contain as many $0$ as of $1$. (Note well that the $0$ and the $1$ can appear in any order.)

This problem is similar to $\{0^n 1^n : n \in \mathbb{N}\}$ except the fact that we mix up all the $0$'s and $1$'s and can be solved with a simple pushdown automata. An instance of an accepting word on the tape would be $010011000111$ and a rejecting word would be $010111$.

I am confused how to set that up. I have thought building a transition with two states :

  1. $q_0$ would be the starting starting which is also the accepting state.
  2. $q_1$ would be the rejecting state.

I have thought using the transition function which will move left when I meet a $0$, move right when I meet a $1$ and using the symbol $\$$ whenever a state has been visited.

Am I on the right track? How to build such diagram?

Robert
  • 19

1 Answers1

1

The machine below uses the standard $5$-tuple transition representation $(q_i,s_i,q_f,s_f,d)$ where $d\in\{L,R\}$; accepting and rejecting are expressed as $(q_i,s_i,Yes/No)$. The tape head is initially on the leftmost bit of the input, surrounded by a sea of blanks $-$. $b$ or $c$ represent either $0$ or $1$ and $\neg$ the negation.

Each pass of the machine will do the following, pairing up bits and recursing into smaller and smaller strings until a result is clear:

  • Look at the first bit and erase it. If there are no more bits, we accept
  • Look for a matching bit (opposite value) and erase that. If the end is reached, we reject
  • Pick up a bit at the start if necessary and move it to fill the gap in the string left by the step above

There are eight states in the machine and initially we start in state $L$. The transitions are as follows: $$(L,b,L_{\neg b},-,R)\\ (L,-,Yes)\\ (L_b,\neg b,L_b,\neg b,R)\\ (L_b,-,No)\\ (L_b,b,R,-,L)\\ (R,b,R,b,L)\\ (R,-,P,-,R)\\ (P,b,P_b,-,R)\\ (P,-,L,-,R)\\ (P_b,c,P_b,c,R)\\ (P_b,-,S,b,L)\\ (S,b,S,b,L)\\ (S,-,L,-,R)$$

A refinement of the above machine combines searching for an opposite bit and bit pickup into one forward-and-backward motion: $$(L,-,Yes)\\ (L,b,L_{\neg b},-,R)\\ (L_b,-,No)\\ (L_b,b,L,-,R)\\ (L_b,\neg b,M_b,-,R)\\ (M_b,-,No)\\ (M_b,\neg b,M_b,\neg b,R)\\ (M_b,b,R,\neg b,L)\\ (R,b,R,b,L)\\ (R,-,L,-,R)$$

Parcly Taxel
  • 103,344