Problem Solving in Automata, Languages, and Complexity

2.6 Closure Properties of Regular Languages 61

Proof. Let r be a regular expression for language L and, for each a E C, ra be
the regular expression for language f(a). R e pl ace each occurrence of symbol
ainrbyf(a). Th en, we obtain a new regular expression T’.
Now, we observe the following simple facts:
(a) For any twosets A G C* and B C c”, we have f(AUB) = f(A)Uf(B),
f(AB) = f(A)f(B), and f(A’) = f(A)*
(b) For any two regular expressions Y and s, (r + s)’ = r’ + s’, (rs)’ = r’ l s’ ,
and (r)’ = (r’)*.
Using these facts, we can prove by a simple induction that L(r’) = f(L)
(cf. Examples 1.21 and 1.22). Thus, f(L) is regular. cl

Define the quotient of two languages L1 and L2 as

L1/L2 = {z I (3 E J52)[23/ E Ll]}.

For instance, if L1 = {w E {O,l}* 1 w h as an even number of occurrences of

symbol 0}, L2 = (0) and L3 = {O,OO}, then Ll/L2 = {w E {O,l}* 1 w has an

odd number of occurrences of symbol 0)) and Ll/ Ls = { 0, l}*.

Example 2.36 Show that for any lunguuge L2, if L1 is regular then Ll/L2

is also regular.

ProoJ Suppose that L1 is accepted by a DFA A4 = (Q, C, S, ~0, F). For

any string x E LJL2, there exists a string y E L2 such that S(qo, zy) =

qqqo, X),Y) E Fe I n other words, suppose that we run A4 on x: and reach

a state 4; = S(qo,x). If th ere exists y E L2 such that S(q+, y) E F, then II:

should be accepted; that is, qi should be considered as a final state for L&J.

Therefore, we can simply define

F’ = (a E Q 1 (3~ E ~52) [d(q, Y) E FI),

and let W = (Q,C,&qo,F’). It is clear that ikl’ accepts LJL2.^0

Example 2.37 Let L be a regular language over C, k a positive integer and

4 a mupping from C” to C. Prove that

L1 = {$!+la2 ” l ak) ” l +(a(n-l)k+la(n-l)k+2 l l l ank) I ala2 l l l %k E L}

is regular.

Proof. Assume that L be accepted by a DFA A4 = (Q, C, S, s, F). Then, the

required NFA can be defined as A&’ = (Q, C, S’, s, F), where for each q E Q

and each a E C,

s’(q, a) = {d(q, 611612 ’ ’ l ak) 1 $+I, a2, l ’ ‘, ak) = a}. cl

For any language L, let

MIN(L) = {z E L 1 no proper prefix of z belongs to L}.