69) Turing machine (TM) is more powerful than FMS (Finite State Machine) because

tape movement is confined to one direction

it has no finite state

it has the capability to remember arbitrarily long sequences of input symbols

none of these

Answer is:

it has the capability to remember arbitrarily long sequences of input symbols

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)

L ∈ Time(cf)

L ∈ Time (h)

none of these

Answer is:

L ∈Time (f)

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

Theory of Computation MCQ with Answers

For more MCQ's Click Here

69) Turing machine (TM) is more powerful than FMS (Finite State Machine) because

it has the capability to remember arbitrarily long sequences of input symbols

Theory of Computation MCQ with Answers

Related 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)

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

Theory of Computation MCQ with Answers