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, keigleyhannah30
Aplate clutch has a single pair of mating friction surfaces 250-mm od by 175-mm id. the mean value of the coefficient of friction is 0.30, and the actuating force is 4 kn. a) find the maximum pressure and the torque capacity using the uniform-wear model. b) find the maximum pressure and the torque capacity using the uniform-pressure model.
Answers: 3
image
Engineering, 04.07.2019 18:10, Fahaddie
The thermal expansion or contraction of a given metal is a function of the f a)-density b)-initial temperature c)- temperature difference d)- linear coefficient of thermal expansion e)- final temperature f)- original length
Answers: 2
image
Engineering, 04.07.2019 18:20, CelesteN64
Most leaks in reciprocating air compressors can be detected and minimized by: (clo4) a)-detecting leakage areas using ultrasonic acoustic detector. b)-tightening joints and connections c)-replacing faulty equipment d)-all of the given options
Answers: 2
image
Engineering, 04.07.2019 18:20, hayleymckee
Steam enters a converging nozzle at 3.0 mpa and 500°c with a at 1.8 mpa. for a nozzle exit area of 32 cm2, determine the exit velocity, mass flow rate, and exit mach number if the nozzle: negligible velocity, and it exits (a) is isentropic (b) has an efficiency of 94 percent
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
History, 01.10.2019 03:30