GATE CS 1990 Q3-vi — Turing Machines

To determine which statements are correct, let us analyze the properties of Recursive languages (also known as decidable languages) in the context of the Chomsky hierarchy:

1. A proper superset of context-free languages:

   According to the Chomsky hierarchy, the containment relationship is:

   $$\text{Regular} \subset \text{Context-Free (CFL)} \subset \text{Context-Sensitive (CSL)} \subset \text{Recursive} \subset \text{Recursively Enumerable (Type 0)}$$

   Since Context-Free Languages are a proper subset of Recursive languages, Recursive languages are indeed a proper superset of Context-Free languages.

   (Option A is correct)
2. Always recognizable by pushdown automata:

   Pushdown automata (PDAs) recognize only Context-Free Languages. Since there are recursive languages that are not context-free (for example, $L = \{a^n b^n c^n \mid n \ge 0\}$), they cannot all be recognized by a PDA.

   (Option B is incorrect)
3. Also called type 0 languages:

   Type 0 languages in the Chomsky hierarchy correspond to Recursively Enumerable (RE) languages. Recursive languages are a proper subset of Type 0 languages (specifically, those RE languages for which a halting Turing machine exists).

   (Option C is incorrect)
4. Recognizable by Turing machines:

   A language is recursive if and only if there exists a Turing machine (specifically, a decider) that accepts strings in the language and rejects strings not in the language, halting in both cases. Since every recursive language is decided (and thus recognized) by a Turing machine, this statement is true.

   (Option D is correct)

Therefore, the correct options are A and D.