1
GATE CSE 1998
+2
-0.6
Which of the following statements is false?
A
Every finite subset of a non-regular set is regular
B
Every subset of a regular set is regular
C
Every finite subset of a regular set is regular
D
The intersection of two regular sets is regular
2
GATE CSE 1997
+2
-0.6
Which of the following languages over $$\left\{ {a,b,c} \right\}$$ is accepted by Deterministic push down automata?
A
$$\left\{ {w \subset {w^R}\left| {w \in \left\{ {a,b} \right\}{}^ * } \right.} \right\}$$
B
$$\left\{ {w{w^R}\left| {w \in \left\{ {a,b,c} \right\}{}^ * } \right.} \right\}$$
C
$$\left\{ {{a^n}{b^n}{c^n}\left| {n \ge 0} \right.} \right\}$$
D
$$\left\{ {w\left| w \right.} \right.$$ is palindrome over $$\left. {\left\{ {a,b,c} \right\}} \right\}$$
3
GATE CSE 1996
+2
-0.6
If $${L_1}$$ and $${L_2}$$ are context free languages and $$R$$ a regular set, one of the languages below is not necessarily a context free language. Which one?
A
$${L_1}$$$${L_2}$$
B
$${L_1}\, \cap \,{L_2}$$
C
$${L_1}\, \cap \,R$$
D
$${L_1}\, \cup \,{L_2}$$
4
GATE CSE 1996
Subjective
+2
-0
Let $$G$$ be a context free grammar where $$G = \left( {\left\{ {S,A,.B,C} \right\},\left\{ {a,b,d} \right\},P,S} \right)$$ with productions $$P$$ given below
\eqalign{ & S \to ABAC\,\,\,\,\,\,\,\,\,S \to aA{\mkern 1mu} \left| \varepsilon \right. \cr & S \to bB{\mkern 1mu} \left| \varepsilon \right.\,\,\,\,\,\,\,\,\,\,\,\,\,\,C \to d \cr}

($$\varepsilon$$ denotes the null string). Transform the given grammar $$G$$ to an equivalent context- free grammar $${G^1}$$ that has no $$\varepsilon$$ productions ($$A$$ unit production is of the from $$x \to y,\,x$$ and $$y$$ are non terminals).

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