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

Hot questions in Theory of Computation

0 votes
1 answer
151
selfdoubt testseries toc
isn’t this language regular? it’s nfa according to me
isn’t this language regular?it’s nfa according to me
User Avatar
0 votes
1 answer
153
#Applied Course
Please explain this.
Please explain this.
User Avatar
38 votes
4 answers
154
GATE CSE 2004 | Question: 86
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$ odd and even even and odd divisible by $2$ and $3$
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$odd and evene...
User Avatar
1 votes
0 answers
157
GATE-2008
If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a, b} will be accepted by the new DFA? How to convert this FA to Reg-ex By state Elimination method
If the final states and non-final states in the DFAbelow are interchanged, then which of the followinglanguages over the alphabet {a, b} will be acceptedby the new DFA?Ho...
User Avatar
0 votes
2 answers
160
#self doubt
MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid
MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid
User Avatar
0 votes
0 answers
162
Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
User Avatar
1 votes
2 answers
164
Ace Test series
Which of the following Language has Prefix property? A) L=01* B) L=0*1* c) L= {0" 1" | n>, 1} D) L= {WW | We(0+1)*}
Which of the following Language has Prefix property?A) L=01*B) L=0*1*c) L= {0" 1" | n>, 1}D) L= {WW | We(0+1)*}
User Avatar
0 votes
1 answer
165
Micheal Sipser 3rd Edition, Problem 2.36
Is the following language context free? $L=\left \{ a^ib^j\:|\: i\neq j\:and\:2i\neq j \right \}$
Is the following language context free?$L=\left \{ a^ib^j\:|\: i\neq j\:and\:2i\neq j \right \}$
User Avatar
1 votes
2 answers
168
DFA to Regular Expression
Help to Convert DFA in to Regular Expression
Help to Convert DFA in to Regular Expression
User Avatar
41 votes
5 answers
169
GATE CSE 1995 | Question: 2.23
A finite state machine with the following state table has a single input $x$ and a single out $z$ ... $C$ is: $01$ $10$ $101$ $110$
A finite state machine with the following state table has a single input $x$ and a single out $z$.$$\begin{array}{|c|ll|}\hline\textbf{present state} & \qquad \textbf{nex...
User Avatar
0 votes
1 answer
170
Countable Sets Self Doubt
Is countable sets part of GATE CS 2024 syllabus?
Is countable sets part of GATE CS 2024 syllabus?
User Avatar
Page: