3.4.8 Exercises for Section 3.4

Exercise 3.4.1: Verify the following identities involving regular expressions. *a) n-\rS = S + R.

b) {R + S) + T = R + {S + T).

c) {RS)TB{ST).

regular expressions denote the same languagt; until Section 4.4. However, we can use ad-hoc means to decide the equality of the pairs of languages that we actually care about. Recall that if the languages are not the same, than it is sufficient to provide one counterexample: a single string that is in one language but not the other.

Theorem 3.14; The above test correctly identifies the true laws for regular expressions.

PROOF: We shall show that L{E) = L[F) for any languages in place of the variables of £ and F if and only if L{C) = 1(D).

(Only-if) Suppose L{E) = L{F] for all choices of languages for the variables. In particular, choose for every variable L the conc:rete symbol a that r(!places L in expressions С and D. Then for this choice, L{C) = L{E), and L{D) = L{F). Since L{E) = L{F) is given, it follows that L{C) =L{D).

(If) Suppose L(C) - L[D). By Theorem 3.13, L{E) and L{F) are each constructed by replacing the concrete symbols of strings in L{C) and L{D), respectively, by strings in the languages that correspond to those symbols. If the strings of L{C) and L{D) are the same, then the two languages constructed in this manner will also be the same; that is, L{E) = L(F). □

Example 3.15: Consid(r the prospective law (L + M)* = {LM). If we replace variables L and M by concrete symbols a and Ь respectively, we get the regular expressions (a + b) and (a*b*)*. It is еачу to check that both these expressions denote the language with all strings of as and bs. Thus, the two concrete expressions denote the same language, and the law holds.

For another example of a law, consider L* = LL*. The concrete languages are a* and aa*, respectively, and each of these is the set of all strings of as. Again, the law is found to hold; that is, concatenation of a closed language with itself yields that language.

Finally, consider the prosjjective law L + ML = (L + M)L. If we choose symbols a and b for variables L and AI, respectively, we have the two concrete regular expressions a + ba and (a + b}a. However, the languages of these expressions are not the same. For example, the string aa is in the second, but not the first. Thus, the prospc;ctive law is falst;. □

ЗА. ALGEBRAIC LAWS FOR REGULAR EXPRESSIONS 121

Extensions of the Test Beyond Regular Expressions

May Fail

Let us consider an extended regular-expression algebra tliat includes the intersection operator. Interestingly, adding П to the three regular-expression operators does not increase the set of languages we can describe, as we shall see in Theorem 4,8. However, it dtjes make the test for algfihraic laws invalid.

Consider the law L П M П N = LD M; that is, the intersection of any three languages is the same as the intersection of the first two of these languages. This law is patently false. For example, let L = M = {a} and N - 9- But the test based on concretizing the variables would fail to see the difference. That is, if we replaced L, M, and Л by the symbols a, b, and c, respectively, we would t(st whether [a] П {b} Q {c} = { }П {b}. Since both sides are the empty S(t, the equality of languages holds and the test would imply that the law is true.

d) R{S + T) = RS+ RT.

e) {R+S)T = RT + ST.

* f) {RY R*.

g) (f - Л-,

h) {RS*Y = {R + Sy.

! Exercise 3.4.2: Prove or disprove each of th(; following .statements about regular expressions.

* a) [R + Sy = R +S.

b) {RS + RyR = R{SR + Ry. *c) {RS + RyRS = (RRSy.

d) {R + SyS =iRSy.

e) SiRS + SyR~ RR*S{RR\Sy.

Exercise 3.4.3: In Example 3.G, we developed th(> regular exi)ression

(0 H-1)-1(0-}-1)-I-(0-H)1(0-H)(0-i-1)

Use the distributive laws to develop two different, simpler, equivalent expressions.

3.6 References for Chapter 3

The idea of regular expressions and the proof of their equiwlence to finite automata is the work of S. C. Kleene [3]. However, the construction of an e-NFA from a regular expression, as presented here, is the McNaughton-Yamada construction, from [4]. The test for regular-expression identities by treating variables as constants was written down by J. Gischer [2]. Although thought to

Exercise 3.4.4: At the beginning of Section 3.4.6, we gave part of a proof that (L*M*)* = {L + МУ. Complete the proof by showing that strings in (L*M*)* are also in (L + M) .

Exercise 3.4,5: Complete the proof of Theorem 3.13 by handling the cases where regular expression E is of the form FG or of the form F*.

3.5 Summary of Chapter 3

V Regular Expressions: This algebraic notation describes exactly the same languages as finite automata: the regular languages. The regular-expression operators are union, concatenation (or dot ), and closure (or star ).

4- Regular Expressions in Practice: Systems such as UNIX and various of its commands use an extended regular-expression language that provides shorthands for many common expressions. Character classes allow the easy expression of sets of symbols, while operators such as one-or-more-of and at-most-one-of augment the usual regular-exjiression operators.

+ Equivalence of Regular Expressions and Finite Automata: We can convert a DFA to a regular expression by an inductive construction in which expressions for the labels of paths allowed to pass through increasingly larger sets of states are constructed. Alternatively, we can use a state-elimination procedure to build the regular expression for a DFA. In the other direction, we can construct recursively an e-NF.4 from regular expressions, and then convert the e-NFA to a DFA, if we wish.

f The Algebra of Regular Expressions: Regular expressions obey many of the algebraic laws of arithmetic, although there are differences. Union and concatenation aie associative, but only union is commutative. Concatenation distributes over union. Union is idempotent.

f Testing Algebraic Identities: We can tell whether a regular-expression equivalence involving variables as arguments is true by replacing the variables by distinct constants and testing whether the resulting languages are the same.