subject
Engineering, 22.02.2020 02:25 vegetavigitop4l0r0

Consider the following specification of a Turing machine that, when placed on the leftmost letter of a string of a's and b's (where the end of the string is marked by an 'x' -- think of 'x' as denoting a blank cell on the tape), detects whether that string is a palindrome.

We will write down the transition function in the following format:

(s, i) -> (s', w, d)

This would mean that if the Turing machine is in state s, and the current cell under the read/write head contains symbol i, then it changes to state s', writes w on the cell, and then moves the head in the d direction. In the instructions below, L and R stand for left and right directions, and the states are the numbers 0 through 7.

Note: The comments after the transition rules (text between /* and */) are just comments to help explain in conceptual terms what the Turing machine is "doing" when in different states. The actual functioning of the Turing machine is completely determined by the transition rules themselves.

CO, a) - (1,x, R) State 0 (start state) */ C0,b) - (2,x, R) CO, x) -> C5,x, L) (1,a) -> (1,a, R) /*Seen an askip to right end of the input to look for match* (2,a) -> (2,a, R) /*Seen a b; skip to right end of the input to look for match* (3,a) -> (7,x, L) Test right end for a * (3,x) -> C5,x, L) (4,a) -> (6,a, L) Test right end for b */ C4,b) - (7,x, L) C4,x) -> C5,x, L) 5,* ->halt (6,*) ->halt Found a palindrome* /* Did not find a palindrome */ (7,a) -> (7,a, L) Found a match at the right end; return to left end of input (7,x) -> C0,x, R)

Suppose that the machine starts with the following sequence of symbols on its input tape: a b a b x x x . . . Assume that the machine starts with the read/write head on the leftmost non-blank cell (so it is reading the first "a"), and starts in state 0.

If this Turing machine executes on this input:

A) What is the sequence of states that it will enter? Show your work. (Note: You should enter one state number for each step of the computation. The machine may enter the same state twice or more--you should still list that state each time it is entered.)

B) What are the contents of the tape at the end of the execution?

ansver
Answers: 3

Other questions on the subject: Engineering

image
Engineering, 04.07.2019 18:10, aaliyah80
The drive force for diffusion is 7 fick's first law can be used to solve the non-steady state diffusion. a)-true b)-false
Answers: 1
image
Engineering, 04.07.2019 18:10, redrosesxx
Water at 55c flows across a flat plate whose surface temperature is held constant at 95c. if the temperature gradient at the plate's surface for a given value of x is 18 c/mm, find a) local heat transfer coefficient. b) heat flux
Answers: 3
image
Engineering, 04.07.2019 18:20, maustin5323
Athin walled concentric tube exchanger is used to cool engine oil from 160°c to 60°c with water that is available at 25°c acting as a coolant. the oil and water flow rates are each at 2 kg/s, and the diameter of the inner tube is 0.5 m and the corresponding value of the overall heat transfer coefficient is 250 w/m2. oc. how long must the heat exchanger be to accomplish the desired cooling? cpwater=4.187 kj/kg-candcpengine el=2.035 kj/kg·°c, oil . 120]
Answers: 1
image
Engineering, 04.07.2019 18:20, 21megoplin
How much power could a wind turbine produce if it had the following specifications? cp = 0.45 -d=1.2kg/m3 d=50m v 5m/s
Answers: 2
You know the right answer?
Consider the following specification of a Turing machine that, when placed on the leftmost letter of...

Questions in other subjects:

Konu
Mathematics, 29.05.2020 00:05
Konu
Mathematics, 29.05.2020 00:05
Konu
Mathematics, 29.05.2020 00:05
Konu
History, 29.05.2020 00:05