Automata GATE CS and IT previous year questions with answer
Ques 11 Gate 2020
Consider the following languages.
L2 = { xy ∣ x,y ∈ (a+b)*, ∣x∣=∣y∣, x≠y }
Ques 12 Gate 2020
Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M.
L1 = { ⟨M⟩ ∣ L(M)=∅ }
L2 = { ⟨M,w,q⟩ ∣ M on input w reaches state q in exactly 100 steps }
L3 = { ⟨M⟩ ∣ L(M) is not recursive }
L4 = { ⟨M⟩ ∣ L(M) contains at least 21 members }
Ques 13 Gate 2020
Consider the language L = { an ∣ n≥0 }∪{ anbn∣ n≥0 } and the following statements.
I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE ?
Ques 14 Gate 2020
Consider the following statements
I. If L1∪L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE ?
Ques 15 Gate 2020
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1′s ?
Ques 16 Gate 2020
Consider the following language.
The minimum number of states in DFA that accepts L is _________ .
6 is the correct answer.
Ques 17 Gate 2020
Consider the following language.
L = { x∈{a,b}* ∣ number of a’s in x divisible by 2 but not divisible by 3 }
The minimum number of states in DFA that accepts L is _________ .
6 is the correct answer.
Ques 18 Gate 2019
Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function, i.e. id(j) = j,∀ j. Let ° denote composition on functions. For a string x = x1 x2 ... xn ∈ Σn, n ≥ 0, let π(x) = x1°x2° ... °xn. Consider the language L = {x ∈ Σ* ⏐ π(x) = id}. The minimum number of states in any DFA accepting L is _________ .
120 is the correct answer.
Ques 19 Gate 2019
Consider the following sets:
S2: Set of all syntactically valid C programs.
S3: Set of all languages over the alphabet {0, 1}.
S4: Set of all non-regular languages over the alphabet {0, 1}.
Which of the above sets are uncountable?
Ques 20 Gate 2019
Which one of the following languages over ∑ = {a, b} is NOT context-free?