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

3 votes
3 answers
6361
Can DPDA accept ambiguous grammars?
Option D is correct. But G is ambiguous. Can DPDA accept G?
Option D is correct. But G is ambiguous. Can DPDA accept G?
User Avatar
0 votes
1 answer
6363
how to find whether a language is regular or not
my question is whether we have a shortcut an idea which can help us in recognizing any language to be regular or not,in GATE .and also what is the best way to get it properly done when you want to do it the old school way?
my question is whether we have a shortcut an idea which can help us in recognizing any language to be regular or not,in GATE .and also what is the best way to get it prop...
User Avatar
4 votes
5 answers
6364
minimal DFA
The minimal state DFA, accepting all strings over the alphabet {0,1} where the nth symbol in every string from the right end is a 1, has a) 2n states b) 2n-1 states c) 2n+1 states d) None of the above  
The minimal state DFA, accepting all strings over the alphabet {0,1} where the nth symbol in every string from the right end is a 1, hasa) 2n states b) 2n-1 states c) 2n...
User Avatar
1 votes
2 answers
6368
choosing incorrect identity
Q choose incorrect identity from the following a) (a+b)* = (a+b)*(a+b)* b) (a+b)* = a(a+b)*b(a+b)* + ∈ c)(a+b)* = (a+b)*ab(a+b)* + b*a* d)None of the above correct answer given is option D but obviously option B and option C both are wrong too.
Qchoose incorrect identity from the followinga) (a+b)* = (a+b)*(a+b)*b) (a+b)* = a(a+b)*b(a+b)* + ∈c)(a+b)* = (a+b)*ab(a+b)* + b*a*d)None of the abovecorrect answer ...
User Avatar
4 votes
1 answer
6370
equality of regular expressions
Q which of the following pair of regular expressions are not equal a)∅* & ∈* b)(01+0)*0 & 0(10+0)* c)r1*(r1+r2)* & (r1 + r2)* d)None of the above in my view option A should be the correct option but answer given is option D
Qwhich of the following pair of regular expressions are not equala)∅* & ∈*b)(01+0)*0 & 0(10+0)*c)r1*(r1+r2)* & (r1 + r2)*d)None of the abovein my view option A...
User Avatar
0 votes
1 answer
6372
plz answer !
User Avatar
1 votes
2 answers
6373
Consider following Regular Expression (i) a*b*b (a+ (ab)*)* b*(ii) a*(ab + ba)* b*
Consider following Regular Expression (i) a*b*b (a+ (ab)*)* b* (ii) a*(ab + ba)* b* What is length of shortest string which is in both (i) & (ii)? A. 2 B. 3 C. 4 D. None
Consider following Regular Expression(i) a*b*b (a+ (ab)*)* b*(ii) a*(ab + ba)* b*What is length of shortest string which is in both (i) & (ii)?A. 2 B. 3 C. 4 D. None
User Avatar
Page: