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

0 votes
1 answer
5191
Give an algorithm which, for any given context-free grammar G, can determine whether or not: λ $\in$ L(G) ,where $\lambda$ denotes the empty string .
0 votes
0 answers
5192
Please explain why L3 is not CFL?
0 votes
3 answers
5193
0 votes
1 answer
5194
Determine whether or not the following language is context-free.MY ANSWER : The given language is equivalent to L1 = { wwR : where w $\in$ {a,b}* } . And so the given lan...
0 votes
0 answers
5195
0 votes
1 answer
5196
0 votes
1 answer
5198
2 votes
2 answers
5200
REF: https://gateoverflow.in/76419/decidabilityConsider the language:1) L = {<M>| L(M) = $\epsilon$ } 2) L = {<M>| M accepts epsilon }Now, lets consider the 1st language:...
1 votes
1 answer
5202
Construct a DFA that accepts the language represented by: r = (ab/ba)* aa (ab/ba)*
0 votes
1 answer
5203
Give a regular expression for LR, where L is the language given below,L = (a + b) b (a + ab)*My answer : ( a + ba )* b ( a + b ).Please verify ...
0 votes
1 answer
5204
What language is accepted by the npda below if we make F = {q0, qf }, where F denotes set of final states.Answer is L = $\sum$* ...........right ???
0 votes
1 answer
5205
Find dfa that accept regular expression ab(a+ab)*(a+aa)
0 votes
2 answers
5206
Construct the DFA for all string with at least one a and exactly two b
0 votes
3 answers
5208
Let sigma = { a,b }.Find the grammar which generates the language,where na(w) and nb(w) denote the number of a's in w and number of b's in w respectively.
2 votes
1 answer
5209
WHat is the union of the following wo languagesL=0*1+0+1* ∪ 10*1L=001 U 0*1*
1 votes
1 answer
5210