A regular expression (r.e.) represents a set specified by the following rules:
O represents the
empty set, that is, the set with no strings;
l represents
the set {l},
which is the set containing the empty string;
x represents the set {x} containing the
string with one symbol x;
(AB) represents the concatenation of the
sets represented by A and B;
A U B represents the union of the sets represented
by A and by B;
A* represents the Kleene closure of the
sets represented by A."
Note: Kleene closure, A*, is defined over a set of strings, A, and consists of the concatenations of arbitrarily many strings from A.
(from "Discrete Mathematics and Its Applications"
by Kenneth H. Rosen (4th edition), p 656)
Interpret each regular expression below as a data structure and draw a structure diagram for it.
Hint: [interpret * as iteration, | as alternation, and ab as sequence]
(a) ((a*|b*)*c)|db (a*)*|b|cd)
(c) ((a|b|cd)*)* da|(b(cd)*)
(e) ab(c|d*)* fa*b*(c|d)*