Question

7. (1 point) The collection of recognizable languages is closed under: A. union. B. concatenation. C. star. D. intersection. E. All of the above. Page 3 of 8 8. (1 point) L is decided by a deterministic) TM containing 100 tapes in time t(n) where n denotes the length of an input string. Which one of the following represents the time complexity of an equivalent single tape (deterministic) TM which decides L? A. Oft(n) 100). B. Oſt(n)). C. O(t(n)99). D. Oſt(n)). E. O(t(n)50).

Answer 1

7) Option E - All of the above given options is the correct one.

Collection of recognizable languages is closed under Union and intersection. Because, a recognizable language is a machine which recognizes the language. Recognizer of the language may or may not halt on the strings which are not in the language.

Turing recognizable language is closed under concatenation and star.

Hence, collection of recognizable languages is closed under union and intersection, concatenation and star.

8) Option A- O(t(n)^100) is the correct time complexity.

Because, given that L is decided by a deterministic TM that has 100 tapes. Now, we have to find time complexity of a single tape which is decided by L. But L is decided by TM with 100 tapes. So, required time complexity is raised power of t(n), where the power is total no.of iterations or tapes. So, L is decided by 100 tapes.

Hence, time complexity is O(t(n)^100).

---------------

Comment for any queries. Upvote if u like it.

Thank you.