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

Hot questions in Theory of Computation

0 votes
0 answers
4201
are both regular expression correct ?
User Avatar
0 votes
1 answer
4203
Which of the following language generated by given grammar?
Which of the following language generated by given grammar? 1) L = {w : na(w) and nb(w) both are even} 2) L = {w : na(w) and nb(w) both are odd} 3) L = {w : na(w) or nb(w) are even} 4) L = {w : na(w) or nb(w) are odd}
Which of the following language generated by given grammar?1) L = {w : na(w) and nb(w) both are even}2) L = {w : na(w) and nb(w) both are odd}3) L = {w : na(w) or nb(w) a...
User Avatar
0 votes
0 answers
4204
test series
I am getting ans as B.....but ans is given c...plzz explain....
I am getting ans as B.....but ans is given c...plzz explain....
User Avatar
0 votes
1 answer
4205
Reducability
If a problem A is reducable to problem B and it is known that B is undecidable then is A undecidable?
If a problem A is reducable to problem B and it is known that B is undecidable then is A undecidable?
User Avatar
3 votes
3 answers
4207
Peter Linz Exercise 8.1
#10 Is the below language context free? L = { w1cw2 : w1,w2 ∈ {a,b}* , w1≠ w2} As per my analysis it is not. Please verify.
#10 Is the below language context free?L = { w1cw2 : w1,w2 ∈ {a,b}* , w1≠ w2}As per my analysis it is not. Please verify.
User Avatar
0 votes
0 answers
4208
What is the family of language described?
Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any languange , then what is the smallest language family $L'$ belongs to?
Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any languange , then what is the smallest language family $L'$ belongs to?
User Avatar
0 votes
1 answer
4209
toc-identify class of a language
User Avatar
0 votes
1 answer
4210
NFA and #states in DFA
Give the language accepted by the above NFA and #states in DFA accepting that language is _________________
Give the language accepted by the above NFA and #states in DFA accepting that language is _________________
User Avatar
0 votes
0 answers
4211
Which of given languages is/are DCFL / CLF?
DCFL or CFL? $L_1=\{0^n1^{2n} | n>=1\}$ $L_2=\{1^{2n}0^n | n>=1\}$
DCFL or CFL?$L_1=\{0^n1^{2n} | n>=1\}$$L_2=\{1^{2n}0^n | n>=1\}$
User Avatar
1 votes
0 answers
4212
Concatenation of two different language
Concatenation of two different language cannot be commutative until atleast one of them is ‘Φ’ or ‘∈ True or false
Concatenation of two different language cannot be commutative until atleast one of them is ‘Φ’ or ‘∈True or false
User Avatar
2 votes
2 answers
4213
micheal sipser
draw dfa w | w is any string not in (ab+)* ?
draw dfa w | w is any string not in (ab+)* ?
User Avatar
5 votes
0 answers
4214
Inherently Ambiguity
How to know whether L(G) is inherently ambiguous or not for a particular grammar 'G' ? Is there any algorithm for it ?
How to know whether L(G) is inherently ambiguous or not for a particular grammar 'G' ? Is there any algorithm for it ?
User Avatar
5 votes
2 answers
4215
How to make a minimal DFA
Draw a minimal DFA which accepts a language L over {a,b} 01 [ ((10) * + 111) * + 0 ] * 1
Draw a minimal DFA which accepts a language L over {a,b}01 [ ((10) * + 111) * + 0 ] * 1
User Avatar
0 votes
0 answers
4216
#theory of computation
User Avatar
0 votes
0 answers
4219
Test Series
How are P and NP classes related to Recursive and Recursively Enumerable classes ?
How are P and NP classes related to Recursive and Recursively Enumerable classes ?
User Avatar
0 votes
0 answers
4220
all npcomplete
2 problems A and B both are known to be NP-COMPLETE ? Is it possible that we can reduce A to B ??
2 problems A and B both are known to be NP-COMPLETE ? Is it possible that we can reduce A to B ??
User Avatar
Page: