Alphabet, string, language — formal definitions: Visual walkthrough

We are re-deriving the central result of the parent topic. Everything you meet here — strings, $Σ^{*}$ , canonical order — becomes the raw material for Regular Languages, Finite Automata (DFA NFA), Regular Expressions, and the counting arguments in Countability and Diophantine Diagonalization.

Step 1 — The alphabet is a box of stamps

WHAT. We start with the most concrete object possible: a small finite box of distinct rubber stamps. Call the whole box $Σ$ (the Greek letter "Sigma", just a name for "the box"). Each stamp inside is a symbol. For the whole walkthrough we use the binary box $Σ = {0, 1}$ — exactly two stamps.

WHY this object. Every rule of the theory has to be checkable by a machine with finite memory. A machine can only "know" its stamps if there are finitely many of them — so $Σ$ is finite. And you cannot write a single word with an empty box, so $Σ$ must have at least one stamp (non-empty). Two stamps is the smallest interesting case.

PICTURE. The two stamps sit in a warm tray. $∣Σ∣$ means "how many stamps are in the box" — here $∣Σ∣ = 2$ .

Figure — Alphabet, string, language — formal definitions

Step 2 — A string is a row of stamp-marks

WHAT. Take a strip of paper with numbered slots and press one stamp into each slot, left to right. The finished row of marks is a string. If the strip has no slots at all — a blank strip — that is the empty string, written $ε$ ("epsilon").

WHY a row (ordered). Order carries meaning: 01 is a different word from 10, just as "on" differs from "no". So a string is not a set of symbols, it is an ordered sequence — position matters.

PICTURE. Slot 1, slot 2, slot 3 filled with stamps gives the string 010. The blank strip beside it is $ε$ : real paper, zero marks.

Step 3 — Group the strings by their length $k$

WHAT. Instead of throwing every possible string into one heap, we sort them into shelves. Shelf $k$ holds exactly the strings whose length is $k$ . We name that shelf $Σ^{k}$ .

WHY sort by length. Length is the one honest measuring stick we already built (Step 2). A machine reads a string left to right, so "how long is it" is the most natural way to organise the infinite pile — and, as the next step shows, it makes the counting trivial.

PICTURE. Three shelves: $Σ^{0}$ holds the single blank strip; $Σ^{1}$ holds 0 and 1; $Σ^{2}$ holds the four two-slot strings.

Step 4 — Why the count on shelf $k$ multiplies: the choice tree

WHAT. Now we count how many strings sit on shelf $Σ^{k}$ . Build the string slot by slot. Slot 1 can be any of the $∣Σ∣$ stamps. For each of those choices, slot 2 can again be any of the $∣Σ∣$ stamps. And so on for $k$ slots.

WHY multiply, not add. The choices are independent: picking 0 for slot 1 does not remove any option from slot 2. Independent stages combine by the multiplication rule — the number of full paths is the product of the branch-counts at each stage. (If choices shared options we would need something subtler, but here they do not.)

PICTURE. A tree that fans out. The root splits into $∣Σ∣ = 2$ branches (slot 1). Each of those splits into $2$ again (slot 2). The leaves at depth $k$ are exactly the strings of $Σ^{k}$ — count them.

Step 5 — The degenerate shelves (never skip these)

WHAT. Two shelves look strange, so we check them directly against the formula.

Shelf $0$ : $∣ Σ^{0} ∣ = ∣Σ ∣^{0} = 1$ . That "1" is the empty string $ε$ . The choice tree agrees: with zero slots there is one path — the empty path, "do nothing," which lands you at $ε$ .
A one-stamp box $Σ = {a}$ : then $∣ Σ^{k} ∣ = 1^{k} = 1$ for every $k$ . Only one string of each length: $ε, a, aa, aaa, \dots$ . The tree never branches — one straight trunk.

WHY this matters. A formula you trust only in the "nice" middle is a trap. Confirming $k = 0$ and $∣Σ∣ = 1$ shows $∣Σ ∣^{k}$ holds at the very edges too.

PICTURE. Left: the empty path landing on the blank strip (count = 1). Right: the non-branching trunk of a single-stamp alphabet.

Step 6 — Stack the shelves: $Σ^{*}$ and $Σ^{+}$

WHAT. Now pour every shelf together. The union of all shelves $k \geq 0$ is $Σ^{*}$ ("Sigma star") — every finite string, blank one included. If you drop only shelf $0$ , you get $Σ^{+}$ ("Sigma plus") — every string of length at least $1$ .

WHY two names. Some constructions want the "do-nothing" $ε$ available ( $Σ^{*}$ ); others forbid it ( $Σ^{+}$ ). Keeping both names avoids constant fine print. Their only difference is the single blank strip.

PICTURE. All shelves stacked into one tall tower labelled $Σ^{*}$ ; a bracket marks off shelf $0$ (just $ε$ ) whose removal leaves $Σ^{+}$ .

Step 7 — Why the tower is infinite but still listable (countable)

WHAT. The tower $Σ^{*}$ never stops growing: each shelf $Σ^{k}$ is non-empty (it has $∣Σ ∣^{k} \geq 1$ strings), and there is always a taller shelf $k + 1$ . So $Σ^{*}$ is infinite. Yet we can put every string into one single numbered list with no string left out. The recipe: read shelf $0$ , then shelf $1$ , then shelf $2$ , …, and within each shelf sort alphabetically. This ordering is called canonical (shortlex) order.

WHY this is the whole point. "Countable" means "can be matched one-to-one with $1, 2, 3, \dots$ " — i.e. put in a list where every item eventually appears. Because each shelf is finite ( $∣Σ ∣^{k}$ items, Step 4), you finish reading it in finite time and move on. Nothing gets stranded infinitely far down. This is exactly why $Σ^{*}$ is countable even though it is infinite — the finiteness of each shelf does the work.

WHY tool: length-first ordering (not plain dictionary order). Pure dictionary order fails: it would try to place all strings starting with 0 before ever reaching 1, and there are infinitely many of those, so 1 would never get a number. Sorting by length first caps how long you linger on any prefix, so every string gets a finite position.

PICTURE. The shelves emptied one at a time into a single ruler-line: position 1 = $ε$ , position 2 = 0, 3 = 1, 4 = 00, 5 = 01, 6 = 10, 7 = 11, 8 = 000, …

The one-picture summary

Below: the whole chain on one page. Box of $∣Σ∣$ stamps → row of slots (a string) → shelves $Σ^{k}$ counted by the choice tree as $∣Σ ∣^{k}$ → shelves stacked into $Σ^{*}$ → poured into one canonical list, proving infinite yet countable.

Recall Feynman retelling (try to say it yourself first)

Start with a little box holding a few rubber stamps — that box is $Σ$ , and $∣Σ∣$ is just how many stamps are in it. A string is a strip of paper where you press one stamp per slot; the blank strip counts too, and we call it $ε$ . Now sort every possible strip by how many slots it has: shelf $Σ^{k}$ holds the ones with exactly $k$ slots. To count a shelf, fill it slot by slot — each slot is a fresh, independent pick from all $∣Σ∣$ stamps, so the counts multiply: $∣Σ ∣^{k}$ strips on shelf $k$ . Even shelf $0$ has one strip (the blank one), because "do nothing" is one path. Stack all the shelves and you get $Σ^{*}$ , the tower of every finite strip — it never ends, because there's always a taller shelf. But it's tame infinity: each shelf is finite, so you can read them one after another and hand every single strip a ticket number ( $ε$ = 1, 0 = 2, 1 = 3, 00 = 4, …). That numbered line is why $Σ^{*}$ is infinite and countable — and that single fact is the seed the whole Theory of Computation grows from.

Recall

Why does $∣ Σ^{k} ∣ = ∣Σ ∣^{k}$ multiply rather than add? ::: The $k$ slots are filled by independent choices, so the multiplication rule chains them: $∣Σ∣ \times \dots \times ∣Σ∣$ ( $k$ times). Why is $Σ^{*}$ countable despite being infinite? ::: Each shelf $Σ^{k}$ is finite, so shortlex order (length first, then alphabetical) gives every string a finite position. Why sort by length before alphabetical order? ::: Plain dictionary order gets stuck on infinitely many strings sharing a prefix; length-first caps each shelf so every string is reached. What is $∣ Σ^{0} ∣$ and which string sits there? ::: $∣ Σ^{0} ∣ = ∣Σ ∣^{0} = 1$ ; the single string is $ε$ , the empty path in the choice tree.