-
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 and 2
- 1 and 4
- 2 and 3
- 2 and 4
- 1 and 2
Correct Option: B
Statement 1 Decidable : The algorithm can be used to check the finiteness/infiniteness on the DFA and also the two given DFAs, a product DFA can be constructed.
Statement 2 Undecidable : It is not decidable since the language is context-free.
Statement 3 Undecidable : It is also undecidable that whether two push-down automata accept the same language.
Statement 4 Decidable : If the LHS of each production has one and only one variable then it is a context-free grammar.
