1
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$ is
A
Regular
B
Context-free but not regular
C
Context sensitive but not context free
D
Type-$$0$$ but not context sensitive
2
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
Consider the following grammar $$G:$$
$$\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr & A \to bA\,\left| {\,aB} \right. \cr & B \to bB\,\left| {\,aS\,\left| {\,a} \right.} \right. \cr} $$

Let $${N_a}\left( w \right)$$ and $${N_b}\left( w \right)$$ denote the number of $$a's$$ and $$b's$$ in a string $$w$$ respectively. The language
$$L\left( G \right)\,\,\, \subseteq \left\{ {a,b} \right\} + $$ generated by $$G$$ is

A
$$\left\{ {w\,\left| {Na\left( w \right) > 3Nb\left( w \right)} \right.} \right\}$$
B
$$\left\{ {w\,\left| {Nb\left( w \right) > 3Na\left( w \right)} \right.} \right\}$$
C
$$\left\{ {w\,\left| {Na\left( w \right) = 3k,k \in \left\{ {0,1,2,...} \right\}} \right.} \right\}$$
D
$$\left\{ {w\,\left| {Nb\left( w \right) = 3k,k \in \left\{ {0,1,2,...} \right\}} \right.} \right\}$$
3
GATE CSE 2000
MCQ (Single Correct Answer)
+2
-0.6
Consider the following decision problems:
$${P_1}$$ Does a given finite state machine accept a given string
$${P_2}$$ Does a given context free grammar generate an infinite number of stings.

Which of the following statements is true?

A
Both $${P_1}$$ and $${P_2}$$ are decidable
B
Neither $${P_1}$$ and $${P_2}$$ are decidable
C
Only $${P_1}$$ is decidable
D
Only $${P_2}$$ is decidable
4
GATE CSE 1999
MCQ (More than One Correct Answer)
+2
-0.6
If $${L_1}$$ is a context free language and $${L_2}$$ is a regular which of the following is/are false?
A
$${L_1} - {L_2}$$ is not context free
B
$${L_1} \cap {L_2}$$ is context free
C
$$ \sim {L_1}$$ is context free
D
$$ \sim {L_2}$$ is regular
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12