68) Which of the following is not primitive recursive but partially recursive ?

Carnot's function

Ricmann function

Bounded function

Ackermann's function

Answer is:

Ackermann's function

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

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

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)

Theory of Computation MCQ with Answers

For more MCQ's Click Here

68) Which of the following is not primitive recursive but partially recursive ?

Ackermann's function

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

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

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)

Theory of Computation MCQ with Answers