Register

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.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}& \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\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&3&3&2&2&2&3&3&3&2&2.5&3
\\\hline\textbf{2 Marks Count} & 3 &3&4&3&3&3&5&3&3&3&3&3.3&5
\\\hline\textbf{Total Marks} & 8 &8&11&9&8&8&12&9&9&9&\bf{8}&\bf{9.1}&\bf{12}\\\hline
\end{array}}}$$

Filter

Previous GATE Questions in Theory of Computation

54 votes
4 answers
151
GATE CSE 2014 Set 1 | Question: 36
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^* $ $0^*1^*1+11^*0^*1 $ $(0+1)^*1$ I and II only I and III only II and III only I, II and III
Which of the regular expressions given below represent the following DFA?$0^*1(1+00^*1)^* $$0^*1^*1+11^*0^*1 $$(0+1)^*1$I and II onlyI and III onlyII and III onlyI, II an...
User Avatar
29 votes
5 answers
153
GATE CSE 2014 Set 1 | Question: 16
Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$? $\{q_0,q_1,q_2\}$ $\{q_0,q_1\}$ $\{q_0,q_1,q_2,q_3\}$ $\{q_3\}$
Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$?$\{q_0,q_1,q_2\}$$\{q_0,q_1\}$$\{q_0,q_1,q_2,q_3\}$...
User Avatar
23 votes
3 answers
157
GATE CSE 1998 | Question: 2.6
Which of the following statements is false? Every finite subset of a non-regular set is regular Every subset of a regular set is regular Every finite subset of a regular set is regular The intersection of two regular sets is regular
Which of the following statements is false?Every finite subset of a non-regular set is regularEvery subset of a regular set is regularEvery finite subset of a regular set...
User Avatar
39 votes
4 answers
158
GATE CSE 1998 | Question: 2.5
Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$ is $2$ $5$ $8$ $3$
Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$...
User Avatar
41 votes
7 answers
159
GATE CSE 1998 | Question: 1.12
The string $1101$ does not belong to the set represented by $110^*(0 + 1)$ $1(0 + 1)^*101$ $(10)^*(01)^*(00 + 11)^*$ $(00 + (11)^*0)^*$
The string $1101$ does not belong to the set represented by$110^*(0 + 1)$$1(0 + 1)^*101$$(10)^*(01)^*(00 + 11)^*$$(00 + (11)^*0)^*$
User Avatar
37 votes
4 answers
162
GATE CSE 1998 | Question: 1.9
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is true? $A \subset B$ $B \subset A$ $A$ and $B$ are incomparable $A = B$
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is t...
User Avatar
24 votes
4 answers
163
GATE CSE 2012 | Question: 25
Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$? $ abaabaaabaa$ $ aaaabaaaa$ $ baaaaabaaaab$ $ baaaaabaa$ $\text{1, 2 and 3}$ $\text{2, 3 and 4}$ $\text{1, 2 and 4}$ $\text{1, 3 and 4}$
Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$?$ abaabaaabaa$$ aaaabaaaa$$ baaaaabaaaab$$ baaaaabaa$$\text{1, 2 and 3}...
User Avatar
34 votes
2 answers
169
GATE CSE 1999 | Question: 7
Show that the language $L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$ is not context free. $c$ is not $0$ or $1$.
Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.
User Avatar
Page: