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

0 votes
1 answer
5101
Doubt on decidability
Are these 2 problems different? 1. Given grammar G, is G regular? 2. Given grammar G, is L(G) regular? Which of these 2 are decidable?
Are these 2 problems different?1. Given grammar G, is G regular?2. Given grammar G, is L(G) regular?Which of these 2 are decidable?
User Avatar
0 votes
0 answers
5102
string with quantification & alternation characters
User Avatar
0 votes
0 answers
5103
Turing Machine
Is Turing Machine that accpet Regular Languages Decidable ?
Is Turing Machine that accpet Regular Languages Decidable ?
User Avatar
6 votes
4 answers
5105
TOC- DFA
Number of states in DFA which accepts the binary strings divisible by 4 or 5. answer?
Number of states in DFA which accepts the binary strings divisible by 4 or 5.answer?
User Avatar
2 votes
1 answer
5106
context free grammar || Linz 5.1
... third grammar In Linz book it is given as $\begin{align*} & S\rightarrow aSbSa|aaSb|bSaa|SS|a \\ \end{align*}$ ..better explanation if possible.??
$\begin{align*} & L = \left \{ w \in \left \{ a,b \right \}^{*}\;\; : n_a(w) \neq n_b(w) \right \} \\ & S\rightarrow aSb|bSa|A|B \\ & A \rightarrow aA|a \\ & B \rightarro...
User Avatar
0 votes
2 answers
5109
MadeEasy Test Series: Theory Of Computation - Decidability
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable? Please explain.
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable?Please explain.
User Avatar
0 votes
1 answer
5110
Regular or not
Is xwwr regular or not Is wxwr regular X={a,b}*not +
Is xwwr regular or notIs wxwr regular X={a,b}*not +
User Avatar
0 votes
1 answer
5111
complement of prefix
User Avatar
0 votes
1 answer
5112
PDA membership
User Avatar
0 votes
1 answer
5113
TM acceptance
User Avatar
0 votes
2 answers
5115
dpda }} Linz7.3-4
DPDA for $L = \left \{ a^nb^n:n\geq 1 \right \} \cup\left \{ a \right \}$
DPDA for $L = \left \{ a^nb^n:n\geq 1 \right \} \cup\left \{ a \right \}$
User Avatar
0 votes
0 answers
5116
made easy_TOC
I think below is CFL, we need two copies but answer given is DCFL..please help for below lang. L= {a bn an | n>0} U {aa bk a2k | k>0 }
I think below is CFL, we need two copies but answer given is DCFL..please help for below lang.L= {a bn an | n>0} U {aa bk a2k | k>0 }
User Avatar
0 votes
2 answers
5117
dpda || Linz 7.3-2
DPDA for $L = \left \{ a^nb^m|m\geq n+2 \right \}$
DPDA for $L = \left \{ a^nb^m|m\geq n+2 \right \}$
User Avatar
0 votes
0 answers
5120
ace test
User Avatar
Page: