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
5201
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
5202
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
5203
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
5206
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
5207
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
5208
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
5209
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
5210
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
5211
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
5212
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
5213
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
2 votes
1 answer
5214
Test by Bikram | Theory of Computation | Test 1 | Question: 16
The Minimal Finite Automata accepting the set of all strings over $(0+1)^*$ that do NOT have the sub-string $0001$ has: $5$ states $6$ states $7$ states $9$ states
The Minimal Finite Automata accepting the set of all strings over $(0+1)^*$ that do NOT have the sub-string $0001$ has:$5$ states$6$ states$7$ states$9$ states
User Avatar
2 votes
2 answers
5215
Test by Bikram | Theory of Computation | Test 1 | Question: 17
The language $L =\{a^n \ b^n \mid n \geq 1\} \cup \{a^m \ b^{2m} \mid m \geq 1\}$ is: DCFL CFL but not DCFL Non-CFL Regular Language
The language $L =\{a^n \ b^n \mid n \geq 1\} \cup \{a^m \ b^{2m} \mid m \geq 1\}$ is:DCFLCFL but not DCFLNon-CFLRegular Language
User Avatar
1 votes
1 answer
5216
Test by Bikram | Theory of Computation | Test 1 | Question: 18
The regular set $A =(01+1)^*$ and the regular set $B =((01)^*1^*)^*$ Which of the following statements is TRUE? $A$ is a subset of $B$ $B$ is a subset of $A$ $A$ and $B$ are incomparable $A=B$
The regular set $A =(01+1)^*$ and the regular set $B =((01)^*1^*)^*$Which of the following statements is TRUE?$A$ is a subset of $B$$B$ is a subset of $A$$A$ and $B$ are ...
User Avatar
2 votes
2 answers
5217
Test by Bikram | Theory of Computation | Test 1 | Question: 11
Identify the Regular Expression among the following which denotes ALL strings of $a$'s and $b$'s, where each string contains at least $2$ $b$'s: $(a+b)^*ba^*b$ $(a+b)^*ba^*ba$ $(a+b)^*ba^*b(a+b)^*$ $(a+b)^*ab^*ab$
Identify the Regular Expression among the following which denotes ALL strings of $a$'s and $b$'s, where each string contains at least $2$ $b$'s:$(a+b)^*ba^*b$$(a+b)^*ba^*...
User Avatar
6 votes
1 answer
5219
Test by Bikram | Theory of Computation | Test 1 | Question: 13
An NFA has $10$ states out of which $3$ are final states. The maximum number of final states in converted DFA is: $895$ $894$ $896$ $897$
An NFA has $10$ states out of which $3$ are final states. The maximum number of final states in converted DFA is:$895$$894$$896$$897$
User Avatar
Page: