Design and Analysis of Algorithms

628 Design and Analysis of Algorithms

A.6.8 Closure of a Language

Let X be a language over Σ. The closure of X, denoted by X*, is defi ned as follows:

X * =

0i≥

∪

X

i

= X

0

∪ X

1

∪ X

2

∪. . .

The positive closure of X, denoted by X +, is defi ned as follows.

X

+

=

1i≥

∪ X

i

= X

1

∪ X

2

∪. . .

Note that the set of all strings over Σ is equal to the closure of Σ, where Σ is viewed as a set of strings of

length 1 rather than an alphabet. This is the reason we denote the set of all strings over Σ by Σ

*

.

Usually we treat X* as a unary operation to X, called Kleene star.

A.7 PROOF BY INDUCTION

The concept of induction provides not only a method of defi ning infi nite sets, but also powerful techniques

for proving assertions of the form ∀x, P(x), where the universe ...