This question was previously asked in

GATE CS 2021 Official Paper: Shift 1

Option :

IBPS SO IT Officer Mains: Full Mock Test

4845

60 Questions
60 Marks
45 Mins

__ Answer__: Option 1

__ Explanation__:

__ Option 1__:L = { \(\left\langle M \right\rangle \) | M is a PDA such that L(M) = ∑*}

This is __ not Recursive.__ As completeness Problem is Undecidable for CFL and Hence no algorithm exists to decide whether or not the Language of PDA is ∑

** Option 2**: L = { \(\left\langle M \right\rangle \) | M is a DFA such that L(M) = Φ}

This is **Recursive**. for DFA accept empty language Algorithm exists

** Option 3**: L = { \(\left\langle M \right\rangle \) | M is a PDA such that L(M) = Φ}

This is also __ Recursive__. for a CFL to checking for empty language problem is decidable. Hence there exists an algorithm to decide whether a PDA accepts empty language or not.

** Option 4**:L = { \(\left\langle M \right\rangle \) | M is a DFA such that L(M) = ∑*}

This is also __Recursive.__ Completeness problem for regular language is decidable.