2. Let L be the language over { a, b } that contains a string u...

 

Transcribed Image Text:

2. Let L be the language over { a, b } that contains a string u if it satisfies one of the following conditions: (i) u = a'b' and length(u) 100, or (ii) length(u) > 100. (a) (10 points) Describe the design of a standard TM M that accepts L. (b) (10 points) Give the function tcm. (c) (5 points) What is the best polynomial rate of growth that describes tcm. 2. Let L be the language over { a, b } that contains a string u if it satisfies one of the following conditions: (i) u = a'b' and length(u) 100, or (ii) length(u) > 100. (a) (10 points) Describe the design of a standard TM M that accepts L. (b) (10 points) Give the function tcm. (c) (5 points) What is the best polynomial rate of growth that describes tcm.

Answer rating: 100% (QA)

QUESTION Let L be the language over a b that contain a string if itatisfies one ofthe flowing condit... View the full answer