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

0 votes
2 answers
6121
How to tell whether a language is recursively enumerable or not?Also answer the question with proper algorithm :-)
3 votes
1 answer
6122
Find minimal finitte automata forL1:L1 contains set of strings starting with 1010 and length of string is divisible by 4.L2:L2 contains set of strings starting woth 1010 ...
1 votes
1 answer
6123
no of states for accepting €?
0 votes
0 answers
6124
Construct a transition table and diagram for the NFAM=({q1,q2,q3},∂,q1,{q3}) where ∂ is given by∂(q1,0)={q2,q3}, ∂(q1,1)={q1},∂(q2,0)={q1,q2}, ∂(q2,1)=∅...
4 votes
2 answers
6125
Is DFCL closed under complement ? If so can you provide any text for the same.
0 votes
0 answers
6130
I have gone through this link already but still couldn't catch up the logic , so please clarify what is it trying to convey ? http://cs.stackexchange.com/questions/44195/...
0 votes
1 answer
6132
I solved both of these qs in a traditional way,by drawing nfa and then convert them to dfa..by tthis process ans shoulbe 4 and 2..but both of them are wrong..pls check..
5 votes
2 answers
6133
1 votes
2 answers
6136
construct DFA that accepts all binary numbers are divisible by either 2 or 3
1 votes
1 answer
6140
L1 = {ambn | m+n = Even} L2 = {ambn | m-n = 4}(a) L1 is Regular, L2 is Not Regular(b) Both are Regular(c) Both are Non- Regular(d) L2 is Regular, L1 is Not Regular