FORMAL LANGUAGE & AUTOMATA THEORY

A language is said to be recursively enumerable if it is accepted by a

(i) DFA
(ii) Turing Machine
(iii) PDA
(iv) Linear Bounded Automaton

If an infinite language is passed to Machine $M$, the subsidiary which gives a finite solution to the infinite input tape is:

(i) Compiler
(ii) Interpreter
(iii) Loader and Linkers
(iv) None of the mentioned

Enumerator in a Turing machine is a TM with:

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

A Turing Machine that prints strings of a language is called

(i) Acceptor
(ii) Transducer
(iii) Generator
(iv) Enumerator

A Turing Machine has:

(i) A finite tape
(ii) An infinite tape
(iii) A stack
(iv) A queue

A Turing machine that is able to simulate other Turing machines is called:

(i) nested Turing machine
(ii) universal Turing machine
(iii) counter machine
(iv) None of the above

From the options, the pair having different expressive powers is:

(i) DPDA and NPDA
(ii) DFA and NFA
(iii) single-tape TM and multi-tape TM
(iv) deterministic single-tape TM and nondeterministic single-tape TM

Recursive languages are:

(i) a proper superset of CFLs
(ii) always recognizable
(iii) also called type-0 languages
(iv) recognizable by Turing machines

RASP stands for:

(i) Random Access Storage Program
(ii) Random Access Stored Program
(iii) Randomly Accessed Stored Program
(iv) Random Access Storage Programming

Multi-tape TM is

(i) More powerful than single-tape TM
(ii) Less powerful
(iii) Equivalent in power
(iv) Not equivalent

A language $L$ is Turing decidable if:

(i) recursive
(ii) TM recognizes $L$
(iii) TM accepts $L$
(iv) None of the above

Design a Turing Machine to compute $n \bmod 2$.

Design a Turing Machine that increments a binary number by $1$.

Design a Turing machine that recognizes strings containing equal number of $0$’s and $1$’s.

Explain the various types of Turing Machines.

Design a Turing machine that accepts all palindromes over:

$$\Sigma = \{ a, b \}$$

Design a Turing Machine that enumerates all strings over {a, b} in lexicographic order. Explain the working of the machine.

Design a single-tape Turing Machine that multiplies two unary numbers, where the input is of the form $1^m 0 1^n$ and the output is $1^{m \times n}$. Clearly define the input alphabet, tape alphabet, and halting condition. Simulate the working of the Turing Machine on the input string $1101$.

Write short notes on: Multi-tape Turing Machine.

Write a short note on Multi-stack Turing Machine.