# GATE 1996 Question - Mark 1

## 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 undecidbale.

(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}).

Total 6 Questions

×

## Correct Option is :

D

## Explanation

Case (a):

The Halting Problem for TM is un-decidable problem.By un-decidable means no algorithm exist for it.

Case (b):

Ambiguity in a CFG is undecidable.No algorithm can decide if a CFG is ambiguous.By ambiguous means the CFG has two or more derivations for some sentence.

Case (c):

The equivalance problem of CFGs is undecideable.We have no algorithm to decide if two CFGs generate the same language.

Case (d):

The regular sets are a well behaved class of languages.Practically everything about Regular Language is decidable.

## Connect with Us: