Web Page

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\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&2&3&3&3&2&2.5&3 \\\hline\textbf{2 Marks Count}&3&3&5&3&3&3&3&3.3&5 \\\hline\textbf{Total Marks}&8&8&12&9&9&9&\bf{8}&\bf{9.2}&\bf{12}\\\hline \end{array}}}$$

# Recent questions in Theory of Computation

1
$(00+01+10)(0+1)^*$ represents Strings not starting with $11$ Strings of odd length Strings starting with $00$ Strings of even length
2
What is the complement of the language accepted by the NFA shown below? $\not{O}$ $\{\epsilon\}$ $a^*$ $\{a,\epsilon\}$ $1$ $2$ $3$ $4$
3
Let $L$ be a language and $L’$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $L’$ is RE. One of the $L$ and $L’$ is RE but not recursive;the other is not RE. Both $L$ and $L’$ are RE but not recursive. Both $L$ and $L’$ are recursive.
4
Let $L1$ be a recursive language, and let $L2$ be a recursively enumerable but not recursive language. Which one of the following is TRUE? $L1’$ is recursive and $L2’$is recursively enumerable. $L1’$ is recursive and $L2’$is not recursively enumerable. $L1’$ and $L2’$is recursively enumerable. $L1’$ is recursively enumerable and $L2’$is recursive.
5
According to the given language, which among the following expressions does it correspond to ? Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$. $(0+1+0+1+0+1+0+1)^4$ $(0+1)^4$ $(01)^4$ $(0+1+\varepsilon)^4$
6
Let $G$ be a grammar in CFG and let $W_1,W_2\in L(G)$ such that $\mid W_1\mid=\mid W_2\mid$ then which of the following statements is true? Any derivation of $W_1$ has exactly the same number of steps as any derivation of $W_2$. Different derivation have different length. Some derivation of $W_1$ may be shorter than the derivation of $W_2$ None of the options
7
A regular expression is $(a+b^{\ast}c)$ is equivalent to set of strings with either $a$ or one or more occurrence of $b$ followed by $c$. $(b^{\ast}c+a)$ set of strings with either $a$ or zero or more occurrence of $b$ followed by $c$. Both (B) and (C)
8
Which of the following are undecidable? $P1$: The language generated by some CFG contains any words of length less than some given number $n$. $P2$: Let $L1$ be CFL and $L2$ be regular, to determine whether $L1$ and $L2$ have common elements $P3$: Any given CFG is ambiguous or not. ... CFG $G$, to determine whether epsilon belongs to $L(G)$ $P2$ only $P1$ and $P2$ only $P2$ and $P3$ only $P3$ only
9
Recursive enumerable languages are not closed under _________. Set difference Complement Both (A) and (B) None of the options
10
What is the meaning of regular expression $\Sigma^*001\Sigma^*$? Any string containing ‘$1$’ as substring Any string containing ‘$01$’ as substring Any string containing ‘$011$’ as substring All string containing ‘$001$’ as substring
11
If any string of a language $L$ can be effectively enumerated by an enumerator in a lexicographic order then language $L$ is _______. Regular Context free but not necessarily regular Recursive but not necessarily context free Recursively enumerable but not necessarily recursive
12
The collection of Turing recognizable languages are closed under: Union Intersection Complement Concatenation Star Closure (i) Only Both (i),(iv) (i),(ii),(iv)and(v) All of the options
13
Which of the following regular expression is equal to $(r_1+r_2)^*$? $r_1^*r_2^*$ $(r_1r_2)^*$ $r_1^*r_2^*+r_1r_2$ $(r_1^*r_2^*)^*$
14
Which of the following statement is true? $S1$: The power of a multi-tape Turing machine is greater than the power of a single tape Turing machine. $S2$: Every non-deterministic Turing machine has an equivalent deterministic Turing machine. $S1$ $S2$ Both $S1$ and $S2$ None of the options
15
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
16
Which of the following is equivalent regular expressions? $((01)^*(10)^*)^*$ $(10+01)^*$ $(01)^*+(11)^*$ $(0^*+(11)^*+0^*)^*)$ (i) and (ii) (ii) and (iii) (iii) and (iv) (iv) and (i)
17
The string $1101$ does not belong to the set represented by $(00+(11)^*0)$ $1(0+1)^*101$ $(10)^*(01)^*(00+11)^*$ $110^*(0+1)$
Let $n$ is the length of string to test for membership, then the number of table entry in CYK algorithm is $n(n+1)$ $n^2+1$ $n^2-1$ $n(n+1)/2$