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

0 votes
1 answer
4591
let r1=(a+bb)* , r2=(a*+b* ), r3=(aa+b)* which 0f the following is true?
A)L(r1)⊆L(r2) and L(r3)⊆L(r2) b) L(r2)⊆L(r1) and L(r2)⊆L(r3) C) L(r1)=L(r3)⊆L(r2) D) L(r1)⋃L(r3)=L(r2) plz explain with explanation
A)L(r1)⊆L(r2) and L(r3)⊆L(r2)b) L(r2)⊆L(r1) and L(r2)⊆L(r3)C) L(r1)=L(r3)⊆L(r2)D) L(r1)⋃L(r3)=L(r2)plz explain with explanation
User Avatar
0 votes
1 answer
4593
Automata-Grammars
For the language L = { anbmcmdn : n , m>=1 } I came with following set of productions : S-->aSd | A A--> bAc | bc whereas the answer was given as below S--> aSd | aAd A--> bAc | bc how far is my answer correct?
For the language L = { anbmcmdn : n , m>=1 }I came with following set of productions :S >aSd | AA bAc | bcwhereas the answer was given as belowS aSd | aAdA bAc | bcho...
User Avatar
0 votes
3 answers
4594
Peter Linz Exercise 5.1
Is the following language context-free? L= { uvwvR : u,v,w∈ {a,b}+ |u| = |w| =2 } If yes, provide set of productions for the same.
Is the following language context-free?L= { uvwvR : u,v,w∈ {a,b}+ |u| = |w| =2 }If yes, provide set of productions for the same.
User Avatar
1 votes
2 answers
4596
Peter Linz Exercise 5.1
Give a context-free grammar for the language below : (n>=0, m>=0) L= { w ∊ {a,b}* : na(w)=2nb(w)+1}
Give a context-free grammar for the language below :(n>=0, m>=0)L= { w ∊ {a,b}* : na(w)=2nb(w)+1}
User Avatar
2 votes
1 answer
4597
Peter Linz Exercise 5.3
Find the context-free grammar for the following language(n>=0 and m>=0) ? L={an bm : n<=m+3}
Find the context-free grammar for the following language(n>=0 and m>=0) ?L={an bm : n<=m+3}
User Avatar
0 votes
2 answers
4599
eliminate unit production
S -> AA | B A-> BB | S B-> c | ab
S - AA | BA- BB | S B- c | ab
User Avatar
0 votes
1 answer
4600
toc doubt
is there any formula or shortcut or...we need to slove manually what if the large value given like power 10
is there any formula or shortcut or...we need to slove manually what if the large value given like power 10
User Avatar
1 votes
3 answers
4601
Peter Linz Exercise 4.3
Show that the language $\begin{align*} L = \left \{ a^nb^{n+k} \;\; : n\geq 0,k\geq 1 \right \} \cup \left \{ a^{n+k}b^{n} \;\; : n\geq 0,k\geq 3 \right \} \end{align*}$ is not Regular.
Show that the language$$\begin{align*} L = \left \{ a^nb^{n+k} \;\; : n\geq 0,k\geq 1 \right \} \cup \left \{ a^{n+k}b^{n} \;\; : n\geq 0,k\geq 3 \right \} \end{align*}$$...
User Avatar
0 votes
2 answers
4608
Peter Linz Exercise 3.3
Also, provide a regular expression for the language generated.
Also, provide a regular expression for the language generated.
User Avatar
1 votes
2 answers
4609
Peter Linz Exercise 3.2
Provide dfa for the below regular expression
Provide dfa for the below regular expression
User Avatar
1 votes
1 answer
4610
Peter Linz Exercise 3.2
Construct regular expression for the automata given below :
Construct regular expression for the automata given below :
User Avatar
Page: