1
GATE CSE 2023
MCQ (Single Correct Answer)
+2
-0.67

Consider the pushdown automation (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {$$\bot$$, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/$$\gamma$$, where c is an input symbol or $$\in $$, X is a stack symbol, and $$\gamma$$ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string $$\gamma$$ on the stack, and go to state v. In the initial configuration, the stack has only the symbol $$\bot$$ in it. The PDA accepts by empty stack.

GATE CSE 2023 Theory of Computation - Push Down Automata and Context Free Language Question 10 English

Which one of the following options correctly describes the language accepted by P?

A
$$\{ {a^m}{b^n}|1 \le m\,\mathrm{and}\,n < m\} $$
B
$$\{ {a^m}{b^n}|0 \le n \le m\} $$
C
$$\{ {a^m}{b^n}|0 \le m\,\mathrm{and}\,0 \le n\} $$
D
$$\{ {a^m}|0 \le m\} \cup \{ {b^n}|0 \le n\} $$
2
GATE CSE 2022
MCQ (More than One Correct Answer)
+2
-0

Consider the following languages:

L1 = {an wan | w $$\in$$ {a, b}*}

L2 = {wxwR | w, x $$\in$$ {a, b}*, | w | , | x | > 0}

Note that wR is the reversal of the string w. Which of the following is/are TRUE?

A
L1 and L2 are regular.
B
L1 and L2 are context-free
C
L1 is regular and L2 is context-free.
D
L1 and L2 are context-free but not regular.
3
GATE CSE 2022
MCQ (More than One Correct Answer)
+2
-0

Consider the following languages:

$$\eqalign{ & {L_1} = \{ ww|w \in \{ a,b\} *\} \cr & {L_2} = \{ {a^n}{b^n}{c^m}|m,\,n \ge 0\} \cr & {L_3} = \{ {a^m}{b^n}{c^n}|m,\,n \ge 0\} \cr} $$

Which of the following statements is/are FALSE?

A
L1 is not context-free but L2 and L2 are deterministic context-free.
B
Neither L1 nor L2 is context-free.
C
L2, L3 and L2 $$\cap$$ L3 all are context-free.
D
Neither L1 nor its complement is context-free.
4
GATE CSE 2021 Set 2
MCQ (More than One Correct Answer)
+2
-0

For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR = 10110.

Which of the following languages is/are context-free?

A
{wxwRxR | w, x ∈ {0, 1}*}
B
{wwRxxR | w, x ∈ {0, 1}*}
C
{wxwR | w, x ∈ {0, 1}*}
D
{wxxRwR | w, x ∈ {0, 1}*}
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP