Compilers: Principles and Practice

A.2 Formal Language Theory Review

A.2.1 Strings

Let ∑ be a finite, non-empty set of symbols, called an alphabet.

A string (or word) over ∑ is a finite sequence of symbols put side-by-side.

For example, abacc is a string over {a, b, c}.

The length of string s over ∑, denoted by |s|, is the total number of occurrences of symbols in s.

For example, |abacc| = 5.

A string of length 0 is called the empty string or null string, denoted by ε or λ.

A.2.2 Binary Operation on Strings

Let x = a₁ a₂ … a_m and y = b₁ b₂ … b_n be strings over ∑, of lengths m and n respectively. The concatenation of x and y, denoted by xy, or xoy is the string a₁ a₂ … a_m b₁ b₂ …b_n .

A.2.3 Relationships Between Strings

A string x is called a prefix of a string z iff ∃y, [z =