2.1 Alphabet, Strings, Kleene Closure, and Languages

Lexical analysis begins with a surprisingly small set of mathematical objects: symbols, strings, and sets of strings. A compiler sees source code as a finite sequence of characters. Before it can talk about identifiers, numbers, keywords, operators, comments, or whitespace, it needs a precise way to say which sequences of characters are valid. Formal language theory gives us that vocabulary.

An alphabet is a non-empty finite set of symbols. It is usually written as Σ. The symbols do not have to be English letters. For a binary scanner, Σ = {0, 1}. For a tiny expression language, the alphabet might include letters, digits, +, *, (, ), spaces, and newline. For a lexer implementation, the alphabet is often the set of character codes the input stream can contain: ASCII, Unicode scalar values, bytes, or a reduced character class alphabet such as letter, digit, space, and other.

A string over an alphabet is a finite sequence of symbols from that alphabet. 0011 is a string over {0, 1}. count42 is a string over an alphabet that contains letters and digits. The empty string is written as ε; it contains no symbols and has length 0. This matters in compilers because many patterns allow optional pieces. A sign in a number literal may be present or absent. A parameter list may contain zero parameters. A comment body may contain zero characters.

Strings as Algebraic Objects

Strings have operations, and compiler algorithms depend on them being precise:

• |w| is the length of string w.
• A prefix of w is a string obtained by removing zero or more symbols from the end.
• A suffix of w is a string obtained by removing zero or more symbols from the beginning.
• A substring of w is a contiguous slice inside w.
• Concatenation combines two strings: if x = ab and y = cd, then xy = abcd.
• Exponentiation repeats a string: $x^3 = xxx$, and $x^0 = ε$.
• Reversal flips order: if w = abc, then $w^R = cba$.

The empty string behaves like an identity for concatenation: εw = wε = w. That small fact shows up everywhere. If a grammar rule has an optional part, it often means that part can derive ε. If an automaton has an epsilon transition, it can change state without consuming input. If a regular expression contains a?, it means a | ε.

Fixed-Length Layers and Kleene Closure

$Σ^k$ is the set of all strings of length k over alphabet Σ. If Σ = {a, b}, then:

• $Σ^0 = {ε}$
• $Σ^1 = {a, b}$
• $Σ^2 = {aa, ab, ba, bb}$
• $Σ^3 = {aaa, aab, aba, abb, baa, bab, bba, bbb}$

In general, if |Σ| = n, then $|Σ^k| = n^k$. This is one reason exhaustive testing explodes so quickly. With 80 possible input characters, all strings of length 5 already form $80^5 = 3,276,800,000$ candidates. A lexer cannot be validated by trying every possible string; it needs specifications, generators, carefully chosen examples, and property tests.

The Kleene closure of Σ is $Σ^*$, the set of all finite strings over Σ:

The positive closure is $Σ^+$, which excludes the empty string:

For any non-empty finite alphabet, $Σ^*$ is infinite, but every individual string in $Σ^*$ is finite. This distinction is important. A compiler reads finite source files, but a language definition describes an infinite set of possible files.

Languages as Sets of Strings

A language over Σ is a set of strings from $Σ^*$. That is all the word "language" means in this part of theory. It may be a programming language, a token language, or a tiny mathematical language such as "all binary strings with exactly one 1."

Examples over Σ = {0, 1}:

L1 = { ε, 0, 00, 000, ... }
L2 = { w | w contains at least one 1 }
L3 = { w | |w| is even }
L4 = { w | w contains substring 001 }

Some languages are finite, such as {if, else, while, return}. Some are infinite, such as the set of all identifiers. In a compiler, token specifications are often languages:

• IF = {if}
• INT = {0, 1, 2, 3, ...}
• IDENT = strings that begin with a letter or underscore, followed by letters, digits, or underscores
• WS = non-empty strings of spaces, tabs, carriage returns, or newlines

The lexer receives one long source string and repeatedly chooses a prefix that belongs to one of these token languages. The parser later receives a token string, not a character string, and checks membership in a higher-level syntactic language.

Why This Matters for Lexers

Consider the source fragment:

if count42 == 0

At the character level, this is one string. At the token level, the lexer should produce something like:

IF IDENT(count42) EQEQ INT(0)

That transformation is a sequence of language membership decisions. Does the prefix if belong to the keyword language? Yes. Does count42 belong to the identifier language? Yes. Does == belong to the equality-operator language? Yes. Should = be accepted before the scanner sees the second =? Usually no, because lexer generators normally use longest match. We will return to longest match later in this chapter.

The mathematical vocabulary is not decoration. It lets us state scanner behavior without relying on informal examples. A token is not "whatever looks right." It is a string in a specified language, selected by deterministic rules when several languages match the same prefix.

Formal Notation Pays for Precision

If Σ = {a, b}, then $Σ^*$ contains ε, a, b, aa, ab, and every other finite string over that alphabet. $Σ^+$ is the same set without ε. Concatenation is ordered: {a, ab}{b, aa} = {ab, aaa, abb, abaa}. The empty language ∅ contains no strings at all, whereas {ε} contains one string of length zero; confusing these two breaks proofs and automaton constructions.

When defining a language, state both membership and boundary cases. For “binary strings with an even number of 1s,” test ε, 0, 1, 11, and 101. For “identifiers,” distinguish the character alphabet from the token language: the alphabet might be ASCII letters, digits, and underscore, while the language imposes positional rules. This habit maps directly to lexer tests.

Proof Habits

• To prove equality of languages, prove both inclusions. Examples are evidence, not a proof.

• Write one witness for each rejected boundary case; it often exposes an accidental use of + where * was intended.

• Keep “string”, “language”, and “alphabet” distinct. A string is an element; a language is a set of strings; an alphabet supplies the symbols.