FORMAL LANGUAGE & AUTOMATA THEORY

Answer

Correct Option: (ii) Turing Machine

Explanation

A language $L$ is called Recursively Enumerable (RE) iff there exists a Turing Machine $M$ such that $L = L(M)$, i.e., $M$ halts and accepts exactly the strings in $L$. On strings not in $L$, $M$ may either reject or loop forever. This is the most general language class in the Chomsky hierarchy (Type-0).

Why other options are incorrect

• (i) DFA : Accepts Regular languages (Type-3), strictly smaller than RE.
• (iii) PDA : Accepts Context-Free Languages (Type-2), also properly contained in RE.
• (iv) Linear Bounded Automaton (LBA) : Accepts Context-Sensitive Languages (Type-1), also a proper subset of RE.

Hierarchy recall

$$\text{REG} \subset \text{CFL} \subset \text{CSL} \subset \text{RE} \subset \text{ALL}$$

• REG → DFA
• CFL → PDA
• CSL → LBA
• RE → Turing Machine
• Recursive → Decidable TM (always halts)

Final Answer

Hence, Recursively Enumerable Languages are exactly those accepted by Turing Machines. Correct answer is (ii) Turing Machine.

Answer

Correct Option: (iv) None of the mentioned

Explanation

An infinite language requires a machine with unbounded memory. In the Turing Machine model $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$ the tape is infinite, but the finite control itself is finite.

• Compiler: Translates a high-level program to target code before execution. It does not provide run-time handling of an infinite input tape; it assumes input is finite source text.
• Interpreter: Executes source line-by-line, still requires entire input to be presented finitely; it does not make an infinite tape finite.
• Loader and Linkers: Perform loading / relocation of object code into memory. They handle finite modules, not an infinite language / infinite tape.

The subsidiary that actually gives a finite description of an infinite computation is the finite control (finite automaton) + the Turing Machine’s transition function or, in language theory, the finite representation (regular expression / grammar / TM description) itself. None of the three listed system softwares fulfills this role.

The theoretical concept is:

• Infinite language $L \subseteq \Sigma^*$ is described finitely by a grammar / regular expression / TM encoding $\langle M \rangle$, not by compiler/interpreter/loader.

Hence none of (i)-(iii) is correct.

Final Answer

None of the mentioned. The finite solution is provided by the finite control / finite encoding $\langle M\rangle$ of the machine, not by compiler / interpreter / loader.

Answer

Correct Option: (i) an output printer

Explanation

An Enumerator $E$ is a variant of Turing Machine that enumerates a language.

Formal definition (Sipser):

Enumerator is a TM with a work tape and a write-only output tape (printer). The printer head moves only right and cannot read. Whenever $E$ wants to output a string, it writes it on the printer and the string is considered enumerated.

• Enumerator has no input; it starts from blank tape.
• Language enumerated is $L(E) = \{ w \mid E \text{ eventually prints } w \}$.
• Theorem: $L$ is Turing-recognizable iff some enumerator enumerates $L$.

Options:

• (ii) 5 tapes — multi-tape TM, not enumerator.
• (iii) stack — PDA, not enumerator.
• Hence (i) is correct.

Final Answer

Enumerator = TM with an output printer → Option (i).

Answer

Correct Option: (iii) Generator (also enumerated as Transducer/Enumerator in some texts — “Generator” is the term for printing strings)

Explanation

TM views:

Mode	Description
Acceptor / Recognizer	Decides $w\in L$ by accepting/rejecting (yes/no).
Transducer	Computes function $f(w)$ on output tape.
Generator / Enumerator	Prints (generates) strings of $L$ one after another on output tape (printer).
Decider	Acceptor that always halts.

A TM that prints strings of a language is called Generator (or Enumerator if it lists all). Many textbooks list (iii) Generator and (iv) Enumerator as synonyms; exam key typically Generator.

Final Answer

Generator (prints strings) → Option (iii). Enumerator is equivalent variant.

Answer

Correct Option: (ii) universal Turing machine

Explanation

Universal Turing Machine $U$: A TM that takes as input encoding of any TM $M$ and input $w$: $U(\langle M, w\rangle) = M(w)$.

• Can simulate any other TM (stored-program concept).
• Basis for von Neumann architecture, stored-program computers.
• Exists by Church-Turing thesis; constructed by Turing (1936).
• Leads to undecidability of halting problem.

Other options:

• Nested TM — not standard.
• Counter machine — weaker (but Turing-equivalent with 2 counters).

Final Answer

Universal TM → Option (ii).

Answer

Correct Option: (ii) An infinite tape

Explanation

Turing Machine model: $M = (Q,\Sigma,\Gamma,\delta,q_0,B,F)$ with

• Finite control (states $Q$),
• One infinite tape divided into cells, each holds symbol from $\Gamma$ ($\Sigma \subset \Gamma$), extends infinitely in one direction (or both in some definitions), with a read/write head.
• Initially tape contains input $w$ + blanks $B$ to the right (infinite blanks).

It does not have a stack (that's PDA) or queue as primary memory, nor finite tape (that would be LBA / finite automaton).

Final Answer

TM has an infinite tape → Option (ii).

Answer

Correct Option: (i) DPDA and NPDA

Explanation

Expressive power comparison:

Pair	Power Same?
DPDA vs NPDA	Different — NPDA = CFL, DPDA = DCFL ⊂ CFL. Example $\{a^n b^n\}\cup\{a^n b^{2n}\}$ is CFL but not DCFL.
DFA vs NFA	Same — both = Regular
Single-tape TM vs Multi-tape TM	Same — both = RE, polytime difference only
Deterministic single-tape TM vs Nondeterministic single-tape TM	Same — $DTM = NTM$ in power

Hence different expressive powers is DPDA vs NPDA.

Final Answer

DPDA and NPDA have different power → Option (i).

Answer

Correct Option: (ii) Random Access Stored Program

Explanation

RASP = Random Access Stored Program machine.

• Model by Elgot–Robinson, Hartmanis.
• Like RAM but program stored in memory like data (von Neumann).
• Has registers and memory with random access, program counter.
• Turing-equivalent, but more realistic cost model.

Other expansions are incorrect variations.

Final Answer

Random Access Stored Program → Option (ii).

Answer

Correct Option: (i) a proper superset of CFLs (and (ii)/(iv) also true depending on option set)

Explanation

Recursive languages = Decidable languages = $L$ decided by TM that always halts.

Hierarchy:
$$\text{Regular} \subset \text{DCFL} \subset \text{CFL} \subset \text{CSL} \subset \text{Recursive} \subset \text{RE}$$

• (i) Proper superset of CFLs → True. Every CFL is recursive (PDA can be simulated by halting TM), but not vice versa (e.g., $a^n b^n c^n$ is recursive not CFL).
• (ii) Always recognizable (RE) → True, recursive ⊂ RE, so yes.
• (iv) Recognizable by TM → True (RE definition).
• (iii) also called Type-0 → False, Type-0 = RE, not Recursive (Type-1 is CSL, not Recursive either; Recursive is not a Chomsky type but decidable).

If single choice, (i) proper superset of CFLs is the intended answer. If multiple, (i),(ii),(iv) are true.

Final Answer

Recursive languages are proper superset of CFLs → Option (i) (also RE).

Answer

Correct Option: (i) recursive (Turing decidable = recursive)

Explanation

Turing decidable ≡ Recursive language ≡ Decided by a TM that always halts (decider).

Definitions:

• Recursively Enumerable (RE): TM recognizes $L$ (accepts if $w\in L$, may loop if $w
  otin L$). Options (ii) “TM recognizes” and (iii) “TM accepts” describe RE, not decidable.
• Recursive: TM decides $L$ : for every $w$, TM halts and says accept/reject.

So $L$ is Turing decidable iff $L$ is recursive.

Decider vs Recognizer distinction is key: recognizer may not halt on rejection.

Final Answer

Decidable = recursive → Option (i).

Answer

Correct Option: (iii) Equivalent in power

Explanation

Multi-tape TM vs Single-tape TM:

• Power: Equivalent. Any $k$-tape TM can be simulated by single-tape TM with at most quadratic slowdown (or $O(t^2)$). Both accept exactly RE languages; deciders both accept Recursive languages.
• Efficiency: Multi-tape can be faster (e.g., palindrome $O(n)$ vs $O(n^2)$ on single tape), but not more powerful in computability.
• Construction: Single tape encodes $k$ tapes via tracks ($k$-track tape) + markers for heads.

Therefore they are equally powerful (Turing-equivalent).

Final Answer

Equivalent in power → Option (iii).