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{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} &1&1&3& 2 &2&3& 1&2&3
\\\hline\textbf{2 Marks Count} &2&3&3& 3 &3&4& 2&3&4
\\\hline\textbf{Total Marks} &5&7&9& 8 &8&11&\bf{5}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Filter

Recent questions in Theory of Computation

2 votes
1 answer
3723
R.E Language Question
Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. then what can you say about this - True/False a) A is Recursive, but B is not R.E
Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B.then what can you say about this - True/Falsea) A is Recursive...
User Avatar
0 votes
0 answers
3724
phrase structure grammar
User Avatar
1 votes
3 answers
3725
Pushdown Automata Question
i) I, II, III ii) I, II only iii) I only iv) none of the above
i) I, II, IIIii) I, II onlyiii) I onlyiv) none of the above
User Avatar
0 votes
1 answer
3726
PDA Construction
1)What is the main difference while drawing the PDA of {an bn | n>=0 } and {an bn | n>=1} ? 2)How does PDA changes when we have 0 in it as a constraint . 3)For all other cases how does the PDA changes on inclusion of 0.
1)What is the main difference while drawing the PDA of {an bn | n>=0 } and {an bn | n>=1} ?2)How does PDA changes when we have 0 in it as a constraint .3)For all other c...
User Avatar
0 votes
0 answers
3727
ACE test series
I and 2 are wrong statements. If 1 were right then since every DCFL is a recursive language the intersection of two DCFL would be DCFL which is not. Same logic can be applied to 2. Ace test series sucks.
I and 2 are wrong statements.If 1 were right then since every DCFL is a recursive language the intersection of two DCFL would be DCFL which is not.Same logic can be appli...
User Avatar
1 votes
1 answer
3728
PDA Doubt
In the below diagram which solution is correct and why ?
In the below diagram which solution is correct and why ?
User Avatar
0 votes
0 answers
3729
Problem while making a PDA
I feel it difficult to know when to change the state while making a PDA. Could anyone tell me in detailed manner when to cahnge the state . Below is the solution to a problem , could anyone tell me which one is more appropriate with justification.
I feel it difficult to know when to change the state while making a PDA.Could anyone tell me in detailed manner when to cahnge the state .Below is the solution to a probl...
User Avatar
3 votes
0 answers
3731
Is cnf gnf & cyk algoritm present in gate 2018 toc syllabus??
User Avatar
1 votes
1 answer
3732
Automata: CFG to CNF
As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"?
As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"?
User Avatar
2 votes
1 answer
3733
gatebook
Why answer a is not correct and how C is answer?
Why answer a is not correct and how C is answer?
User Avatar
0 votes
1 answer
3737
gatebook
What is meant by S grammar??
What is meant by S grammar??
User Avatar
1 votes
1 answer
3738
total recuursive function
What is total recursive function?
What is total recursive function?
User Avatar
0 votes
1 answer
3739
closuree
What are the languages closed under right quotient
What are the languages closed under right quotient
User Avatar
Page: