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}}}$$

Highest voted questions in Theory of Computation

41 votes
5 answers
95
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...
41 votes
7 answers
97
41 votes
1 answer
99
The language accepted by a Pushdown Automaton in which the stack is limited to $10$ items is best described asContext freeRegularDeterministic Context freeRecursive
41 votes
4 answers
100
40 votes
2 answers
102
Consider the regular grammar below$S \rightarrow bS \mid aA \mid \epsilon $$A \rightarrow aS \mid bA$ The Myhill-Nerode equivalence classes for the language generated by ...
40 votes
4 answers
108
39 votes
4 answers
110
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$...