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
0 answers
6081
which length string has to be removed
User Avatar
0 votes
4 answers
6084
language
User Avatar
0 votes
1 answer
6085
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
6087
Find Language
User Avatar
1 votes
1 answer
6088
dfa
dfa for a*b* + b*a* ?
dfa for a*b* + b*a* ?
User Avatar
0 votes
1 answer
6089
Is phi a regular language or not
phi is regular language or not
phi is regular language or not
User Avatar
1 votes
2 answers
6090
Left linear grammar
Consider the following right linear grammar. S->aA/abc A->aA/bB/a B->bB/cC/b C->cC/c Find left linear grammar is equivalent to the above right linear grammar?
Consider the following right linear grammar.S->aA/abcA->aA/bB/aB->bB/cC/bC->cC/cFind left linear grammar is equivalent to the above rightlinear grammar?
User Avatar
0 votes
1 answer
6091
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
6093
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
5 votes
4 answers
6094
If L1 is Regular, and L1UL2 is regular, then L2 is?
Consider L1, L2 ⊆ Ʃ* such that L1 and L1 ∪ L2 are regular. (a) L2 is definitely regular (b) L2 may not be regular (c) L2 is context free (d) None of above Is it option B or C? How?
Consider L1, L2 ⊆ Ʃ* such that L1 and L1 ∪ L2 are regular.(a) L2 is definitely regular(b) L2 may not be regular(c) L2 is context free(d) None of aboveIs it option B ...
User Avatar
0 votes
1 answer
6095
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
6096
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
6098
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
6100
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: