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}}}$$

Recent questions in Theory of Computation

0 votes
1 answer
4022
Let L1 = $0^+1^+$ and L2 = $(01)^+$, $L3 = \frac{L1}{ L2^*}$. The number of state needed for minimal DFA are _____.
0 votes
2 answers
4024
2 votes
2 answers
4025
Consider the following NFANumber of states in the equivalent minimal DFA is_________????(Note: Count one for the dead state (if required))
2 votes
1 answer
4026
consider the above NFA where input alphabet is{a.b}.The number of strings of length 5 accepted by this NFA is_______?????
0 votes
0 answers
4027
what is the meaning of regular set??
1 votes
0 answers
4028
while converting RE to FA how to decide which state is Final/Non final??
1 votes
2 answers
4029
2 votes
1 answer
4030
In Regular Expressions I saw (a+b)* = (a*b*)*Now my question is how (a*b*)* is able to generate 'ba' string (or any string in which 'a' comes after 'b')
0 votes
0 answers
4031
how to convert FA to Left linear regular grammar??
1 votes
2 answers
4032
What do we mean by Proper Substring? Please give some examples also in your explanation?
2 votes
2 answers
4033
input {a,b} Write R.E where every b is followed by at least 2 K a's? (K is +ve integer)
3 votes
2 answers
4034
input {0,1} Set of all strings that begin and end with either 0 or 1. What does this statement/line means and what would be the R.E for this?
1 votes
1 answer
4035
A minimum state deterministic finite automaton accepting the language L={w∣w∈{0,1}} where fifth symbol from the right is 0 has how many states?
2 votes
0 answers
4036
3 votes
1 answer
4037
Please explain the UNION and the INTERSECTION of two DFAs with suitable examples. I looked over the internet and I'm not satisfied with any of the explanations I came acr...
1 votes
1 answer
4038
IF a language L(M) over a Σ={a,b} accepts strings ending with b. Language L(N) over a Σ={a,b} accepts strings ending with a.Then what is minimal DFA for L(M) Ո L(N) ?
1 votes
1 answer
4039
What does it mean for grammar or a language if it has a shift-reduce conflict or reduce-reduce conflict?Is the language/grammar ambiguous? (always/maybe)? I want to know ...
2 votes
2 answers
4040
draw dfa w | w is any string not in (ab+)* ?