Question

02-) 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 0's > the number of l's 1: If the number of 1's the number of O'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): <Current State> <Input symbol <Output symbol>Direction<Next State>) Tuple entry Meaning Blank character, 0 Wildcard in <Input symbol> or <Current State to match any character or state. For Output symbol>, <Next State Direcon> means "no change". Move head left Move head right The "starting" state 40 HALT The "halting" state

Answer 1

Turing Machine design:

Assume the input is an integer N given as a binary string.

Also, assume head is placed at left most symbol of the input string and initial state is q0.

Step 1: Check the current symbol, if it is 1 replace it by X and change the state to q1. move to right until a 0 is found or a blank is found. If a blank is found in q0 means that there are equal number of 1’s and equal number of 0’s. Thus, go to step 7.

Step 2: If a 0 is found, replace it by Y and change state to q3. Move to extreme left. If blank is found change to state q0(continue from step1).

Step 3: otherwise, if a blank is found means that there are extra 1’s. Thus, change the state to q5 and move to extreme left. While moving change any symbol to blank(_). If left blank is found, write a 1 (i.e., number of 1’s > number 0’s) and change the state to q_HALT.

Step 4: Check the current symbol, if it is 0 replace it by Y and change the state to q2. move to right until a 1 is found or a blank is found.

Step 5: If a 1 is found, replace it by X and change state to q4. Move to extreme left. If blank is found change to state q0(continue from step1).

Step 6: otherwise, if blank is found means that there are extra 0’s. Thus, change the state to q6 and move to extreme left. While moving change any symbol to blank(_). If left blank is found, write a 0 (i.e., number of 0’s > number 1’s) and change the state to q_HALT.

Step 7: Move to extreme right. While moving, replace Xs with 1s and Ys with 0s(i.e., writing N )

If a black is found, change the state to q_HALT.

The required Program (set of instructions) for the given Turning Machine that outputs according to given instructions, is as follows:

(q₀ 1 X R q1)

(q₀ 0 Y R q2)

(q₀ X * R q0)

(q₀ Y * R q0)

(q₀ _ * L q₇)

(q1 0 Y L q3)

(q1 1 * R q1)

(q1 X * R q1)

(q1 Y * R q1)

(q1 _ * L q5)

(q2 1 X L q4)

(q2 0 * R q2)

(q2 X * R q2)

(q2 Y * R q2)

(q2 _ * L q6)

(q3 * * L q3)

(q3 _ * R q0)

(q4 * * L q4)

(q4 _ * R q0)

(q5 * _ L q5)

(q5 _ 0 R q_HALT)

(q6 * _ L q5)

(q6 _ 1 R q_HALT)

(q₇ X 1 R q₇)

(q₇ Y 0 R q₇)

(q₇ _ * * q_HALT)

State diagram:

X/XL Y/Y, L 1/1, L 0/0, L LUR 93 0/Y, L X/XR Y/Y, RO 1/1,R Vai X_,L YI, 11,L 91 K q5 K 01 , 1/8, 11X, by X/1, R X/1, ,R Y/0, R 1 - LR X/XR Y/Y, RS qo _/0, 0/Y, R 92 X/X,R Y/YR 0/0, R 1/ XL LR X/X, L Y/Y, L 1/1, L 0/0, L