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
0 answers
6561
Epsilon
Is Epsilon a terminal ? If yes, then why not we consider it as a separate column while making the LL(1) parsing table ?
Is Epsilon a terminal ? If yes, then why not we consider it as a separate column while making the LL(1) parsing table ?
User Avatar
0 votes
1 answer
6562
construct the dfa
Give minimal DFA that performs as a MOD-3 1's counter,i.e outputs a '1' each time the number of 1's in the input sequence is a multiple of 3.
Give minimal DFA that performs as a MOD-3 1's counter,i.e outputs a '1' each time the number of 1's in the input sequence is a multiple of 3.
User Avatar
0 votes
0 answers
6563
MOORE AND MEALY MACHINES
MOORE AND MEALY MACHINES PROBLEMS WILL COMES UNDER THE GATE CS 2017 SYLLABUS OR NOT?
MOORE AND MEALY MACHINES PROBLEMS WILL COMES UNDER THE GATE CS 2017 SYLLABUS OR NOT?
User Avatar
0 votes
0 answers
6564
Homomorphishm operation
If ∑={0,1} ∆={a,b} and h(0)=aa h(1)=bb And L={ab+ba}* then what is h(h-1(L)) ? I knw here h-1(L) is ∅(phi).
If ∑={0,1} ∆={a,b} and h(0)=aa h(1)=bbAnd L={ab+ba}*then what is h(h-1(L)) ?I knw here h-1(L) is ∅(phi).
User Avatar
0 votes
2 answers
6565
transition diagram for the given regular language
L={wxwr∣ w,x∈(a,b)*} Is this language regular language? Plz give transition diagram or table?
L={wxwr∣ w,x∈(a,b)*}Is this language regular language?Plz give transition diagram or table?
User Avatar
0 votes
0 answers
6566
Dfa
Construct the minimal dfa that accept all binary numbers which have congruent to 2mod4 Can't we eliminate state q3? as q1 and q3 hav same inputs and output transition. I think it is same as a language having strings ending with 10. Right na?
Construct the minimal dfa that accept all binary numbers which have congruent to 2mod4Can't we eliminate state q3?as q1 and q3 hav same inputs and output transition.I thi...
User Avatar
0 votes
1 answer
6567
PDA
I m student of MCA. (PDA) plz tell me difference b/w - a^n b^n | n >=0 or a^n b^n | n>=1 in my view :- L={1,11,111,........} is >=1 condition and L={€, 1,11,111,.........} is >=0 condition. this is rght or wrong. plz tell me difference with pda transition
I m student of MCA. (PDA) plz tell me difference b/w - a^n b^n | n >=0ora^n b^n | n>=1in my view :-L={1,11,111,........} is >=1 condition andL={€, 1,11,111,............
User Avatar
0 votes
1 answer
6571
Class of language
Identify the class of this language - L = { w1w2 | w1 != w2 & |w1| = |w2|} A) Regular B) CFL C) CSL D) Rec
Identify the class of this language -L = { w1w2 | w1 != w2 & |w1| = |w2|}A) RegularB) CFLC) CSLD) Rec
User Avatar
0 votes
1 answer
6572
DECIDABILITY
I an not getting the meaning of turing recognizable language..can someone please help..
I an not getting the meaning of turing recognizable language..can someone please help..
User Avatar
0 votes
2 answers
6574
REL
How to tell whether a language is recursively enumerable or not? Also answer the question with proper algorithm :-)
How to tell whether a language is recursively enumerable or not?Also answer the question with proper algorithm :-)
User Avatar
0 votes
0 answers
6575
construct NFA
Construct a transition table and diagram for the NFA M=({q1,q2,q3},∂,q1,{q3}) where ∂ is given by ∂(q1,0)={q2,q3}, ∂(q1,1)={q1}, ∂(q2,0)={q1,q2}, ∂(q2,1)=∅, ∂(q3,0)={q2}, ∂(q3,1)={q1,q2},
Construct a transition table and diagram for the NFAM=({q1,q2,q3},∂,q1,{q3}) where ∂ is given by∂(q1,0)={q2,q3}, ∂(q1,1)={q1},∂(q2,0)={q1,q2}, ∂(q2,1)=∅...
User Avatar
0 votes
0 answers
6577
why do we add an initial state while transforming PDA acceptance by final state into PDA acceptance by empty string ?
I have gone through this link already but still couldn't catch up the logic , so please clarify what is it trying to convey ? http://cs.stackexchange.com/questions/44195/...
User Avatar
0 votes
1 answer
6578
minimum no of states and final states
I solved both of these qs in a traditional way,by drawing nfa and then convert them to dfa..by tthis process ans shoulbe 4 and 2..but both of them are wrong..pls check..
I solved both of these qs in a traditional way,by drawing nfa and then convert them to dfa..by tthis process ans shoulbe 4 and 2..but both of them are wrong..pls check..
User Avatar
Page: