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

Most answered questions in Theory of Computation

0 votes
1 answer
4203
Decidable and Undecidable problems of automata
Please list down all the decidable and undecidable problems for FA, PDA, TM. Since there isnt a single place where all are listed.
Please list down all the decidable and undecidable problems for FA, PDA, TM.Since there isnt a single place where all are listed.
User Avatar
0 votes
1 answer
4204
REGULAR OR NOT
WHICH ONE REGULAR 1.{a^m b^n} m=4-n 2{a^m b^n} m=n-4 3.{a^m b^n} m-n=4
WHICH ONE REGULAR 1.{a^m b^n} m=4-n2{a^m b^n} m=n-43.{a^m b^n} m-n=4
User Avatar
0 votes
1 answer
4208
Closure property
A CFL $\cap$ a DCFL (i.e what is the intersection of a CFL with a DCFL??)
A CFL $\cap$ a DCFL (i.e what is the intersection of a CFL with a DCFL??)
User Avatar
0 votes
1 answer
4210
Find Language
User Avatar
1 votes
1 answer
4211
dfa
dfa for a*b* + b*a* ?
dfa for a*b* + b*a* ?
User Avatar
0 votes
1 answer
4212
Is phi a regular language or not
phi is regular language or not
phi is regular language or not
User Avatar
0 votes
1 answer
4213
Pumping Lemma RL CFL & Pumping Length
What is the basic Conditions for Pumping Lemma of RL and CFL I found different ans in different sources Also Tell me what is a pumping length ? IS there any minimum pumping length or something ?
What is the basic Conditions for Pumping Lemma of RL and CFLI found different ans in different sourcesAlso Tell me what is a pumping length ?IS there any minimum pumping ...
User Avatar
2 votes
1 answer
4215
Number of final state require to accept Φ in minimal finite automata.
Number of final state require to accept Φ in minimal finite automata. a) 1 b) 2 c) 3 d) None of the mentioned
Number of final state require to accept Φ in minimal finite automata.a) 1b) 2c) 3d) None of the mentioned
User Avatar
0 votes
1 answer
4216
Regular Expression and strings
Let L1 = 0*1*, L2 = 1*0*, L3 = (0+1)* and L4 = 0*1*0*. Then the number of strings in the following language L are ________. L = (L1 ∩ L2 ) – (L3 ∩ L4 )
Let L1 = 0*1*, L2 = 1*0*, L3 = (0+1)* and L4 = 0*1*0*. Then the number of strings in the following language L are ________. L = (L1 ∩ L2 ) &nd...
User Avatar
0 votes
1 answer
4217
type of language
let L=(a,b,c)* | the length of x is square then L is - a)Regular b)recursive but not context free c)context free but not regular d)none of these.
let L=(a,b,c)* | the length of x is square then L is -a)Regularb)recursive but not context freec)context free but not regulard)none of these.
User Avatar
0 votes
1 answer
4219
Virtual Gate Test Series: Theory Of Computation - Decidable Language
$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$ (C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$ (D) $L^R$ is decidable
$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$(C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$(D) $L^R$ is decidable
User Avatar
2 votes
1 answer
4220
Dfa
Dfa to accept strings with 0's and 1's so that no of 0's should be even and no of 1's is divisible by 3
Dfa to accept strings with 0's and 1's so that no of 0's should be even and no of 1's is divisible by 3
User Avatar
Page: