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

Most answered questions in Theory of Computation

0 votes
1 answer
3931
$\large L=\left \{ a^m b^n c^k | k<=min(m,n) \right \}$ is this context free?
0 votes
1 answer
3932
{ w x wR : w belongs to (a+b)*, x belongs to (a+b)+How is this language regular?
0 votes
1 answer
3933
1 votes
1 answer
3934
Consider the following DFA: Language accepted by DFA isAll the string ending with same symbolAll the string containing 10 or 01 as substringAll the string where leftmost ...
0 votes
1 answer
3935
what is the difference between x belongs to {a,b}* and x belongs to {a+b}*?
1 votes
1 answer
3936
construct a dfa :all string with at-least one a and exactly two b's ,
0 votes
1 answer
3937
L1={ϕ}L2={ Σ *}My question is how L1 is a subset of L2 but not the proper subset ?also how L1 is a subset of L2 ?? explain ?
0 votes
1 answer
3938
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
3939
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
1 votes
1 answer
3940
In pumping lemma for CFL a^nb^n ....the pumping is done on equal number of a and b then pumping lemma is valid for this CFL...but when I take unequal a and b pumping lemm...
1 votes
1 answer
3941
If $L1$ is regular and $L2$ is a subset of $L1$, then which of the following has to be regular ?(a) $L2$ (b) $L1\cap L2$ ( c) $L2^{n}$ ( d) $L1^{n}$
0 votes
1 answer
3943
The grammer is M→PDAPDA→DPDADPDA→LBALBA→TMTM→a1.type02.type13.type24.type3
0 votes
1 answer
3944
which of following is true1. L={a^nb^n /n>=1}U{a^mb^2m /m>=1} can be accepted by DPDA2.the regular set accepted to final state by DPDA with n state and one push down symb...
0 votes
1 answer
3945
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
0 votes
1 answer
3946
L1= O*1*0*L2={0^n10^n /n>0}then L1∩L2 and L2 are1.regular,cfl2.cfl,regular3.reguler,regular4.cfl.cfl
0 votes
1 answer
3947
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
3 votes
1 answer
3948
consider all palindrome even if they are sentencein English which are of finite lengh. let this language be La.L is regular setb.L is finite setc. L is dcfld.L is CFL
1 votes
1 answer
3950