Theory of Computation GATE Question Answers with Explanation.
Q1 – Suppose that L1 is a regular language and L2 is a context free language. Which one of the following languages is NOT necessarily context-free? (GATE 2021 Set 1)
Â
L1 ∩ L2
L1.L2
L1 – L2
L1 U L2
Ans – (3)
Explanation –Â
Q2 – Let ⟨M⟩ denote an encoding of an automaton M. Suppose that Σ={0,1}. Which of the following languages is/are NOT recursive? (GATE 2021 Set 1)
Â
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)=Σ*}
Ans – (4)
Explanation –
Q3 – Consider the following language:
L = { w ∈ {0,1}∗ ∣ w ends with the substring 011 }
Which one of the following deterministic finite automata accepts L? (GATE 2021 Set 1)
1.
2.
3. 
4. 
Ans – (4)
Explanation –
Q4 – 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? (GATE 2021 Set 1)
Â
Both L1 and L2 are decidable
L1 is decidable and L2 is undecidable
L1 is undecidable and L2 is decidable
Both L1 and L2 are undecidable
Ans – (1)
Explanation –
Q15 – In a pushdown automaton P=(Q, Σ, Γ, δ, q0, F), a transition of the form,Â
where p, q ∈ Q, a ∈ σ ∪ {ϵ}, X, Y ∈ Γ ∪ {ϵ}, represents
(q,Y) ∈ δ(p,a,X)
Consider the following pushdown automaton over the input alphabet Σ= {a, b} and stack alphabet Γ = {#, A}.Â
The number of strings of length 100 accepted by the above pushdown automaton is ___________. (GATE 2021 Set 1)
Ans – (50)
Explanation –