Which of the following are decidable? I. Whether the intersection of two…

GATE · 2008 · CS

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

  1. A.

    I and II

  2. B.

    I and IV

  3. C.

    II and III

  4. D.

    II and IV

Attempted by 57 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…