Let M denote an encoding of an automaton M. Suppose that = \0, 1\. Which of the following languages is/are NOT recursive?

L = \ M M is a PDA such that L(M) = ^*\

L = \ M M is a DFA such that L(M) = \

L = \ M M is a DFA such that L(M) = ^*\

L = \ M M is a PDA such that L(M) = \

L = \ M M is a PDA such that L(M) = ^*\

GATE CSE 2021 Set 1 Q22: Which DFA/PDA emptiness and universality problems are undecidable

Theory of Computation
1 mark
MSQ
No negative marking

Let $\langle M \rangle$ denote an encoding of an automaton $M$ . Suppose that $\Sigma = \{0, 1\}$ . Which of the following languages is/are NOT recursive?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: D (official GATE 2021 final answer key)

Concept used: Emptiness and universality are decidable for DFAs; for context-free languages emptiness is decidable but universality is not.

First step: Recall which of the four properties is the classic undecidable problem for context-free grammars.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2021 Set 1 questions →

GATE CSE 2021 Set 1 Q22: Which DFA/PDA emptiness and universality problems are undecidable

Question

Full step-by-step solution

More Theory of Computation PYQs