FORMAL LANGUAGE & AUTOMATA THEORY

Answer

Correct Option: (iii) B only

Explanation

Evaluate each statement:

A. For every nondeterministic TM, an equivalent deterministic TM exists.

True. Turing Machines are deterministic simulatable: a DTM can simulate an NTM via BFS over computation tree with at most exponential slowdown. NTM does not increase power, unlike for PDA. $NTM = DTM$ in language power.

B. Turing-recognizable (RE) languages are closed under union and complementation.

False.

• RE is closed under union and intersection: if $M_1$ recognizes $L_1$ and $M_2$ recognizes $L_2$, a NTM can dovetail to recognize $L_1 \cup L_2$ and $L_1 \cap L_2$.
• RE is NOT closed under complement. If $L$ is RE but not recursive, $\overline{L}$ is not RE. Example $A_{TM}$ is RE, $\overline{A_{TM}}$ is not RE. So the conjunction “union and complementation” fails.

C. Turing-decidable (Recursive) languages are closed under intersection and complementation.

True. Recursive languages are decidable by a TM that always halts. Deciders can be complemented by swapping accept/reject, and intersected via product construction. They are closed under all Boolean operations: union, intersection, complement, difference.

D. Turing-recognizable languages are closed under union and intersection.

True. As noted in B, RE retains closure under union and intersection, only complement fails.

Summary

Statement	Truth
A	True
B	False
C	True
D	True

Only B is false.

Final Answer

B only is false → Option (iii).

Answer

Correct Option: (i) $L'$ is recursively enumerable (equivalently (iii) Both if $T$ is decider)

Explanation

Theorem (Sipser): RE language $L$ is recursive (decidable) iff both $L$ and $\overline{L}$ are RE.

• If $L$ is RE and $\overline{L}$ is RE, then dovetail enumerators for $L$ and $\overline{L}$; whichever enumerates $w$ first decides.
• Formal: $L$ recursive ⇔ $L$ RE and $L'$ RE.

Option (ii) “every sequence of moves halts” is characterization of decider (always halts), also true for recursive $L$ but not the standard RE condition. Option (i) is the textbook criterion.

If exam lists (iii) Both (i) and (ii), that is also correct for decider TM. Most keys mark (i) or (iii).

Final Answer

$L$ recursive iff $L'$ is RE → Option (i) (and (iii) Both if inclusive).

Answer

Correct Option: (iii) The Halting Problem

Explanation

Decidability:

Problem	Decidable?
DFA acceptance $w \in L(DFA)$?	Decidable — simulate DFA $O(|w|)$
NFA acceptance	Decidable — subset simulation or convert to DFA
Regex matching $w \in L(R)$?	Decidable — convert to DFA/NFA
Emptiness $L(DFA)=\emptyset$?	Decidable
Halting Problem $M$ halts on $w$?	Undecidable (Turing 1936)

Proof sketch: Assume $H(\langle M,w\rangle)$ decides halting, diagonalize with $D(\langle M\rangle)=$ loop if $M$ halts on $\langle M\rangle$ else halt. $D(\langle D\rangle)$ contradicts.

Final Answer

Undecidable is Halting Problem → Option (iii).