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{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} &1&1&3& 2 &2&3& 1&2&3
\\\hline\textbf{2 Marks Count} &2&3&3& 3 &3&4& 2&3&4
\\\hline\textbf{Total Marks} &5&7&9& 8 &8&11&\bf{5}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Filter

Recent questions in Theory of Computation

0 votes
1 answer
5182
decidability 
Decidability of M is a TM and L(M) is a regular language ?
Decidability of M is a TM and L(M) is a regular language ?
User Avatar
0 votes
1 answer
5184
turning machine
TM 'M1' accepts atmost 2 distinct input . TM 'M2' accept more than 2 distinct input . Which of the machine is Turning recognizable ?
TM 'M1' accepts atmost 2 distinct input .TM 'M2' accept more than 2 distinct input . Which of the machine is Turning recognizable ?
User Avatar
0 votes
2 answers
5185
toc rlg
Construct a Right Linear Grammar for the Language L((aab*ab)*)
Construct a Right Linear Grammar for the Language L((aab*ab)*)
User Avatar
0 votes
1 answer
5186
Toc RLG to LLG
Construct right-linear grammar and left-linear grammar for the language L ={anbm : n$\geq$2 , m$\geq$3} Explanation about this....???
Construct right-linear grammar and left-linear grammar for the languageL ={anbm : n$\geq$2 , m$\geq$3}Explanation about this....???
User Avatar
0 votes
3 answers
5187
cfg toc
S->AbaC A->BC B->b/epsilon C->D/epsilon D->d I want to know that will A contain epsilon as B and C both are null variables???(In Elimination of epsilon-production)
S->AbaCA->BCB->b/epsilonC->D/epsilonD->d I want to know that will A contain epsilon as B and C both are null variables???(In Elimination of epsilon-production)
User Avatar
1 votes
1 answer
5188
DOubt TOC
L = { ap | P is NOT Prime } - How to prove is it CFL or NOT?
L = { ap | P is NOT Prime } - How to prove is it CFL or NOT?
User Avatar
1 votes
2 answers
5189
Self Doubt TOC
L = { am bm cn dn ei fi | i > m>n>0 , i<= 10 } is DCFL or not?
L = { am bm cn dn ei fi | i m>n>0 , i<= 10 } is DCFL or not?
User Avatar
2 votes
2 answers
5190
TOC test
L ={$a^nb^k$ | n$\leq$k$\leq$2n} CFL or not?? L ={$a^ib^jc^k$ | (i$\leq$j) or (j$\leq$i), j=k} CFL or not??
L ={$a^nb^k$ | n$\leq$k$\leq$2n} CFL or not??L ={$a^ib^jc^k$ | (i$\leq$j) or (j$\leq$i), j=k} CFL or not??
User Avatar
0 votes
1 answer
5191
toc non context free grammar
Why is a^n^2 a non context free language?..please explain
Why is a^n^2 a non context free language?..please explain
User Avatar
1 votes
2 answers
5192
ME FLT -3
User Avatar
1 votes
2 answers
5193
moore machine toc
Construct a moore machine that takes set of all strings over {0,1} and produces 'A' as output if input ends with '10' or produces 'B' as output if input ends with '11' otherwise produces 'C'.
Construct a moore machine that takes set of all strings over {0,1} and produces 'A' as output if input ends with '10' or produces 'B' as output if input ends with '11' ot...
User Avatar
2 votes
1 answer
5194
moore machine dfa
Construct a moore machine that takes set of all strigs over {a,b} and count the number of occurences of substring "baa".
Construct a moore machine that takes set of all strigs over {a,b} and count the number of occurences of substring "baa".
User Avatar
1 votes
2 answers
5195
ToC grammar
The total number of 4 length strings generated by this grammar (0+1+ | 2+3+)* are _______________.
The total number of 4 length strings generated by this grammar (0+1+ | 2+3+)* are _______________.
User Avatar
0 votes
0 answers
5197
doubt
User Avatar
0 votes
1 answer
5198
question bank
Consider the following statements: S1: Infinite union of regular languages can be context-free. S2: Language obtained after applying Kleen closure on a regular language will always be regular and infinite. Which of the above statement is true?
Consider the following statements:S1: Infinite union of regular languages can be context-free.S2: Language obtained after applying Kleen closure on a regular language wil...
User Avatar
1 votes
1 answer
5199
toc dfa
Construct minimal DFA which accepts set of all srings over {a,b} which starts and ends with the same symbol???
Construct minimal DFA which accepts set of all srings over {a,b} which starts and ends with the same symbol???
User Avatar
Page: