Which of the following are decidable? I. Whether the intersection of two…
2008
Which 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- A.
I and II
- B.
I and IV
- C.
II and III
- D.
II and IV
Attempted by 6 students.
Show answer & explanation
Correct answer: B
Statement I is decidable because the intersection of two regular languages is regular, and we can check if it's infinite using standard algorithms. Statement IV is decidable because determining whether a given grammar is context-free involves checking its production rules, which is a syntactic property. Statement II is undecidable since it's not algorithmically possible to determine if a context-free language is regular. Statement III is undecidable because equivalence of push-down automata languages cannot be decided. Therefore, only I and IV are decidable.
A video solution is available for this question — log in and enroll to watch it.