Alphabets, Strings and Languages

Alphabet (Σ)

Any finite, non-empty set of symbols. {a, b}, {0, 1}, the ASCII characters, a CPU's instruction set — all alphabets. Those two adjectives are the whole definition, and both are load-bearing.

String (or word)

A finite sequence of symbols from Σ. Order matters and repetition is allowed, which is what makes it a sequence rather than a set. Its length |w| is the number of symbols in it.

Empty string (ε)

The string of length zero. It is a perfectly ordinary string, and it is a member of Σ* for every Σ.

Language (L)

Any subset of Σ\*. That is all — no grammar, no meaning, no machine is part of the definition. ∅ and Σ* are both languages.

This is the most common early mistake in the subject, and it costs marks for years if it is not fixed immediately. Three different objects:

Test yourself with concatenation: L · ∅ = ∅ for every L, but L · {ε} = L. If those two look like the same statement, the distinction has not landed yet.

Concatenation (xy)

Write x then y. |xy| = |x| + |y|, and εw = wε = w, which makes ε the identity. Concatenation is associative but not commutative.

Powers (wⁿ)

w repeated n times, with w⁰ = ε by definition. This is what lets you write aⁿbⁿ and mean something precise.

Reversal (wᴿ)

The same symbols backwards. A string with w = wᴿ is a palindrome.

Prefix, suffix, substring

A prefix is any leading part, a suffix any trailing part, a substring any contiguous run. Every string is a prefix and a suffix of itself, and ε is a prefix of everything.

Σ\* is the set of all strings over Σ, of every length, including ε. It is always infinite (as long as Σ is non-empty), because there is no bound on length. Σ⁺ is the same set with ε removed.

But notice what Σ\* does not contain: infinite strings. Every member is finite; there are merely unboundedly many of them. That is why a machine reading an input is always guaranteed to reach the end of it, which is what makes acceptance a well-defined question at all.

For |Σ| = k there are exactly kⁿ strings of length n, so |Σ*| = 1 + k + k² + …. The count of length-n strings is a standard exam question and it is just kⁿ.

Languages are sets, so union, intersection and complement mean what they always mean. Two more are specific to strings, and they are the ones that build regular expressions:

• Concatenation. L₁ · L₂ = { xy : x ∈ L₁, y ∈ L₂ } — every way of taking one from each, in that order.
• Kleene star. L* = { w₁w₂…wₙ : n ≥ 0, each wᵢ ∈ L } — any number of members glued together, including zero of them. **ε ∈ L* always**, even when L = ∅.

∅* = {ε} catches almost everyone. Zero concatenations is a legal choice, and it produces ε.

Fix a language L. Hand a machine a string and ask: is w ∈ L? Recognising L means answering correctly for every string in Σ\* — including the infinitely many you will never test.

This looks restrictive and is not. "Is this program syntactically valid C?" is membership in the language of valid C programs. "Is this number prime?" is membership in the language of decimal strings denoting primes. Reducing all of computation to one yes/no shape is exactly what makes it possible to prove things about what can and cannot be computed.