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

2 votes
2 answers
5941
Finite Automata
How many different finite automata are possible with three states x, y and z over the alphabet {a, b} where x is always the start state. Justify your Answer with Example .
How many different finite automata are possible with three states x, y and z over the alphabet {a, b} where x is always the start state.Justify your Answer with Example ....
User Avatar
0 votes
2 answers
5944
context free languages
State True/False: "Any finite subset of {a,b}* is a context free language."
State True/False:"Any finite subset of {a,b}* is a context free language."
User Avatar
1 votes
1 answer
5946
context free languages
State True/False: class of context free languages are closed under union. class of context free languages are closed under intersection. class of context free languages are closed under complementation.
State True/False:class of context free languages are closed under union.class of context free languages are closed under intersection.class of context free languages are ...
User Avatar
1 votes
1 answer
5947
Regular Expression
Prove that : Let $r_1$, $r_2$, and $r_3$ be regular expressions. L(($r_1$ + $r_2$) . $r_3$) = L($r_1$ . $r_3$ + $r_2$ . $r_3$).
Prove that : Let $r_1$, $r_2$, and $r_3$ be regular expressions. L(($r_1$ + $r_2$) . $r_3$) = L($r_1$ . $r_3$ + $r_2$ . $r_3$).
User Avatar
1 votes
1 answer
5948
Regular expression
Give a regular expression for the language L over Σ = {a, b} of words that contain exectly 2 b's?
Give a regular expression for the language L over Σ = {a, b} of words that contain exectly 2 b's?
User Avatar
6 votes
2 answers
5951
ISI2011-PCB-CS-4a
Let $L$ be the set of strings over $\{0, 1\}$ containing an unequal number of $0$s and $1$s. Prove that $L$ is not regular. $L^2$ is regular.
Let $L$ be the set of strings over $\{0, 1\}$ containing an unequal number of $0$s and $1$s. Prove that$L$ is not regular.$L^2$ is regular.
User Avatar
3 votes
1 answer
5952
ISI2012-PCB-CS-3
Design a Turing machine that recognizes the unary language consisting of all strings of 0’s whose length is a power of 2, i.e., $L = \{0^{2n} \mid n \geq 0\}$
Design a Turing machine that recognizes the unary language consisting of all strings of 0’s whose length is a power of 2, i.e., $L = \{0^{2n} \mid n \geq 0\}$
User Avatar
12 votes
3 answers
5960
ISI2013-PCB-CS-4b
Write a regular expression for all strings of $0$’s and $1$’s in which the total number of $0$’s to the right of each $1$ is even. Justify your answer.
Write a regular expression for all strings of $0$’s and $1$’s in which the total number of $0$’s to the right of each $1$ is even. Justify your answer.
User Avatar
Page: