1
GATE CSE 2012
MCQ (Single Correct Answer)
+1
-0.3
What is the complement of the language accepted by the $$NFA$$ shown below?
Assume $$\sum { = \left\{ a \right\}\,\,} $$ and $$\varepsilon $$ is the empty string. GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 97 English
A
$$\phi $$
B
$$\left\{ \varepsilon \right\}$$
C
$$a{}^ * $$
D
$$\left\{ {a,\,\,\varepsilon } \right\}$$
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 61 English
A
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 61 English Option 1
B
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 61 English Option 2
C
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 61 English Option 3
D
GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 61 English Option 4