Assume the statements S₁ and S₂ given as: S₁: Given a context free grammar G,…
2013
Assume the statements S₁ and S₂ given as:
S₁: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite
S₂: There exists an algorithm to determine whether two context free grammars generate the same language
Which of the following is true?
- A.
S₁ is correct and S₂ is not correct
- B.
Both S₁ and S₂ are correct
- C.
Both S₁ and S₂ are not correct
- D.
S₁ is not correct and S₂ is correct
Attempted by 14 students.
Show answer & explanation
Correct answer: A
Statement S₁ is true because the infiniteness problem for context-free grammars is decidable. This can be determined by checking for cyclic derivations among non-terminals. Statement S₂ is false because the equivalence problem for context-free grammars is undecidable. No algorithm exists to determine if two arbitrary CFGs generate the exact same language.
A video solution is available for this question — log in and enroll to watch it.