1
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+1
-0.3
Language $${L_1}$$ is defined by the grammar: $$S{}_1 \to a{S_1}b|\varepsilon $$
Language $${L_2}$$ is defined by the grammar: $$S{}_2 \to ab{S_2}|\varepsilon $$

Consider the following statements:
$$P:$$ $${L_1}$$ is regular
$$Q:$$ $${L_2}$$ is regular

Which one of the following is TRUE?

A
Both $$P$$ and $$Q$$ are true
B
$$P$$ is true and $$Q$$ is false
C
$$P$$ is false and $$Q$$ is true
D
Both $$P$$ and $$Q$$ are false
2
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+1
-0.3
Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which of the following is/are TRUE?

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\overline {{L_3}} \cup {L_4}$$ is recursively enumerable
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ $$\overline {{L_2}} \cup {L_3}$$ is recursive
$$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ $$L_1^ * \cap {L_2}$$ is context-free
$$\,\,\,{\rm I}V.\,\,\,\,\,\,\,$$ $${L_1} \cup \overline {{L_2}} $$ is context-free

A
$${\rm I}$$ only
B
$${\rm I}$$ and $${\rm III}$$ only
C
$${\rm I}$$ and $${\rm IV}$$ only
D
$${\rm I},$$ $${\rm II}$$ and $${\rm III}$$ only
3
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Consider the following two statements:

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting states then the language accepted by the
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$NFA$$ is $$\sum {^ * } .$$
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,$$ There exists a regular language $$A$$ such that for all languages $$B,A \cap B$$ is
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ regular.

Which one of the following is CORRECT?

A
Only $${\rm I}$$ is true
B
Only $${\rm II}$$ is true
C
Both $${\rm I}$$ and $${\rm II}$$ are true
D
Both $${\rm I}$$ and $${\rm II}$$ are false
4
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Consider the following languages: $$$\eqalign{ & {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^n}{b^n}{c^{2n}}:n \ge 1} \right\} \cr} $$$

Which one of the following is TRUE?

A
Both $${L_1}$$ and $${L_2}$$ are context-free.
B
$${L_1}$$ is context-free while $${L_2}$$ is not context-free.
C
$${L_2}$$ is context-free while $${L_1}$$ is not context-free.
D
Neither $${L_1}$$ nor $${L_2}$$ is context-free.
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12