Which one of the following problems is undecidable?

Deciding if a given context-free grammar is ambiguous.
Deciding if a given string is generated by a given context-free grammar.
Deciding if the language generated by a given context-free grammar is empty.
Deciding if the language generated by a given context-free grammar is finite.

Correct answer: Deciding if a given context-free grammar is ambiguous.

Solution

Ambiguity checking for a context-free grammar is undecidable. In contrast, membership, emptiness, and finiteness for context-free languages are decidable problems. Hence the first option is correct.

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 →