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
Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.
2
Review the way that we define sets to be the same size in Definition $4.12$ (page $203$). Show that “is the same size” is an equivalence relation.
3
Let $T = \{(i, j, k)\mid i, j, k \in N \}$. Show that $T$ is countable.
4
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.
5
Let $X$ be the set $\{1, 2, 3, 4, 5\}$ and $Y$ be the set $\{6, 7, 8, 9, 10\}$. We describe the functions $f : X\rightarrow Y$ and $g : X\rightarrow Y$ in the following tables. Answer each part and give a reason for each negative answer. $n$ $f(n)$ 1 6 2 7 3 6 4 7 5 ... 9 3 8 4 7 5 6 Is $f$ one-to-one? Is $f$ onto? Is $f$ a correspondence? Is $g$ one-to-one? Is $g$ onto? Is $g$ a correspondence?
6
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.
7
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
8
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
9
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
10
11
Let $A$ be the language containing only the single string $s$, where $s = \left\{\begin{matrix} \text{0 if life never will be found on Mars} \\ \:\: \text{1 if life will be found on Mars someday} \end{matrix}\right.$ Is $A$ decidable? Why or why not? For the purposes of this problem, assume that the question of whether life will be found on Mars has an unambiguous $YES$ or $NO$ answer.
12
Let $c_{1}x^{n} + c_{2}x^{n-1} + \dots + c_{n}x + c_{n+1}$ be a polynomial with a root at $x = x_{0}.$ Let $c_{max}$ be the largest absolute value of a $c_{i}.$ Show that $\mid x_{0} \mid < (n+1)\frac{c_{max}}{\mid c_{1} \mid}.$
13
Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.
14
Show that every infinite Turing-recognizable language has an infinite decidable subset.
15
Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
16
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable language consisting of $TM$ descriptions. Show that there is a decidable language $C$ consisting of $TM$ descriptions such that every machine described in $B$ has an equivalent machine in $C$ and vice versa.
17
Show that the collection of Turing-recognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.
A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,S\}$ At each point, the machine can move its head ... the same position. Show that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?