1.2 Regular Languages 13
If the second rightmost symbol is the first case, then the two rightmost symbols
form a minimal string in the language (i.e., the minimal string has length 2
and the second rightmost symbol is the leftmost symbol). In the other three
cases, the third rightmost symbol must exist and has the same four choices
as the second rightmost symbol.
Thus, from the above analysis, we see that this language has the following
regular expression:
[(:)+(:)+(1)+(9)[(2)+(:)+( i)]*(i)]**
qMathematical induction is an important proof technique in mathematics.
To prove a statement Sn true for all natural numbers n = 0, 1,... , we can
prove it by induction on n as follows:
1. (Basis Step) For n = 0, prove that the statement 5’0 is true.
2. (Induction Step) Suppose that the statement Sn is true for an arbitrary
integer n > 0. Prove that the statement $+I is true.
We used this-proof technique in Example 1.9: To show that X C A*B, we
proved that for each n, if (~1 =nthenwEX 3 ~EA*B. -
This induction principle can be generalized to other sets of objects which
are defined by an inductive (or, recursive) definition. Since regular languages
are defined inductively, this principle can be employed to prove a property Q
of regular languages in the following way:
(1) Prove that 8 has the property Q.
(2) For each a E C, prove that {a) has the property Q.
(3) Prove that if A and B have the property Q, then each of A U B, AB,
and A* has the property Q.
Here, steps (1) and (2) serve as the basis step, and step (3) serves as the
induction step.
Example 1.21 For each language L over alphabet C, let L’ be the set of all
sufixes of strings in L, that is, L’ = {w ( uw E L for some string u}. Show
that if L is a regular language so is L’.
SoZution. We prove this result by induction as follows.
Basis Step (1): 8’ = 8 is a regular set.
Basis Step (2): For any a E C, {a)’ = {E, a} is a regular set.
Induction Step (3): Suppose that L1 and L2 are regular sets with the
property that L/, and LL are regular sets. Then, we have
(a) (LI U L2)’ = {w 1 (3u)[uw f Ll UL2]}
= {w 1 (3u)[uw E Ll] or (3u)[uw E L2]}