---
title: "Recursive language and its properties"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:recursive-language-properties"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/recursive-language-properties
site: BCT Engineering
---

# Recursive language and its properties

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2072 Chaitra; 2073 Chaitra (asked 2 times)
- Video: [TOC Lec 54 - Properties of Recursive language by Deeba Kannan](https://www.youtube.com/watch?v=_4asJqA2xTI) — DEEBA KANNAN
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/recursive-language-properties
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

What is a recursive language? Mention its properties.

## Short answer

A recursive language is decidable: a Turing machine halts on all inputs and accepts exactly the strings in L. Properties: closed under complement, union, intersection, difference; recursive ⊂ RE; L is recursive iff L and its complement are RE; membership is decidable; hierarchy: regular ⊂ CFL ⊂ CSL ⊂ recursive ⊂ RE.

## Answer

#### Definition
A language L is **recursive** (also called **decidable** or **Turing-decidable**) if there is a Turing machine M that **halts on every input** and accepts exactly the strings of L: M accepts w if w ∈ L and halts in a rejecting state (or with no move) if w ∉ L. Such a TM is called a **decider** or an algorithm for L.

This differs from a recursively enumerable (RE) language, where the TM must halt and accept for w ∈ L but may loop forever for w ∉ L.

Examples: every regular language and every CFL; { aⁿbⁿcⁿ }; the set of prime numbers in binary.

#### Properties
1. **Closed under complement.** Run the decider and swap accept and reject.
2. **Closed under union and intersection.** Run both deciders on the input (one after the other) and accept if either (union) or both (intersection) accept. Both always halt.
3. **Closed under difference** (L1 − L2 = L1 ∩ L2ᶜ), **concatenation**, **Kleene star** and **reversal**.
4. **Recursive ⊂ RE.** Every recursive language is RE, but not conversely (the halting language is RE but not recursive).
5. **L is recursive if and only if both L and its complement Lᶜ are RE.**
6. **Membership is decidable:** for a recursive L, the question "is w in L?" always has an algorithmic yes/no answer.
7. **Hierarchy:** regular ⊂ CFL ⊂ context sensitive ⊂ recursive ⊂ RE ⊂ all languages.
8. Recursive languages are not closed under arbitrary homomorphism (RE languages are).

If L is RE but not recursive, then its complement is not RE.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What makes a language recursive?
   A. A TM accepts every string of L but may loop on strings not in L
   B. A TM halts on every input and accepts exactly the strings in L
   C. A PDA accepts it
   D. It has a regular expression
   Answer: B. A recursive (decidable) language has a decider TM that always halts, accepting members and rejecting non-members. (Key point: Definition)

2. Why are recursive languages closed under complement?
   A. Run the decider and swap accept and reject, as it always halts
   B. Complement of any TM language is a TM language
   C. Because the language is finite
   D. Because the TM can loop on the complement
   Answer: A. Since the decider halts on all inputs, swapping its accept and reject outcomes decides the complement. (Key point: Complement closure)

3. Which statement characterises recursive languages?
   A. L is recursive iff L is RE
   B. L is recursive iff L is context free
   C. L is recursive iff both L and its complement are RE
   D. L is recursive iff its complement is not RE
   Answer: C. Running recognisers for L and its complement together always halts, and conversely recursive implies both are RE. (Key point: Recursive iff)

4. Which hierarchy is correct?
   A. regular < CFL < context sensitive < recursive < RE
   B. regular < recursive < CFL < RE
   C. CFL < regular < recursive < RE
   D. recursive < context sensitive < RE < CFL
   Answer: A. Each class is properly contained in the next, ending with recursive inside RE. (Key point: Hierarchy)

## Related in Theory of Computation

- [Recursive iff language and complement are RE](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-iff-complement-re) — Theory of Computation, chapter 4, asked 2×
- [Recursive and recursively enumerable languages](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-vs-re-examples) — Theory of Computation, chapter 4

## Related in other subjects

- [BST properties and recursive search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-properties-recursive-search) — Data Structure and Algorithm, chapter 6
- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5
- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aclosure-properties-regular-language) — Discrete Structure, chapter 2, asked 2×
- [Ideal op-amp properties; non-inverting gain](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Aopamp-props-noninverting-gain) — Basic Electronics Engineering, chapter 4, asked 3×