Question:
Which one of the following problems is undecidable?
Which one of the following problems is undecidable?
Show Hint
Ambiguity checking for context-free grammars is undecidable, while membership and emptiness problems are decidable.
Updated On: Feb 8, 2026
- Deciding if a given context-free grammar is ambiguous
- Deciding if a given string can be 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
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
Step 1: Understanding decidability.
A problem is decidable if there exists an algorithm that always terminates with a correct yes or no answer for all inputs.
Step 2: Analyzing each option.
Deciding whether a string belongs to a CFG language is decidable using parsing algorithms like CYK.
Checking whether a CFG generates an empty language is decidable.
Checking whether a CFG generates a finite language is also decidable.
Step 3: Identifying the undecidable problem.
Determining whether a context-free grammar is ambiguous is a well-known undecidable problem in formal language theory. There is no algorithm that can solve this for all CFGs.
Step 4: Final conclusion.
Hence, the undecidable problem is deciding whether a given context-free grammar is ambiguous.
A problem is decidable if there exists an algorithm that always terminates with a correct yes or no answer for all inputs.
Step 2: Analyzing each option.
Deciding whether a string belongs to a CFG language is decidable using parsing algorithms like CYK.
Checking whether a CFG generates an empty language is decidable.
Checking whether a CFG generates a finite language is also decidable.
Step 3: Identifying the undecidable problem.
Determining whether a context-free grammar is ambiguous is a well-known undecidable problem in formal language theory. There is no algorithm that can solve this for all CFGs.
Step 4: Final conclusion.
Hence, the undecidable problem is deciding whether a given context-free grammar is ambiguous.
Was this answer helpful?
0
0
Top OJEE Computer Science & Information Technology Questions
- How many null links does an arbitrary binary tree with $n$ nodes have?
- Which one of the following recurrence relations best represents the time complexity of the binary search algorithm running on an ordered array of $n$ elements?
- Consider the following C function foo(int n). How many times does foo(2) get called on making the call foo(5)?
C Function:
float foo(int n){ if(n <= 2) return 1; else return (2*foo(n-1) + 3*foo(n-2)); } - Suppose in a time-shared operating system, a certain process is performing I/O. It must be in which one of the following states?
- Consider a processor that generates 32-bit virtual addresses. It uses a direct mapped cache whose size is 32 KByte and has 32 Byte blocks. What is the number of bits needed for cache addressing?
View More Questions
Top OJEE Theory of Computations Questions
Consider the grammar $S \rightarrow aSa \mid bSb \mid a \mid b$. Which one of the following options correctly characterizes the language generated by the given grammar over the alphabet {a,b}
- To prove that a problem $\chi$ in NP is NP-complete, it would be sufficient to show which one of the following to be true?
Top OJEE Questions
- In 1831, Robert Brown described
- In a stationary wave all the particies
- In brain lateral ventricle is connected to diocoel by
- In genetic engineering experiment, DNA fragments are joined by
- In glycolytic pathway which of the following steps shows reduction of co-enzyme ?
View More Questions