NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
1

GATE CSE 1996

MCQ (Single Correct Answer)
Which of the following statements is false?
A
The halting problem for Turing machine is un-decidable
B
Determining whether ambiguity a context free grammar is un-decidable
C
Given two arbitrary context free grammars $${G_1}$$ and $${G_2}$$ whether $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)$$
D
Given two regular grammars $${{G_1}}$$ and $${{G_2}},$$ it is un-decidable whether $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)$$

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 CFG's is undecideable. We have no algorithm to decide if two CFG's generate the same language.

Case (d):
The regular sets are a well behaved class of languages. Practically everything about Regular Language is decidable.
Write for Us

Do you want to write for us? Help us by contributing to our platform.

Questions Asked from Undecidability

On those following papers in Marks 1
Number in Brackets after Paper Indicates No. of Questions
GATE CSE 2016 Set 1 (1)
GATE CSE 2014 Set 3 (1)
GATE CSE 2012 (1)
GATE CSE 2008 (1)
GATE CSE 1996 (1)

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12