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

20 votes
3 answers
6561
GATE CSE 1999 | Question: 1.5
Context-free languages are closed under: Union, intersection Union, Kleene closure Intersection, complement Complement, Kleene closure
Context-free languages are closed under:Union, intersectionUnion, Kleene closureIntersection, complementComplement, Kleene closure
User Avatar
46 votes
2 answers
6562
GATE CSE 1999 | Question: 1.4
Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains $n$ states $n+1$ states $n+2$ states None of the above
Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression cont...
User Avatar
50 votes
5 answers
6565
GATE CSE 2013 | Question: 8
Consider the languages $L_1 = \phi$ and $L_2 = \{a\}$. Which one of the following represents $L_1 {L_2}^* \cup {L_1}^*$ ? $\{\epsilon\}$ $\phi$ $a^*$ $\{\epsilon, a\}$
Consider the languages $L_1 = \phi$ and $L_2 = \{a\}$. Which one of the following represents $L_1 {L_2}^* \cup {L_1}^*$ ?$\{\epsilon\}$$\phi$$a^*$$\{\epsilon, a\}$
User Avatar
46 votes
7 answers
6574
GATE CSE 2009 | Question: 41
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.
User Avatar
42 votes
6 answers
6576
GATE CSE 2009 | Question: 27
Given the following state table of an FSM with two states $A$ and $B$ ... length of an input string which will take the machine to the state $A=0,B=1$ with $output=1$. $3$ $4$ $5$ $6$
Given the following state table of an FSM with two states $A$ and $B$,one input and one output.$$\small\begin{array}{|c|c|c|c|c|c|}\hline \textbf{PRESENT} & \textbf{PRESE...
User Avatar
Page: