Prove or disprove the following a For any language L L must

Prove or disprove the following:

(a) For any language L, L* must be regular.

(b) The union of finite number of regular languages is always regular.

(c) The union of infinite number of regular languages is always regular.

Solution

L* is also not regular. To prove this, we need first to prove a lemma, which we’ll call EQAB: s, s
L* #a(s) = #b(s). To prove the lemma, we first observe that any string s in L* must be able to be
decomposed into at least one finite sequence of strings, each element of which is in L. Some strings will have
multiple such decompositions. In other words, there may be more than one way to form s by concatenating
together strings in L. For any string s in L*, let SQ be some sequence of elements of L that, when concatenated
together, form s. It doesn’t matter which one. Define the function HowMany on the elements of L*.
HowMany(x) returns the length of SQ. Think of HowMany as telling you how many times we went through the
Kleene star loop in deriving x. We will prove EQAB by induction on HowMany(s).
Base case: If HowMany(s) = 0, then s = . #a(s) = #b(s).
Induction hypothesis: If HowMany(s) N, then #a(s) = #b(s).
Show: If HowMany(s) = N+1, then #a(s) = #b(s).
If HowMany(s) = N+1, then w,y such that s = wy, w L*, HowMany(w) = N, and y L. In other words,
we can decompose s into a part that was formed by concatenating together N instances of L plus a second part
that is just one more instance of L. Thus we have:
(1) #a(y) = #b(y). Definition of L
(2) #a(w) = #b(w). Induction hypothesis
(3) #a(s) = #a(w) + #a(y) s = wy
(4) #b(s) = #b(w) + #b(y). s = wy
(5) #b(s) = #a(w) + #b(y) 4, 2
(6) #b(s) = #a(w) + #a(y) 5, 1
(7) #b(s) = #a(s) 6, 3 Q

If L were regular, then its complement, L1, would also be regular. L1 contains all strings over {a, b} that are
not in L. There are two ways not to be in L: have any a\'s that occur after any b\'s (in other words, not have all
the a\'s followed by all the b\'s), or have an equal number of a\'s and b\'s. So now consider
L2 = L1 a*b*
L2 contains only those elements of L1 in which the a\'s and b\'s are in the right order. In other words,
L2 = an
bn
But if L were regular, then L1 would be regular. Then L2, since it is the intersection of two regular languages
would also be regular. But we have already shown that it (an
bn
) is not regular. Thus L cannot be regular