6 REGULAR LANGUAGES
Example 1.7 A+ = A* if and only if 6 E A.
Proof. Clearly, A+ - C A*. If & E A, then {E} = A0 C - A C - A+. Thus,
A *- - A+.Conversely, if E 4 A, then every string in A+ has positive length. Thus,
A+ does not contains E. But, & E A. Hence, A # A+. 0
For a language A, define the reversal language of A to be AR = {xR 1 IX: E
Example 1.8 For languages A and B, (AB)R = BRAR and (A U B)R =
ARuBR.
Proof. (AB)R = {xR 1 x E AB}
= {(Y4R I Y E A, z E B)= {zRyR 1 y E A, x E B} (by Example 1.2)
= {zR 1 ZE B} l {yR
= BRAR ,(Au B)” = (zRIxxAuB}
= {xR 1 x E A} u {zR
=ARuBR.x E B}
Cl
* Example 1.9 (Arden’s Lemma). Assume that A, B are two languages with
E c$ A, and X is a language satisfying the relation X = AX U B. Then,
X = A*B.
Proof. We use induction to show X C A* B. First, consider x = E. If x E X,
then 3 E AX U B. Since E $ A, we must have x E B and, hence, x E A* B.
Next, assume that for all strings w of length less than or equal to n, if zu E X
then w E A* B, and consider a string x of length n + 1. If x E X = AX U B,
then either x E B C - A*B or x = yw for some y E A and w E X. In the
second case, we must have y # E and, hence, IwI < 1x1. So, by the inductive
hypothesis, w E AB and x E AAB C A*B. This completes the induction
step, and it follows that X C - A*B. -
Conversely, we use induction to show that A” B C X for all n > 0. For
n = 0, we have A”B = B C AXUB = X. For n > 0, we have, by the inductive
hypothesis, A”B = A(A “-lB)CAX -. Thus ’ A”BCAXCAXuB=X. - - •I
- Example 1.10 Assume that languages A, B E {a, b}* satisfy the following
two equations:
A = {E} u {a}A u {b}B,
B = {E} u {b}B.
Find simple representations for A and B.