ExamSIDE
Questions (Powered by ExamGOAL)
Theory of Computation
Finite Automata and Regular Language
Marks 1Marks 2Marks 5
Push Down Automata and Context Free Language
Marks 1Marks 2
Undecidability
Marks 1Marks 2
Recursively Enumerable Language and Turing Machine
Marks 1Marks 2
Previous Next
1
GATE CSE 2008
MCQ (Single Correct Answer)
+1
-0.3
Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?
A
It is not accepted by a Turing machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free, but accepted by a Turing machine
2
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-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?
A
$$L$$ is necessarily finite
B
$$L$$ is regular but not necessarily finite
C
$$L$$ is context free but not necessarily regular
D
$$L$$ is recursive but not necessarily context free
3
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-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?

A
$$L$$ is recursive
B
$$L$$ is recursively enumerable but not recursive
C
$$L$$ is not recursively enumerable
D
Whether $$L$$ is recursive or not will be known after we find out if $$P=NP.$$
4
GATE CSE 1998
MCQ (Single Correct Answer)
+1
-0.3
Regarding the power of recognition of languages, which of the following statement is false?
A
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
B
Non-deterministic Push-down automata are equivalent to deterministic Push-down automata.
C
Non-deterministic Turing machines are equivalent to deterministic Turing machines.
D
Multi-tape Turing machines are equivalent to Single-tape Turing machines.
Previous Next
Questions Asked from Marks 1
GATE CSE 2022 (1) GATE CSE 2020 (1) GATE CSE 2016 Set 2 (1) GATE CSE 2015 Set 2 (1) GATE CSE 2015 Set 1 (1) GATE CSE 2014 Set 2 (1) GATE CSE 2013 (1) GATE CSE 2008 (1) GATE CSE 2003 (2) GATE CSE 1998 (1) GATE CSE 1992 (3)
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization