Question

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 grammer is context-free

• A. 2 and 3
• B. 1 and 2
• C. 1 and 4
• D. 2 and 4

Answer 1

The correct option is C 1 and 4

1. "Intersection of two regular languages a infinite" is decidable, since we can construct a product dfa of the 2 given dfas and then using the algorithm to check finiteness or infiniteness on this dfa, we can solve the problem.
2. "Whether a given CFL is regular" is undecidable.
3. "Whether two PDA's accept the same language" is undecidable, since equivalence of CFL's is undecidable.
4. "Whether a given grammar is context-free" is decidable since we can easily check using a TM, whether the LHS of every productive has a single variable and, then it is a CFG's else it is not a CFG.
$\therefore$ 1 and 4 are decidable.