Past exam question: 2081 Chaitra (Regular), Q4(c)
Open in the Padhaiko appExplain 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:
- 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.
- 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:
- Union (): Closed. Run decider on . If it accepts, accept. Otherwise, run decider on . Accept iff accepts.
- Intersection (): Closed. Run on . If it rejects, reject. If it accepts, run on and accept iff accepts.
- Complementation (): Closed. Simulate decider on and swap its terminal decisions (accept becomes reject, reject becomes accept).
- Concatenation (): Closed. For input of length , test all possible splits . Since both and halt on all inputs, all splits are verified in finite time.
- Kleene Star (): Closed. Test all partitions of in finite time.
(Post's Theorem: is recursive if and only if both and are recursively enumerable).
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).