1
GATE CSE 2014 Set 3
+2
-0.6
Consider the following languages over the alphabet $$\sum { = \left\{ {0,\,1,\,c} \right\}:}$$
\eqalign{ & {L_1} = \left\{ {{0^n}\,{1^n}\,\left| {n \ge } \right.0} \right\} \cr & {L_2} = \left\{ {wc{w^r}\,\left| {w \in \left\{ {0,\,1} \right\}{}^ * } \right.} \right\} \cr & {L_3} = \left\{ {w{w^r}\,\left| {w \in \left\{ {0,\,1} \right\}{}^ * } \right.} \right\} \cr}

Here, $${w^r}$$ is the reverse of the string $$w.$$ Which of these languages are deterministic Context- free languages?

A
None of the languages
B
$$(B)$$ Only $${L_1}$$
C
Only $${L_1}$$ and $${L_2}$$
D
All the three languages.
2
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
3
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
4
GATE CSE 2011
+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 GATE CSE Subjects
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination