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
4621
How many N bits Strings?
Consider the below DFA over the alphabet {0,1} State 0 1 →*Q0 Q1 Q3 Q1 Q2 Q0 Q2 Q3 Q1 Q3 Q0 Q2 How many N bits strings will be accepted by the above DFA if N=2X where X={2,3,4.......}? a)NC2 b)NC2+2 c)NC(N/2)+2 d)NC(N/2)
Consider the below DFA over the alphabet {0,1}State01→*Q0Q1Q3Q1Q2Q0Q2Q3Q1Q3Q0Q2How many N bits strings will be accepted by the above DFA if N=2X where X={2,3,4.......}?...
User Avatar
1 votes
1 answer
4622
test-series
User Avatar
0 votes
1 answer
4624
equivalence
2. Which of the following is true? a) (01)*0 = 0(10)* b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)* c) (0+1)*01(0+1)*+1*0* = (0+1)* d) All of the mentioned
2. Which of the following is true?a) (01)*0 = 0(10)*b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*c) (0+1)*01(0+1)*+1*0* = (0+1)*d) All of the mentioned
User Avatar
1 votes
1 answer
4625
test-series
User Avatar
0 votes
1 answer
4626
mock-test
Which of the following regular expression generates the set of all strings not containing ‘baa’ as a substring over input alphabet {a, b}? (a) a*(b*a)* (b) a*b*ab (c) a*baba* (d) a*(ba+b)*
Which of the following regular expression generates the set of all strings not containing ‘baa’ as a substring over input alphabet {a, b}?(a) a*(b*a)* (b) a*b*ab(c) a...
User Avatar
2 votes
1 answer
4627
Regular Expression
What is the regular expression for all strings over {0, 1} not containing the substring 101?
What is the regular expression for all strings over {0, 1} not containing the substring 101?
User Avatar
1 votes
2 answers
4629
Theory of computation
No of State for minimal DFA for empty language ? If your answer is 1 or 2 then please explain to support your answer
No of State for minimal DFA for empty language ?If your answer is 1 or 2 then please explain to support your answer
User Avatar
0 votes
0 answers
4630
Turing Machine
Given transition table of TM as follows, 0 1 B q0 qo,1,R, q0,0,R q1,B,R q1 q0,1,R q0,0,R Halt What is the language accepted by above single tape TM where q0 is start State. Tape Alphabet {0,1,B} and input alphabet {0,1}.
Given transition table of TM as follows, 01Bq0qo,1,R,q0,0,Rq1,B,Rq1q0,1,Rq0,0,RHalt What is the language accepted by above single tape TM where q0 is start State.Tape ...
User Avatar
2 votes
2 answers
4631
MDFA.
Consider the following NFA Number of states in the equivalent minimal DFA is_________???? (Note: Count one for the dead state (if required))
Consider the following NFANumber of states in the equivalent minimal DFA is_________????(Note: Count one for the dead state (if required))
User Avatar
0 votes
2 answers
4632
Automata Grammar Language
What is the relationship between a Language -to- Grammar and a Grammar -to -Language .Give an example for both. A. One -to- Many B. One -to- One C. Many -to- One D. Many to- Many
What is the relationship between a Language -to- Grammar and a Grammar -to -Language .Give an example for both.A. One -to- ManyB. One -to- OneC. Many -to- One D. Many to-...
User Avatar
0 votes
2 answers
4633
#TOC Simplify RegEx
Can we simplify this RegEx - $a^*ba^*b(a+b)^*$
Can we simplify this RegEx - $a^*ba^*b(a+b)^*$
User Avatar
0 votes
1 answer
4635
doubt: Closure Property
Let Exchange(L1) : { XwY | YwX ∈ L1 , X,Y∈ Σ } Is Exchange(L1) closed or regular? If yes please give some prove .
Let Exchange(L1) : { XwY | YwX ∈ L1 , X,Y∈ Σ }Is Exchange(L1) closed or regular?If yes please give some prove .
User Avatar
0 votes
2 answers
4636
context free
a) L = {0i1j2k | k <= i or k <= j} its CFL or DCFL? b) L is a set of binary complement what does this mean?
a) L = {0i1j2k | k <= i or k <= j}its CFL or DCFL?b) L is a set of binary complementwhat does this mean?
User Avatar
0 votes
1 answer
4637
Union
How to calculate the union of two regular expression? Kindly explain with an example. Thank you.
How to calculate the union of two regular expression? Kindly explain with an example. Thank you.
User Avatar
0 votes
1 answer
4638
ace test series
Choose appropriate context free language l2..
Choose appropriate context free language l2..
User Avatar
1 votes
0 answers
4639
Is it regular ?
L={vuv|v,u∈{a,b}*,|v|=3 } . Is L regular ?
L={vuv|v,u∈{a,b}*,|v|=3 } . Is L regular ?
User Avatar
0 votes
1 answer
4640
LAnguage
L = { a^m b^n b^k d^l |(n+k)=odd only if m=l; m, n, k , l>0}. Which is true? a)CFL but not DCFL b)regular but not CFL c)DCFL but not regular d)none
L = { a^m b^n b^k d^l |(n+k)=odd only if m=l; m, n, k , l>0}. Which is true?a)CFL but not DCFLb)regular but not CFLc)DCFL but not regulard)none
User Avatar
Page: