Project ForgeWhich of the following are decidable?
I. Whether the intersection of two regular languages is infinite. II. Whether a given context-free language is regular. III. Whether two push-down automata accept the same language. IV. Whether a given grammar is context-free.
- AI and II
- I and IV
- CII and III
- DII and IV
Explanation
I is decidable (build the product automaton for the two regular languages, then check reachability of an accepting state from a cycle — a decidable graph property). II (is an arbitrary CFL regular?) is undecidable in general. III (CFL/PDA equivalence) is undecidable in general. IV (checking that a grammar's productions syntactically conform to context-free form) is a purely structural/syntactic check — trivially decidable. So I and IV are decidable.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.