1
GATE CSE 2013
MCQ (Single Correct Answer)
+2
-0.6
Consider the following languages
$${L_1} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0} \right.} \right\}$$
$${L_2} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0,p \ne r} \right.} \right\}$$

Which one of the following statements is FALSE?

A
$${L_2}$$ is context-free
B
$${L_1} \cap {L_2}$$ is context-free
C
Complement of $${L_2}$$ is recursive
D
Complement of $${L_1}$$ is context-free but not regular
2
GATE CSE 2012
MCQ (Single Correct Answer)
+2
-0.6
Consider the set of strings on $$\left\{ {0,1} \right\}$$ in which, every substring of $$3$$ symbols has at most two zeros. For example, $$001110$$ and $$011001$$ are in the language, but $$100010$$ is not. All strings of length less than $$3$$ are also in the language. A partially completed $$DFA$$ that accepts this language is shown below.

The missing arcs in the $$DFA$$ are

GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 34 English
A
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 34 English Option 1
B
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 34 English Option 2
C
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 34 English Option 3
D
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 34 English Option 4
3
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
Definition of the language $$L$$ with alphabet $$\left\{ a \right\}$$ is given as following. $$L = \left\{ {{a^{nk}}} \right.\left| {k > 0,\,n} \right.$$ is a positive integer constant$$\left. \, \right\}$$

What is the minimum number of states needed in a $$DFA$$ to recognize $$L$$?

A
$$k+1$$
B
$$n+1$$
C
$${2^{n + 1}}$$
D
$${2^{k + 1}}$$
4
GATE CSE 2010
MCQ (Single Correct Answer)
+2
-0.6
Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1's} \right\},$$ i.e $$L$$ is the set of all bit strings with even number of $$1's.$$ which one of rhe regular expression below represents $$L.$$
A
$$\left( {{0^ * }{{10}^ * }1} \right){}^ * $$
B
$${0^ * }\left( {{{10}^ * }{{10}^ * }} \right){}^ * $$
C
$${0^ * }\left( {{{10}^ * }1} \right){}^ * {0^ * }$$
D
$${0^ * }\,\,1\left( {{{10}^ * }1} \right){}^ * {10^ * }$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Joint Entrance Examination
JEE MainJEE AdvancedWB JEEBITSATMHT CET
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN