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
0 answers
5001
Testbook
Consider the following sets L1 = {apbq | p +q >= 106 } L2 = {ambn | m - n >= 106} Which of the following is a Regular Language? Also how to find the compliment of the given languages?
Consider the following sets L1 = {apbq | p +q >= 106 }L2 = {ambn | m - n >= 106}Which of the following is a Regular Language? Also how to find the compliment of the given...
User Avatar
1 votes
1 answer
5003
Minimal DFA
Number of states in Minimal DFA that accepts Language L=$\left \{ ab^* a^* \cup (ab)^* ba\right \}$
Number of states in Minimal DFA that accepts Language L=$\left \{ ab^* a^* \cup (ab)^* ba\right \}$
User Avatar
2 votes
1 answer
5004
Vgate
Which of the following is correct? a) Top-down parser complexity is O(n4) b) Bottom-up parser complexity is O(n3) (A) True, False (B) False, True (C) True, True (D) False, False can anyone explain how to analyze this complexity?
Which of the following is correct?a) Top-down parser complexity is O(n4)b) Bottom-up parser complexity is O(n3)(A) True, False(B) False, True(C) True, True(D) False, Fals...
User Avatar
1 votes
1 answer
5006
Language accepted by NFA
Consider the NFA below: The above NFA acceptes all those binary strings which represents the decimal numbers and are a. divisible by 6 only b. dividible by 2 and 3 only c. divisible by 2 or 3 d. None of these
Consider the NFA below:The above NFA acceptes all those binary strings which represents the decimal numbers and area. divisible by 6 onlyb. dividible by 2 and 3 onlyc. di...
User Avatar
5 votes
2 answers
5011
Minimal DFA
$L_1 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 8 = 0 \right \}$ $L_2 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 4 = 0 \right \}$ $d(w) = \text{decimal value of binary string w}$ Minimum no of states in both the cases ?
$L_1 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 8 = 0 \right \}$$L_2 = \left \{ w \;\; | \;\; d(w) \text{ mod} \; 4 = 0 \right \}$$d(w) = \text{decimal value of binary ...
User Avatar
2 votes
1 answer
5012
Intersection of two context free languages
Does the below problem makes any sense? And if yes what is its answer? How?
Does the below problem makes any sense? And if yes what is its answer? How?
User Avatar
2 votes
1 answer
5013
How is this language context free?
How below language is context free? I am not able to imagine what could be the behaviour of the PDA accepting this language. Can anyone give a hint? $L=\{\omega:2n_a(\omega)\leq n_b(\omega)\leq 3n_a(\omega)\}$
How below language is context free? I am not able to imagine what could be the behaviour of the PDA accepting this language. Can anyone give a hint?$L=\{\omega:2n_a(\omeg...
User Avatar
0 votes
1 answer
5014
Number of nodes
I am getting option (D). But answer is given as (B). Please check.
I am getting option (D). But answer is given as (B). Please check.
User Avatar
0 votes
0 answers
5015
Gateforum MT 3
User Avatar
0 votes
1 answer
5016
Regular language
L= {(ap)* | p is a prime number} is this regular? if yes, then how?
L= {(ap)* | p is a prime number} is this regular? if yes, then how?
User Avatar
0 votes
2 answers
5017
Regular Languages
if this is regular and its Regular expression can be written as [(0+1)*0(0+1)*0]+ [(0+1)*1(0+1)*1] then it will also include those strings where first W2 second W2 are different. I am not getting this somebody please clear this doubt.
if this is regular and its Regular expression can be written as [(0+1)*0(0+1)*0]+ [(0+1)*1(0+1)*1] then it will also include those strings where first W2 second W2 are di...
User Avatar
0 votes
0 answers
5018
decidability doubt
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems??
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems...
User Avatar
0 votes
2 answers
5020
Language Class
User Avatar
Page: