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
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination