Question

Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet

a. $\left\{w|w\mathrm{contains}\mathrm{an}\mathrm{equal}\mathrm{number}\mathrm{of}0s\mathrm{and}1s\right\}$

b.$\left\{w|w\mathrm{contains}\mathrm{twice}\mathrm{as}\mathrm{many}0s\mathrm{as}1s\right\}$

c.$\left\{w|w\mathrm{does}\mathrm{not}\mathrm{contain}\mathrm{twice}\mathrm{as}\mathrm{many}0s\mathrm{as}1s\right\}$

Short answer

a. $\left\{\mathrm{w}|\mathrm{w}\mathrm{contains}\mathrm{an}\mathrm{equal}\mathrm{number}\mathrm{of}0\mathrm{s}\mathrm{and}1\mathrm{s}\right\}$y

b. $\left\{\mathrm{w}|\mathrm{w}\mathrm{contains}\mathrm{twice}\mathrm{as}\mathrm{many}0\mathrm{s}\mathrm{as}1\mathrm{s}\right\}$

c. $\left\{\mathrm{w}|\mathrm{w}\mathrm{does}\mathrm{not}\mathrm{contain}\mathrm{twice}\mathrm{as}\mathrm{many}0\mathrm{s}\mathrm{as}1\mathrm{s}\right\}$

Step-by-step solution

Turing machine.

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine.

A Turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions.

Solution for part a.

a)

$\left\{\mathrm{w}|\mathrm{w}\mathrm{contains}\mathrm{an}\mathrm{equal}\mathrm{number}\mathrm{of}0\mathrm{s}\mathrm{and}1\mathrm{s}\right\}$

“On input string w:

1. Scan the tape and mark the first zero that has not been marked. If no unmarked zero is found, go to stage four.

Otherwise, move the head back to the front of the tape.

2. Scan the tape and mark the first one that has not been marked. If no unmarked one is found, reject.

3. Move the head back to the front of the tape and go to stage one.

4. Move the head back to the front of the tape. Scan the tape to see if any unmarked 1s remain. If none are found, accept; otherwise, reject.”

$\left\{\mathrm{w}|\mathrm{w}\mathrm{contains}\mathrm{an}\mathrm{equal}\mathrm{number}\mathrm{of}0\mathrm{s}\mathrm{and}1\mathrm{s}\right\}$

Solution for part b.

b)

$\left\{\mathrm{w}|\mathrm{w}\mathrm{contains}\mathrm{twice}\mathrm{as}\mathrm{many}0\mathrm{s}\mathrm{as}1\mathrm{s}\right\}$

1.Scan the tape and mark the first one which has not been marked. If no unmarked 1’s are found go to stage five. Otherwise move the head back to the start of the tape

2. Scan the tape until an unmarked zero is found, mark the zero, if no zero’s are found reject

3. Scan the tape once more until an unmarked zero is found, mark the zero, if no zero’s are found reject

4. Move the head back to the start of the tape and go to stage 1 5. Move the head back to the start of the tape. Scan the tape to see if any unmarked zero’s are found. If none are found accept, otherwise reject.

$\left\{\mathrm{w}|\mathrm{w}\mathrm{contains}\mathrm{twice}\mathrm{as}\mathrm{many}0\mathrm{s}\mathrm{as}1\mathrm{s}\right\}$

Solution for part c.

c)

$\left\{\mathrm{w}|\mathrm{w}\mathrm{does}\mathrm{not}\mathrm{contain}\mathrm{twice}\mathrm{as}\mathrm{many}0\mathrm{s}\mathrm{as}1\mathrm{s}\right\}$

1. Scan the tape and mark the first one which has not been marked. If no unmarked one’s are found go to stage five. Otherwise move the head back to the start of the tape

2. Scan the tape until an unmarked zero is found, mark the zero, if no zero’s are found accept

3. Scan the tape once more until an unmarked zero is found, mark the zero, if no zero’s are found accept

4. Move the head back to the start of the tape and go to stage 1 5. Move the head back to the start of the tape. Scan the tape to see if any unmarked zero’s are found. If none are found reject, otherwise accept.

$\left\{\mathrm{w}|\mathrm{w}\mathrm{does}\mathrm{not}\mathrm{contain}\mathrm{twice}\mathrm{as}\mathrm{many}0\mathrm{s}\mathrm{as}1\mathrm{s}\right\}$,