In formal language theory and computational complexity decidable languages play a crucial role in understanding the limits of computation. A language is decidable if there exists a Turing machine that can determine in finite time whether a given string belongs to the language or not.
One fundamental property of decidable languages is that their union is also decidable. In this topic we will explore what this means why it holds true and its implications in computational theory.
Understanding Decidable Languages
Definition of Decidable Languages
A language L is decidable if there exists a Turing machine M that for every input string w does the following:
- Accepts if w belongs to L.
- Rejects if w does not belong to L.
- Always halts for every input (i.e. it never runs indefinitely).
Such languages are also called recursive languages because they can be fully determined by an algorithm.
Examples of Decidable Languages
- The set of all even-length binary strings.
- The set of all valid arithmetic expressions.
- The set of all palindromes over {a b}.
The Union of Two Decidable Languages
Formal Statement
If L₁ and L₂ are two decidable languages then their union L = L₁ ∪ L₂ is also decidable.
This means there exists a Turing machine that can determine in finite time whether an input string w belongs to L₁ ∪ L₂.
Proof of Decidability of the Union
Let M₁ be a Turing machine that decides L₁ and M₂ be a Turing machine that decides L₂. Since both M₁ and M₂ are deciders they always halt on any input w.
To construct a Turing machine M that decides L = L₁ ∪ L₂ follow these steps:
-
Simulate M₁ on input w:
- If M₁ accepts w then accept w (because w ∈ L₁ ∪ L₂).
- If M₁ rejects w proceed to step 2.
-
Simulate M₂ on input w:
- If M₂ accepts w then accept w.
- If M₂ rejects w then reject w.
Since both M₁ and M₂ are guaranteed to halt the combined machine M also halts on every input w. Thus L₁ ∪ L₂ is decidable.
Why Is This Important?
1. Closure Properties of Decidable Languages
This proof confirms that decidable languages are closed under union. Other operations that maintain decidability include:
- Intersection (L₁ ∩ L₂) – A language remains decidable if two decidable languages are intersected.
- Complementation (~L₁) – The complement of a decidable language is also decidable.
- Concatenation (L₁ ∘ L₂) – Concatenating two decidable languages results in another decidable language.
2. Practical Applications
- Compiler Design: Combining multiple rules in lexical analysis.
- Database Queries: Merging search results from different conditions.
- Natural Language Processing: Recognizing multiple valid sentence structures.
3. Relationship to Recognizable Languages
While decidable languages are always recognizable the reverse is not true. However the union of two recognizable (but not necessarily decidable) languages is also recognizable though not necessarily decidable.
We have proven that the union of two decidable languages is always decidable by constructing a Turing machine that simulates both deciders. This result is significant because it ensures that decidability is preserved under union reinforcing the robustness of the class of recursive languages.
Understanding these closure properties is essential for theoretical computer science with direct applications in programming database management and language processing.
