Why start with three tiny words
In the previous guide we saw the one big idea of this whole subject: the theory of computation turns every computational problem into a question about strings of symbols. That move only pays off if we are razor-sharp about what a string actually is. So this guide does something that feels almost too small to matter — it carefully defines three nouns: an alphabet, a symbol, and a string. They are the bricks; everything heavier you will build later (machines, grammars, the whole tower of language classes) is just clever ways of stacking these bricks.
Here is the honest reason for the fuss. Almost every confusing moment a beginner has later — Is epsilon a symbol or a string? Is the empty language the same as the empty string? Why does a^n b^n break a finite-memory machine? — traces back to a fuzzy grip on these three words. Spend ten careful minutes now, and you buy yourself months of clarity. The payoff is real, even if the definitions look obvious.
The alphabet Sigma and its symbols
An alphabet is simply the set of building blocks you are allowed to use — think of the tiles in a Scrabble box. Before you can talk about words, you first agree on which tiles exist. Formally an alphabet is a finite, non-empty set, and by long tradition we name it with the Greek capital letter Σ (Sigma, written as a capital E lying on its side). Two everyday examples: the binary alphabet Σ = {0, 1}, and a tiny letter alphabet Σ = {a, b}.
Both requirements earn their keep. Finite means only finitely many distinct tiles exist; you cannot have infinitely many different letters. Non-empty means there is at least one tile — with no tiles you could never write anything at all. The members of Σ are called symbols (or letters), and the theory treats each one as an indivisible atom: it never peeks inside a symbol. Whether 'a' is printed in one font or another, whether '0' means zero or off, is irrelevant. All that matters is that distinct symbols are distinguishable from one another.
Strings: beads on a wire
A string (also called a word) over Σ is a finite, ordered sequence of symbols drawn from Σ — picture beads threaded on a wire in a definite order. If Σ = {a, b}, then aab is a string: an a, then another a, then a b. Order matters, so aab and aba are different strings even though they use the very same symbols. Repetition is fine: aaa is a perfectly good string. We usually name strings with letters like w, x, y. And crucially, a string is finite — it has a last bead, even if it is very long.
The length of a string is just how many beads it has, counted from first to last, repeats included. We write it with vertical bars: |ab| = 2, |aaa| = 3, |b| = 1. There is also one very special string with no beads at all, the empty string, written ε (epsilon, a small curly Greek 'e'). It has length zero: |ε| = 0. It feels like nothing, but it is a genuine, well-defined object — exactly the way the number 0 is a real number even though it counts nothing. We always need a name for the result of writing down no symbols.
Gluing strings: concatenation and powers
How do we build longer strings from shorter ones? With concatenation — gluing two strings end to end, exactly like snapping two LEGO trains into one. The concatenation of x and y is written xy: first all of x in order, then all of y in order. So if x = ab and y = ba, then xy = abba. Two clean rules always hold. Lengths add: |xy| = |x| + |y|. And the empty string changes nothing: εw = wε = w, the way adding 0 leaves a number unchanged.
Concatenation is associative — (xy)z = x(yz), so we freely write xyz without worrying about grouping — but it is NOT commutative: xy and yx are usually different (abba is not baab). Repeating concatenation gives us powers of a string: w^k means w glued to itself k times. So if w = ab, then w^2 = abab and w^3 = ababab, while w^0 = ε (zero copies is the empty string, the natural starting point). Powers let us name whole infinite families compactly — the famous pattern a^n b^n means n copies of a followed by n copies of b.
That tiny pattern a^n b^n is worth flagging because it foreshadows the whole drama ahead. To check that a string really has the form a^n b^n, you must remember how many a's you saw in order to demand exactly that many b's — and n can be arbitrarily large. A machine with only fixed, finite memory cannot keep that count, which is exactly why a^n b^n sits just out of reach of the simplest machines you will meet (finite automata) and needs a slightly stronger one. You will trace that very example by hand a few rungs from now; for today, just notice that a one-line pattern of powers can already separate the weak machines from the strong.
Sigma-star: the universe of all strings
Now collect everything you could ever write with one alphabet into a single set. That set is Sigma-star, written Σ* (the asterisk is the Kleene star — a single star, never a doubled one). Σ* is the set of all finite strings over Σ, including ε. You can picture it built up in layers by length: length 0 gives just ε; length 1 gives the symbols of Σ; length 2 gives all pairs; and so on forever. Σ* is the giant bag of every possible input — the universe from which, in the next guide, every language gets carved out as a subset.
Sigma = {a, b}. Layer Sigma* by length:
length 0 : epsilon
length 1 : a b
length 2 : aa ab ba bb
length 3 : aaa aab aba abb baa bab bba bbb
... ... and on forever ...
Sigma* = every row, unioned together (includes epsilon)
Sigma+ = Sigma* with the epsilon row removed (non-empty strings only)Here is a fact that looks small but secretly runs deep: every single string in Σ* is finite, yet the set Σ* itself is infinite. There is no contradiction — each row in the picture is finite, but there are infinitely many rows. (If you ever want all non-empty strings only, that set has its own name, Σ-plus, written Σ+ — it is just Σ* with the ε row removed.) And Σ* is the gentlest kind of infinite: you could in principle list its members one after another — first by length, then alphabetically within each length — so that every string eventually shows up. That orderly listability is called being countable, and it is the quiet hinge on which one of the deepest results of the subject turns: because there are only countably many possible programs but uncountably many possible languages, some problems must have no program at all.
Where these bricks are headed
You now have the full vocabulary of the ground floor: an alphabet of symbols, strings built by concatenation and powers, the empty string ε, and the universe Σ* of all finite strings. The very next guide makes the leap that this whole subject is built on — it picks out interesting subsets of Σ* and calls each one a language. Then the rest of the ladder is one long question: which subsets can which machine recognize?
It helps to keep the destination in view. Sorted from simplest to most powerful, the machines and their string-sets form the Chomsky hierarchy: the finite automaton recognizes the regular languages; add a stack and the pushdown automaton reaches the context-free languages (this is where a^n b^n finally becomes recognizable); and the all-powerful Turing machine reaches the recursively-enumerable languages and defines what 'an algorithm' even means. Every one of those grand ideas is, at bottom, a statement about subsets of the Σ* you just built. Get these bricks right, and the cathedral above them will make sense.