search
Log In

Web Page

Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\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
3 answers
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
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 397 views
1 vote
3 answers
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
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 524 views
1 vote
3 answers
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$
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 386 views
0 votes
1 answer
4
A context free grammar is : type $0$ type $1$ type $2$ type $3$
asked Mar 28, 2020 in Theory of Computation jothee 106 views
0 votes
1 answer
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
asked Mar 28, 2020 in Theory of Computation jothee 530 views
0 votes
2 answers
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)^*$
asked Mar 27, 2020 in Theory of Computation jothee 172 views
0 votes
1 answer
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)
asked Mar 26, 2020 in Theory of Computation jothee 88 views
0 votes
2 answers
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
asked Mar 24, 2020 in Theory of Computation jothee 218 views
1 vote
3 answers
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}$
asked Mar 24, 2020 in Theory of Computation jothee 196 views
1 vote
3 answers
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
asked Mar 24, 2020 in Theory of Computation jothee 196 views
0 votes
0 answers
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)$
asked Mar 24, 2020 in Theory of Computation jothee 173 views
0 votes
3 answers
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
asked Mar 24, 2020 in Theory of Computation jothee 314 views
0 votes
1 answer
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.
asked Mar 24, 2020 in Theory of Computation jothee 143 views
0 votes
3 answers
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
asked Mar 24, 2020 in Theory of Computation jothee 203 views
0 votes
1 answer
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
asked Mar 24, 2020 in Theory of Computation jothee 75 views
0 votes
2 answers
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
asked Mar 24, 2020 in Theory of Computation jothee 287 views
7 votes
5 answers
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^*$
asked Feb 12, 2020 in Theory of Computation Arjun 6.2k views
3 votes
4 answers
18
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 Ⅱ
asked Feb 12, 2020 in Theory of Computation Arjun 3.6k views
8 votes
4 answers
19
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
asked Feb 12, 2020 in Theory of Computation Arjun 5k views
12 votes
7 answers
20
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
asked Feb 12, 2020 in Theory of Computation Arjun 3.3k views
...