GATE exam stream
GATE CS — Computer Science & IT
174 questions and papers
Compiler Design — GATE Previous Year Questions
Algorithms — GATE Previous Year Questions
GATE CS 2021 Set 1 — Question 40
For a Turing machine \(M\), \(\langle M \rangle\) denotes an encoding of \(M\). Consider the following two languages.\(L_1 = \{\langle M \rangle \mid M\) takes more than 2021 steps on all inputs\(\}\)\(L_2 =…
GATE CS 2017 Set 2 — Question 30
Consider the language \(L\) given by the regular expression \((a+b)^*b(a+b)\) over the alphabet \(\{a,b\}\). The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting \(L\)…
GATE CS 2019 — Question 37
For \(\Sigma = \{a,b\}\), let us consider the regular language \(L = \{x \mid x = a^{2+3k}\) or \(x = b^{10+12k},\ k \ge 0\}\). Which one of the following can be a pumping length (the constant guaranteed by the pumping…
GATE CS 2016 Set 1 — Question 19
Language \(L_1\) is defined by the grammar: \(S_1 \rightarrow a S_1 b \mid \varepsilon\)Language \(L_2\) is defined by the grammar: \(S_2 \rightarrow ab S_2 \mid \varepsilon\)Consider the following statements:P: \(L_1\) is regularQ: \(L_2\) is regularWhich one of the following is…
GATE CS 2015 Set 3 — Question 33
The number of states in the minimal deterministic finite automaton corresponding to the regular expression \((0+1)^*(10)\) is ______.
GATE CS 2015 Set 1 — Question 23
Let \(L\) be the language represented by the regular expression \(\Sigma^*0011\Sigma^*\), where \(\Sigma = \{0,1\}\). What is the minimum number of states in a DFA that recognizes \(\bar{L}\) (complement of \(L\))?
GATE CS 2014 Set 3 — Question 16
Let \(L\) be a language and \(\bar{L}\) be its complement. Which one of the following is NOT a viable possibility?
Answers and explanations unlock on sign-in
Every question here is free to read. A free account adds the verified key, the worked solution and your progress.