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 =…
Subject-wise GATE questions
Theory of Computation
12 questions and papers
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?
GATE CS 2014 Set 2 — Question 35
Let \(L_1 = \{w \in \{0,1\}^* \mid w\) has at least as many occurrences of (110)'s as (011)'s\(\}\). Let \(L_2 = \{w \in \{0,1\}^* \mid w\) has at least as many occurrences of (000)'s as (111)'s\(\}\). Which one of the following is TRUE?
GATE CS 2010 — Question 35
Let \(L = \{w \in (0+1)^* \mid w\) has an even number of 1s\(\}\), i.e. \(L\) is the set of all bit strings with an even number of 1s. Which one of the regular expressions below represents \(L\)?
GATE CS 2012 — Question 27
Which of the following problems are decidable?Does a given program ever produce an output?If \(L\) is a context-free language, then is \(\bar{L}\) also context-free?If \(L\) is a regular language, then is \(\bar{L}\) also regular?If \(L\) is a recursive…
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.