Alphabet, string, language — formal definitions: Worked examples

The scenario matrix

Before solving anything, let's map the terrain. Every problem about alphabets/strings/languages lands in one of these cells. Think of it as a checklist: if we cover every row, we've covered the topic.

Cell	Case class	The tricky thing it tests	Example
C1	Counting strings of a length	multiplication rule $∣ Σ ∣^{k}$ , and $k = 0$	E1
C2	The three "empties"	telling $ε$ , ${ε}$ , $\emptyset$ apart	E2
C3	Concatenation with $ε$ inside a language	why ${ε} L = L$ but $\emptyset L = \emptyset$	E3
C4	Language star with degenerate inputs	$\emptyset^{}$ , ${ε}^{}$	E4
C5	Length / reversal algebra	$∣ x y ∣$ , $∣ w^{R} ∣$ , $(x y)^{R}$	E5
C6	Counting a whole language up to a bound	summing $∣ Σ ∣^{k}$ , geometric growth	E6
C7	Real-world word problem	modelling something as strings/language	E7
C8	Countability twist (exam favourite)	$Σ^{}$ countable vs $2^{Σ^{}}$ uncountable	E8
C9	Prefix / suffix / substring counting	positions & off-by-one edge cases	E9

Rows C1–C9 are every "cell". The nine examples below hit them one-to-one. Cases like "single-symbol alphabet" and "the empty string as an input" appear inside several examples so degenerate inputs never go untested.

E1 — Counting strings of an exact length (cell C1)

Worked example Statement

Let $Σ = {a, b, c}$ . How many strings have length exactly $4$ ? How many have length exactly $0$ ?

Forecast: guess both numbers before reading on. (Hint: one of them is not zero.)

Step 1 — Name the tool. We use the multiplication rule for length- $k$ strings: $∣ Σ^{k} ∣ = ∣ Σ ∣^{k} .$ Why this step? A string of length $k$ is $k$ independent slots; each slot can be filled with any of the $∣ Σ ∣$ symbols, and choices in different slots don't interfere. Independent choices multiply — that is the multiplication rule (see the slot picture below).

Step 2 — Plug in $k = 4$ . Here $∣ Σ ∣ = 3$ , so $∣ Σ^{4} ∣ = 3^{4} = 81.$ Why this step? Four slots, three choices each: $3 \times 3 \times 3 \times 3$ .

Step 3 — The degenerate length $k = 0$ . A length- $0$ string has no slots to fill, so there is nothing to choose. There is exactly one empty arrangement: the empty string $ε$ . $∣ Σ^{0} ∣ = 3^{0} = 1.$ Why this step? The formula must stay consistent at $k = 0$ , and $3^{0} = 1$ matches "there is exactly one way to write nothing." Not zero — one.

Verify: count length- $4$ another way — list the first slot's 3 choices, each opening 27 completions of the last 3 slots: $3 \times 27 = 81$ . ✔ And $Σ^{0} = {ε}$ has size $1$ . ✔

Naive-answer trap

Saying

∣ Σ^{0} ∣ = 0

because "there are no symbols." There is one string — the blank one — so the count is

1

E2 — The three empties, side by side (cell C2)

Worked example Statement

For $Σ = {0, 1}$ , decide the truth of each: (a) $ε = \emptyset$ , (b) ${ε} = \emptyset$ , (c) $∣{ε}∣ = 1$ , (d) $∣ \emptyset ∣ = 0$ , (e) $ε \in {ε}$ , (f) $ε \in \emptyset$ .

Forecast: how many of the six are true? Guess, then check.

Step 1 — Sort each object onto its floor of the tower. $ε$ is a string (one blank word). ${ε}$ and $\emptyset$ are languages (sets of strings). Why this step? You can only compare things on the same floor. A string is never equal to a set.

Step 2 — Evaluate.

(a) $ε = \emptyset$ : false — a string is not a set.
(b) ${ε} = \emptyset$ : false — one holds a member, the other holds none.
(c) $∣{ε}∣ = 1$ : true — the box contains exactly one word (the blank sheet).
(d) $∣ \emptyset ∣ = 0$ : true — the empty box holds zero words.
(e) $ε \in {ε}$ : true — the blank word is inside that box.
(f) $ε \in \emptyset$ : false — nothing is inside the empty box.

Why this step? Every answer follows from "which floor?" plus "how many members?".

Verify: count of true statements $= 3$ (c, d, e). Box analogy holds: empty box $\neq =$ box-with-a-blank-sheet $\neq =$ the-sheet-itself. ✔

E3 — Concatenation when a language contains $ε$ (cell C3)

Worked example Statement

Let $L_{1} = {0, 01}$ and $L_{2} = {1, ε}$ . Compute $L_{1} L_{2}$ . Then compute ${ε} L_{1}$ and $\emptyset L_{1}$ .

Forecast: which of the three results is the smallest?

Step 1 — Definition of language concatenation. $L_{1} L_{2} = {x y : x \in L_{1}, y \in L_{2}} .$ Why this step? We must pair every $x$ with every $y$ — it is a set of glued products, not a symbol-wise operation.

Step 2 — Form all four products. $0 \cdot 1 = 01, 0 \cdot ε = 0, 01 \cdot 1 = 011, 01 \cdot ε = 01.$ Why this step? Gluing $ε$ onto the end changes nothing ( $x ε = x$ ), which is exactly why $0 ε = 0$ and $01 ε = 01$ .

Step 3 — Collect into a set (drop duplicates). $L_{1} L_{2} = {0, 01, 011} .$ Why this step? $01$ was produced twice ( $0 \cdot 1$ and $01 \cdot ε$ ); a set keeps one copy.

Step 4 — The two degenerate multipliers.

${ε} L_{1}$ : every $x = ε$ glued in front of each $w \in L_{1}$ gives $w$ unchanged, so ${ε} L_{1} = L_{1} = {0, 01}$ .
$\emptyset L_{1}$ : there is no $x$ to pick from $\emptyset$ , so no products form: $\emptyset L_{1} = \emptyset$ . Why this step? ${ε}$ is the concatenation identity; $\emptyset$ is the concatenation "annihilator" (like multiplying by $0$ ).

Verify: $∣ L_{1} L_{2} ∣ = 3$ ; ${ε} L_{1} = {0, 01}$ has size $2$ ; $\emptyset L_{1} = \emptyset$ has size $0$ — the smallest, as forecast. ✔

E4 — Star of degenerate languages (cell C4)

Worked example Statement

Compute $\emptyset^{*}$ and ${ε}^{*}$ . Also compute ${0}^{*}$ (describe the set).

Forecast: is $\emptyset^{*}$ empty?

Step 1 — Definition of star. $L^{*} = ⋃_{k \geq 0} L^{k}, L^{0} = {ε}, L^{k} = L^{k - 1} L .$ Why this step? Star means "concatenate the language with itself zero or more times." The zero case $L^{0} = {ε}$ is always thrown in — that is the crucial edge.

Step 2 — $\emptyset^{*}$ . For $k \geq 1$ , $\emptyset^{k} = \emptyset$ (multiplying by the annihilator). But $L^{0} = {ε}$ is included regardless. So $\emptyset^{*} = {ε} \cup \emptyset \cup \emptyset \cup \dots = {ε} .$ Why this step? Even a language that produces nothing still allows the "do it zero times" option, which yields the empty string.

Step 3 — ${ε}^{*}$ . Every power of ${ε}$ is ${ε}$ : gluing blank words together gives a blank word, so ${ε}^{1} = {ε}$ , ${ε}^{2} = {εε} = {ε}$ , and so on. The union of copies of ${ε}$ is still ${ε}$ : ${ε}^{*} = {ε} .$ Why this step? Repeating "the blank word" any number of times can only ever produce the blank word again, so nothing new can enter the union — the set cannot grow past ${ε}$ .

Step 4 — ${0}^{*}$ . Powers give $ε, 0, 00, 000, \dots$ , i.e. all strings of only $0$ 's: ${0}^{*} = {0^{n} : n \geq 0} = {ε, 0, 00, 000, \dots} .$ Why this step? Repeating the single word $0$ any number of times, including zero.

Verify: both $\emptyset^{*}$ and ${ε}^{*}$ equal ${ε}$ , size $1$ — never $\emptyset$ . ✔ ${0}^{*}$ is infinite. ✔ This links to Regular Languages and Regular Expressions, where the star operator is central.

E5 — Length & reversal algebra (cell C5)

Worked example Statement

Let $x = 011$ , $y = 10$ . Compute $∣ x y ∣$ , verify $(x y)^{R} = y^{R} x^{R}$ , and check $∣ w^{R} ∣ = ∣ w ∣$ for $w = x y$ .

Forecast: guess $(x y)^{R}$ before computing.

Step 1 — Concatenate and use the length rule. $x y = 01110$ , and $∣ x y ∣ = ∣ x ∣ + ∣ y ∣ = 3 + 2 = 5.$ Why this step? Length was built so concatenation lengths add — no re-counting needed.

Step 2 — Reverse the product directly. Reversing $01110$ position-by-position gives $01110$ … careful: read back-to-front: $0, 1, 1, 1, 0 \to 0, 1, 1, 1, 0$ . So $(x y)^{R} = 01110$ . Why this step? $01110$ happens to be a palindrome, a nice sanity target.

Step 3 — Reverse via the rule $y^{R} x^{R}$ . $y^{R} = (10)^{R} = 01$ , $x^{R} = (011)^{R} = 110$ . Glue: $y^{R} x^{R} = 01 \cdot 110 = 01110$ . Why this step? The rule $(x y)^{R} = y^{R} x^{R}$ says reversing swaps order and reverses each piece — the figure shows why the pieces cross over.

Step 4 — Length under reversal. Reversal only re-orders positions; it adds/removes nothing, so $∣ w^{R} ∣ = ∣ w ∣ = 5$ .

Verify: both routes give $01110$ ; $∣ x y ∣ = 5 = ∣(x y)^{R} ∣$ . ✔

E6 — Counting a whole language up to a bound (cell C6)

E7 — Real-world word problem (cell C7)

Worked example Statement

A door lock accepts a PIN of exactly 4 digits, each from ${0, 1, \dots, 9}$ , but rejects any PIN whose four digits are all identical (like $7777$ ). How many PINs does it accept?

Forecast: guess to the nearest thousand.

Step 1 — Model as a language. Alphabet $Σ = {0, \dots, 9}$ , so $∣ Σ ∣ = 10$ . Accepted PINs are strings of length exactly $4$ , i.e. a subset of $Σ^{4}$ minus the "all-same" ones. Why this step? A lock is a bouncer for a language; "what it accepts" is a set of strings.

Step 2 — Count all length-4 strings. $∣ Σ^{4} ∣ = 1 0^{4} = 10000.$ Why this step? Multiplication rule: 4 slots, 10 choices each.

Step 3 — Subtract the forbidden ones. All-identical PINs are $0000, 1111, \dots, 9999$ : exactly $10$ of them (one per digit). $10000 - 10 = 9990.$ Why this step? The accepted language is $Σ^{4} ∖ (all-same)$ ; sizes subtract for a subset removal.

Verify: $1 0^{4} = 10000$ , minus $10$ gives $9990$ accepted PINs — a shade under ten thousand. ✔ Units: pure count of strings, dimensionless. ✔

E8 — The countability twist (cell C8)

Worked example Statement

True or false: (a) $Σ^{*}$ for $Σ = {0, 1}$ is countably infinite. (b) The set of all languages over $Σ$ is countable.

Forecast: guess before reading — most people get (b) wrong.

Step 1 — List $Σ^{*}$ in shortlex order. $ε, 0, 1, 00, 01, 10, 11, 000, \dots$ Why this step? A set is countable exactly when you can put it in one infinite list with no gaps. As the definition above shows, shortlex places every finite string at a definite position (its length-block is finite), so nothing is missed. Hence (a) is true.

Step 2 — Count the set of all languages. A language is a subset of $Σ^{*}$ , so the set of all languages is the power set $2^{Σ^{*}}$ . By Cantor's diagonal argument the power set of any countably infinite set is uncountable. Why this step? You cannot list all subsets: any proposed list misses the "diagonal" subset. So (b) is false — see Countability and Diophantine Diagonalization.

Step 3 — Why this matters. Programs (which recognise languages) are finite strings, so there are only countably many of them. But there are uncountably many languages. So most languages have no program — the seed of undecidability, later formalised with the Pumping Lemma and machine models Finite Automata (DFA NFA) / Context-Free Grammars.

Verify: (a) true — shortlex is a gap-free enumeration; (b) false — $2^{Σ^{*}}$ is uncountable. Number of true statements among {(a),(b)} $= 1$ . ✔

E9 — Prefix / suffix / substring counting (cell C9)

Worked example Statement

Let $w = ab c a$ ( $∣ w ∣ = 4$ ). Count: (a) prefixes of $w$ (including $ε$ and $w$ ), (b) suffixes, (c) distinct non-empty substrings.

Forecast: are there more substrings than prefixes?

Step 1 — Prefixes. A prefix ends after position $i$ for $i = 0, 1, 2, 3, 4$ : $ε, a, ab, ab c, ab c a$ . That is $∣ w ∣ + 1 = 5$ . Why this step? Each cut point (including "before everything" $= ε$ and "after everything" $= w$ ) gives one prefix; there are $∣ w ∣ + 1$ cut points.

Step 2 — Suffixes. By symmetry, cut from the other side: $ε, a, c a, b c a, ab c a$ — also $∣ w ∣ + 1 = 5$ . Why this step? Same off-by-one logic mirrored; $ε$ and $w$ are both prefix and suffix.

Step 3 — Distinct substrings. A substring picks a start $i$ and length $ℓ \geq 1$ ; count contiguous non-empty pieces, then dedupe. List by length: $len 1: a, b, c (note two a ’s collapse); len 2: ab, b c, c a;$ $len 3: ab c, b c a; len 4: ab c a .$ Add these distinct non-empty substrings: $3 + 3 + 2 + 1 = 9$ . Why this step? Total non-empty contiguous pieces $= \frac{4 \cdot 5}{2} = 10$ , but the letter $a$ repeats (positions 1 and 4), collapsing one duplicate → $9$ .

Verify: prefixes $= 5$ , suffixes $= 5$ , distinct non-empty substrings $= 9$ . Sanity: $9 < 10$ because of the one duplicate $a$ . ✔ Yes, more substrings than prefixes. ✔

Did we cover every cell?

We promised an exhaustive stress test of C1–C9. Here is the final tally:

Cell	Covered by	Key takeaway
C1	E1	$∣ Σ^{k} ∣ = ∣ Σ ∣^{k}$ , and $k = 0$ gives 1
C2	E2	$ε$ / ${ε}$ / $\emptyset$ live on different floors
C3	E3	${ε} L = L$ , $\emptyset L = \emptyset$
C4	E4	$\emptyset^{} = {ε}^{} = {ε}$ , never $\emptyset$
C5	E5	lengths add; reversal swaps order & pieces
C6	E6	disjoint sizes add: $1 + 2 + 4 + 8 = 15$
C7	E7	model as a language, then subtract: $9990$
C8	E8	$Σ^{}$ countable, $2^{Σ^{}}$ uncountable
C9	E9	$∣ w ∣ + 1$ prefixes/suffixes; dedupe substrings → 9

Every row of the scenario matrix now has a fully worked example, including the degenerate inputs ( $k = 0$ , $ε$ , $\emptyset$ ) threaded through several of them. No case class is left untested.

Recall Quick self-test (try before opening)

Q1 — $∣ Σ^{0} ∣$ for any alphabet? ::: $1$ (the single empty string $ε$ ). Q2 — Value of $\emptyset^{*}$ ? ::: ${ε}$ , because $L^{0} = {ε}$ is always included. Q3 — Is the set of all languages over ${0, 1}$ countable? ::: No — it is $2^{Σ^{*}}$ , uncountable. Q4 — Accepted PINs in E7? ::: $9990$ . Q5 — What does shortlex order mean? ::: Sort by length first, then lexicographically within each length.