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

Recent questions in Theory of Computation

1 votes
1 answer
123
In a DFA, does every state have to have a transition for each of the symbols?
0 votes
1 answer
124
0 votes
0 answers
125
Describe Thomson Construction method for converting Regular expression into ε-NFA. Convert regular expression (a(a+b)*abb)+ab into ε-NFA.
0 votes
1 answer
128
0 votes
2 answers
129
0 votes
2 answers
130
0 votes
1 answer
131
Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by an odd number of 1's and ending with any number of 2's. Please give the answ...
0 votes
1 answer
132
0 votes
0 answers
133
Can anyone help me in this exercise:Show that the language L = {an : n is a multiple of three, but not a multiple of 5} is regular with DFA.i make DFA but i don’t sure ...
0 votes
1 answer
137
Could anyone confirm is this a part of TOC gate syllabus or not? Thank you!
0 votes
0 answers
138
For the following regular expression:a+|(ab)+Over the alphabet:{a,b}Give an epsilon-NFA that recognizes the same language.
0 votes
1 answer
140