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

Highest voted questions in Theory of Computation

0 votes
1 answer
6541
Find Language
User Avatar
0 votes
1 answer
6542
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
6543
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
0 votes
1 answer
6544
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
6545
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
6547
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
0 votes
2 answers
6548
why is the given property of language non-trivial ?
L={<M>|L(M) is regular } ,isn't it a trivial property because every TM accepts regular language.
L={<M>|L(M) is regular } ,isn't it a trivial property because every TM accepts regular language.
User Avatar
0 votes
2 answers
6549
Dcfl or not
L={w0w $\mid$ w$\in$(0+a+b)*}
L={w0w $\mid$ w$\in$(0+a+b)*}
User Avatar
0 votes
0 answers
6550
Minimization of dfa
Do we have any shortcut for minimization of dfa
Do we have any shortcut for minimization of dfa
User Avatar
0 votes
0 answers
6552
Partially Decideable 1,1
Some explanation?
Some explanation?
User Avatar
0 votes
1 answer
6553
TOC: DFA Minimization
Clear Image URL: http://postimg.org/image/ljcst3k0t/
Clear Image URL: http://postimg.org/image/ljcst3k0t/
User Avatar
0 votes
1 answer
6555
what is the class of Min(R) for a given regular language ?
Let R be any regular set .Let Min(R) is a set of all strings 'w' in R , where every proper prefix of 'w' is not in R, then to which class of language does this Min(R) belong ?
Let R be any regular set .Let Min(R) is a set of all strings 'w' in R , where every proper prefix of 'w' is not in R, then to which class of language does this Min(R) bel...
User Avatar
0 votes
5 answers
6556
MadeEasy Test Series: Theory Of Computation - Finite Automata
Let L = {(aP)*⎪P is a prime number} and Σ={a}. The minimum number of states in NFA that accepts the language L are ________. i don't think it is even a regular language. then how can NFA be generated?
Let L = {(aP)*⎪P is a prime number} and Σ={a}. The minimum number of states in NFA that accepts the language L are ________.i don't think it is even a regular language...
User Avatar
0 votes
1 answer
6557
How to design PDA for given language ?
L={anbn :n>=0 ,n!=100} how to take care of the condition that n !=100 ?
L={anbn :n>=0 ,n!=100} how to take care of the condition that n !=100 ?
User Avatar
0 votes
1 answer
6558
What sub-topics do I need to study to cover Turing machines and Undecidability ?
Do I need to study basic concepts of complexity classes (P, NP , NP-Hard...reduction etc.) ?
Do I need to study basic concepts of complexity classes (P, NP , NP-Hard...reduction etc.) ?
User Avatar
0 votes
1 answer
6559
DCFL,CFL,NonDCFL,Non CFl
how to we identify them... if a lang is not cfl then it is DCFL?? what is differenc between all of them
how to we identify them...if a lang is not cfl then it is DCFL??what is differenc between all of them
User Avatar
0 votes
1 answer
6560
regular or context free ?
(a+b)^* a^n b^n n>=1
(a+b)^* a^n b^n n>=1
User Avatar
Page: