The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+25 votes

Which of the following are decidable?

  1. Whether the intersection of two regular languages is infinite
  2. Whether a given context-free language is regular
  3. Whether two push-down automata accept the same language
  4. Whether a given grammar is context-free
  1. I and II
  2. I and IV
  3. II and III
  4. II and IV
asked in Theory of Computation by Veteran (59.9k points) | 3k views
What if given grammar is ambiguous?

What  wuld be the ans if option D were > Whether a given language is context-free. ,


Is it option IV Membership Problem?

3 Answers

+23 votes
Best answer

Lets see options one by one :

  1. The language here will be regular as intersection of regular languages will lead to regular language only..And we know that given a regular language , whether it is finite or not is a decidable problem..This can be seen by observing the DFA..If DFA contains a state which contains a loop and that state is reachable from start state and that state is either a final state or leading to final state , then the language will be infinite..
  2. The regularity property is undecidable for context free languages..Hence it is undecidable..Details regarding this :
  3. Now equivalence of two CFLs is also undecidable property..Hence given $2$ PDAs which is nothing but characterising CFLs , whether the $2$ CFLs will be same or not cannot be decided..
  4. Given a grammar , it is context free iff its productions are of the type V --> ( V  U  Σ )* .....Hence it is a decidable property..

Hence, B) should be correct answer..

answered by Veteran (101k points)
edited by
"This can be seen by observing the DFA..If DFA contains a state which contains a loop" there should be a mechanical solution to this problem. we have eyes so we can know that there is a loop in DFA but how a m/c will recognize it?
+19 votes
(1) Intersection of two regular languages is regular. And checking if a regular language is infinite is decidable.

(2) Undecidable

(3) Undecidable

(4) Decidable as we just have to check if the grammar obeys the rules of CFG. (Obviously undecidable had it been language instead of grammar)

answered by Boss (18.2k points)
why 3 is undecidable ??

Can't we draw the PDA's for two languages and compare the two PDA's ??
How do we go about solving such questions ?
We need to learn the decidable and undecidable properties as such or is there any logic behind this ?
(c) equality problem is undecidable for all languages except for FA ( regular languages )
(d) is decidable - CYK algorithm
Why (2) is undecidable? if we simplify the CFG and compare the resulting grammar with chomsky form for RL then we can tell about it.
Sir, In point no. 4. How can you say that checking if language is context-free is undecidable ?

Can't we make a PDA and check ?
+1 vote
Ans is (B) I and IV
answered by Loyal (6.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,443 questions
53,648 answers
70,908 users