Web Page

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum} \\\hline\textbf{1 Mark Count}&2&2&2&3&3&3&2&2.5&3 \\\hline\textbf{2 Marks Count}&3&3&5&3&3&3&3&3.3&5 \\\hline\textbf{Total Marks}&8&8&12&9&9&9&\bf{8}&\bf{9.2}&\bf{12}\\\hline \end{array}}}$$

# Recent questions in Theory of Computation

1 vote
1
Which of the following statement is true? Deterministic context free language are closed under complement. Deterministic context free language are not closed under Union. Deterministic context free language are closed under intersection with regular set. All of the options
1 vote
2
Which machine is equally powerful in both deterministic and non-deterministic form? Push Down Automata Turing machine Linear Bounded Automata None of the options
1 vote
3
Which of the following is a correct hierarchical relationships of the following where $L_1$: set of languages accepted by NFA $L_2$: set of languages accepted by DFA $L_3$: set of languages accepted by DPDA $L_4$: set of languages accepted by NPDA $L_5$: set of ... $L_2\subset L_1\subset L_3\subset L_4\subset L_5\subset L_6$ $L_1\subset L_2\subset L_3\subset L_4\subset L_6\subset L_5$
4
A context free grammar is : type $0$ type $1$ type $2$ type $3$
5
Consider a Moore machine $M$ whose digraph is : Then $L(M)$, the language accepted by the machine M, is the set of all strings having : two or more b’s three or more b’s two or more a’s three or more a’s
6
Which of the regular expressions corresponds to this grammar ? $S → AB/AS, A → a/aA, B → b$ $aa^*b^+$ $aa^*b$ $(ab)^*$ $a(ab)^*$
7
The context-free languages are closed for : Intersection Union Complementation Kleene Star (i) and (iv) (i) and (iii) (ii) and (iv) (ii) and (iii)
8
Which of the following are not regular? Strings of even number of a’s Strings of a’s , whose length is a prime number. Set of all palindromes made up of a’s and b’s. Strings of a’s whose length is a perfect square. (a) and (b) only (a), (b) and (c) only (b),(c) and (d) only (b) and (d) only
1 vote
9
Consider the languages $L_{1}= \phi$ and $L_{2}=\{1\}$. Which one of the following represents $L_{1}^{\ast}\cup L_{2}^{\ast} L_{1}^{\ast}$? $\{\in \}$ $\{\in,1\}$ $\phi$ $1^{\ast}$
1 vote
10
Given the following statements: A class of languages that is closed under union and complementation has to be closed under intersection A class of languages that is closed under union and intersection has to be closed under complementation Which of the following options is correct? Both (a) and (b) are false Both (a) and (b) are true (a) is true, (b) is false (a) is false, (b) is true
11
Let $G= (V,T,S,P)$ be a context-free grammer such that every one of its productions is of the form $A\rightarrow v$, with $\mid v \mid=K> 1$. The derivation tree for any $W \in L(G)$ has a height $h$ ... $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid - 1}{K-1} \right)$
12
Given the following two languages : $L_{1}= \{a^{n}b^{n}, \mid n\geq 0,n \neq 100 \}$ $L_{2}= \{w \in \{a,b,c \} ^{\ast} \mid n_{a}(w)=n_{b}(w)=n_{c}(w) \}$ Which of the following options is correct? Both $L_{1}$ and $L_{2}$ ... are context free language $L_{1}$ is context free language, $L_{2}$ is not context free language $L_{1}$ is not context free language, $L_{2}$ is context free language
13
Given the following two statements: $L=\{w\mid n_{a}(w)=n_{b}(w)\}$ is deterministic context free language, but not linear. $L=\{a^{n}b^{n}\} \cup \{a^{n}b^{2n} \}$ is linear, but not deterministic context free language. Which of the following options is correct? Both (A) and (B) are false. Both (A) and (B) are true. (A) is true, (B) is false. (A) is false, (B) is true.
14
Which of the following pairs have different expressive power? Single-tape-turing machine and multi-dimensional turing machine. Multi-tape turing machine and multi-dimensional turing machine. Deterministic push down automata and non-deterministic pushdown automata. Deterministic finite automata and Non-deterministic finite automata
15
Which of the following statements is false? Every context –sensitive language is recursive The set of all languages that are not recursively enumerable is countable The family of recursively enumerable languages is closed under union The families of recursively enumerable and recursive languages are closed under reversal
16
Which of the following strings would match the regular expression : $p+ [3-5] * [xyz]$? $p443y$ $p6y$ $3xyz$ $p35z$ $p353535x$ $ppp5$ I, IlI and VI only IV, V and VI only II, IV and V only I, IV and V only
17
Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s? $((0+1)^*1(0+1)^*1)^*10^*$ $(0^*10^*10^*)^*0^*1$ $10^*(0^*10^*10^*)^*$ $(0^*10^*10^*)^*10^*$
Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Both Ⅰ and Ⅱ Neither Ⅰ nor Ⅱ
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only