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

1 votes
0 answers
3871
gatequestions
How to solve turing machine decidable/undecidable questions ? Do I need to mug them up ?
How to solve turing machine decidable/undecidable questions ? Do I need to mug them up ?
User Avatar
1 votes
0 answers
3872
peter linz
User Avatar
1 votes
2 answers
3873
peter linzdfa
(4.d) dfa of L (((aa*)* b)*).
(4.d) dfa of L (((aa*)* b)*).
User Avatar
2 votes
2 answers
3874
peter linz
a) Find a regular expression that denotes all bit strings whose value, when interpreted as a binary integer, is greater than or equal to 40. b) Find a regular expression for all bit strings, with leading bit 1, interpreted as a binary integer, with values not between 10 and 30.
a) Find a regular expression that denotes all bit strings whose value, when interpreted as a binaryinteger, is greater than or equal to 40.b) Find a regular expression fo...
User Avatar
1 votes
1 answer
3875
peter linz
For the case of a regular expression r that does not involve λ or Ø, give a set of necessary and sufficient conditions that r must satisfy if L(r) is to be infinite.
For the case of a regular expression r that does not involve λ or Ø, give a set of necessary andsufficient conditions that r must satisfy if L(r) is to be infinite.
User Avatar
1 votes
1 answer
3876
At most one pair of consecutive 1's
If regular expression (1+01)*(0+1*) is represented as E. Which of the following regular expression denotes the set of all strings in {0,1}* that contains at most one pair of consecutive 1's a)E* b)E+E c)EE d)None of the above
If regular expression (1+01)*(0+1*) is represented as E. Which of the following regular expression denotes the set of all strings in {0,1}* that contains at most one pair...
User Avatar
5 votes
1 answer
3877
Peter Linz CFL
Which of the following languages are CFL? $a) L=\{a{^n}ww{^R}a{^n} \ | n>=0, w\ \epsilon \{a,b\}{^*}\}$ $b) L=\{a{^n}b{^j}a{^j}b{^n} \ | n>=0, j>=0\}$ $c) L=\{a{^n}b{^j}a{^n}b{^j} \ | n>=0, j>=0\}$ $d) L=\{a{^n}b{^n}c{^j} \ | n<=j\}$
Which of the following languages are CFL?$a) L=\{a{^n}ww{^R}a{^n} \ | n>=0, w\ \epsilon \{a,b\}{^*}\}$$b) L=\{a{^n}b{^j}a{^j}b{^n} \ | n>=0, j>=0\}$$c) L=\{a{^n}b{^j}a{^n...
User Avatar
2 votes
2 answers
3878
Find The DFA
User Avatar
3 votes
2 answers
3879
DFA No. Strings
User Avatar
1 votes
0 answers
3880
no of strings dfa
User Avatar
3 votes
1 answer
3881
Regular Expression
User Avatar
2 votes
2 answers
3882
languages
L1 = {am bn cn | m,n>=0} L2 = {an bn | n>=0} if L ={ L1 -L2} then L is a) finite lang b) regular c) DCFL d) CFL but not DCFL
L1 = {am bn cn | m,n>=0} L2 = {an bn | n>=0} if L ={ L1 -L2} then L isa) finite langb) regularc) DCFLd) CFL but not DCFL
User Avatar
2 votes
1 answer
3884
Regular Expression
User Avatar
0 votes
0 answers
3886
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
0 votes
1 answer
3887
Number of States in minimal DFA
How many states will have the minimal DFA accepting the language L={w|wϵ{0,1}* and contains atleast one 0 and two 1's} a) 6 b)7 c)8 d)12
How many states will have the minimal DFA accepting the language L={w|wϵ{0,1}* and contains atleast one 0 and two 1's}a) 6b)7c)8d)12
User Avatar
0 votes
0 answers
3888
DFA (TOC)
Construct a minimal dfa which accepts set of all strings over {a,b} such that third symbol from RHS is 'a'.
Construct a minimal dfa which accepts set of all strings over {a,b} such that third symbol from RHS is 'a'.
User Avatar
0 votes
1 answer
3889
self doubt
what is the relation between P AND NP PROBLEMS and decidability?? .. please suggest me a resource to learn in short time or explain in brief
what is the relation between P AND NP PROBLEMS and decidability?? .. please suggest me a resource to learn in short time or explain in brief
User Avatar
0 votes
0 answers
3890
Regular language
{XWWrY} is regular or not? XYW € (0,1)+
{XWWrY} is regular or not?XYW € (0,1)+
User Avatar
Page: