If f : N--> N. If L can be recognized by a TM T, so thatτT(n)≤ f (n) for all but finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).

www.ThinkITI.com

Home
MCQ
Search
Free Apps
Important
Study Groups
Contact Us
Policy

Home
MCQ
Objective Questions
Engineering
Computer Science
Computer Science Set-1
Theory of Computation
70

Theory of Computation MCQ with Answers

70) If f : N--> N. If L can be recognized by a TM T, so thatτT(n)≤ f (n) for all but finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).

L ∈Time (f)

L ∈ Time(cf)

L ∈ Time (h)

none of these

Answer is:

L ∈Time (f)

Theory of Computation MCQ with Answers

For more MCQ's Click Here

71) Let s is a step-counting function satisfying s(n) ≥n, and L be a language accepted by a (multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes for an input string of length n, then T∈

Space(s)

F(n)

Time(f)

Time(h)

Answer is:

Space(s)

72) Which of the following statements is false ?

Halting problem of Turing machines is undecidable

Determining whether a context-free grammar is ambiguous is undecidable

Given two arbitrary context-free grammars G1 G2 and it is undecidable whetherL (G1) = L (G2).

Given two regular grammars G1G2 and it is undecidable whether L (G1) = L (G2)

Answer is:

Given two regular grammars G1G2 and it is undecidable whether L (G1) = L (G2)

73) Bounded minimalization is a technique for

proving whether a promotive recursive function is turning computable or not

proving whether a primitive recursive function is a total function or not

generating primitive recursive functions

generating partial recursive functions

Answer is:

generating primitive recursive functions

74) If there exists a language L, for which there exists a TM, T, that accepts every word in L and either rejects or loops for every word that is not in L, is called

recursive

recursively enumerable

NP-HARD

none of these

Answer is:

recursively enumerable

Theory of Computation MCQ with Answers

For more MCQ's Click Here

70) If f : N--> N. If L can be recognized by a TM T, so thatτT(n)≤ f (n) for all but finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).

L ∈Time (f)

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

71) Let s is a step-counting function satisfying s(n) ≥n, and L be a language accepted by a (multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes for an input string of length n, then T∈

Space(s)

72) Which of the following statements is false ?

Given two regular grammars G1G2 and it is undecidable whether L (G1) = L (G2)

73) Bounded minimalization is a technique for

generating primitive recursive functions

74) If there exists a language L, for which there exists a TM, T, that accepts every word in L and either rejects or loops for every word that is not in L, is called

recursively enumerable

Theory of Computation MCQ with Answers