GATE CSE 1996 | Question: 1.9

Question

Which of the following statements is false?

• A. The Halting Problem of Turing machines is undecidable

• B. Determining whether a context-free grammar is ambiguous is undecidable

• C. Given two arbitrary context-free grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$

• D. Given two regular grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$

Comments

https://gatecse.in/grammar-decidable-and-undecidable-problems/

---

option c is decidable for Deterministic context free grammar

---

Click for Video Solution

Answer 1

Answer is D.

Equivalence of Regular languages is decidable.

1. Membership,
2. Emptiness,
3. Finiteness,
4. Equivalence,
5. Ambiguity,
6. Regularity,
7. Everything,
8. Disjointedness...

All are decidable for Regular languages.

First $3$ for CFL.

Only $1$^st for CSL and REC.

None for RE.

Comments

http://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems

---

Updated link: https://gatecse.in/grammar-decidable-and-undecidable-problems/

---

But if w is a member of a TM is undecidable. Isnt that the halting problem?

Answer 2

A) halting problem of turing machine are undecidable.

B) Ambiguty problem of CFG  are undecidable

C) equvalance problem of CFG is undecidable

d)  equvalance problem of regular grammar is decidable

so option d is correct option