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 57 English
A
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 57 English Option 1
B
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 57 English Option 2
C
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 57 English Option 3
D
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 57 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 2011
MCQ (Single Correct Answer)
+2
-0.6
A deterministic finite automation $$(DFA)$$ $$D$$ with alphabet $$\sum { = \left\{ {a,b} \right\}} $$ is given below GATE CSE 2011 Theory of Computation - Finite Automata and Regular Language Question 44 English

Which of the following finite state machines is a valid minimal $$DFA$$ which accepts the same languages as $$D?$$

A
GATE CSE 2011 Theory of Computation - Finite Automata and Regular Language Question 44 English Option 1
B
GATE CSE 2011 Theory of Computation - Finite Automata and Regular Language Question 44 English Option 2
C
GATE CSE 2011 Theory of Computation - Finite Automata and Regular Language Question 44 English Option 3
D
GATE CSE 2011 Theory of Computation - Finite Automata and Regular Language Question 44 English Option 4
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP