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}}}$$

Most answered questions in Theory of Computation

1
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\}$
2
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .
3
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
4
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... in $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$
5
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only
6
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: $\begin{array}{|c|c|c|c|}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$ ... $\widehat{\delta}(q_2, aba)$ is $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
7
Identify the language generated by the following grammar, where $S$ is the start variable. $S \rightarrow XY$ $X \rightarrow aX \mid a$ $Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $\{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$
8
The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .
9
Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$
10
The regular expression $0^*(10^*)^*$ denotes the same set as $(1^*0)^*1^*$ $0+(0+10)^*$ $(0+1)^*10(0+1)^*$ None of the above
11
Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$
12
In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If $L$ and $D$ denote the sets of letters and digits respectively, which of the following expressions defines an identifier? $(L + D)^+$ $(L.D)^*$ $L(L + D)^*$ $L(L.D)^*$
13
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$
14
Consider the context-free grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are non-terminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ $G_{2}:S\rightarrow bSa \mid T, T \rightarrow cT \mid \epsilon$ The language $L\left ( G_{1} \right )\cap L(G_{2})$ is Finite Not finite but regular Context-Free but not regular Recursive but not context-free
15
What is the highest type number that can be assigned to the following grammar? $S\to Aa,A\to Ba,B \to abc$ Type 0 Type 1 Type 2 Type 3
16
Let $M$ range over Turing machine descriptions, Consider the set $\text{REG = {M | L(M) is a regular set }}$ and let the complement of $REG$ be $Co-REG.$ Which of the following is true? REG is recursively enumerable but Co-REG is not REG is not recursively enumerable but Co-REG is Both are recursively enumerable. None of the above
17
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where $K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and $Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsilon), (s, a)), (( s, a, a), (f, \epsilon)), ((f, a, a), (f, \epsilon)), ((f, b, a), (f, \epsilon))\}$. Which one of the following strings is not a member of $L(M)$? $aaa$ $aabab$ $baaba$ $bab$
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$