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{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} &1&1&3& 2 &2&3& 1&2&3
\\\hline\textbf{2 Marks Count} &2&3&3& 3 &3&4& 2&3&4
\\\hline\textbf{Total Marks} &5&7&9& 8 &8&11&\bf{5}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Filter

Recent questions in Theory of Computation

#4321
1.7k
views
0 answers
4 votes
regular expression from DFA
..Design regular expression for no 2 a's should come together , what i did i draw a dfa for 2 a's come together and then took complement ... getting correct regular expression from this , correct regular expression is given below in image
User Avatar
#4322
1.7k
views
3 answers
4 votes
CFL decidability
Problem :- intersection of 2 CFL's is CFL. Is this decidable ?
User Avatar
#4323
157
views
0 answers
1 votes
theory of computation
which is strongest correct about a finite language over some fimite alphabet sigma (E) ?A) could be undecidableB)it is TM recognisableC) it is regular langD)it ... then its also CSL, so that seems more correct right?shouldnt it be option D
User Avatar
#4324
342
views
0 answers
1 votes
theory of computation
regular grammar to CFG conversion is possible algorithmically ,is the vice versa possible?
User Avatar
#4325
293
views
1 answers
1 votes
dfa union
if i union two minimal dfa then is it sure i will get a minimal dfa or not
User Avatar
#4326
598
views
0 answers
0 votes
Testbook Series TOC 2018 GATE
In the above, doesn't it also accepts empty string, and {a} or {b}? I think the answer there is wrong. Correct me if I am wrong.How is that they took ... second one? z should be same, isn't it?Is PDA possible here?Isn't empty allowed?
User Avatar
#4327
1.4k
views
1 answers
0 votes
state elimination method
do we have to consider dead state in state elimination method
User Avatar
#4328
389
views
1 answers
1 votes
design a dfa for 2 a's come together over {a,b} ,
here we have to consider aa as substring ???
User Avatar
#4329
876
views
1 answers
0 votes
Pumping lemma Peter Linz examples
Prove language is regular or not using pumping lemma -1. L={a^nb^l :n!=l}2. L={(ab)^na^k : n>k ,k>=0}Plzz explain using pumping lemma.....
User Avatar
#4330
457
views
2 answers
2 votes
join dfa
iam not getting when to use cross product or union of dfa to join two dfa can someone tell me
User Avatar
#4331
318
views
0 answers
2 votes
regular expression
write regular expression for atmost 2 a's over ∑ = {a , b } , i know its easy but plz reply , then i can tell what i have problem in this
User Avatar
#4332
513
views
2 answers
1 votes
Toc CFL DCfL
CaptionIs this CFL or DCFL or not CFL
User Avatar
#4333
375
views
1 answers
2 votes
theory of computation
regular expresiion for length of string atmost 2 , over {a,b}answer : ε+ a + b + ab+ ba +bb + aa = (a+b+ ε) (a+b+ ε) how these two equations are same ?
User Avatar
#4334
599
views
1 answers
1 votes
context- free grammers
L = {a^nb^m : n >= m+3}below context grammer is correct??S ==> aA | AaA ==> aAb | bAa | abA | baA | aa
User Avatar
#4335
745
views
2 answers
1 votes
Regular grammar form
Regular grammar can be of form :-A->tV or A->Vt or A->t where t is terminal and V is variable.Here is t string of terminals or a single terminal? I am seeing different definitions of terminal everywhere.
User Avatar
#4336
555
views
1 answers
2 votes
union of dfa
can anyone tell me when we have to perform DFA UNION , CONCATENATION OR CROSS PRODUCT ???
User Avatar
#4337
437
views
2 answers
1 votes
theory of computation
which languages amongregular langCFLCSLRECREL have ambiguos grammar and which has unambiguos grammar and which can have both
User Avatar
#4338
615
views
2 answers
1 votes
Theory of computation
if x=10 and y= 1010x is a proper prefix of yif x =11 and y = 101101is x a proper prefix of y?? or is it only a substringproper prefixes must contain from the zeroth element and not just any part in between?
User Avatar
#4339
11.1k
views
3 answers
3 votes
Following language: L = {a^n b^n c^n d^n , n ≥ 1} ,How it is CSL and not CFL?
My understanding :We can create PDA as followsfor every 'a' push operation and on 'b' pop operation and again on 'c' push operation and on seeing 'd' pop operation. ... , if i am wrong.I am sorry, if it is not important.Thanks lot :)
User Avatar
#4340
1.1k
views
2 answers
2 votes
are following langauges CFL
How to check whether following language are context free1)L= {a^nb^m ; n<=m<=3n}2)L={w:2na(w) <=nb(w)<=3na(w) making NPDA or DPDA is not easy/convenient perhaps
User Avatar
Page: