Let 𝐺1 and 𝐺2 be arbitrary context free languages and 𝑅 an arbitrary…
2020
Let 𝐺1 and 𝐺2 be arbitrary context free languages and 𝑅 an arbitrary regular language. Consider the following problems:
(A) Is 𝐿(𝐺1)=𝐿(𝐺2)?
(B) Is 𝐿(𝐺2)≤𝐿(𝐺1)?
(C) Is 𝐿(𝐺1)=𝑅?
Which of the problems are undecidable?
Choose the correct answer from the options given below:
- A.
(A) Only
- B.
(B) Only
- C.
(A) and (B) Only
- D.
(A), (B) and (C)
Attempted by 26 students.
Show answer & explanation
Correct answer: D
Answer: All three problems are undecidable.
Equality of the two context-free languages L(G1) and L(G2): Undecidable. This is a standard result: the equivalence problem for arbitrary context-free grammars is undecidable (it can be shown by a reduction from the Post Correspondence Problem or other known undecidable problems).
Containment of L(G2) in L(G1) (i.e., L(G2) ⊆ L(G1)): Undecidable. If containment were decidable for arbitrary context-free languages, then equivalence would be decidable by checking containment in both directions (L(G1) ⊆ L(G2) and L(G2) ⊆ L(G1)), contradicting the undecidability of equivalence.
Equality of a context-free language L(G1) with a regular language R: Undecidable. A direct reduction: if one could decide whether L(G)=R for arbitrary regular R, then taking R to be Σ* would decide whether L(G)=Σ*, i.e., universality for the context-free grammar. Universality for context-free grammars is a known undecidable problem, so equality with a regular language is undecidable.
Therefore all three questions are undecidable.
A video solution is available for this question — log in and enroll to watch it.