GATE CSE 2025 Set 1 | Push Down Automata and Context Free Language Question 4 | Theory of Computation

GATE CSE 2025 Set 1

MCQ (Single Correct Answer)

-0.33

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (nonterminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as:

$$\begin{aligned} & S \rightarrow a a B \mid A b b \\ & A \rightarrow a \mid a A \\ & B \rightarrow b \mid b B \end{aligned}$$

Which ONE of the languages $L(G)$ is accepted by $G$ ?

$L(G)=\left\{a^2 b^n \mid n \geq 1\right\} \cup\left\{a^n b^2 \mid n \geq 1\right\}$

$L(G)=\left\{a^n b^{2 n} \mid n \geq 1\right\} \cup\left\{a^{2 n} b^n \mid n \geq 1\right\}$

$L(G)=\left\{a^n b^n \mid n \geq 1\right\}$

$L(G)=\left\{a^{2 n} b^{2 n} \mid n \geq 1\right\}$

GATE CSE 2021 Set 2

MCQ (More than One Correct Answer)

-0

Let L₁ be a regular language and L₂ be a context-free language. Which of the following languages is/are context-free?

L₁ ∩ L̅₂

L₁ ∪ (L₂ ∪ L̅₂)

$$\overline {{{\bar L}_1} \cup {{\bar L}_2}} $$

(L₁∩ L₂) ∪ (L̅₁ ∩ L₂)

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.33

Suppose that L₁ is a regular and L₂ is a context-free language, Which one of the following languages is NOT necessarily context-free?

L₁ ⋅ L₂

L₁ ∪ L₂

L₁ ∩ L₂

L₁ - L₂

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0

Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

L = { $$\left\langle M \right\rangle $$ | M is a PDA such that L(M) = ∑*}

L = { $$\left\langle M \right\rangle $$ | M is a DFA such that L(M) = Φ}

L = { $$\left\langle M \right\rangle $$ | M is a PDA such that L(M) = Φ}

L = { $$\left\langle M \right\rangle $$ | M is a DFA such that L(M) = ∑*}

PREVIOUS NEXT