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

Most answered questions in Theory of Computation

2 votes
0 answers
6182
What does it mean .TOC?
"A regular expression denoting a language (set of strings) means it should generate all string in L and not generate any string not in L" L is set of all strings not containing 100 as substring?
"A regular expression denoting a language (set of strings) means it should generate all string in L and not generate any string not in L"L is set of all strings not conta...
User Avatar
2 votes
0 answers
6183
Turing machine
If a Turing machine cannot accept € then how are regular languages subset of recursive enumerable languages?
If a Turing machine cannot accept € then how are regular languages subset of recursive enumerable languages?
User Avatar
0 votes
0 answers
6184
Turing machine
Can a Turing machine accept €? If no then how are regular languages subset of recursive enumerable languages?
Can a Turing machine accept €?If no then how are regular languages subset of recursive enumerable languages?
User Avatar
5 votes
0 answers
6185
Inherently Ambiguity
How to know whether L(G) is inherently ambiguous or not for a particular grammar 'G' ? Is there any algorithm for it ?
How to know whether L(G) is inherently ambiguous or not for a particular grammar 'G' ? Is there any algorithm for it ?
User Avatar
2 votes
0 answers
6186
Turing Machine
Which of the following Strings are not generated by given TM. 1) aabbaa 2) Epsilon 3) aabb
Which of the following Strings are not generated by given TM.1) aabbaa2) Epsilon3) aabb
User Avatar
1 votes
0 answers
6188
micheal sipser book
L3= {wxw^R ; w belongs {a,b}+ , x does not belong {a,b}} is ?? is x does not belong {a,b} then x will be ????
L3= {wxw^R ; w belongs {a,b}+ , x does not belong {a,b}} is ??is x does not belong {a,b} then x will be ????
User Avatar
0 votes
0 answers
6189
If a language(L1) is Recursive (REC) and L2 is Recursive (REC) , then what will be L1-L2 ?
If a language(L1) is Recursive (REC) and L2 is Recursive (REC) , then what will be L1-L2 ?
If a language(L1) is Recursive (REC) and L2 is Recursive (REC) , then what will be L1-L2 ?
User Avatar
1 votes
0 answers
6190
madeeasy work book
S-->aSb|SS|epsilon L={w|w belongs {a,b}* and a(v)>=b(v), where v is any prefix of w} (propery balanced parenthesis) plz someone tell me what does it mean am not getting???
S >aSb|SS|epsilonL={w|w belongs {a,b}* and a(v)>=b(v), where v is any prefix of w} (propery balanced parenthesis) plz someone tell me what does it mean am not getting???
User Avatar
2 votes
0 answers
6191
madeeasy work book
L={a^n b^n a^n |n=1,2,3.........} is an example of a language that is a)context free b)not context free c)not context free but whose complement is CF d)context free but whose complement is not CF
L={a^n b^n a^n |n=1,2,3.........} is an example of a language that is a)context freeb)not context freec)not context free but whose complement is CFd)context free but whos...
User Avatar
1 votes
0 answers
6193
Number of states in DFA
L = {s ∈ (0 + 1)* d(s)mod5 = 2 or d(s)mod7 != 4} where d(s) is the decimal equivalent of the binary string s. How many states does the above DFA have? How many final states? Please explain your answer.
L = {s ∈ (0 + 1)* d(s)mod5 = 2 or d(s)mod7 != 4} where d(s) is the decimal equivalent of the binary string s.How many states does the above DFA have? How many final sta...
User Avatar
0 votes
0 answers
6195
Compiler Design Syllabus Query
Do we need to study Assembler in Compiler Design. It's just I saw questions on Assembler in GO book, but all those questions were from 90's. So, do we need to study Assembler in depth for 2018? Thank you!
Do we need to study Assembler in Compiler Design. It's just I saw questions on Assembler in GO book, but all those questions were from 90's. So, do we need to study Asse...
User Avatar
1 votes
0 answers
6196
madeeasy
L={a^n b^n c^i | i<=n} L={a^n b^n c^i | i != n} why they are not cfl?
L={a^n b^n c^i | i<=n}L={a^n b^n c^i | i != n}why they are not cfl?
User Avatar
1 votes
0 answers
6197
TOC:- Moore Melay Machine
The output of moore machine will always have start state output as prefix? True/False?
The output of moore machine will always have start state output as prefix? True/False?
User Avatar
1 votes
0 answers
6198
Not from book
1. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2* U L1* a) € b) a* c) All of the mentioned d) None of the mentioned View Answer
1. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2* U L1*a) €b) a*c) All of the mentionedd) None of the mentionedView Answer
User Avatar
3 votes
0 answers
6199
Undecidability
L = {<M> | M is a TM and L(M) is infinite }..How to prove it as not RE..Here L(Tyes) = Sigma* is not subset of L(Tno) = Phi..So Rice Theorem's 2nd part is not applicable.. Can anyone please explain it ?
L = {<M | M is a TM and L(M) is infinite }..How to prove it as not RE..Here L(Tyes) = Sigma* is not subset of L(Tno) = Phi..So Rice Theorem's 2nd part is not applicable.....
User Avatar
2 votes
0 answers
6200
If a language(L) is Context-free, or CSL or RL , then it will always be Recursive ?
If a language(L) is Context-free, or CSL or RL , then it will always be Recursive ?
If a language(L) is Context-free, or CSL or RL , then it will always be Recursive ?
User Avatar
Page: