4. L (r 1 + r 2 ) = L (r 1 )∪ L (r 2 ),
5.L (r 1 · r 2 ) = L (r 1 ) ∪ L (r 2 );
6 L ((r 1 )) = L (r 1 ),
7.L ( ) = (L (r 1 ))*.
The last four rules of this definition are used to reduce L (r) to simpler
components recursively; the first three are the termination conditions for this
recursion. To see what language a given expression denotes, we apply these rules
repeatedly.
Example 3.2
Exhibit the language L(a* · (a + b)) in set notation.
There is one problem with rules (4) to (7) in Definition 3.2. They define a
language precisely if r 1 and r 2 are given, but there may be some ambiguity in
breaking a complicated expression into parts. Consider, for example, the regular
expression a . b+ c. We can consider this as being made up of r 1 = a . b and r 2 = c.
In this case, we find L (a . b + c) = {ab, c}. But there is nothing in Definition 3.2
to stop us from taking r 1 = a and r 2 = b + c. We now get a different result, L(a . b
+ c) = {ab, ac}. To overcome this, we could require that all expressions be fully
parenthesized, but this gives cumbersome results. Instead, we use a convention
familiar from mathematics and programming languages. We establish a set of
precedence rules for evaluation in which star-closure precedes concatenation and
concatenation precedes union. Also, the symbol for concatenation may be
omitted, so we can write r 1 r 2 for r 1 .r 2 .
With a little practice, we can see quickly what language a particular regular
expression denotes.