Alphabets, Strings, and the Closure Properties That Define a Language Class

A language over an alphabet Σ is any subset of Σ*, the set of all finite strings of symbols drawn from Σ. That is the entire definition. No grammar, no rule, no machine is required. Under it, almost every language that exists can never be written down or recognised, and the first structural fact worth absorbing is how small and how special the writable ones are.

Σ* is a free monoid, and that fixes the vocabulary

Σ* is the set of finite sequences over Σ, including the empty sequence ε. Concatenation is associative and ε is its identity, so Σ* is a monoid, and it is the free monoid on Σ: every element has exactly one decomposition into symbols, with no relations imposed. A string of length n is a function from positions {1..n} to Σ, and length is a homomorphism from (Σ*, ·) to (ℕ, +).

That algebraic starting point generates the standard vocabulary without further invention. A prefix of w is any initial segment; a suffix any final segment; a factor (or substring) any contiguous segment. Reversal is the anti-automorphism that maps a₁a₂…aₙ to aₙ…a₂a₁. A language is a subset of Σ*, and the operations on languages are the pointwise liftings of string operations plus the set operations inherited from the powerset:

• Union, intersection, and complement, where complement is taken relative to Σ* and is therefore well defined only once the alphabet is fixed.
• Concatenation L·M = {uv : u ∈ L, v ∈ M}, and powers Lᵏ defined by repeated concatenation with L⁰ = {ε}.
• Kleene star L* = ⋃{k≥0} Lᵏ, and Kleene plus L⁺ = ⋃{k≥1} Lᵏ. The difference between the two is exactly the empty string.
• Reversal, homomorphism (symbol-by-symbol substitution by strings), inverse homomorphism, and quotient L/M = {u : ∃v ∈ M, uv ∈ L}.

Each of these is a composition operator on specifications. If a class of languages is closed under an operator, a specification written in that class can be combined with another specification and stay inside the class. That is the practical content of a class: not the languages in it, but the algebra they support.

Closure is what makes a class usable as a specification language

Take the regular languages. They are closed under union, intersection, complement, concatenation, star, reversal, homomorphism, inverse homomorphism, and quotient by any language whatsoever. All nine closure facts are constructive: given finite automata or regular expressions for the operands, each proof yields an automaton for the result. Closure under intersection, for instance, is the product construction, whose state count is the product of the operand state counts, so two automata of 10 and 12 states yield one of 120. Complement is a relabelling of accepting and non-accepting states and costs nothing in size.

The context-free languages sit differently. They are closed under union, concatenation, star, reversal, homomorphism, and intersection with a regular language. They are not closed under intersection or complement, and the failure is not a gap in the proofs but a theorem with a two-line witness, covered in Closure Gaps in Context-Free Languages. The consequence is concrete: a specification language without complement cannot express “everything except this shape”, and one without intersection cannot conjoin two independent structural constraints and stay inside the class.

Closure facts also come with prices. Regular languages are closed under star, and the construction is cheap: add a new start state with ε-transitions to the old start and from every accepting state back to it, then make the old start non-accepting. Closure under complement for nondeterministic automata, however, requires determinisation first, and that step can multiply the state count by an exponential, as Right-Linear Grammars and the Limits of One-Way Derivation describes. A closure property that exists but costs 2ⁿ states is different in practice from one that costs a constant factor, and the theory tracks both.

A language is a set; a description is a finite string

Fix Σ with at least two symbols. Σ* is countably infinite, since it is the union of the finite sets Σⁿ. The set of all languages is the powerset of Σ*, which has cardinality 2^ℵ₀. Every grammar, automaton, regular expression, and program is a finite string over some finite alphabet, so the set of all descriptions is countable. Therefore only countably many languages have any description at all, and the overwhelming majority of languages are not merely undecidable but nameless: no finite object denotes them.

This is why formal language theory is organised around representations rather than sets. The questions that classify a class are always of the form “given a description of this kind, decide the following”:

• Membership. Given a description D and a string w, is w ∈ L(D)? For a deterministic automaton this takes time linear in |w| and constant space beyond the input. For a context-free grammar the standard algorithm is cubic in |w|, described in Chomsky Normal Form and the CYK Table.
• Emptiness. Is L(D) = ∅? For grammars this is a reachability question over nonterminals that can generate terminal strings.
• Equivalence. Do two descriptions denote the same set? Decidable for deterministic automata by minimisation or by a product construction, undecidable for context-free grammars.

A set has no complexity. A description does, and the same set can have cheap descriptions and expensive ones: the language of strings over {a,b} with an even number of a’s has a two-state automaton, a short regular expression, and also arbitrarily bloated grammars.

The asymmetry between sets and descriptions also explains the standard non-constructive proofs. When a theorem says “there exists a non-regular language”, the counting argument above suffices: there are continuum many languages and only countably many automata. When a theorem says “this particular language is not regular”, counting is useless and a combinatorial argument is required, which is the role of the pumping lemma.

The alphabet size is a red herring; the encoding is not

Any finite alphabet can be injected into {0,1} by a prefix-free code, and the encoding of a language is its image under the induced homomorphism. Regularity and context-freeness are preserved by homomorphism and inverse homomorphism, so the choice of alphabet does not change which class a language belongs to. A three-symbol alphabet and a binary alphabet describe the same classes.

Encoding does change complexity, and the change is large. An input of value n written in unary has length n; written in binary it has length ⌈log₂(n+1)⌉. An algorithm that runs in time linear in the input length is therefore polynomial in n for the unary encoding and exponential in n for the binary one. This is the origin of the term pseudo-polynomial, and it is why problems stated over formal-language encodings must always name the encoding. A decision problem is a language, but the language depends on how instances are written down.

Enumerating strings is not deciding a language

The gap between “can list the members” and “can decide membership” is easiest to see in code. Shortlex order enumerates Σ* by length, then lexicographically within a length:

from itertools import islice, product

def shortlex(sigma, max_len):
    """Yield every string over sigma with length <= max_len, shortest first."""
    symbols = sorted(sigma)
    for n in range(max_len + 1):
        for tup in product(symbols, repeat=n):
            yield ''.join(tup)

print(list(islice(shortlex({'a', 'b'}, 3), 8)))
# ['', 'a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa']

Every string appears at a finite index, so the enumeration is complete. A recogniser built on it, however, terminates only on acceptance: to answer “no” it would have to exhaust an infinite sequence. That is a semi-decision procedure, and it is the weakest kind of answer a decision problem admits. The classes in the Chomsky hierarchy are distinguished precisely by which of these questions can be answered in finite time for every input, a distinction The Chomsky Hierarchy as a Ladder of Memory develops.

The definition of a language as an arbitrary subset is extensional and almost empty. Everything the subject has to say comes from restricting the allowed descriptions and then asking what those restrictions buy.