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
6581
Plz explain
. Consider these 2 statements: S1: LR = L, if and only if L is the language of palindromes. where LR is obtained by reversing all the strings of L. S2: | L1∙ L2 | = | L1 | × | L2 | Relation? (a) Both are F (b) Both are T 2 (c) S1 → T, S2 → F (d) S1 → F, S2 → T
. Consider these 2 statements:S1: LR = L, if and only if L is the language of palindromes. where LR is obtained by reversing all the strings of L.S2: | L1∙ L2 | = | L1 ...
User Avatar
0 votes
1 answer
6584
what is the minimum no of DFA states required to recognise below language?
L={a^nk , k>0 and n is an integer constant } In this question which constant should be changed , n or k while considering the DFA since then it can be either n+1 or k+1 ?
L={a^nk , k>0 and n is an integer constant }In this question which constant should be changed , n or k while considering the DFA since then it can be either n+1 or k+1 ?
User Avatar
0 votes
1 answer
6586
How to make a DFA given a regular grammar ?
A-->aB/bA/b , B-->aC/bB , C-->aA/bC/a what is the approach ?
A >aB/bA/b , B >aC/bB , C >aA/bC/awhat is the approach ?
User Avatar
0 votes
2 answers
6587
Correct sustring in below fsm.
User Avatar
0 votes
0 answers
6588
Correct substring in in fsm.
User Avatar
0 votes
1 answer
6589
How to solve below recurrence relation ?
I tried till k=5 and then got 2 as no of words ,N(1)=N(3)=0 ,N(2)=N(4)=N(5)=2
I tried till k=5 and then got 2 as no of words ,N(1)=N(3)=0 ,N(2)=N(4)=N(5)=2
User Avatar
0 votes
1 answer
6590
what is the regular expression equivalent to the DFA ?
I tried it through state elimination method but I am getting stucked at the outgoing edge from D to A .
I tried it through state elimination method but I am getting stucked at the outgoing edge from D to A .
User Avatar
0 votes
2 answers
6591
CFG
Why is S2 not a correct option?
Why is S2 not a correct option?
User Avatar
0 votes
1 answer
6592
How can we say r* and r+ may be equal?? Is it correct?
How can we say r* and r+ may be equal?? Is it correct?
How can we say r* and r+ may be equal?? Is it correct?
User Avatar
0 votes
1 answer
6594
solve this one
L=b^m right??
L=b^m right??
User Avatar
0 votes
1 answer
6595
Plz solve this one
  the formula is n^(n*m+1)*2^n ,where n=no of states and m= no of input symbols. right?? 
 the formula is n^(n*m+1)*2^n ,where n=no of states and m= no of input symbols. right?? 
User Avatar
0 votes
1 answer
6596
Identify the class of the language
Identify the class of the language $L = \Bigl \{a^n b^m \mid n \leq m \leq 2n\Bigr \}$. a) CFL but not DCFL b) DCFL but not regular c) not CFL
Identify the class of the language $L = \Bigl \{a^n b^m \mid n \leq m \leq 2n\Bigr \}$.a) CFL but not DCFLb) DCFL but not regularc) not CFL
User Avatar
0 votes
1 answer
6600
GNF
consider the following CFG find minimum no of productions when converted in GNF form S->AA|0 A->SS|1
consider the following CFG find minimum no of productions when converted in GNF formS->AA|0A->SS|1
User Avatar
Page: