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
6181
Equivalence and Emptiness problems in RE
Please classify following as NOT RE and RE but Not REC 1. Given L1 and L2 as RE languages,is L1=L2 ? 2. L(M) accepts some String ? 3.L(M) is empty? How can i prove these questions?
Please classify following as NOT RE and RE but Not REC1. Given L1 and L2 as RE languages,is L1=L2 ?2. L(M) accepts some String ?3.L(M) is empty?How can i prove these ques...
User Avatar
0 votes
0 answers
6182
Which of the following is CSL?
User Avatar
0 votes
0 answers
6183
Random
How to solve questions where we need to find the generated expression by the given expression . What is the techniques to solve such question ?
How to solve questions where we need to find the generated expression by the given expression . What is the techniques to solve such question ?
User Avatar
0 votes
1 answer
6185
Compound automata
Construct the dfa that accepts all the strings of a's and b's where no of a's is even OR no of b's is odd.
Construct the dfa that accepts all the strings of a's and b's where no of a's is even OR no of b's is odd.
User Avatar
0 votes
1 answer
6186
toc test
User Avatar
0 votes
1 answer
6188
TOC epsilon closure doubt
Please explain?
Please explain?
User Avatar
0 votes
1 answer
6189
Pumping lemma for regular grammer
True/False Pumping lemma is generally used to prove whether given grammar is not regular.
True/FalsePumping lemma is generally used to prove whether given grammar is not regular.
User Avatar
0 votes
0 answers
6190
TOC - Pls verify its solution
Please go through its solution. I am unable to understand how L1 and L2 are decidable.
Please go through its solution. I am unable to understand how L1 and L2 are decidable.
User Avatar
0 votes
0 answers
6191
METest
Codes: A B C D (a) 3 2 1 4 (b) 3 4 1 2 (c) 3 4 2 1 (d) 4 3 2 1 a b c d Whats the difference between CFL and DCFL? Is (b) correct option?
Codes: ABCD(a)3214(b)3412(c)3421(d)4321abcdWhats the difference between CFL and DCFL?Is (b) correct option?
User Avatar
0 votes
2 answers
6192
Gateforum TOC
PS:Ans is (C), Explain why statement-4 is TRUE?
PS:Ans is (C), Explain why statement-4 is TRUE?
User Avatar
0 votes
1 answer
6193
made easy mock
Let L1 = {an bm cn⎪m, n ≥ 0} and L2 = {an cn⎪n ≥ 0}. Both L1 and L2 are context free languages. If L = (L1 – L2) then L is ________ Finite language Regular language DCFL Not DCFL can anyone give the elaboration..??
Let L1 = {an bm cn⎪m, n ≥ 0} and L2 = {an cn⎪n ≥ 0}. Both L1 and L2 are context free languages. If L = (L1 – L2) then L is ________Finite languageRegular langua...
User Avatar
0 votes
0 answers
6194
made easy test 3
here i have doubt E4 is equal.......here its in E4 (left side) don't create 101 string ?? plz check
here i have doubt E4 is equal.......here its in E4 (left side) don't create 101 string ?? plz check
User Avatar
0 votes
1 answer
6195
Decidable/Undecidable
Let A = {<M>|M is a TM and L(M) is regular}. Then A is _________ a) Decidable language and regular language b) Undecidable but partially decidable c) Totally not decidable d) Decidable language but not regular language
Let A = {<M>|M is a TM and L(M) is regular}. Then A is _________a) Decidable language and regular languageb) Undecidable but partially decidablec) Totally not decidabled)...
User Avatar
0 votes
2 answers
6197
If L=(a+b)* and R=a*b*a* then L intersection R=?
We know, here R subset L so by formula R intersection L= R, but for any string R=L( both language are same) R intersection L can be R or L? Correct me!
We know, here R subset L so by formula R intersection L= R, but for any string R=L( both language are same) R intersection L can be R or L?Correct me!
User Avatar
0 votes
1 answer
6200
DCFl Decidability
Under what operations DCFL is Not decidable?I
Under what operations DCFL is Not decidable?I
User Avatar
Page: