Formal Language & Automata Theory

Which of the following statements is/are False?

A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
B. Turing recognizable languages are closed under union and complementation.
C. Turing decidable languages are closed under intersection and complementation.
D. Turing recognizable languages are closed under union and intersection.

(i) A and D only
(ii) A and C only
(iii) B only
(iv) C only

Enumerator is a Turing machine with

(i) an output printer
(ii) 5 input tapes
(iii) a stack
(iv) None of the above

Recursively Enumerable languages are also called

(i) Turing Recognizable
(ii) Turing Decidable
(iii) Regular
(iv) Context-Free

A language $L$ may not be accepted by a turing machine if

(i) it is recursively enumerable
(ii) it is recursive
(iii) $L$ can be enumerated by some turing machine
(iv) None of the above

Design a turing machine to compute the sum of two positive integers $m$ and $n$.

Define recursively enumerable languages. Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2 - L_1$ is necessarily recursively enumerable.

Design a Turing machine (TM) to compute $n \bmod 2$.

Explain the multi-tape version of turing machine and its significance.

Explain the basic model of a Turing Machine with its formal 7-tuple definition.

Design a turing machine that accepts all palindromes over $\Sigma = \{a, b\}$.

Design a Turing Machine that accepts the language $L = \{a^{n}b^{n} \mid n \ge 0\}$. Show the transition diagram/table and trace for input aabb.

State and explain the Church-Turing Thesis.

Design a Turing machine to perform 2's compliment operation on binary string.

Prove that if $L$ is the language generated by an unrestricted grammar $G = (N, T, P, S)$, then $L$ is recognized by a turing machine.

Show that the sum function

$$f(x, y) = x + y$$

is primitive recursive.

Define Turing machine. Design a Turing machine $M$ to recognize the language $\{ 1^n 2^n 3^n / n \ge 1 \}$.

Discuss the power and limitations of Turing Machines. Compare Turing Machines with Pushdown Automata.

Write a short note on: Multistack Turing machine

Write short notes on: Multistack Turing Machine