Theory of Computation — GATE Previous Year Questions

Consider the languages \(L_1 = \{a^n b^n c^m \mid n, m > 0\}\) and \(L_2 = \{a^n b^m c^m \mid n, m > 0\}\). Which one of the following statements is FALSE?

A minimum state deterministic finite automaton accepting the language \(L = \{w \mid w \in \{0,1\}^*\), number of 0s and 1s in \(w\) are divisible by 3 and 5, respectively\(\}\) has

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\)?

Which of the following problems are decidable?

1. Does a given program ever produce an output?
2. If \(L\) is a context-free language, then is \(\bar{L}\) also context-free?
3. If \(L\) is a regular language, then is \(\bar{L}\) also regular?
4. If \(L\) is a recursive language, then is \(\bar{L}\) also recursive?

Let \(L\) be a language and \(\bar{L}\) be its complement. Which one of the following is NOT a viable possibility?

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?

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\))?

The number of states in the minimal deterministic finite automaton corresponding to the regular expression \((0+1)^*(10)\) is ______.

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 regular
Q: \(L_2\) is regular

Which one of the following is TRUE?

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\) is ______.

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 lemma) for \(L\)?

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 = \{\langle M \rangle \mid M\) takes more than 2021 steps on some input\(\}\)

Which one of the following options is correct?