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
3931
Non-Deterministic PDA
I'm getting its equaltion {anbn | n > 0} U {a} U {b} But given is {anbn | n >= 0} U {a} U {b} Whether epsilon is accepted or not??
I'm getting its equaltion {anbn | n 0} U {a} U {b}But given is {anbn | n >= 0} U {a} U {b}Whether epsilon is accepted or not??
User Avatar
0 votes
0 answers
3932
turing machine
which of the following turing recognizable..????? L1 = {⟨M⟩∣ TM M accepts more than 2 distinct inputs} L2 = {⟨M⟩∣ TM M accepts at most 2 distinct inputs}
which of the following turing recognizable..?????L1 = {⟨M⟩∣ TM M accepts more than 2 distinct inputs}L2 = {⟨M⟩∣ TM M accepts at most 2 distinct inputs}
User Avatar
2 votes
1 answer
3933
TOC - Language Interpretation
$L_1=\{a^nb^nc^n\ |n>=0\}$ $L_2=\{a^{2n}b^{2n}c^{2n}\ |n>=0\}$ $L_3=\{ a^{2n}b^{2n}c^n\ |n>=0\}$ Options : $1)\ L_2 \subseteq L_1 \&L_2 \subseteq L_3 $ $2)\ L_2 \subseteq L_1 \&L_2 \not\subset L_3 $
$L_1=\{a^nb^nc^n\ |n>=0\}$$L_2=\{a^{2n}b^{2n}c^{2n}\ |n>=0\}$$L_3=\{ a^{2n}b^{2n}c^n\ |n>=0\}$Options :$1)\ L_2 \subseteq L_1 \&L_2 \subseteq L_3 $$2)\ L_2 \subseteq L_1 ...
User Avatar
0 votes
0 answers
3934
Type of Language
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
User Avatar
1 votes
2 answers
3936
(DCFL U Reg) '
Hi Guys, What will be ${\left ( DCFL \cup Regular \right )} '$ ?
Hi Guys,What will be ${\left ( DCFL \cup Regular \right )} '$ ?
User Avatar
3 votes
0 answers
3937
given language is DCFL?
$L=\{0^l1^{2l}0^{l+n}|l\geq{0},n\geq{0}\}$
$L=\{0^l1^{2l}0^{l+n}|l\geq{0},n\geq{0}\}$
User Avatar
1 votes
0 answers
3939
toc ace
User Avatar
0 votes
0 answers
3940
Turing machine
Cant we infer that their complexity remains same
Cant we infer that their complexity remains same
User Avatar
2 votes
0 answers
3941
ACE TEST SERIES
Identify an equivalent non-left recursive CFG for the following CFG: How to solve such quesitons? I know that, if A->Ax/y then it will be reduced to A->yA' A'->xA'/epsilon How to identify "y" from above example.
Identify an equivalent non-left recursive CFG for the following CFG:How to solve such quesitons?I know that, ifA->Ax/ythen it will be reduced toA->yA'A'->xA'/epsilonHow t...
User Avatar
2 votes
1 answer
3942
Decidable or undecidable
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
User Avatar
2 votes
0 answers
3943
TOC(Language)
getting B and C both as answers how it is closed under compliment.
getting B and C both as answers how it is closed under compliment.
User Avatar
2 votes
0 answers
3944
Gate_Model_Paper_TOC
How to find give language is true or not ? please explain it ....step by step
How to find give language is true or not ? please explain it ....step by step
User Avatar
0 votes
0 answers
3945
Turing machine tape moves
The maximum number of moves required by a single tape turing machine to simulate a 5-tape turing machine, which has 20 moves is a) 20 b) 50 c) 80 d) 90
The maximum number of moves required by a single tape turing machine to simulate a 5-tape turing machine, which has 20 moves isa) 20b) 50c) 80d) 90
User Avatar
2 votes
1 answer
3946
Peter Linz ex-2.3
Convert the nfa defined by δ (q0,a)={q0,q1} δ (q1,b)={q1,q2} δ (q2,a)={q2} δ (q1,λ)={q1,q2} Where q0 is initial state and q2 final state into equivalent DFA.
Convert the nfa defined byδ (q0,a)={q0,q1}δ (q1,b)={q1,q2}δ (q2,a)={q2}δ (q1,λ)={q1,q2}Where q0 is initial state and q2 final state into equivalent DFA.
User Avatar
1 votes
0 answers
3948
MadeEasy Test Series 2018: Theory of Computation - Regular Grammer
What is the correct way to solve questions of this kind where equations like these are given and you are asked to determine what languages do the variables X1 X2 X3.. represent?
What is the correct way to solve questions of this kind where equations like these are given and you are asked to determine what languages do the variables X1 X2 X3.. rep...
User Avatar
2 votes
0 answers
3949
minimal dfa
Consider the following grammar: $S\rightarrow aA|bB$ $A\rightarrow aA|bB$ $B\rightarrow bB|ϵ$ Then the number of states in a minimal D.F.A of the above grammar is ______________ ?
Consider the following grammar:$S\rightarrow aA|bB$$A\rightarrow aA|bB$$B\rightarrow bB|ϵ$Then the number of states in a minimal D.F.A of the above grammar is __________...
User Avatar
1 votes
0 answers
3950
TOC:- Moore Melay Machine
The output of moore machine will always have start state output as prefix? True/False?
The output of moore machine will always have start state output as prefix? True/False?
User Avatar
Page: