1
GATE CSE 2015 Set 3
+2
-0.6
Which of the following languages are context-free? \eqalign{ & {L_1} = \left\{ {{a^m}{b^n}{a^n}{b^m}|m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^m}{b^n}{a^m}{b^n}|m,n \ge 1} \right\} \cr & {L_3} = \left\{ {{a^m}{b^n}|m = 2n + 1} \right\} \cr}A $${L_1}$$ and $${L_2}$$ only B $${L_1}$$ and $${L_3}$$ only C $${L_2}$$ and $${L_3}$$ only D $${L_3}$$ only 2 GATE CSE 2014 Set 3 MCQ (Single Correct Answer) +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. 3 GATE CSE 2013 MCQ (Single Correct Answer) +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 4 GATE CSE 2011 MCQ (Single Correct Answer) +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
GATE CSE Subjects
EXAM MAP
Medical
NEET