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

57 votes
1 answer
6701
GATE CSE 1999 | Question: 1.6
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true? $L_1 = L_2$ $L_1 \supset L_2$ $L_1 \subset L_2$ None
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?$L_1 = L...
User Avatar
3 votes
1 answer
6702
Find n(K) where K is the size of string that a DFA accepts.
Subject: Finite Automata Topic: DFA Q) Can anyone explain me how i can find the no of strings of length k words that is accepted by a given DFA. Do post the resources which can be helpful to understand this concept.
Subject: Finite AutomataTopic: DFAQ) Can anyone explain me how i can find the no of strings of length k words that is accepted by a given DFA.Do post the resources which ...
User Avatar
1 votes
1 answer
6709
If anybody have some note or link to the topic like NP related questions, Please provide. I have never been successful in answering these type of question. Any help will be really appreciated.
If anybody have some note or link to the topic like NP related questions, Please provide. I have never been successful in answering these type of question. Any help will ...
User Avatar
17 votes
2 answers
6710
L(M) = Σ*
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $ A. $L$ is RE but $L'$ is not RE B. Both $L$ and $L'$ are RE C. $L$ is not RE but $L'$ is RE D. Both $L$ and $L'$ are not RE
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $A. $L$ is RE but $L'$ is not REB. Both $L$ and $L'$ are REC. $L$ is not RE but $L'$ is RED. Both $L$ and $L'$ are not RE...
User Avatar
17 votes
4 answers
6711
L(M) is infinite
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$ $L$ is RE but $L'$ is not RE Both $L$ and $L'$ are RE $L$ is not RE but $L'$ is RE Both $L$ and $L'$ are not RE
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$$L$ is RE but $L'$ is not REBoth $L$ and $L'$ are RE$L$ is not RE but $L'$ is REBoth $L$ and $L'$ are not RE
User Avatar
5 votes
2 answers
6714
Identify the class of L
Consider $L_1 = \left\{a^nb^nc^md^m \mid m,n \ge 1\right\}$ $L_2 = \left\{a^nb^n \mid n \ge1\right\}$ $L_3 = \left\{(a+b)^*\right\}$ Intersection of $L_1$ and $L_2$ is (A) Regular (B) CFL but not regular (C) CSL but not CFL (D) None of these
Consider$L_1 = \left\{a^nb^nc^md^m \mid m,n \ge 1\right\}$$L_2 = \left\{a^nb^n \mid n \ge1\right\}$$L_3 = \left\{(a+b)^*\right\}$Intersection of $L_1$ and $L_2$ is(A) Reg...
User Avatar
71 votes
14 answers
6716
GATE CSE 2012 | Question: 12
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$
What is the complement of the language accepted by the NFA shown below?Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.$\phi$$\{\epsilon\}$$a^*$$\{a , \epsilon...
User Avatar
23 votes
4 answers
6717
GATE CSE 2012 | Question: 4
Assuming $P \neq NP$, which of the following is TRUE? $NP- \ complete = NP$ $NP-complete \cap P = \phi$ $NP-hard = NP$ $P = NP-complete$
Assuming $P \neq NP$, which of the following is TRUE?$NP- \ complete = NP$$NP-complete \cap P = \phi$$NP-hard = NP$$P = NP-complete$
User Avatar
Page: