Union of Regular Expressions
Algorithm
The steps to create two regular expressions are:
- enclose the two regular expressions in brackets;
- join them together using the + operator, defined to be
the union operator on the context of regular expressions.
In this case, bracketting is not strictly necessary, but is still
used so as to avoid ambiguities.
Example
Consider the two regular expressions:
(a* + b) and
b+
The union of the two regular expressions is:
((a* + b)) + ( b+)
Note that this is equivalent to a* + b + b+.
Exercises
- ab and
c + f
- 01 and
1 + (11)0
- (a + b)* and
a+ + 1
- Bracketing is not really necessary in this case because of all
the regular expression operators, +
has the lowest precedence. What is the
other condition necessary?
Hint: consider the language of
arithmetic expressions with - and + and - having the
highest precedence.