search
Log In

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.

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

0 votes
0 answers
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?
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 32 views
0 votes
0 answers
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.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 20 views
0 votes
0 answers
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}.$
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 20 views
0 votes
0 answers
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.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
0 votes
0 answers
19
A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. Each write operation (we'll call it a ... a special accept state at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 60 views
0 votes
0 answers
20
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?
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 50 views
...