If L is a regular language, so is the set of all prefixes of strings in L (see Sect. 1.9.3). So we should be able to transform a regular expression for L into a regular expression for the set of all...

If L is a regular language, so is the set of all prefixes of strings in L

(see Sect. 1.9.3).

So we should be able to transform a regular expression for L into a regular expression for the set of all prefixes of strings in L. We want to do this with a function prefixes that is recursive over the structure of the regular expression for L, i.e., of the form: prefixes(ε) = ε prefixes(a) = a? where a is an alphabet symbol prefixes(s|t) = prefixes(s)| prefixes(t) prefixes(s t) = ... prefixes(s∗) = ... prefixes(s+) = ... a) Complete the definition of prefixes by replacing the occurrences of “...” in the rules above by expressions similar to those shown in the rules for ε, a and s|t. b) Use this definition to find prefixes(ab∗c).