Register

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

Filter

Recent questions in Theory of Computation

2 votes
0 answers
241
gate academy
I think S1 is false because, for n=0, no 0’s will be added in stack, but in the transition to the next state (q2->q3) there is one mandatory 1 canceling out 0 in stack which will be absent in case of n=0. But solutions say S1 is true.
I think S1 is false because, for n=0, no 0’s will be added in stack, but in the transition to the next state (q2->q3) there is one mandatory 1 canceling out 0 in stack...
User Avatar
0 votes
0 answers
245
Test-Series
Consider the language given below: $L$ $=$ { $p$ $|$ $p$ $\neq$ $w$ $and$ $p$ $is$ $the$ $prefix$ $of$ $w$ $and$ $w$ $\epsilon$ {$0,1$}*} Which of following is true about L. A)L is CFL B)L is DCFL C)L is CSL D)L is regular
Consider the language given below:$L$ $=$ { $p$ $|$ $p$ $\neq$ $w$ $and$ $p$ $is$ $the$ $prefix$ $of$ $w$ $and$ $w$ $\epsilon$ {$0,1$}*}Which of following is true about ...
User Avatar
2 votes
1 answer
247
Test-Series
Consider the following language over $\sum$ = {0, 1} L = {w | w $\epsilon \sum$ * and |w| is divisible by 2 and not by 4} How many sates will min-DFA accepting L will have?
Consider the following language over $\sum$ = {0, 1}L = {w | w $\epsilon \sum$ * and |w| is divisible by 2 and not by 4}How many sates will min-DFA accepting L will have?...
User Avatar
0 votes
1 answer
248
Made easy postal course example problem
What will be the DFA for wxw^r where w belongs to (a,b)^+ and x belongs to (a,b)^+
What will be the DFA for wxw^r where w belongs to (a,b)^+ and x belongs to (a,b)^+
User Avatar
0 votes
1 answer
249
#self_doubt#CFG
Are these two grammars equal? 1->------------------- S->X|epsilon X->BBX|epsilon B->a|b 2->------------ S->AAS|epsilon A->a|b
Are these two grammars equal?1- -S->X|epsilonX->BBX|epsilonB->a|b2- S->AAS|epsilonA->a|b
User Avatar
0 votes
1 answer
250
Theory of computation
What does right quotient actually mean????
What does right quotient actually mean????
User Avatar
0 votes
3 answers
251
#selfDoubt
what will be the DFA for RE – (a*ba)*
what will be the DFA for RE – (a*ba)*
User Avatar
0 votes
0 answers
252
#self_doubt #DFA
Regular Expression for accepting the language L = { 0^n1^m | n+m=even } I got this solution – (00)*(11)*+0(00)*1(11)* please point out how this – {(00)* (01)* (11)* } RE differs from the above one
Regular Expression for accepting the language L = { 0^n1^m | n+m=even }I got this solution – (00)*(11)*+0(00)*1(11)*please point out how this – {(00)* (01)* (11)* } ...
User Avatar
1 votes
2 answers
253
toc decidablity
M is a Turing Machine and M is the only Turing Machine that accepts L(M) is decidable. TRUE/FALSE
M is a Turing Machine and M is the only Turing Machine that accepts L(M) is decidable. TRUE/FALSE
User Avatar
0 votes
1 answer
254
Theory Of Computation (NFA/DFA)
**MSQ** The Finite State Autometa with a Regular Expression P= 0+1, will accept the string(s) 0 1 01 10
MSQ The Finite State Autometa with a Regular Expression P= 0+1, will accept the string(s)010110
User Avatar
0 votes
1 answer
256
Theory of Computation
b* a* ∩ a*b* = (a U b)* Is this statment wrong or correct ?
b* a* ∩ a*b* = (a U b)* Is this statment wrong or correct ?
User Avatar
0 votes
1 answer
257
Theory of Computation
does this string ‘baab’ belongs (ba)* U (ab)* ?
does this string ‘baab’ belongs (ba)* U (ab)* ?
User Avatar
0 votes
1 answer
258
theroy of computation
{ε}* , {ε} are these two expressions equal or different ? where ε is the empty string
{ε}* , {ε} are these two expressions equal or different ? where ε is the empty string
User Avatar
0 votes
1 answer
259
regular expressions
{(a* b)a } intersection {a*b*}, is this considered a regular language ? or not and how do i know ?
{(a* b)a } intersection {a*b*}, is this considered a regular language ? or not and how do i know ?
User Avatar
0 votes
0 answers
260
theory of computuation
is λ the same as {λ}* ? are these expressions equal ?
is λ the same as {λ}* ? are these expressions equal ?
User Avatar
Page: