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

0 votes
1 answer
5191
question bank
Consider the following statements: S1: Infinite union of regular languages can be context-free. S2: Language obtained after applying Kleen closure on a regular language will always be regular and infinite. Which of the above statement is true?
Consider the following statements:S1: Infinite union of regular languages can be context-free.S2: Language obtained after applying Kleen closure on a regular language wil...
User Avatar
1 votes
1 answer
5192
toc dfa
Construct minimal DFA which accepts set of all srings over {a,b} which starts and ends with the same symbol???
Construct minimal DFA which accepts set of all srings over {a,b} which starts and ends with the same symbol???
User Avatar
32 votes
8 answers
5194
GATE CSE 1989 | Question: 3-ii
Context-free languages and regular languages are both closed under the operation (s) of : Union Intersection Concatenation Complementation
Context-free languages and regular languages are both closed under the operation (s) of :UnionIntersectionConcatenationComplementation
User Avatar
5 votes
6 answers
5195
Regular Languages
If L1 contains finite number of strings and L2 is a CFL then $L1\cap L2$ is ____ (A) Regular (B) CSL (C) CFL (D) None of these
If L1 contains finite number of strings and L2 is a CFL then $L1\cap L2$ is ____(A) Regular(B) CSL(C) CFL(D) None of these
User Avatar
20 votes
2 answers
5197
GATE CSE 1990 | Question: 15a
Is the language generated by the grammar $G$ regular? If so, give a regular expression for it, else prove otherwise G: $S \rightarrow aB$ $B \rightarrow bC$ $C \rightarrow xB$ $C \rightarrow c$
Is the language generated by the grammar $G$ regular? If so, give a regular expression for it, else prove otherwiseG: $S \rightarrow aB$$B \rightarrow bC$$C \rightarro...
User Avatar
0 votes
1 answer
5198
Test by Bikram | Theory of Computation | Test 1 | Question: 29
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an: Decidable problem Undecidable problem Cannot ascertain None
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
User Avatar
6 votes
2 answers
5199
Test by Bikram | Theory of Computation | Test 1 | Question: 30
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is: Decidable Undecidable but semi-decidable Not even semi-decidable Indeterminable
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
User Avatar
4 votes
1 answer
5200
Test by Bikram | Theory of Computation | Test 1 | Question: 25
If all the strings of a language can be enumerated in $\text{lexicographic}$ order, then this is an example of a _______ language. Regular CFL but need not be regular CSL but need not be a CFL Recursive but need not be a CSL
If all the strings of a language can be enumerated in $\text{lexicographic}$ order, then this is an example of a _______ language.Regular CFL but need not be regular ...
User Avatar
0 votes
1 answer
5203
Test by Bikram | Theory of Computation | Test 1 | Question: 28
Recursive Enumerable Languages are NOT closed under : Union Intersection Complement Homomorphism
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
User Avatar
1 votes
2 answers
5204
Test by Bikram | Theory of Computation | Test 1 | Question: 23
PDA can be used for: infix to postfix conversion implementing recursive function calls evaluating arithmetic expressions all of the above
PDA can be used for:infix to postfix conversionimplementing recursive function callsevaluating arithmetic expressionsall of the above
User Avatar
0 votes
0 answers
5205
Test by Bikram | Theory of Computation | Test 1 | Question: 24
By reading any string, which of the following is possible for a Turing Machine? TM halts in Final State TM halts in Non Final State TM enters into Infinite Loop All of these
By reading any string, which of the following is possible for a Turing Machine?TM halts in Final StateTM halts in Non Final StateTM enters into Infinite LoopAll of these
User Avatar
3 votes
1 answer
5206
Test by Bikram | Theory of Computation | Test 1 | Question: 19
Consider the following CFG : $S \rightarrow AB$ $A \rightarrow BC \mid a$ $B \rightarrow CC \mid b$ $C \rightarrow a \mid AB$ The Rank of Variable $A$ is: $2$ $3$ $4$ not possible to define
Consider the following CFG :$S \rightarrow AB$$A \rightarrow BC \mid a$$B \rightarrow CC \mid b$$C \rightarrow a \mid AB$The Rank of Variable $A$ is:$2$$3$$4$not possible...
User Avatar
2 votes
1 answer
5207
Test by Bikram | Theory of Computation | Test 1 | Question: 20
Which of the following is not a Regular Expression? $[(a+b)^* – (aa+bb)]^*$ $[(0+1) – (0b + a1)^* (a+b)]^*$ $(01+11+10)^*$ $(1+2+0)^* (1+2)^*$
Which of the following is not a Regular Expression?$[(a+b)^* – (aa+bb)]^*$$[(0+1) – (0b + a1)^* (a+b)]^*$$(01+11+10)^*$$(1+2+0)^* (1+2)^*$
User Avatar
4 votes
2 answers
5208
Test by Bikram | Theory of Computation | Test 1 | Question: 21
Consider the following grammar: $G$ $E \rightarrow E+E \mid E-E \mid E^*E \mid (E)\mid \text{id}$ The number of derivation trees for the string $\text{id} +\text{id} ^* \text{id} – \text{id}$ is: $5$ $6$ $7$ $8$
Consider the following grammar: $G$ $E \rightarrow E+E \mid E-E \mid E^*E \mid (E)\mid \text{id}$The number of derivation trees for the string $\text{id} +\text{id} ^* \t...
User Avatar
3 votes
2 answers
5209
Test by Bikram | Theory of Computation | Test 1 | Question: 22
Total Recursive Functions are similar to: Recursive Languages Recursive Enumerable Languages Cannot relate the two None
Total Recursive Functions are similar to:Recursive LanguagesRecursive Enumerable LanguagesCannot relate the twoNone
User Avatar
0 votes
3 answers
5210
Test by Bikram | Theory of Computation | Test 1 | Question: 15
Which one is a correct statement in terms of accepting powers of DPDA and NPDA? DPDA and NPDA are equal DPDA and NPDA are not comparable DPDA < NPDA DPDA > NPDA
Which one is a correct statement in terms of accepting powers of DPDA and NPDA?DPDA and NPDA are equalDPDA and NPDA are not comparableDPDA < NPDADPDA NPDA
User Avatar
Page: