Discrete Mathematics

278

DISCRETE

MATHEMATIC>7.--------------------------

where, 0 denotes the empty set. This may seem a bit strange, but there is good mathematical justification

for it, which will become apparent shortly.

If

Lis

nonempty, then

1:*

is

an

infinite set

of

finite-length strings.

Be

careful not to confuse strings and

sets. Here are some differences between strings and sets:

•

{a,b}={b,a}butab:t-ba

• {a, a,

b}

={a,

b}

but aab :t-ab

Note also that

0,

{ E

},

and E are three different things. The first is a set with no elements; the second

is a set with one element, namely

E ; and the last is a string, not a set.

9.2.2

Operations

on

Strings

The operation ...