Problem Solving in Automata, Languages, and Complexity

14 REGULAR LANGUAGES

= {w 1 (3u)[uw E Ll]} u {w 1 (3u)[uw E L21) = L1’ u L2’.

(b) (L1L2)’ = {w 1 (~U)[UW E ~51~521)

= {w ] either w E L2’ or w = zy for some z E Ll’, y E L2)

= L2’ u LI’L:!.

(c) (Ll*)’ = ( E Ll”)’ = E(Ll”)’

i=o i=o

bY Part (4

= {E} u (G(L1’ u LI’LI u * l l u L1’Lf’))

i=l

bY Part (b)

ccl

II Ll’ l

(u ({E} u L1 u ’ l l u Lli-l ,>

= L&*.

i=l

Therefore, (L1 U Lz)‘, (L1 Lz)‘, and (Ll*)’ are regular sets. This completes

the induction step. cl

Remark. What is wrong with the following proof for part (c) of Example 1.21?

Proof for part (c). From part (a), we know that

(Ll*)’ = ( 6 Ll”)’ = E(L1”)‘.

i=o i=o

From part (b), we know that each (Li)’ is regular for i > 0. There-

fore, (L;)’ is the union of regular languages (Li)‘, for z7= 0, 1,... ,

and so it is regular.

In the last step of the above “proof,” the rule of

[A, B are regular 3 A U B is regular]

has been illegally extended to

Ao, A1, A2, l. l are regular 3 6 A; ’ is regular.

i=o^1

This generalized rule is false. To see this, we note that every language L C C*

can be written as the union of an infinite number of regular languages. ‘Let

the elements in L be ~0, x1, x2,.... Then, L = (20) U {xl} U {x2} U. l l.

Thus, the generalized rule would imply that every language is regular, which

is known to be false (see Section 2.8).

Example 1.22 Show that every regular language has a regular expression in

disjunctive normal form cul+a2+* l -+a,, in which euch ai, for i = 1,2, l.. , n,

does not contain the operator +.