Which of the following are decidable?
1) Whether the intersection of two regular language 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.
A)1 and 2
B)1 and 4
C)2 and 3
D)2 and 4

Question

Quizplus · Accepted Answer

1) The intersection of two regular languages is decidable because regular languages are closed under intersection, and it is decidable whether a regular language is infinite by constructing its minimal DFA and checking for cycles.4) Determining whether a given grammar is context-free is decidable because the definition of a context-free grammar is based on specific rules (productions of the form A → α, where A is a single non-terminal and α is a string of terminals and/or non-terminals), which can be checked algorithmically.

Which of the Following Are Decidable