in Theory of Computation edited by
6,827 views
26 votes
26 votes

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)$

in Theory of Computation edited by
6.8k views

3 Comments

option c is decidable for Deterministic context free grammar
0
0
0
0

2 Answers

32 votes
32 votes
Best answer

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.

edited by

3 Comments

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

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

Answer:

Related questions