Compilers: Principles and Practice by Pearson

412 Appendix A

Inductive Definition of Σ*

1. Base Clause: ε is in Σ*.

2. Inductive Clause: If x is in Σ* and b ∈ Σ, then xb ∈ Σ*.

3. Extremal Clause: Σ* includes only those strings which can be constructed by a finite

number of applications of (1) and (2).

A language over Σ is a subset of Σ*.

For example, let Σ = {a, b}.

Language L = {a

n

b

n

| n ≥ 0} = λ, ab, aabb, aaabbb, …

A.2.5 Binary Operation on Languages

Let X and Y be languages over Σ. The concatenation of X and Y, denoted by XY, is defined as

XY = {xy | x ∈ X and y ∈ Y}.

For example,

X = {a, ab, bb, baa}, Y = {0, 11} and XY = {a0, a11, ab0, ab11, bb0, bb11, baa0, baa11}

Note that XY and