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

Answer: B. I and IV — 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…

  1. A.

    I and II

  2. B.

    I and IV

  3. C.

    II and III

  4. D.

    II and IV

Attempted by 34 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.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…