What exactly is a language?

What does it mean for a piece of text to be "valid"? A valid Python identifier, a valid IPv4 address, a valid arithmetic expression, a valid English sentence — every one of these is really the same question in disguise: given this string of symbols, does it belong to the set of strings we've agreed to call valid? Theory of Computation exists because that question, asked precisely, turns out to have beautiful and sometimes surprising structure. This section makes the question precise.

The intuition, no symbols yet

Think of an alphabet as just a bag of allowed symbols — letters, digits, punctuation, whatever a problem calls for. A string is any sequence you build by pulling symbols from the bag, one after another, as many times as you like, including zero times. A language is simply the collection of sequences you've decided to call "good." That's genuinely all of it. The formalism below exists only to let us reason about that idea precisely enough to prove things, not to complicate it.

The formal treatment

An alphabet, written Σ, is a finite, non-empty set of indivisible symbols. Throughout this chapter Σ = {a, b}. A string (equivalently, a word) over Σ is a finite sequence of symbols from Σ. The number of symbols in a string w is its length, written |w|. There is exactly one string of length 0, called the empty string and written ε — it is a string, not a set, and not "nothing."

Σ* is called the Kleene star of Σ (after mathematician Stephen Kleene). Two strings concatenate by writing one after the other: if u = "aa" and v = "b" then uv = "aab". A language L over Σ is any subset of Σ* — formally, L ⊆ Σ*. Nothing more is required. L is a finite language if it has finitely many strings as members (for example L_tiny = {a, ab, abb, aabb}, exactly four strings, full stop) and an infinite language otherwise.

Worked example · classifying the spine strings

Recall the chapter's two running languages over Σ = {a, b}:

Ten strings, sorted by hand against both definitions:

Two rows worth staring at. aabb and abab have the same letter counts (two a's, two b's) yet land in different places for L_eq — because L_eq cares about order (a's strictly before b's), while L_even never looks at order at all, only at the count of a's. Same alphabet, same string lengths, genuinely different questions being asked.

Seeing Σ* · a language is just a chosen set of dots

Practice · 1.1

Section 1.1 defined L_eq by a description in English: "all a's, then equally many b's." That description is a set-builder rule, and it's fine for a human reader, but it isn't yet something you can mechanically follow, one small step at a time, to actually produce strings. A grammar is what closes that gap.

The intuition, no symbols yet

Picture a recipe card with one starting stand-in symbol — not a real ingredient yet, just a slot — and a short list of allowed substitutions. You keep substituting, choosing freely among the rules that apply, until every slot is filled and only real ingredients remain. Different sequences of choices can produce different finished dishes; the set of every dish reachable this way is the language the recipe generates.

The formal treatment

A grammar is a 4-tuple G = (V, Σ, R, S):

• V, a finite set of non-terminals (also called variables) — stand-in symbols that exist only inside the grammar and must never appear in a finished, fully-generated string.
• Σ, the familiar alphabet of terminals — the real symbols a finished string is allowed to contain. V and Σ never share a symbol.
• R, a finite set of production rules, each written α → β and read "α may be rewritten as β."
• S ∈ V, the designated start symbol — every derivation begins here.

Starting from S, repeatedly pick some rule whose left side appears in your current string and replace it with the rule's right side. Each such step is written with ⇒ ("yields"); a full chain of steps is a derivation, written S ⇒* w. Any string that appears partway through a derivation — terminals and leftover non-terminals mixed together — is called a sentential form. Only once every non-terminal is gone is the result a genuine member of the language generated by G:

Different grammars can generate the very same language — a fact Unit 3 leans on heavily when it converts grammars into standard forms (CNF, GNF) without changing what they generate. "The grammar" and "the language" are not the same object; a language is a set, a grammar is one particular recipe for that set, and a set can have many recipes.

Ambiguity, in one clean example

A grammar is ambiguous if some string it generates has more than one distinct derivation tree (equivalently, more than one distinct leftmost derivation). The smallest example worth memorising: G_amb has V={S}, Σ={a}, start S, and rules S → SS | a. It generates a⁺ = {a, aa, aaa, …}. Watch what happens for "aaa":

Both trees are built entirely from legal rules of G_amb, both have exactly three leaves reading "aaa," and they are structurally different trees. One string, two trees — that's the entire definition of ambiguity, made concrete. (Non-terminals are drawn violet throughout this book, per the colour key — that's the standing meaning of violet from here on.)

Worked example · deriving aaabbb from G_eq

Try other values of n

Practice · 1.2

L_eq and L_even looked, in Section 1.1, like two similarly simple rules about the letters a and b. They are not similarly simple. Recognising L_even needs one bit of memory: is the a-count so far odd or even? Recognising L_eq needs to remember exactly how many a's you've seen, with no upper bound — one bit will never be enough, no matter how cleverly you design the bit. That gap in memory requirement is not a curiosity; it's the organising idea of the entire syllabus.

The intuition, no symbols yet

Picture a family of nested boxes, each one demanding a more powerful kind of machine to check membership than the box inside it. The innermost box holds languages a machine with a fixed, finite memory can check (Unit 2). The next box out needs a machine with a stack — unbounded, but restricted to last-in-first-out access (Unit 4). Further out still, machines need general read-write memory with no restrictions at all (Unit 5). Every language in an inner box is automatically also a member of every box surrounding it — being easy to recognise never disqualifies a language from the harder categories.

The formal treatment · four grammars, four restrictions

Noam Chomsky's classification sorts languages by placing a restriction on the shape of the production rules (Section 1.2) allowed to generate them. Using A, B ∈ V for non-terminals, a ∈ Σ for a terminal, and α, β, γ for arbitrary strings over V ∪ Σ:

Type 2's rule shape is exactly the grammar shape Section 1.2 already used for G_eq and G_amb — every grammar you wrote there was already, without saying so, context-free. Type 3 tightens this further: only one terminal per rule, always paired with at most one trailing non-terminal. Type 1's requirement |γ| ≥ 1 means a rule can never shrink the string — the surrounding context α, β must survive unchanged, which is where the name comes from.

Here is the one-non-terminal, right-linear grammar that proves L_even is Type 3 — note every rule is exactly the shape A→aB or A→a the table demands:

Every rule matches Type 3's shape exactly, so this alone certifies L_even is regular — no separate machine needed to make the claim, though Unit 2 will hand you the matching finite automaton directly from this grammar's two states.

Worked example · four languages, four tiers

Where each language actually sits

Practice · 1.3

Almost every "prove this language is not regular" argument in Unit 2, and every "prove this language is not context-free" argument in Unit 3, is the same one idea wearing different clothes: if you don't have enough memory, something has to repeat, and that repeat can be exploited. The counting fact behind "something has to repeat" is the pigeonhole principle, and it's worth having cold before it shows up disguised as a five-line lemma with quantifiers.

The intuition, no symbols yet

If you have more letters than mailboxes and every letter must go in some mailbox, at least one mailbox ends up with more than one letter. That's the entire idea. It sounds too simple to be useful — it becomes useful the moment "mailboxes" means "the finite number of states a machine can be in," and "letters" means "the positions along an impossibly long input string."

The formal treatment

Pigeonhole principle. If n+1 objects are distributed among n boxes, at least one box receives 2 or more objects. More generally, if kn+1 objects are distributed among n boxes, some box receives at least k+1. Nothing here says which box, or how many extra — only that a collision is unavoidable once the counts cross that threshold.

Adjacency matrix. For a directed graph G = (V, E), the adjacency matrix M is a |V|×|V| table of 0s and 1s where M[i][j] = 1 exactly when there is an edge from node i to node j. Row i is "edges leaving i"; column j is "edges arriving at j." This convention (row = from, column = to) is a choice, not a law of nature — state it explicitly whenever you draw one, since some textbooks flip it.

Closure properties & the pumping lemma — named now, proved later

A class of languages C is closed under an operation if applying that operation to member(s) of C always produces another member of C. As a trivial but genuine example: the class of finite languages is closed under union — take any two finite languages, their union just has (at most) the combined number of strings, still a finite count. Unit 2 asks the much sharper question "is the class of regular languages closed under union, intersection, complement, concatenation, star?" (spoiler: yes to all five, and each proof teaches a different construction), and Unit 3 asks the same question for context-free languages (spoiler: closure holds for some of these operations and breaks for others).

The pumping lemma, in one sentence with no quantifiers yet: any sufficiently long string in a regular (or context-free) language must contain a short piece that can be repeated, or removed, arbitrarily, while the result stays in the language. "Sufficiently long" and "short piece" get exact meanings in Units 2 and 3; what matters now is why this is true at all — and that's just pigeonhole again. A machine with a fixed number of states, forced to process a string much longer than its state count, must revisit some state twice (pigeonhole: more input positions than states). Between those two visits sits a loop the machine is willing to go around any number of times — including zero — without changing its final verdict. That loop is exactly the "piece that can be pumped."

Practice · 1.4