Discussion
Let \(G_{1}\), \(G_{2}\) be Context Free Grammars (CFGs) and \(R\) be a regular expression. For a grammar \(G\), let \(L(G)\) denote the language generated by \(G\).
Which ONE among the following questions is decidable?
Answer: D
The decidable question is: Is \(L(G_{1}) = \emptyset\)?
Emptiness of a context-free grammar is decidable: mark every terminal as generating, then repeatedly mark a variable as generating if some production rewrites it into generating symbols only. The language is empty exactly when the start symbol is never marked. This runs in polynomial time.
The other three are undecidable. Equivalence of two CFGs, emptiness of the intersection of two context-free languages, and whether a CFG generates the same language as a given regular expression (which includes the undecidable question of whether a CFG generates everything, Σ*) are classic undecidable problems, proved by reduction from the Post correspondence problem.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development