1
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
Consider the languages $${L_1}$$, $${L_2}$$ and $${L_3}$$ are given below. $$$\eqalign{ & {L_1} = \left\{ {{0^p}{1^q}\left| {p,q \in N} \right.} \right\} \cr & {L_2} = \left\{ {{0^p}{1^q}\left| {p,q \in N} \right.\,\,and\,\,p = q} \right\}\,\,and \cr & {L_3} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r\, \in N\,\,\,and\,\,\,p = q = r} \right.} \right\}. \cr} $$$

Which of the following statements is not TRUE?

A
Pushdown automata $$(PDA)$$ can be used to recognize $${L_1}$$ and $${L_2}$$
B
$${L_1}$$ is a regular language
C
All the three languages are context free
D
Turing machines can be used to recognize all the languages
2
GATE CSE 2010
MCQ (Single Correct Answer)
+2
-0.6
Consider the languages $$$\eqalign{ & {L_1} = \left\{ {{0^i}{1^j}\,\left| {i \ne j} \right.} \right\},\,{L_2} = \left\{ {{0^i}{1^j}\,\left| {i = j} \right.} \right\}, \cr & {L_3} = \left\{ {{0^i}{1^j}\,\left| {i = 2j + 1} \right.} \right\}, \cr & {L_4} = \left\{ {{0^i}{1^j}\,\left| {i \ne 2j} \right.} \right\}, \cr} $$$
A
only $${L_2}$$ is context free
B
only $${L_2}$$ and $${L_3}$$ are context free
C
only $${L_1}$$ and $${L_2}$$ are context free
D
all are context free
3
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Which of the following statement is false?
A
Every $$NFA$$ can be converted to an equivalent $$DFA$$
B
Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine.
C
Every regular language is also a context- free language
D
Every subset of a recursively enumerable set is recursive
4
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Match the following List-$${\rm I}$$ with List - $${\rm II}$$

List-$${\rm I}$$
$$E)$$ Checking that identifiers are declared before their
$$F)$$ Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function
$$G)$$ Arithmetic expression with matched pairs of parentheses
$$H)$$ Palindromes

List-$${\rm II}$$
$$P)$$ $$L = \left\{ {{a^n}{b^m}{c^n}{d^m}\,|\,n \ge 1,m \ge 1} \right\}$$
$$Q)$$ $$X \to XbX\,|\,XcX\,|\,dXf\,|g$$
$$R)$$ $$L = \left\{ {www\,|\,w \in \left( {a\,|\,b} \right){}^ * } \right\}$$
$$S)$$ $$X \to bXB\,|\,cXc\,|\,\varepsilon $$

A
$$E - P,\,F - R,\,G - Q,\,H - S$$
B
$$E - R,\,F - P,\,G - S,\,H - Q$$
C
$$E - R,\,F - P,\,G - Q,\,H - S$$
D
$$E - P,\,F - R,\,G - S,\,H - Q$$

GATE CSE Subjects

Browse all chapters by subject

Software Engineering
Web Technologies