GATE CSE 2008 | Recursively Enumerable Language and Turing Machine Question 17 | Theory of Computation

GATE CSE 2008

MCQ (Single Correct Answer)

-0.3

Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?

It is not accepted by a Turing machine

It is regular but not context-free

It is context-free but not regular

It is neither regular nor context-free, but accepted by a Turing machine

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows
$$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,\,\,Otherwise} \cr } } \right.$$

Which of the following statement is true?

$$L$$ is recursive

$$L$$ is recursively enumerable but not recursive

$$L$$ is not recursively enumerable

Whether $$L$$ is recursive or not will be known after we find out if $$P=NP.$$

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is true?

$$L$$ is necessarily finite

$$L$$ is regular but not necessarily finite

$$L$$ is context free but not necessarily regular

$$L$$ is recursive but not necessarily context free

GATE CSE 1998

MCQ (Single Correct Answer)

-0.3

Regarding the power of recognition of languages, which of the following statement is false?

The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.

Non-deterministic Push-down automata are equivalent to deterministic Push-down automata.

Non-deterministic Turing machines are equivalent to deterministic Turing machines.

Multi-tape Turing machines are equivalent to Single-tape Turing machines.