Let \(๐บ_1, ๐บ_2 \) be Context Free Grammars (CFGs) and \(๐ \) be a regularโฆ
2025
Letย \(๐บ_1, ๐บ_2 \) be Context Free Grammars (CFGs) andย \(๐
\) be a regular expression. For a grammar \(G\), letย \(๐ฟ(๐บ)\) denote the language generated by \(G\).
Which ONE among the following questions is decidable?
- A.
\(Is ๐ฟ(๐บ_1) = ๐ฟ(๐บ_2)?\) - B.
\(Is ๐ฟ(๐บ_1) โฉ ๐ฟ(๐บ_2) = โ ?\) - C.
\(Is ๐ฟ(๐บ_1) = ๐ฟ(๐ )?\) - D.
\(Is ๐ฟ(๐บ_1) = โ ?\)
Attempted by 81 students.
Show answer & explanation
Correct answer: D
Answer: The only decidable question among the list is "Is L(G1) = โ ?"
Why this is decidable:
There is a standard algorithm to decide emptiness of a context-free grammar.
Algorithm (marking/generating-variable method):
Initialize a set M of nonterminals that have a production whose right-hand side is composed entirely of terminals.
Repeat: add any nonterminal A to M if there is a production A โ ฮฑ where every symbol of ฮฑ is either a terminal or already in M.
When no new nonterminals can be added, check whether the start symbol is in M. If it is, the grammar generates at least one string (so L(G) โ โ ); otherwise L(G) = โ .
Why the other questions are not decidable (sketches):
Equivalence of two arbitrary context-free grammars is undecidable. There is no algorithm that decides for every pair of CFGs whether they generate the same language.
Emptiness of the intersection of two context-free languages is undecidable. Deciding whether L(G1) โฉ L(G2) is empty is known to be an undecidable problem.
Equality between an arbitrary context-free language and a given regular language is not generally decidable; there is no uniform algorithm that solves this equality test in all cases.
Therefore the decidable question among the provided choices is the emptiness test for a single CFG.
A video solution is available for this question โ log in and enroll to watch it.