Compilers: Principles and Practice by Pearson

Formal Languages and Automata 411

A.2.3 Relationships Between Strings

A string x is called a prefix of a string z iff ∃ y, [z = xy]. A string x is called a suffix of a string z iff

∃ y, [z = yx]. A string x is called a substring of a string z iff ∃ u ∃ v [z = uxv].

x is a proper prefix of z iff x is a prefix of z and x ≠ z. x is a proper suffix of z iff x is a suffix of z

and x ≠ z. x is a proper substring of z iff x is a substring of z and x ≠ z.

Σ* denotes the set of all strings over Σ.

Theorem A.2.1 Let Σ be an alphabet. (Σ*, , ε) forms a monoid, where  is concatenation and ε

is the empty string.

This theorem means that strings as defined ...