Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 305

Operations on Languages

SupposeLandMare languages over an alphabetA. Then the “concatenation” ofLandM, denoted byLM,
is the language defined as follows:
LM={uv|u∈L, v∈V}

That is,LMdenotes the set of all words which come from the concatenation of a word fromLwith a word
fromM. For example, suppose

L 1 ={a, b^2 },L 2 ={a^2 ,ab,b^3 },L 3 ={a^2 ,a^4 ,a^6 ,...}

Then:
L 1 L 1 ={a^2 ,ab^2 ,b^2 a, b^4 },L 1 L 2 ={a^3 ,a^2 b, ab^3 ,b^2 a^2 ,b^2 ab, b^5 }
L 1 L 3 ={a^3 ,a^5 ,a^7 ,..., b^2 a^2 ,b^2 a^4 ,b^2 a^6 ,...}

Clearly, the concatenation of languages is associative since the concatenation of words is associative.
Powersof a languageLare defined as follows:

L^0 ={l},L^1 =L, L^2 =LL, Lm+^1 =LmL for m> 1.

The unary operationL* (read “Lstar”) of a languageL, called theKleeneclosure ofLbecause Kleene proved
Theorem 12.2, is defined as the infinite union:

L∗=L^0 ∪L^1 ∪L^2 ∪···=

⋃∞

k= 0

Lk

The definition ofL agrees with the notationA which consists of all words overA. Some texts defineL+to be
the union ofL^1 ,L^2 ,...that is,L+is the same asL* but without the empty wordλ.

12.4Regular Expressions, Regular Languages

LetAbe a (nonempty) alphabet. This section defines a regular expressionroverAand a languageL(r)over
Aassociated with the regular expressionr. The expressionrand its corresponding languageL(r)are defined
inductively as follows.

Definition 12.1: Each of the following is a regular expression over an alphabetA.

(1) The symbol “l” (empty word) and the pair “( )” (empty expression) are regular expressions.

(2) Each letterainAis a regular expression.

(3) Ifris a regular expression, then(r∗)is a regular expression.

(4) Ifr 1 andr 2 are regular expressions, then(r 1 ∨r 2 )is a regular expression.

(5) Ifr 1 andr 2 are regular expressions, then (r 1 r 2 )is a regular expression.

All regular expressions are formed in this way.
Observe that a regular expressionris a special kind of a word (string) which uses the letters ofAand the
five symbols:
()∗∨l

We emphasize that no other symbols are used for regular expressions.

Definition 12.2: The languageL(r)overAdefined by a regular expressionroverAis as follows:

(1)L(l)={l}andL(( ))=
, the empty set.

(2)L(a)={a}, whereais a letter inA.