Push Down Automata: CFL & DCFL GATE 2013 Question #2742 with Solution

GATE 2013

Theory of ComputationPush Down Automata: CFL & DCFLmediumMCQ2 marks

Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.

A1 and 4 onlyB1 and 3 onlyC2 onlyD3 only

Save your progress

Related Theory of Computation PYQs

GATE 2013

Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = ϕ? 2. G is a CFG. Is L(G) = Σ*? 3. M is a Turing machine. Is L…

GATE 2013

Which of the following languages is NOT regular?

GATE 2013

Which of the following statements is FALSE?

GATE 2013

Consider the following deterministic finite automaton (DFA) over the alphabet {0, 1} with states {q0, q1, q2}, where q0 is the sta…

GATE 2013

The language L = {a^n b^m c^m d^n | n, m >= 1} is:

GATE 2013 · session-1

Consider the languages L₁=∅ and L₂={a}. Which one of the following represents L₁L₂* ∪ L₁*?

Saved progressKeep answers, mock results and completion history across devices.

Adaptive practiceGet questions matched to your recent accuracy and difficulty level.

Bookmarks and notesBuild a personal revision list and record why a question was difficult.

Performance insightsSee weak subjects, accuracy trends, streaks and exam readiness.

Related Theory of Computation PYQs

Turn practice into measurable progress