Which of the following are decidable ?
1) whether the intersection of two regular language is infinite.
2) whether a give 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 possible to construct a finite automaton for the intersection and then check if this automaton accepts an infinite number of strings (e.g., by checking for cycles in its state graph).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 \rightarrow \alpha$, where $A$ is a single non-terminal and $\alpha$ is a string of terminals and/or non-terminals), which can be checked algorithmically.

Which of the Following Are Decidable