Foundations: Alphabets, Strings & Languages

the empty language versus the language of the empty string

These two things look almost the same on the page and are constantly mixed up, but they are genuinely different, in the same way that an empty box and a box containing a single blank sheet of paper are different. One is an empty collection. The other is a collection with exactly one thing inside it, and that one thing happens to be the empty string.

The empty language, written ∅ or {} , is the language that contains no strings at all. Its size is zero: there is nothing in it, not even ε. Asking is some string w in ∅? always answers no. The language of the empty string, written {ε}, is the language that contains exactly one string, namely the empty string ε. Its size is one. Asking is ε in {ε}? answers yes, while is a in {ε}? answers no. So the distinction is: zero members versus one member.

Why care? The difference changes how these languages behave under operations, and getting it wrong corrupts proofs. Concatenating the empty language with any language L gives ∅ again (∅ . L = ∅), because there is no string to start from, like multiplying by zero. But concatenating {ε} with L just gives L back ({ε} . L = L), because ε is the do-nothing string, like multiplying by one. In short, ∅ behaves like the number 0 and {ε} behaves like the number 1 under concatenation; treating them as the same is exactly the classic beginner trap this entry exists to defuse.

|∅| = 0 (no strings); |{ε}| = 1 (one string, the empty one). Under concatenation: ∅ . {a, b} = ∅, but {ε} . {a, b} = {a, b}.

∅ acts like 0 and {ε} acts like 1 under language concatenation.

∅ has zero strings; {ε} has one string. They are never equal. The most common error is to write {ε} when you mean ∅, or vice versa.

Also called
∅ vs {ε}{} versus {epsilon}空語言與 {ε}