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

Hot questions in Theory of Computation

1 votes
1 answer
6181
0 votes
1 answer
6182
my doubt is if some grammer contain both left recursive and right recursive grammer then it's ambigious grammer. is this stmt is true for all such type of grammer???
0 votes
1 answer
6184
L =Set of all string which starts with a and ends with a .what will be the min no of states in FA represented by this Lang.
0 votes
1 answer
6187
Let L be a Context Free Language. Even(L) is the set of all strings w in L such that |w| is even. What can you say about even(L)?(a) It will be regular(b) It will be cont...
0 votes
1 answer
6188
which of following is cfl1.L={a^n^2 /n>=0}2. L={a^p /p is prime}3.L={a^p /p^100< finite number}4. none
3 votes
2 answers
6190
0 votes
1 answer
6191
letL1{a^n+m b^n c^m /n,m>=0}L2{a^n+m b^m+n c^m /n,m>=0}L3{a^n+m b^n c^m+n /n,m>=0}which of the above is not context freee1.L1,L22. L1,L33. L2,L34 L3 only
0 votes
1 answer
6192
Let Q0 and Q1 are two states and Q0 is always the inital state over the alphabet {a,b} ,then possible number of DF'a with two states will be1)322)643)804)120
0 votes
1 answer
6193
The grammer is M→PDAPDA→DPDADPDA→LBALBA→TMTM→a1.type02.type13.type24.type3
1 votes
1 answer
6195
the left liner grammer given below genratesH→Ha/aS→Hb1.(a+b)^+2.aa*b3 a*b4 none
2 votes
1 answer
6197
why do we study Epsilon-nfa...i mean to say what is the significance of epsilon nfa in real applications??
1 votes
0 answers
6198
the language generate by the grammer S→SS/aSb/abis accepted by___a. DPDAb.PDAc.LBAd turing machine1. D>C>B>A2. A>B>C>D3. B>D>A>B4. D>A>B>C
2 votes
2 answers
6199
make a DFA having alphabet set {0,1} means that accept binary strings that start with ' 10 ' and congruent to ' 2 mod 3 '.