Alphabets, Strings, and Languages
Every search engine, every compiler, every network protocol parser answers the same hidden question. Does this input belong to a certain set of acceptable patterns? Before we can build machines that answer such questions, we need a precise vocabulary for talking about "input" itself. We must define what counts as a symbol, what counts as a sequence of symbols, and what counts as a collection of valid sequences. This is the subject of alphabets, strings, and languages — the bedrock layer beneath all of automata theory. These definitions can look almost childishly simple, and that simplicity is the point. Formal language theory succeeds precisely because it strips away the semantics of a problem. It keeps only its combinatorial skeleton: symbols drawn from a finite set, arranged in finite sequences, grouped into sets we call languages. A regular expression, a programming language's grammar, a network protocol's valid packet formats — all of these are, at bottom, languages over some alphabet. Once we fix this vocabulary, we can ask sharp mathematical questions: which languages can a finite-state machine recognize? Which need a stack? Which need unbounded memory? Real systems depend on this abstraction constantly. A lexer for a compiler partitions an input string into tokens. It does this by matching prefixes against a language of valid identifiers, numbers, and keywords. A regular-expression engine in a text editor decides membership in a language defined by a pattern. A JSON or XML parser checks whether a string belongs to the language generated by a formal grammar. Even DNA sequence analysis treats a genome as a string over the alphabet {A, C, G, T}. It searches for membership in biologically meaningful languages (motifs, genes, regulatory regions). This article builds the formal scaffolding: alphabets as finite symbol sets, strings as finite sequences with a precise notion of length and concatenation, the empty string as an identity element, and languages as arbitrary sets of strings. We prove the basic algebraic facts (concatenation is associative, the empty string is a two-sided identity). We introduce standard operations on languages. We also set up exactly the vocabulary that Deterministic Finite Automata, Regular Expressions, and Context-Free Grammars will build upon.
- An alphabet Σ is any finite, nonempty set of symbols; a string is a finite sequence of symbols from Σ.
- The empty string ε has length 0 and is the identity element for string concatenation.
- Concatenation of strings is associative but not commutative; it makes Σ* into a monoid.
- Σ\ denotes the set of all* strings over Σ, including ε; it is always infinite (for |Σ| ≥ 1) yet each individual string is finite.
- A language is simply any subset of Σ\* — languages can be finite, infinite, decidable, or even undecidable as sets.
- Standard operations on languages (union, concatenation, Kleene star, complement) let us build complicated languages from simple ones, foreshadowing regular expressions.
A language is nothing more than a set of strings over a fixed alphabet — every question in automata theory is ultimately a question about which sets of strings a given kind of machine can distinguish.
The idea
An alphabet, conventionally written Σ (capital sigma), is a finite, nonempty set whose elements are called symbols or characters. Examples include Σ = {0, 1} (binary digits), Σ = {a, b, ..., z} (lowercase Latin letters), or Σ = {A, C, G, T} (DNA bases). The finiteness of Σ is essential — it is what makes it possible to enumerate machine transitions, write regular expressions, and reason combinatorially about pattern matching. Nothing is assumed about the symbols' internal structure; they are atomic tokens. A string (also called a word) over Σ is a finite sequence of symbols each drawn from Σ. We write strings by simple juxtaposition, so `0110` is a string over Σ = {0, 1}, and `cat` is a string over the Latin alphabet. The length of a string w, written |w|, is the number of symbols in it; formally, if w = a₁a₂⋯aₙ with each aᵢ ∈ Σ, then |w| = n. There is a unique string of length 0, called the empty string, denoted ε (epsilon). The empty string contains no symbols at all, yet it is a perfectly legitimate string over every alphabet. The set of all strings over Σ, of every possible length, is denoted Σ\, read "sigma star." This notation is the <strong>Kleene star</strong> applied to the alphabet viewed as a language of length-1 strings, and it always includes ε. Formally, ``` Σ = { w : w is a finite sequence over Σ } = ⋃_{n=0}^{∞} Σ^n ``` where Σⁿ is the set of all length-n strings over Σ (so Σ⁰ = {ε}). Even when Σ has just one symbol, Σ is countably infinite, because strings can be arbitrarily long: with Σ = {a}, Σ = {ε, a, aa, aaa, …}. It is also useful to define Σ⁺ = Σ\ − {ε}</strong>, the set of all nonempty strings. The fundamental operation combining strings is <strong>concatenation</strong>. If x = a₁⋯aₘ and y = b₁⋯bₙ are strings over Σ, their concatenation xy (sometimes written x·y) is the string a₁⋯amb₁⋯bₙ formed by writing x immediately followed by y, with |xy| = |x| + |y|. Concatenation is <strong>associative</strong> — (xy)z = x(yz) for all strings x, y, z — because both sides simply describe the same sequence of symbols laid end to end; there is never any ambiguity about how to group a chain of concatenations. It is emphatically <strong>not commutative</strong>: with x = "ab" and y = "ba", xy = "abba" while yx = "baab", and these are different strings whenever x and y are both nonempty and distinct. The empty string ε acts as the <strong>identity element</strong> for concatenation: for every string w, εw = wε = w. This holds because concatenating a sequence of zero symbols before or after w changes nothing about the resulting sequence. Together, associativity and the identity property mean that (Σ\, ·, ε) forms an algebraic structure called a free monoid generated by Σ — "free" because there are no relations among the symbols other than those forced by the definitions themselves (no symbol equals any concatenation of others). This monoid structure is what later lets us define regular expressions as algebraic expressions built from ∪, concatenation, and Kleene star. Finally, a language over Σ is defined with maximum generality: it is any subset L ⊆ Σ\. A language can be finite (L = {"cat", "dog"}), infinite (L = the set of all strings with an even number of 0's), all of Σ\ itself, or even the empty set ∅ (the language containing no strings at all — note carefully that ∅ ≠ {ε}, since {ε} contains one string while ∅ contains none). Because Σ\* is countably infinite, the set of all possible languages over Σ has cardinality 2^(ℵ₀), which is uncountable — a fact with deep consequences (it immediately implies that most languages cannot be described by any finite algorithm or grammar, since there are only countably many finite descriptions).
How it works
There is no "algorithm" for the definitions themselves, but there is a precise algorithmic discipline for working with strings and languages: computing lengths, concatenating, deciding membership, and combining languages via standard operations. We lay these out as the operational toolkit every later automaton-theory construction relies on.
Core string operations. Given strings represented as arrays or lists of symbols, the basic operations are: ``` function LENGTH(w): return number of symbols in w // |ε| = 0 by definition function CONCAT(x, y): // produces the string formed by x immediately followed by y result = new empty sequence append all symbols of x to result append all symbols of y to result return result // CONCAT(ε, y) = y and CONCAT(x, ε) = x (identity law — must hold) function REVERSE(w): // reverses the order of symbols; used later for automaton constructions if w = ε: return ε else: let w = a·w' // a is first symbol, w' is the remaining suffix return CONCAT(REVERSE(w'), a) function IS-SUBSTRING(x, w): // decides whether x occurs as a contiguous block inside w n = LENGTH(w); m = LENGTH(x) if m = 0: return true // ε is a substring of everything for i from 0 to n - m: if w[i .. i+m-1] equals x: return true return false ```
Language-building operations. Since a language is just a set of strings, we can combine languages using ordinary set operations plus two string-specific ones — concatenation of languages and the Kleene star: ``` function UNION(L1, L2): return { w : w ∈ L1 or w ∈ L2 } function INTERSECTION(L1, L2): return { w : w ∈ L1 and w ∈ L2 } function COMPLEMENT(L, Σ): return { w ∈ Σ : w ∉ L } function LANG-CONCAT(L1, L2): // every way of gluing a string from L1 to a string from L2 return { CONCAT(x, y) : x ∈ L1, y ∈ L2 } function KLEENE-STAR(L): // all strings formed by concatenating zero or more strings from L result = { ε } // zero copies of anything gives ε S = { ε } repeat forever (conceptually — this is an infinite union): S = LANG-CONCAT(S, L) ∪ { ε } result = result ∪ S return result // formally: L = ⋃_{k=0}^{∞} L^k , where L^0 = {ε}, L^{k+1} = LANG-CONCAT(L^k, L) ``` These are mathematical definitions, not literal terminating programs — `KLEENE-STAR` as written never halts, because L is generally infinite. The pseudocode communicates the recursive structure (L is built from progressively longer concatenations of L with itself), which is exactly the structure that finite automata later exploit to recognize L* using only finite memory, by tracking "have I just completed a copy of a string in L?" rather than enumerating strings.
Membership as the central computational question. Formal language theory recasts nearly every parsing and pattern-matching problem as one instance of a single question: ``` function MEMBER(w, L): return (w ∈ L) ? true : false ``` Everything downstream — Deterministic Finite Automata deciding membership in regular languages in one linear pass, Regular Expressions compactly specifying such languages, Context-Free Grammars specifying richer languages via derivation rules — is a different engineering answer to `MEMBER`, tailored to different classes of L.
Complexity & correctness
Representational complexity. A string w of length n is typically stored as an array or linked list of n symbols, using O(n) space (assuming a constant-size alphabet, so each symbol takes O(1) space). Concatenation of strings of lengths m and n takes O(m + n) time and space when producing a fresh copy, since every symbol of both strings must be written once; some implementations (rope data structures, used in text editors) achieve O(log n) amortized concatenation by keeping strings as balanced trees of chunks rather than flat arrays, trading simplicity for asymptotic speed on very large texts. `IS-SUBSTRING` as written is the naive O(n·m) algorithm; faster string-matching algorithms (Knuth–Morris–Pratt, Boyer–Moore, achieving O(n + m)) exist but are a separate topic from the definitional questions here.
Correctness of the monoid laws. Two algebraic facts underpin everything downstream, so we verify them directly from the definition of concatenation as sequence-juxtaposition. Associativity: for strings x = a₁⋯aₗ, y = b₁⋯bₘ, z = c₁⋯cₙ, ``` (xy)z = a₁⋯aₗ b₁⋯bₘ c₁⋯cₙ = x(yz) ``` Both (xy)z and x(yz) denote the identical sequence a₁⋯aₗb₁⋯bₘc₁⋯cₙ — concatenation is defined purely as "write one sequence, then the other," so grouping is irrelevant to the resulting sequence of symbols. This is why we may write xyz unambiguously without parentheses, exactly as with numeric addition. Identity: εw is the sequence formed by writing zero symbols followed by the n symbols of w, which is just w itself; symmetrically for wε. Hence ε is a genuine two-sided identity, making (Σ\*, concatenation, ε) a monoid — and specifically a free monoid, since distinct strings are never forced to be equal (no "relations" hold beyond the bookkeeping of sequence equality). This freeness is exactly what licenses unique decomposition: if xy = x'y' and |x| = |x'|, then necessarily x = x' and y = y', because a sequence's initial segment of a given length is uniquely determined. Automaton constructions that prove properties of concatenated strings (e.g., pumping-lemma arguments) implicitly lean on this uniqueness.
Cardinality facts and their consequences. For any nonempty finite alphabet Σ, Σⁿ has exactly |Σ|ⁿ strings (an easy induction: Σ⁰ = {ε} has 1 = |Σ|⁰ string; Σ^{n+1} = {aw : a ∈ Σ, w ∈ Σⁿ} has |Σ|·|Σ|ⁿ = |Σ|^{n+1} strings, since each choice of first symbol and each string in Σⁿ pairs uniquely). Summing over all n shows Σ\ is a countably infinite union of finite sets, hence <strong>countably infinite</strong>. Since the power set of a countably infinite set is uncountable (Cantor's diagonal argument), the collection of all languages over Σ has cardinality 2^ℵ₀. This is the precise sense in which "almost all languages are impossible to describe": there are only countably many finite strings that could serve as descriptions (grammars, regular expressions, Turing machine encodings), so an uncountable "majority" of languages admit no finite specification whatsoever. This single cardinality argument — pure set theory, no automata required — is why formal language theory must always restrict attention to specific, describable classes* of languages (regular, context-free, decidable, recognizable) rather than trying to handle "all languages" at once.
Honest tradeoffs. The definitions here impose no computational cost by themselves — a set-theoretic language is a mathematical object, not a data structure, and asking "is this language regular?" or "is w ∈ L decidable in polynomial time?" are entirely separate, much harder questions addressed by later machinery. The price of this generality is that a language, as defined, gives no algorithmic handle on membership: L = {w : w encodes a proof that P ≠ NP} is a perfectly legitimate language by this definition, even though no known procedure decides membership. Precision at this layer buys nothing computationally; its payoff is that every later theorem (about DFAs, NFAs, CFGs, Turing machines) can be stated and proved with zero ambiguity about what "string" and "language" mean.
Worked example
Let Σ = {a, b}. We trace several definitions concretely, using the language ``` L = { w ∈ Σ* : w contains the substring "ab" } ```
| Expression | Evaluation | Reasoning | ||||
|---|---|---|---|---|---|---|
| \ | Σ\ | 2 | Σ has two symbols: a, b | |||
| \ | ε\ | 0 | the empty string always has length 0 | |||
| \ | "aab"\ | 3 | three symbols: a, a, b | |||
| CONCAT("aa", "b") | "aab" | write "aa" then "b" in sequence | ||||
| CONCAT("b", "aa") | "baa" | order matters — ≠ CONCAT("aa","b"); shows non-commutativity | ||||
| CONCAT(ε, "ba") | "ba" | ε is the identity: no symbols added | ||||
| REVERSE("aab") | "baa" | recursive peel-off-front-append-to-reversed-rest | ||||
| Is "ab" ∈ Σ²? | yes | Σ² = {aa, ab, ba, bb}, all length-2 strings | ||||
| \ | Σ³\ | 8 | \ | Σ\ | ³ = 2³ = 8, by the counting argument above | |
| Is "ab" ∈ L? | yes | "ab" itself contains "ab" as a substring | ||||
| Is "ba" ∈ L? | no | no occurrence of consecutive a-then-b | ||||
| Is "bab" ∈ L? | yes | positions 2–3 spell "ab" | ||||
| Is ε ∈ L? | no | the empty string contains no substrings of length 2 | ||||
| Is "bab" ∈ COMPLEMENT(L, Σ)? | no | "bab" ∈ L, so it is excluded from the complement | ||||
| L ∩ {a, aa, ab} | {ab} | of the three strings, only "ab" contains "ab" |
A second, subtler trace — checking L\ against the Kleene-star definition.</strong> Let L = {"ab", "ba"}. We verify that "abba" ∈ L\ directly from the definition L = ⋃ₖ Lᵏ, rather than by informal inspection. ``` Step 1: Is "abba" ∈ L^0 = {ε}? No, |"abba"| = 4 ≠ 0. Step 2: Is "abba" ∈ L^1 = L? No, "abba" ∉ {"ab","ba"}. Step 3: Is "abba" ∈ L^2 = LANG-CONCAT(L, L)? L^2 = { CONCAT(x,y) : x,y ∈ L } = { "abab", "abba", "baab", "baba" } "abba" = CONCAT("ab", "ba") ✓ found at k = 2. Conclusion: "abba" ∈ L^2 ⊆ L, so "abba" ∈ L. ``` This trace matters pedagogically: it shows that even for a two-string language L, checking membership in L is not "obvious," and requires systematically searching increasing values of k until a decomposition is found (or, for a fixed target string of length n, checking only k up to n, since each factor of L is nonempty and contributes length ≥ 1 — giving a terminating, correct decision procedure for L\*-membership whenever L is finite).
Common pitfalls & traps
| Pitfall | Why it happens | Fix | ||||
|---|---|---|---|---|---|---|
| Confusing ∅ with {ε} | Both feel like "nothing," but ∅ has zero strings while {ε} has one string (the empty one) | Always ask: does the set contain an element, even if that element is the empty string? | ||||
| Assuming concatenation is commutative | Ordinary arithmetic intuition (a+b = b+a) misleads | Check with a concrete asymmetric example: "ab" vs "ba" | ||||
| Treating Σ\* as finite | Σ is finite, so it "feels closed" | Remember Σⁿ grows without bound as n → ∞; Σ* unions all of them | ||||
| Forgetting ε is a substring/prefix/suffix of every string | Intuition treats "empty" as "absent" | By definition, ε occurs (vacuously) at every position, including in ε itself | ||||
| Conflating a language with a grammar or regex that generates it | Many languages are first met via a describing mechanism | A language is the set of strings; a regex/grammar is just one possible finite description of that set | ||||
| Miscounting Σⁿ | Off-by-one errors in induction (using | Σ | ⁿ⁻¹ instead of | Σ | ⁿ) | Re-derive from Σ⁰ = {ε} (1 string) and Σ^{k+1} = Σ·Σᵏ |
| Assuming every language has a finite description | Every language encountered in practice does | Cardinality argument: 2^ℵ₀ languages exist, only ℵ₀ finite descriptions are possible |
Pioneers & history
The formalization of strings and languages as mathematical objects emerged from the convergence of formal logic, linguistics, and early computability theory in the mid-twentieth century, long before "automata theory" existed as a named field. The free-monoid perspective on strings traces to abstract algebra, while the specific idea of treating a language as a set of strings generated or recognized by a finite mechanism was crystallized by mathematical linguists and logicians studying what kinds of "grammars" could describe natural and formal languages alike.
Origins · 1 minNoam Chomsky and how this was discovered
Chomsky's 1956 work on the mathematical structure of grammars introduced the hierarchy of grammar types (later named the Chomsky hierarchy) that classifies languages by the generative power required to produce them. His insistence on treating a language purely as a set of strings — stripped of meaning, judged only by membership — gave computer science exactly the abstraction it needed to build parsers, compilers, and later, automata theory itself.
Where this matters
Every compiler front end begins with a lexer that scans source code as a string over the ASCII or Unicode alphabet and partitions it into tokens, each token being a member of some language (identifiers, integer literals, string literals) specified by a regular expression. Network protocols such as HTTP and DNS define their wire formats as languages over the byte alphabet, and packet parsers must correctly decide membership (and reject malformed input) at line rate. Search engines and text editors implement regex engines that, under the hood, compile a pattern into a description of a language over the alphabet of Unicode code points and then decide membership for candidate substrings. Bioinformatics tools treat genomic sequences as strings over {A, C, G, T} (or the twenty-letter amino-acid alphabet for proteins) and pose alignment and motif-search problems as language-membership and pattern-matching questions. Password-strength checkers, input validators, and configuration-file parsers are all, under the formal surface, deciding membership in a language — which is precisely why the vocabulary built here feeds directly into Deterministic Finite Automata (machines that decide membership in the simplest, "regular," languages), into Regular Expressions (a compact algebraic notation for describing exactly those languages), and into Context-Free Grammars (a strictly more expressive mechanism needed for nested structures like arithmetic expressions and balanced parentheses that no finite automaton can handle).
Ask the tutor: How does the free-monoid structure of Σ* get used to prove the pumping lemma for regular languages?
Is the empty string ε the same as the empty language ∅?
No, and this is the single most common point of confusion in the topic. ε is a string — specifically, the unique string of length 0. ∅ is a language, meaning a set of strings, and specifically the set containing no strings at all. The language {ε} is a perfectly valid, nonempty set that happens to contain exactly one element, the empty string. So {ε} ≠ ∅: the former has one member, the latter has zero. This distinction matters enormously in Kleene-star definitions, where L\* always contains ε (zero copies of anything concatenated together yield the empty string) even when L itself does not contain ε.
Why must an alphabet be finite? What breaks if it isn't?
Finiteness of Σ is what makes automata theory computationally meaningful. A finite-state machine's transition function is a finite table; it must have one entry per (state, symbol) pair, so an infinite alphabet would require infinite tables, breaking the entire premise of "finite" automata. Regular expressions, similarly, are finite strings built from finitely many alphabet symbols and operators, so an infinite alphabet would make some patterns inexpressible as finite text. Practically, every real alphabet (ASCII, Unicode, DNA bases, punch-card columns) is finite by construction, so this restriction costs nothing in practice while buying enormous theoretical tractability.
Can a language contain strings of different lengths?
Yes, and in fact almost every interesting language does. A language is simply an arbitrary subset of Σ*, with no requirement that its members share a length. For example, the language of syntactically valid Python identifiers contains strings of every length from 1 upward. The only languages with a fixed common length are subsets of a single Σⁿ; these are called "finite-length" or sometimes trivial languages, and they are comparatively uninteresting because a finite alphabet and fixed length forces the language itself to be finite (at most |Σ|ⁿ strings), sidestepping most of the deep questions automata theory studies.
Is every set of strings actually a "language" that some machine can recognize?
By the bare definition used here, yes — any subset of Σ qualifies as a language, purely as a set-theoretic object. But recognizability is a separate, much stronger property: it asks whether some algorithmic machine (finite automaton, pushdown automaton, Turing machine) can correctly decide membership. The cardinality argument in this article shows there are uncountably many languages but only countably many finite machine descriptions, so the vast majority of languages are not recognizable by any* algorithm whatsoever. The entire hierarchy of automata theory — regular, context-free, decidable, recognizable — is the study of which "islands" within this uncountable sea of languages admit finite computational descriptions.
Why does the ordering in Σⁿ = |Σ|ⁿ matter, and how is it proved?
It matters because it is the combinatorial engine behind pigeonhole arguments used throughout automata theory (for instance, the pumping lemma relies on counting strings against a finite number of automaton states). The proof is a clean induction: Σ⁰ has exactly one string, ε, matching |Σ|⁰ = 1. Assuming Σⁿ has |Σ|ⁿ strings, each string in Σ^{n+1} is formed by choosing one of |Σ| symbols to prepend to a string in Σⁿ, and distinct choices always give distinct results (this is where uniqueness of decomposition, guaranteed by the free-monoid structure, is used), giving |Σ|·|Σ|ⁿ = |Σ|^{n+1} strings.
How does this vocabulary connect to Deterministic Finite Automata directly?
A DFA is precisely a machine designed to decide membership, w ∈ L, for one specific class of languages, called regular languages, using only a finite number of internal configurations (states) and a single left-to-right pass over w. The alphabet Σ fixed here is literally the DFA's input alphabet; the string w is literally the input tape contents; and "L is regular" means exactly "some DFA's accepted language equals L." Everything about DFA correctness proofs (invariants over the state reached after reading a prefix) is stated in the exact vocabulary of strings, prefixes, and concatenation built in this article.
Do languages have to be described by regular expressions or grammars?
No — description is optional, and this is a subtle but important point. The definition "a language is a subset of Σ" places no requirement that the subset be describable by any finite means. Regular expressions and grammars are tools humans invented* to finitely specify certain (comparatively simple) languages; most languages, by the uncountability argument, admit no such finite specification at all. When we later study regular languages, context-free languages, and decidable languages, we are always studying a strict, describable subclass of "all languages," never the full uncountable collection.