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

Most viewed questions in Theory of Computation

4 votes
4 answers
65
DFA to accept a binary number divisible by 2
Sorry for the bad quality picture. Which of these is correct? (1 or 2)
Sorry for the bad quality picture. Which of these is correct? (1 or 2)
User Avatar
2 votes
2 answers
70
Minimum number of states in the DFA
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$ I draw the following DFA The minimum number of states is 4. The answer given is 8. How is it possible? Please explain.
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$I draw the following DFA The minimum number of states is 4. The answer giv...
User Avatar
3 votes
4 answers
72
regular exp[ression
Which of the following regular expression identities are true ? (A) (r + s)* = r* s* (B) (r + s)* = r* + s* (C) (r + s)* = (r*s*)* (D) r* s* = r* + s*
Which of the following regular expression identities are true ?(A) (r + s)* = r* s*(B) (r + s)* = r* + s*(C) (r + s)* = (r*s*)*(D) r* s* = r* + s*
User Avatar
29 votes
3 answers
73
GATE CSE 2001 | Question: 1.6
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least $N^2$ $2^N$ $2N$ $N!$
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least$N^2$$2^N$$2N$$N!$
User Avatar
26 votes
5 answers
74
GATE CSE 1995 | Question: 2.24
Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n > 0\right\} $ then the languages $L \cup R$ and $R$ are respectively regular, regular not regular, regular regular, not regular not regular, not regular
Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n 0\right\} $ then the languages $L \cup R$ and $R$ are respectivelyregular, regularnot regular, ...
User Avatar
Page: