Question Details

Let G1 ,G2 be Context Free Grammars (CFGs) and RR 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?

Options

A

Is L(G1) = L(G2)?

B

Is L(G1) ∩ L(G2)=∅?

C

Is L(G1)=L(R)?

D

Is L(G1)=∅?

Show Answer
Correct Answer
D
Is L(G1)=∅?

Solution :

The correct option is: Is L(G1)=∅?

To understand why this question is decidable, let us analyze the properties of Context-Free Grammars (CFGs) and the languages they generate, and examine the decidability of each of the options provided.

1. Decidability of Emptiness for CFGs (Is L(G1)=∅?)
The emptiness problem for Context-Free Grammars asks whether a given CFG G1 generates any string at all, i.e., whether L(G1)=∅.
This problem is decidable. We can determine if the language is empty by using a simple algorithm that finds all generating variables in the grammar:
- A variable A is generating if it can derive a terminal string (i.e., A⇒*w where w∈Σ*).
- We start by marking all terminal symbols as generating.
- We then iteratively mark a variable A as generating if there is a production rule A→X where all symbols in X are already marked as generating.
- This process continues until no new variables can be marked. If the start symbol of the grammar is marked as generating, then L(G1)≠∅; otherwise, L(G1)=∅.
Since this algorithm is guaranteed to terminate in finite steps, the emptiness problem for CFGs is decidable.

2. Why the other options are undecidable:
- Is L(G1)=L(G2)?: The equivalence problem for two CFGs is a classic undecidable problem. There is no algorithm that can determine if two arbitrary CFGs generate the same language.
- Is L(G1)∩L(G2)=∅?: The intersection-emptiness problem for two CFGs is also undecidable. This can be proven by reduction from the Post Correspondence Problem (PCP).
- Is L(G1)=L(R)?: Testing whether a context-free language is equal to a regular language is undecidable. Specifically, testing whether L(G1)=Σ* (the universality problem for CFGs, where L(R)=Σ* is a regular language) is undecidable.

Therefore, the only question among the choices that can be decided by an algorithm in all cases is "Is L(G1)=∅?".

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: