Formal Languages and their Properties

The following page is an ongoing attempt to present and attribute the proofs of properties of formal languages. Any and all suggestions are welcome (this most certainly includes mistakes). Just send me a message!

Table of Properties

The languages and properties presented in this table are elaborated on below. An attempt is made to sort the languages in order of their expressiveness.
Types of Languages Decidable … Closed under… Is …
Language Model Membership Emptyness Equality Finiteness Subset Superset Disjointness Enumerability Union Intersection Complement Kleene Star Regular Context-Free Context-Sensitive
Regular Finite ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ¬ ¬
Deterministic Context-Free DPDA ✓ ? ✓ ? ? ? ? ? ✗ ? ? ? ✓ ¬ ¬
Context-Free PDA ✓ ✓ ✗ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✗ ✓ ¬
Indexed Nested Stack ✓ ✓ ✗ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✗ ✓ ¬
Context-Sensitive Linear Bounded ? ? ? ? ? ? ? ? ? ✗ ✗ ✓ ? ? ¬
Recursively Enumerable Turing Machine, λ-Calculus, … ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Properties of Formal Languages

Overview of Languages and their Abstract Machines

Regular Language

3 ⁢ x − 3 3 ⁢ x − 3

Context-Free Language

Context-Sensitive Language

Recursively Enumerable Language

Overview of Properties

Membership of a Word in a Language

The fundamental decision problem of compatibility theory lies in determining if a word w is part of a language L by computational means. Conventionally we understand w to be a string over a alphabet Σ, and L to be a set of such words: L ∈ ℘ ⁢ ( Σ ∗ )

It is a well known result that the there is no recursive procedure to solve the decision problem for

Emptyness of a Language

Equality of two Languages

Language is a Subset of Another

Language is a Superset of Another

Language is a Disjoint of Another

Words of the Language are Enumerable

Closed under Union

Closed under Intersection

Closed under Complementation

Closed under Repetition

Further references