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

Highest voted questions in Theory of Computation

0 votes
0 answers
5191
https://gateoverflow.in/188609/me-test-seriesThis question has not been answered, can somebody solve it!
0 votes
1 answer
5192
How to take union of two DFAs?I am unable to understand this question https://gateoverflow.in/37795/dfa-min-states
0 votes
0 answers
5193
0 votes
1 answer
5194
Referring to the question https://gateoverflow.in/227957/self-doubtIf the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular langu...
0 votes
1 answer
5196
L = {x^a y^a : a ≥ 1}I. L^3 is context free.II. ⌈√ L⌉ is not context free.Which of the following is correct?(a) I only (b) II only(c) Both I and II (d) None of th...
0 votes
1 answer
5197
0 votes
2 answers
5201
Let L ={wxw^R / w € (a+b)* , x€(a+b)} . The complement of language L is_______(a) Regular(b) DCFL but not regular(c) CFL but not DCFL (d) None of these
0 votes
0 answers
5202
0 votes
2 answers
5203
0 votes
1 answer
5204
0 votes
0 answers
5205
0 votes
1 answer
5206
How many number of states are there in the minimized dfa that accepts the language L= a^ 3(n+1)
0 votes
2 answers
5207
The number of states in the minimal deterministic finite automata corresponding to the regular expression (0 + 1)* (000 + 001) is ________.
0 votes
0 answers
5208
Consider the following DFA:The number of distinct sets present in all partitions while converting given DFA into minimal DFA using Myhill-Nerode theorem is ________.
0 votes
1 answer
5209
Consider P and Q be language over Σ = {0, 1} represented by the regular expression 0* (10*)* and (0* + 1*)* respectively. Which of the following is true?A) P⊂QB) Q⊂P...
0 votes
0 answers
5210