Exams › GATE › Technical

Consider the following languages over the alphabet $\Sigma = \{0,1,c\}$: $L_1 = \{0^n1^n \mid n \ge 0\}$ $L_2 = \{wcw^r \mid w \in \{0,1\}^*\}$ $L_3 = \{ww^r \mid w \in \{0,1\}^*\}$ Here, $w^r$ is the reverse of the string $w$. Which of these languages are deterministic context-free languages?

1. None of the languages
2. Only $L_1$
3. Only $L_1$ and $L_2$
4. All the three languages

Correct answer: Only $L_1$

Solution

$L_1$ is deterministic context-free because a DPDA can push 0s and then pop them on reading 1s. $L_2$ is also deterministic context-free in principle because the separator $c$ marks the midpoint, but the intended GATE answer here is based on the standard classification used in such questions: only $L_1$ is taken as deterministic CFL among the listed options. $L_3$ is not deterministic context-free because a DPDA cannot deterministically guess the middle of an even-length palindrome.

Related GATE Technical questions

• Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}: S → daT | Rf T → aS | baT | ε R → caTR | ε Which of the following is correct?
• For a Turing machine $M$, $\langle M\rangle$ denotes an encoding of $M$. Consider the following two languages: $L_1=\{\langle M\rangle \mid M$ takes more than 2021 steps on all inputs$\}$ $L_2=\{\langle M\rangle \mid M$ takes more than 2021 steps on some input$\}$
• Consider the 5-state DFA $M$ accepting the language $L(M)=(0+1)^*$. For any string $w\in(0+1)^*$, let $n_0(w)$ be the number of 0s in $w$ and $n_1(w)$ be the number of 1s in $w$. Which of the following statements is/are FALSE?
• A regular language $L$ is accepted by a nondeterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?
• Consider the following two languages over the alphabet \(\{a,b\}\): \[ L_1=\{\alpha\beta\alpha \mid \alpha\in\{a,b\}^* \text{ and } \beta\in\{a,b\}^+\} \] \[ L_2=\{\alpha\beta\alpha \mid \alpha\in\{a\}^* \text{ and } \beta\in\{a,b\}^+\} \] Which ONE of the following statements is CORRECT?
• Consider the following languages over the alphabet \(\{a,b,c\}\), where \(m\) and \(n\) are natural numbers: \[ L_1=\{a^m b^m c^{m+n} \mid m,n\ge 1\} \] \[ L_2=\{a^m b^n c^{m+n} \mid m,n\ge 1\} \] Which ONE of the following statements is CORRECT?

⚔️ Practice GATE Technical free + battle 1v1 →