736
Modeling Arithmetic, Computation, and Languages
(This definition of a regular expression over I is still another example of a recursive
definition.)
Definition rEGuLAr sEt
Any set represented by a regular expression according to the following conventions is a regular set:
1. [ represents the empty set.
2. l represents the set 5l6 containing the empty string.
3. i represents the set 5i6.
4. For regular expressions A and B,
a. (AB) represents the set of all elements of the form ab where a belongs
to the set represented by A and b belongs to the set represented by B.
b. (AB) represents the union of A’s set and B’s set.
c. (A)* represents the set of all concatenations of members of A’s set.
In our discussion, we will be a little sloppy and say things like “the regular set AB”
instead of “the set represented by the regular expression AB.” Informally, an element
in AB is an item from A followed by an item from B. An element in A ~ B is a single
item chosen from either A or B. An element in (A)* is zero or more repetitions of elements from A. We note that l, the empty string, is a member of the set represented by
A* for any A because it is the case of zero repetitions of elements from A. In writing
regular expressions, we can eliminate parentheses when no ambiguity results. The
regular expression 0* ~ 10 therefore consists of l, 0, 00, 000, 0000, … , 10.
example 32
Here are some regular expressions and a description of the set each one represents.
a. 1*0(01)*
Any number (including none) of 1s, followed by a
single 0, followed by any number (including none)
of 01 pairs.
b. 0 ~ 1*
A single 0 or any number (including none) of 1s.
c. (0 ~ 1)*
Any string of 0s or 1s, including l.
d. 11((10)*11)*(00*)
A nonempty string of pairs of 1s interspersed with
any number (including none) of 10 pairs, followed by
at least one 0. One can see how awkward this verbal
description is and appreciate the compactness of a
regular expression description.
PrACtiCe 50 Which strings belong to the set described by the regular expression?
a. 10100010; (0*10)*
b. 011100; (0 ~ (11)*)*
c. 000111100; ((011 ~ 1l)*(00)*)*
■
PrACtiCe 51 Write regular expressions for the sets recognized by the machines of Practice 49.
■
Modeling Arithmetic, Computation, and Languages
(This definition of a regular expression over I is still another example of a recursive
definition.)
Definition rEGuLAr sEt
Any set represented by a regular expression according to the following conventions is a regular set:
1. [ represents the empty set.
2. l represents the set 5l6 containing the empty string.
3. i represents the set 5i6.
4. For regular expressions A and B,
a. (AB) represents the set of all elements of the form ab where a belongs
to the set represented by A and b belongs to the set represented by B.
b. (AB) represents the union of A’s set and B’s set.
c. (A)* represents the set of all concatenations of members of A’s set.
In our discussion, we will be a little sloppy and say things like “the regular set AB”
instead of “the set represented by the regular expression AB.” Informally, an element
in AB is an item from A followed by an item from B. An element in A ~ B is a single
item chosen from either A or B. An element in (A)* is zero or more repetitions of elements from A. We note that l, the empty string, is a member of the set represented by
A* for any A because it is the case of zero repetitions of elements from A. In writing
regular expressions, we can eliminate parentheses when no ambiguity results. The
regular expression 0* ~ 10 therefore consists of l, 0, 00, 000, 0000, … , 10.
example 32
Here are some regular expressions and a description of the set each one represents.
a. 1*0(01)*
Any number (including none) of 1s, followed by a
single 0, followed by any number (including none)
of 01 pairs.
b. 0 ~ 1*
A single 0 or any number (including none) of 1s.
c. (0 ~ 1)*
Any string of 0s or 1s, including l.
d. 11((10)*11)*(00*)
A nonempty string of pairs of 1s interspersed with
any number (including none) of 10 pairs, followed by
at least one 0. One can see how awkward this verbal
description is and appreciate the compactness of a
regular expression description.
PrACtiCe 50 Which strings belong to the set described by the regular expression?
a. 10100010; (0*10)*
b. 011100; (0 ~ (11)*)*
c. 000111100; ((011 ~ 1l)*(00)*)*
■
PrACtiCe 51 Write regular expressions for the sets recognized by the machines of Practice 49.
■