Let \(⟨M⟩\) denote an encoding of an automaton \(M\). Suppose that Σ={0,1}.…

PYQ GATE 2021

Let ⟨M⟩⟨M⟩ denote an encoding of an automaton MM. Suppose that Σ={0,1}. Which of the following languages is/are NOT recursive?

  1. A.

    L={⟨M⟩L = \{⟨M⟩∣M∣ Mis a DFA such thatis \ a \ DFA \ such \ thatL(M)=∅} L(M)=∅\}

  2. B.

    L={⟨M⟩∣M is a DFA such that L(M)=Σ∗}L = \{{⟨M⟩ ∣ M \ is\ a\ DFA\ such\ that \ L(M)=Σ^*}\}

  3. C.

    L={⟨M⟩∣M is a PDA such that L(M)=∅}L = \{{⟨M⟩ ∣ M\ is\ a\ PDA\ such\ that\ L(M)=∅}\}

  4. D.

    L={⟨M⟩∣M is a PDA such that L(M)=Σ∗}L = \{{⟨M⟩ ∣ M\ is\ a\ PDA\ such\ that\ L(M)=Σ^*}\}

Attempted by 102 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…