Log In
33 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
in Theory of Computation
edited by
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?


B). I and IV

Can someone explain option (4) how it is decidable
It is membership problem and if u check  the decidability table ,it is clearly seen that the context free languages are decidable when it comes to membership problems!

3 Answers

36 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 the 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 an undecidable property. Hence, given $2$ PDAs which is nothing but characterizing 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 \to ( V  \cup  \Sigma )^*$ which can be verified with a Turing machine. Hence, it is a decidable property..

Hence, (B) should be correct answer.

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?
21 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)

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 ?
whether a grammar is context-free or not we can determine it by checking for CFG property on the grammar, not by CYK algorithm. The CYK algorithm is used to check whether a given string could be generated by a CFG grammar or not. and YES if it were language instead of grammar that is undecidable.
1 vote
Ans is (B) I and IV

Related questions

18 votes
4 answers
Which of the following statements is false? Every NFA can be converted to an equivalent DFA Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine Every regular language is also a context-free language Every subset of a recursively enumerable set is recursive
asked Sep 12, 2014 in Theory of Computation Kathleen 3.6k views
25 votes
4 answers
19 votes
2 answers
Which of the following is true for the language $\left\{ a^p \mid p \text{ is a prime } \right \}?$ It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free, but accepted by a Turing machine
asked Sep 11, 2014 in Theory of Computation Kathleen 3.4k views
36 votes
4 answers
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes? In deadlock prevention, the request for resources is always granted if the resulting state is safe In deadlock avoidance, the request for resources is ... state is safe Deadlock avoidance is less restrictive than deadlock prevention Deadlock avoidance requires knowledge of resource requirements apriori..
asked Sep 12, 2014 in Operating System Kathleen 10.5k views