L + M = M + L. This law, the commutative law for union, says that we may take the union of two languages in either order.

(L + M) + N - L + (Af + N). This law, the associative law for union, says that we may take the union of three languages either by taking the union of the first two initially, or taking the union of the last two initially. Note that, together with the commutative law for union, we conclude that we can take the union of any collection of languages with any order

3.4 Algebraic Laws for Regular Expressions

In Example 3.5, we saw the need for simplifying regular expressions, in order to keep the size of expressions manageable. There, we gave some ad-hoc arguments wiiy one expression could lie replaced by another. In all cases, the basic issue was that the two expressions were equivalent, in the sense that they defined the same languages. In this section, we shall offer a collection of algebraic laws that l)ring to a higher level th( issue* of when two regular exj>ressions are etiuivalent. Instead of exannning specific regular expressions, we shall consider pairs of n>gutar expressions with variables as argunrcnts. Two expressions with variables are cquivaltnt if whatev<*r languages we substitute for the variables, the results of the two expressions are the same language.

.An example of this prtjcess in the algebra of arithmetic is as follows. It is one matter to say that 1 + 2 = 2 + 1. That is an example of the commutative law of addition, mid it is easy to check by applying the addition operator on both sides and getting 3 = 3. However, the commutative luw of addition says more; it says that, x + y = у + x, where x iuid у aie variables that can be replaced by any two numbers. That is, no matter what two numbers we add, we get the same result regardless of the order in which we sum them.

Like arithmetic expressions, the regular expressions have a number of laws that work for them. Many of these are similar to the laws for arithmetic, if we think of union as addition and concatenation as multiplication. However, tiiere are a few places where the analogy breaks down, and there are also some laws that apply to regular expressions but have no analog for arithmetic, especially when the closure operator is involved. The next sections form a catalog of the major laws. We conclude with a discussion of how one can check whether a proposed law for regular expressions is indeed a law; i.e., it will hold for any languages that wo may substitute for the variables.

3.4.1 Associativity and Commutativity

Commutativity is the property of an operator that says wo can switch the order of its operands and get the same result. .\n example for arithmetic was given above: x + у - у + x. Associativity is the property of an operator that allows us lo regroup the operands when the operator is applied twice. For example, the associative law of multiplication is (x x y) x г = x >: {y x z). Here ar(< three laws of these types that hold for regular expressions:

and grouping, and the result will be the same. Intuitively, a string is in Li и L2 и и Ljt if and only if it is in one or more of the Lis.

{LM)N - L{MN). This law, the associative law for concatenation, says that we can concatenate three languages by concatenating either the first two or the last two initially.

Missing from this list is the law LM = ML, winch would say that concatenation is commutative. However, this law is false.

Example 3.10: Consider the regular expressions 01 and 10. These expressions denote the languages {01) and {10}, respectively. Since the languages are different the general law LM = ML cannot hold. If it did, we could substitute the regular expression 0 for L and 1 for M and conclude falsely that 01 = 10. □

3.4.2 Identities and Annihilators

An identity for an operator is a value such that when the operator is applied to the identity and some other value, the result is the other value. For instance, 0 is the identity for addition, since 0 + x = x + 0 = x, and 1 is the identity for multiplication, since Ixx - xxl = x. An annihilator for an operator is a value such that when the operator is applied to the amuliilator and some other value, the result is the annihilator. For Instance, 0 is an aimihilator for multiplication, since (}x.x - xy<0-Q. There is no annihilator for addition.

There are three laws for regular expressions involving the.se concepts; we list them below.

<l\ + L- L + <li = L. This law asserts that 0 is the identity for muon.

eL = Lf. = L. This law asserts that б is the identity for concatenation.

0L = L0 = 0. This law asserts that 0 is the annihilator for concatenation.

These laws are powerful tools in simplifications. For example, if we have a union of several expressions, some of which are, or have been simplified to 0, then the 0s can be dropped from the union. Likewise, if we have a concatenation of several expressions, some of which are, or have been simplified to e, we can drop the es from the concatenation. Finally, if we have a concatenation of any nmnber of expressions, and even one of them is 0, then the entire concatenation can be replaced by 0.

3.4.3 Distributive Laws

A distributive law involves two operators, and asserts that one operator can be pushed down to be applied to each argument of the other operator indi\ndually. The most common example from arithmetic is the distributive law of multiplication over addition, that is, x x {y + z) - x x у + x x z. Since multiplication is

roramutative, it doesnt matter whether the multipUcation is on the left or right of the sum. However, there is an analogous law for regular expressions, that wo must state in two forms, since concatenation is not commutative. These laws are:

L{M + N) = LM + LN. This law, is the left distributive law of concatenation over union.

(Л/ + N}L = ML + NL. This law, is the right distributive law of concatenation over union.

Let us prove the left distributive law; the other is proved similarly. The proof will refer to languages only; it does not depend on the languages having regular expressions.

Theorem 3.11: If i, M, and N are any languages, then

LiM UN)=LM[JLN

PROOF: The proof is similar to another proof about a distributive law that we saw in Theorem 1.10. We need first to show that a string w is in L{M U N) if and only if it is in LM U LN.

(Only if) If w is in L{M U n), then w - xy, where x is in L and у is in either M or Л. If is in M, then xy is in LM, and therefore in LM U LN. Likewise, if у is in then xy is in LN and therefore in LM U LN.

(If) Suppose w is in LM U LN. Then w is in either LM or in LN. Suppose first that w is in LM. Then w = xy where x is in L and у is in M. As у is in M, it is also in M U Л. Thus, xy is in L{M U N). Uw is not in LM, then it is surely in LA, and a sinular argument shows it is in L(M U iV). □

Example 3.12 : Consider the regular expression 0+01*. We can factor out a 0 from the union, but first we have to recognize that the expression 0 by itself is actually the concatenation of 0 with something, namely e. That is, we use the identity law for concatenation to replace 0 by Oe, giving us the expression Oe + 01*. Now, we can apply the left distributive law to replace this expression by 0(e + 1). If we further recognize that e is in £-(1*), then we observe that e + 1* 1*, and can simplify to 01*. □

3.4.4 The Idempotent Law

An operator is said to be idempotent if the result of applying it to two of the same values as arguments is that wlue. The common arithmetic operators are not idempotent; э; + г / at in general and x xx фх in general (although there are .some values of x for which the equality holds, such as 0 + 0 = 0). However, union and intersection are common examples of idempotent operators. Thus, for regular expressions, we may assert the following law: