Theory of Computation (3160704) MCQs

MCQs of Computable Functions

Showing 11 to 19 out of 19 Questions
1 2
11.
The decision problem is the function from string to _________
(a) Char
(b) Int
(c) Boolean
(d) None of the mentioned
Answer:

Option (c)

12.
An algorithm is called efficient if it runs in _________ time on a serial computer.
(a) Polynomial
(b) Non polynomial
(c) Logarithmic
(d) None of the mentioned
Answer:

Option (a)

13.
Every recursive language is recursively enumerable
(a) True
(b) False
(c) May be
(d) Can’t say
Answer:

Option (a)

14.
If L1 and L2 are both recursively enumerable languages over ∑, then
(a) L1 ∪ L2 is recursively enumerable
(b) L1 ∩ L2 is recursively enumerable.
(c) Both A and B
(d) None of these
Answer:

Option (c)

15.
Statement: function f(x, y) = x + y is primitive recursive
(a) True
(b) False
(c) Can’t say
(d) May be
Answer:

Option (a)

16.
F: Ʃ1*→Ʃ2*. Then f is computable if and only if f is
(a) Computable
(b) μ-recursive
(c) Decidable
(d) None of the mentioned
Answer:

Option (b)

17.
If L and L' are recursively enumerable, then L is
(a) Regular
(b) Context-free
(c) Context sensitive
(d) Recursive
Answer:

Option (d)

18.
Which of the following is true?
(a) The complement of a recursive language is either recursive or recursively enumerable
(b) The complement of a recursive language is recursive
(c) The complement of a recursively enumerable language is recursively enumerable
(d) The complement of a context-free language is context-free
Answer:

Option (b)

19.
Recursive languages are:
(a) A proper superset of CFG
(b) Always recognized by PDA
(c) Recognized by Turing machine
(d) Also called type 0 language
Answer:

Option (c)

Showing 11 to 19 out of 19 Questions
1 2