Given a string from the language L((0+1)*) on the tape, give the program and draw the state diagram of a Turing Machine that can output on the tape:

• 0: If the number of O's > the number of 1's
• 1: If the number of 1's > the number of 0's
• N: If the number of l's = the number of 0's

Assume null string has an equal number of 0's and 1's. Use the following format for your instructions (5-tuple):

(

)

Examples:

1. (q ₀ 0 X R q ₀ ): If in state the the symbol on the tape is 0, change it to X and move the head to right and stay on the same state.

2. (q ₁ 1 _ R q ₂ ): If in state q1, the symbol on the tape is 1, erase it and move the head to right and change to state q ₂ .

3. (q ₃ * 0 * q _HALT ): If in state q ₃ , the symbol on the tape is not important, just change it to 0 and HALT.

Transcribed Image Text:

Tuple entry Meaning L R 90 9HALT Blank character, Wildcard in or to match any character or state. For , , means "no change". Move head left Move head right The "starting" state The "halting" state Tuple entry Meaning L R 90 9HALT Blank character, Wildcard in or to match any character or state. For , , means "no change". Move head left Move head right The "starting" state The "halting" state

Answer rating: 100% (QA)

Turing Machine design Assume the input is an integer N given as a binary string Also assume head is ... View the full answer