1
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages.

L1 = {(M) | M takes more than 2021 steps on all inputs}

L2 = {(M) | M takes more than 2021 steps on some input}

Which one of the following options is correct?

A
Both L1 and L2 are undecidable.
B
L1 is undecidable and L2 is decidable.
C
L1 is decidable and L2 is undecidable.
D
Both L1 and L2 are decidable.
2
GATE CSE 2021 Set 1
Numerical
+2
-0.67

In a pushdown automaton P = (Q, ∑, Γ, δ, q0, F), a transition of the form,

GATE CSE 2021 Set 1 Theory of Computation - Push Down Automata and Context Free Language Question 8 English 1

where p, q ∈ Q, a ∈ Σ ∪ {ϵ}, and X, Y ∈ Γ ∪ {ϵ}, represents

(q, Y) ∈ δ(p, a, X).

Consider the following pushdown automaton over the input alphabet ∑ = {a, b} and stack alphabet Γ = {#, A}.

GATE CSE 2021 Set 1 Theory of Computation - Push Down Automata and Context Free Language Question 8 English 2
The number of strings of length 100 accepted by the above pushdown automaton is ______

Your input ____
3
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

Consider the following language.

L = { w ∈ {0, 1}* | w ends with the substring 011}

Which one of the following deterministic finite automata accepts L?

A
GATE CSE 2021 Set 1 Theory of Computation - Finite Automata and Regular Language Question 12 English Option 1
B
GATE CSE 2021 Set 1 Theory of Computation - Finite Automata and Regular Language Question 12 English Option 2
C
GATE CSE 2021 Set 1 Theory of Computation - Finite Automata and Regular Language Question 12 English Option 3
D
GATE CSE 2021 Set 1 Theory of Computation - Finite Automata and Regular Language Question 12 English Option 4
4
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67
Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?
A
L = { $$\left\langle M \right\rangle $$ | M is a PDA such that L(M) = ∑*}
B
L = { $$\left\langle M \right\rangle $$ | M is a DFA such that L(M) = Φ}
C
L = { $$\left\langle M \right\rangle $$ | M is a PDA such that L(M) = Φ}
D
L = { $$\left\langle M \right\rangle $$ | M is a DFA such that L(M) = ∑*}
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12