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

1 votes
1 answer
6244
DFA
User Avatar
3 votes
2 answers
6247
Binary Number when interpreted as decimal mod 12
What are the Number of states in minimum DFA that accepts Binary strings when interpreted as decimal mod 12 give 0 as remainder.Also give DFA.
What are the Number of states in minimum DFA that accepts Binary strings when interpreted as decimal mod 12 give 0 as remainder.Also give DFA.
User Avatar
8 votes
3 answers
6249
How is the complement of Language L is Context free ??
The complement of the language $L$ containing an equal number of $a's$,$b's$ and $c's$ is (a) regular (b) context free (c) context sensitive but not context free (d) recursive and not a cfl.
The complement of the language $L$ containing an equal number of $a's$,$b's$ and $c's$ is (a) regular(b) context free(c) context sensitive but not context free(d) recursi...
User Avatar
1 votes
1 answer
6251
Match the following :
User Avatar
1 votes
1 answer
6252
Unambiguous CFL which is not DCFL
Give an example of Unambiguous CFL which is not DCFL .
Give an example of Unambiguous CFL which is not DCFL .
User Avatar
1 votes
2 answers
6253
type of given language ?
let P,Q,R be three languages. if P nd R are regular and if PQ=R the Q is ?
let P,Q,R be three languages. if P nd R are regular and if PQ=R the Q is ?
User Avatar
4 votes
1 answer
6254
Number of symbols necessary to simulate a TM
The number of symbols necessary to simulate a TM with $m$ symbols and $n$ states is ? $m+n$ $8mn+4m$ $mn$ $4mn+m$
The number of symbols necessary to simulate a TM with $m$ symbols and $n$ states is ?$m+n$$8mn+4m$$mn$$4mn+m$
User Avatar
5 votes
0 answers
6256
Identify the class of given mod based language
L = {anbm | n mod m = 0 , n>=0 , m>0} Given language is A) CFL B) CSL C) DCFL D) REC E) RE
L = {anbm | n mod m = 0 , n>=0 , m>0} Given language isA) CFLB) CSLC) DCFLD) RECE) RE
User Avatar
1 votes
0 answers
6258
toc
all FA is regular language but every regular language is not FA.?? wt does it mean.??
all FA is regular language but every regular language is not FA.?? wt does it mean.??
User Avatar
1 votes
3 answers
6260
Identify the class of the language
$L=\left\{ w\in(a+b)^* \mid w \\ \text{ has at least as many occurrences of (bba)'s as (abb)'s}\right\}$     Identify the class of the language.
$L=\left\{ w\in(a+b)^* \mid w \\ \text{ has at least as many occurrences of (bba)'s as (abb)'s}\right\}$    Identify the class of the language.
User Avatar
Page: