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
1 answer
6141
3 votes
2 answers
6142
Is the language given by $ww^R ww^R$, where $w$ is any string over the binary alphabet, Context Free or Context Sensitive?
4 votes
2 answers
6143
if A is context free language and B is a language such that B⊂A then B must be?
1 votes
1 answer
6144
1 votes
1 answer
6145
L1 = {ambnckdl | if(m=n) then (k=l)} L2 = {ambnckdl | if(n=k) then (k=l)}which of the above two languages are not cfl ??how to solve such type of questions?
18 votes
4 answers
6147
4 votes
0 answers
6150
2 votes
1 answer
6151
7 votes
2 answers
6157
The number of equivalence classes which exist for the following regular expression R are ______. $R=(a+b)^*b(a+b+\epsilon )$ what is the meaning of equivale...
4 votes
2 answers
6158
Consider the following turning machine (where,,$\$ $ is represent accept the string).If the string is $01010$ then what will be the output?$10100$$10101$$10110$$10011$
5 votes
4 answers
6159
Consider the following push down automata.The language accepted by above PDA is_______.Regular but infinite.DCFL but not regular.CFL but not DCFLFinite language.
4 votes
1 answer
6160
Prove or Disprove below language is regular or notL1={w|w∈∑* where w visit all state of M atleast once where M is machine accepting L1 L2={w|w∈∑* where ...