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

83 votes
4 answers
6463
GATE CSE 2015 Set 1 | Question: 51
Consider the NPDA ... follows: Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton? $10110$ $10010$ $01010$ $01001$
Consider the NPDA $$ \left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \p...
User Avatar
36 votes
6 answers
6464
GATE CSE 2015 Set 2 | Question: 53
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
User Avatar
14 votes
5 answers
6470
No. of states in the minimal finite automata which accepts the binary strings whose equivalent is divisible by 32 is ________?
No. of states in the minimal finite automata which accepts the binary strings whose equivalent is divisible by 32 is ________?A. 5B. 6C 31D 32
User Avatar
1 votes
1 answer
6471
Recognising type of language
HI, I would like someone to give clarification on how to identify a string is which grammar. I am not able to understand the concept well. So if someone explains ii, it will be highly appreciated. Please give examples. for eg: { a^n } is CFG or not. Thank you.
HI,I would like someone to give clarification on how to identify a string is which grammar. I am not able to understand the concept well. So if someone explains ii, it wi...
User Avatar
4 votes
2 answers
6474
toc
Let $L_1 = \{a^nb^mc^n \mid m,n \geq 0 \}$ and $L_2 = \{a^nc^n \mid n \geq 0 \}$. Both $L_1$ and $L_2$ are context free languages. if $L = ( L_1 - L_2 )$ then $L$ is ____. a. Finite Language b. Regular language c. DCFL d. Not DCFL
Let $L_1 = \{a^nb^mc^n \mid m,n \geq 0 \}$ and $L_2 = \{a^nc^n \mid n \geq 0 \}$. Both $L_1$ and $L_2$ are context free languages. if $L = ( L_1 - L_2 )$ then $L$ is ___...
User Avatar
4 votes
3 answers
6477
What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?
What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?A. 8B. 9C. 6D. None
User Avatar
7 votes
1 answer
6478
Finding the rank of variable for CFG
Consider the following CFG S->AB, A->BC|a , B->CC|b , C->AB|a , What will be the rank of the variable of B?
Consider the following CFGS->AB, A->BC|a , B->CC|b , C->AB|a ,What will be the rank of the variable of B?
User Avatar
4 votes
2 answers
6480
Whether given CFL is Regular is Decidable?
Which of the following are True? $S1$: Every NFA can be converted to equivalent PDA $S2$: Whether a given CFL is Regular is decidable. 1. $S1$ 2. $S2$ 3. Both 4. None
Which of the following are True?$S1$: Every NFA can be converted to equivalent PDA$S2$: Whether a given CFL is Regular is decidable.1. $S1$ ...
User Avatar
Page: