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

Recent activity in Theory of Computation

0 votes
1 answer
2
State diagram
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}. 1- {w| w starts with 0 and has odd length, or starts with 1 and has even length}
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.1- {w| w starts with 0 and has odd length, or starts with 1 and has e...
User Avatar
0 votes
0 answers
6
CFL and regular language
Consider a regular language R and a context free language C. Let the PDA that recognizes C be called P=(QP,∑,Γ,δP,q0P,FP), and the DFA that reconginzes R be (QR,∑,δR,q0R,FR).
Consider a regular language R and a context free language C. Let the PDA that recognizes C be called P=(QP,∑,Γ,δP,q0P,FP), and the DFA that reconginzes R be (QR...
User Avatar
2 votes
1 answer
7
self doubt
The min of a language L is defined as min(L) = { w $\epsilon$ L : there is no u $\epsilon$ L, v $\epsilon$ $\sum$*, such that w = uv }. Show that the family of regular languages is closed under the min operation.
The min of a language L is defined asmin(L) = { w $\epsilon$ L : there is no u $\epsilon$ L, v $\epsilon$ $\sum$*, such that w = uv }. Show that the family of regular lan...
User Avatar
0 votes
1 answer
8
Regular Expression
Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.
Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.
User Avatar
0 votes
1 answer
9
Regular Expression
Set of binary strings starting with 11 and ending with 00. E.g., 1100,1110100 ,1100100
Set of binary strings starting with 11 and ending with 00. E.g., 1100,1110100 ,1100100
User Avatar
0 votes
2 answers
11
Regular language
Can anyone explain how we can write this regular language for the following diagram ?(in depth)
Can anyone explain how we can write this regular language for the following diagram ?(in depth)
User Avatar
0 votes
1 answer
12
#unacademyDPP
User Avatar
0 votes
0 answers
17
Theory of Computation | design of Turing Machine
Is this the correct Turing machine for the language $0^n 1^n0^n$? assuming $ at the end and begining of the input tape
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
User Avatar
To see more, click for all the questions in this category.