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
1
GATE CSE 2010
MCQ (Single Correct Answer)
+1
-0.3
Let $${L_1}$$ recursive language. Let $${L_2}$$ and $${L_3}$$ be languages that are recursively enumerable but not recursive. Which of the following statement is not necessarily true?
A
$${L_2}$$ $$-$$ $${L_1}$$ is recursively enumerable.
B
$${L_1}$$ $$-$$ $${L_3}$$ recursively enumerable.
C
$${L_2} \cap {L_1}$$ is recursively enumerable.
D
$${L_2} \cup {L_1}$$ is recursively enumerable.
2
GATE CSE 2009
MCQ (Single Correct Answer)
+1
-0.3
Which one of the following languages over the alphabet $$\left\{ {0,\left. 1 \right)} \right.$$ is described by the regular expression $${\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^ * }$$
A
The set of all strings containing the substring $$00$$
B
The set of all strings containing at most two $$0’$$s
C
The set of all strings containing at least two $$0’$$s
D
The set of all strings that begin and end with either $$0$$ or $$1$$
3
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-0.3
The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ * $$denotes the same set as
A
$$\left( {{1^ * }0} \right){}^ * {1^ * }$$
B
$$0 + \left( {0 + 10} \right){}^ * $$
C
$$\left( {0 + 1} \right){}^ * 10\left( {0 + 1} \right){}^ * $$
D
None of the above.
4
GATE CSE 2003
MCQ (Single Correct Answer)
+1
-0.3
Consider the set $$\sum {^ * } $$ of all strings over the alphabet $$\,\sum { = \,\,\,\left\{ {0,\,\,\,1} \right\}.\sum {^ * } } $$ with the concatenation operator for strings
A
Does not from a group
B
Forms a non-commutative group
C
Does not have a right identity element
D
Forms a group if the empty string is removed from $${\sum {^ * } }$$
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