PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q4(c)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions

Question

Explain the properties of recursive language.

Solution

Definition and Decidability Characterization: A language is recursive (or decidable) if there exists a deterministic Turing Machine (a decider) that halts on every input string such that:

Key characteristics:

  1. Total Halting: Unlike general Turing machines which may loop infinitely on negative inputs, a decider for a recursive language never loops; its membership test always terminates in a finite number of steps.
  2. Chomsky Hierarchy Position: Recursive languages strictly contain all context-sensitive languages and are strictly contained within the class of recursively enumerable languages:

Closure Properties of Recursive Languages: The class of recursive languages possesses robust closure properties under standard operations:

  1. Union (): Closed. Run decider on . If it accepts, accept. Otherwise, run decider on . Accept iff accepts.
  2. Intersection (): Closed. Run on . If it rejects, reject. If it accepts, run on and accept iff accepts.
  3. Complementation (): Closed. Simulate decider on and swap its terminal decisions (accept becomes reject, reject becomes accept).
  4. Concatenation (): Closed. For input of length , test all possible splits . Since both and halt on all inputs, all splits are verified in finite time.
  5. Kleene Star (): Closed. Test all partitions of in finite time.

(Post's Theorem: is recursive if and only if both and are recursively enumerable).

Answer:

Recursive languages are languages decided by a Turing machine that halts on all inputs. They are closed under union, intersection, complementation, concatenation, and Kleene star. A language is recursive iff both it and its complement are recursively enumerable (Post's Theorem).

All past exam questions for Theory of Computation