91影视

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.

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\}$

鈥淥n 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\}$

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鈥檚 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鈥檚 are found reject

3. Scan the tape once more until an unmarked zero is found, mark the zero, if no zero鈥檚 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鈥檚 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\}$

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鈥檚 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鈥檚 are found accept

3. Scan the tape once more until an unmarked zero is found, mark the zero, if no zero鈥檚 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鈥檚 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\}$,