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

Most viewed questions in Theory of Computation

43 votes
4 answers
91
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
70 votes
3 answers
93
GATE CSE 1994 | Question: 3.3
State True or False with one line explanation A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).
State True or False with one line explanationA FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).
User Avatar
18 votes
1 answer
94
right and left quotient in regular language
how to find L1/L2 for some L1 and L2 (is diagram making must ) how to conclude that L1 is divisible or not divisible by L2
how to find L1/L2 for some L1 and L2 (is diagram making must )how to conclude that L1 is divisible or not divisible by L2
User Avatar
44 votes
7 answers
95
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
29 votes
5 answers
96
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
2 votes
5 answers
98
difference between phi and epsilon?
User Avatar
67 votes
4 answers
103
GATE CSE 2008 | Question: 49
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ ...
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state)$$\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & ...
User Avatar
1 votes
1 answer
105
Grammar that produce more than one Parse tree for same sentence is:
A. Ambiguous B. Unambiguous C. Complementation D. Concatenation Intersection
A. AmbiguousB. UnambiguousC. ComplementationD. Concatenation Intersection
User Avatar
42 votes
8 answers
106
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
24 votes
1 answer
107
GATE CSE 1997 | Question: 20
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$'s is divisible by three.
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...
User Avatar
0 votes
3 answers
109
Language of strings not containing 101
Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then converting it to regular expression?
Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then convert...
User Avatar
Page: