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
3 answers
6262
toc
how to approach $L=\{a^mb^nc^pd^q\ |\ m+n=p+q \}$ give grammar for it???
how to approach$L=\{a^mb^nc^pd^q\ |\ m+n=p+q \}$give grammar for it???
User Avatar
1 votes
2 answers
6263
How to construct PDA for the given language ?
If input symbol is{ a, b} and L ={no of a's =2*no of b's } , issue here is that since we do not have any sequence so what should be done when I see any a or b ?
If input symbol is{ a, b} and L ={no of a's =2*no of b's } , issue here is that since we do not have any sequence so what should be done when I see any a or b ?
User Avatar
2 votes
0 answers
6264
How do we empty non-terminals from the stack in this pda ?
In this one how come from q1 we are directly converting it into qf , since non-terminals have not been emptied , this method is for converting grammar in GNF to PDA .
In this one how come from q1 we are directly converting it into qf , since non-terminals have not been emptied , this method is for converting grammar in GNF to PDA .
User Avatar
3 votes
1 answer
6265
#Toc
I read some where that if thier is one comparision at any time then only CFL otherwise CSL? plz give proof.
I read some where that if thier is one comparision at any time then only CFL otherwise CSL?plz give proof.
User Avatar
2 votes
2 answers
6266
What is the Regular Expression for
The regular expression for the language recognized by the following Finite State Automaton is? $0^* \mid 0^* 1^+$ $0^* \mid 11^*$ $0^* \mid 0^* 1^+ \mid 0^* 1^+ (0+1)^*$ None of these.
The regular expression for the language recognized by the following Finite State Automaton is?$0^* \mid 0^* 1^+$$0^* \mid 11^*$$0^* \mid 0^* 1^+ \mid 0^* 1^+ (0+1)^*$None...
User Avatar
0 votes
1 answer
6267
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
6269
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
6270
Correct sustring in below fsm.
User Avatar
0 votes
0 answers
6271
Correct substring in in fsm.
User Avatar
1 votes
1 answer
6272
How to design grammar for below language ?
L={w ={a,b}* : (no of a's -no of b's) mod 3 =1 }
L={w ={a,b}* : (no of a's -no of b's) mod 3 =1 }
User Avatar
1 votes
1 answer
6273
how to approach this kind of questions , any algorithm ???
Which one of the following strings is not accepted by the finite automaton described by the regular expression $(0+1(01^*0)^*1)^*$? $1100100011011001011$ $0110100010111010010$ $0100011010111010101$ $1101001101100010011$
Which one of the following strings is not accepted by the finite automaton described by the regular expression $(0+1(01^*0)^*1)^*$?$1100100011011001011$$01101000101110100...
User Avatar
5 votes
2 answers
6275
Understanding Rice theorem
Please share some good resources and questions which can make it easier for me to understand and apply Rice theorem.
Please share some good resources and questions which can make it easier for me to understand and apply Rice theorem.
User Avatar
21 votes
5 answers
6276
GATE CSE 1991 | Question: 17,a
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
User Avatar
0 votes
1 answer
6277
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
6278
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
1 votes
1 answer
6280
Theory of computation question
http://geeksquiz.com/gate-gate-cs-2015-set-1-question-60/ please give explanation to this question.
http://geeksquiz.com/gate-gate-cs-2015-set-1-question-60/please give explanation to this question.
User Avatar
Page: