Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

(a) Give the sequence of configurations that the following TM M enters when given as input strings 1# #1 and 0#0. Please use the

(a) Give the sequence of configurations that the following TM M enters when given as input strings 1# #1 and 0#0. Please use the same representation for your configurations as we did in lecture 10. The reject state and transitions to the reject state are not shown. Whenever the TM encounters a character for which there is no explicit transition that means that the TM goes to the reject state. We say that the head moves right in each of these transitions to the reject state. start x R 91 0x, R 0,1 RC 92 #R R 94 0,1 0,1L 97 #R 1x, R xR 98 0,1 R 93 0x, L #L qaccept 1 R xR 95 1 x, L # R 960, 1, x L (b) Give an implementation level description of a TM, possibly nondeterministic and/or with multiple tapes, that recognizes the following language over the alphabet {0,1}: {s#a1#az#... #an| where n is a positive integer, s, a,..., an are binary integers such that some subset of a,..., an sums to s}. (c) Give a state diagram of the TM whose implementation level description is below. "On input w 1. If the first symbol is blank then accept. If it is b then reject. If it is a then erase this a and go to the right and go to the next step. 2. Move the head on the tape right until the blank symbol is found. After it is found move the head to the left (to the last symbol of the string) and go to the next step. 3. If the last symbol is not b then reject. Otherwise, erase this b and go to the left and go to the next step. 4. Move the head on the tape left until the blank symbol is found. After it is found move the head to the right (to the first symbol of the string) and go back to step 1." (d) What language is decided by the TM from (c)?

Step by Step Solution

3.51 Rating (164 Votes )

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Organic Chemistry

Authors: John McMurry

7 Edition

978-0495112587, 0495112585

More Books

Students also viewed these Programming questions

Question

Give the sequence of the following tetra peptide (yellow =S):

Answered: 1 week ago

Question

Give the sequence of the following tetrapeptide:

Answered: 1 week ago

Question

What was the change in net working capital during the year?

Answered: 1 week ago