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 answered questions in Theory of Computation

0 votes
0 answers
6561
ME-Practice Set TOC Q#100
User Avatar
1 votes
0 answers
6562
ME-TOC-Practice Set Q#137
User Avatar
0 votes
0 answers
6563
vgate:TOC
User Avatar
5 votes
0 answers
6564
UNDECIDABLE
User Avatar
0 votes
0 answers
6566
Decidability ME test series
Which of the following language is decidable? a. {(M)| M is a TM and there exist an input whose length is less than 100, on which M halts} b. {(M)| M is a TM and L(M) = {00, 11}} c. Both (a) and (b) d. None of the above
Which of the following language is decidable?a. {(M)| M is a TM and there exist an input whose length is less than 100, onwhich M halts}b. {(M)| M is a TM and L(M) = {00,...
User Avatar
0 votes
0 answers
6568
decidability
1. I know that whether a cfg generates regular language is undecidable .... somone plzz help me to prove that whether a given cfl is regular language also undecidable .... 2. how equvilance problem on 2 dcfl is decidable??
1. I know that whether a cfg generates regular language is undecidable ....somone plzz help me to prove thatwhether a given cfl is regular language also undecidable .......
User Avatar
0 votes
0 answers
6571
test series
is this explaination is correct? .Because according me complement given in explnation is only subset of complement of L . please correct me if i am wrong
is this explaination is correct? .Because according me complement given in explnation is only subset of complement of L . please correct me if i am wrong
User Avatar
0 votes
0 answers
6572
ace test series
is this explaination is correct because according me complement given in language is only subset of complement of L . please correct me if i am wrong
is this explaination is correct because according me complement given in language is only subset of complement of L . please correct me if i am wrong
User Avatar
0 votes
0 answers
6576
Pumping lemma
Why does the pumping lemma (weaker one) fails
Why does the pumping lemma (weaker one) fails
User Avatar
1 votes
0 answers
6578
Number of nodes in the derivation tree
Number of nodes in the derivation tree when a word of length $2^{k}$ is derived from a grammar in CNF? 1. 2^(k+1) – 1 2. 3*2^k – 1 3. 2^(k+1) + 1 4. 3*2^k + 1
Number of nodes in the derivation tree when a word of length $2^{k}$ is derived from a grammar in CNF?1. 2^(k+1) – 12. 3*2^k – 13. 2^(k+1) + 14. 3*2^k + 1
User Avatar
1 votes
0 answers
6579
Turing Machine
Desgin a Turing Machine that accept the language L, a*baa*
Desgin a Turing Machine that accept the language L, a*baa*
User Avatar
5 votes
0 answers
6580
TURING MACHINE
Design a Turing Machine to recognize an arbitrary string divisible by 4, given ∑= {0,1,2}.
Design a Turing Machine to recognize an arbitrary string divisible by 4, given ∑= {0,1,2}.
User Avatar
Page: