1
GATE CSE 2013
+2
-0.6
Consider the $$DFA$$ $$A$$ given below.

Which of the following are FALSE?
$$1.$$ Complement of $$L(A)$$ is context - free.
$$2.$$ $$L(A)$$ $$= \left( {{{11}^ * }0 + 0} \right)\left( {0 + 1} \right){}^ * {0^ * }\left. {{1^ * }} \right)$$
$$3.$$ For the language accepted by $$A, A$$ is the minimal $$DFA.$$
$$4.$$ $$A$$ accepts all strings over $$\left\{ {0,1} \right\}$$ of length at least $$2.$$

A
$$1$$ and $$3$$ only
B
$$2$$ and $$4$$ only
C
$$2$$ and $$3$$ only
D
$$3$$ and $$4$$ only
2
GATE CSE 2011
+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 3 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 Which of the following finite state machines is a valid minimal $$DFA$$ which accepts the same languages as $$D?$$ A B C D 4 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
GATE CSE Subjects
EXAM MAP
Medical
NEET