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

Highest voted questions in Theory of Computation

44 votes
7 answers
81
GATE IT 2008 | Question: 34
Consider a CFG with the following productions. $S \to AA \mid B$ $A \to 0A \mid A0 \mid 1$ $B \to 0B00 \mid 1$ $S$ is the start symbol, $A$ and $B$ ... $\{0, 1\}$ containing at least two $0$'s
Consider a CFG with the following productions.$S \to AA \mid B$$A \to 0A \mid A0 \mid 1$$B \to 0B00 \mid 1$$S$ is the start symbol, $A$ and $B$ are non-terminals and 0 an...
User Avatar
43 votes
6 answers
86
GATE CSE 2007 | Question: 74
Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression $b^*ab^*ab^*ab^*$ $(a + b)^*$ $b^*a(a+b)^*$ $b^*ab^*ab^*$
Consider the following Finite State Automaton:The language accepted by this automaton is given by the regular expression$b^*ab^*ab^*ab^*$$(a + b)^*$$b^*a(a+b)^*$$b^*ab^*a...
User Avatar
43 votes
4 answers
87
GATE CSE 1992 | Question: 02,xviii
If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form? $2l$ $2l +1$ $2l -1$ $l$
If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form?$2l$$2l +1$$2l -1$$...
User Avatar
42 votes
7 answers
88
GATE IT 2007 | Question: 72
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$ Which deterministic finite automaton accepts the language represented by the regular expression $R$?
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression $R$?
User Avatar
42 votes
6 answers
89
GATE CSE 2009 | Question: 27
Given the following state table of an FSM with two states $A$ and $B$ ... length of an input string which will take the machine to the state $A=0,B=1$ with $output=1$. $3$ $4$ $5$ $6$
Given the following state table of an FSM with two states $A$ and $B$,one input and one output.$$\small\begin{array}{|c|c|c|c|c|c|}\hline \textbf{PRESENT} & \textbf{PRESE...
User Avatar
42 votes
8 answers
90
GATE CSE 1992 | Question: 02,xvii
Which of the following regular expression identities is/are TRUE? $r^{(^\ast)} =r^\ast$ $(r^\ast s^\ast)=(r+s)^\ast$ $(r+s)^\ast = r^\ast + s^\ast$ $r^\ast s^\ast = r^\ast+s^\ast$
Which of the following regular expression identities is/are TRUE?$r^{(^\ast)} =r^\ast$$(r^\ast s^\ast)=(r+s)^\ast$$(r+s)^\ast = r^\ast + s^\ast$$r^\ast s^\ast = r^\ast+s^...
User Avatar
41 votes
5 answers
95
GATE CSE 1995 | Question: 2.23
A finite state machine with the following state table has a single input $x$ and a single out $z$ ... $C$ is: $01$ $10$ $101$ $110$
A finite state machine with the following state table has a single input $x$ and a single out $z$.$$\begin{array}{|c|ll|}\hline\textbf{present state} & \qquad \textbf{nex...
User Avatar
41 votes
7 answers
98
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
41 votes
1 answer
100
GATE CSE 2002 | Question: 1.7
The language accepted by a Pushdown Automaton in which the stack is limited to $10$ items is best described as Context free Regular Deterministic Context free Recursive
The language accepted by a Pushdown Automaton in which the stack is limited to $10$ items is best described asContext freeRegularDeterministic Context freeRecursive
User Avatar
Page: