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
EXAM MAP
Medical
NEET