6,827 views

Which of the following statements is false?

1. The Halting Problem of Turing machines is undecidable

2. Determining whether a context-free grammar is ambiguous is undecidable

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

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

option c is decidable for Deterministic context free grammar

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.

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

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

1
8,159 views