If L is a regular language, so is L \ {ε}, i.e., the set of all nonempty strings in L. So we should be able to transform a regular expression for L into a regular expression for L \ {ε}. We want to do...

If L is a regular language, so is L \ {ε}, i.e., the set of all nonempty

strings in L.

So we should be able to transform a regular expression for L into a regular expression for L \ {ε}. We want to do this with a function nonempty that is recursive

over the structure of the regular expression for L, i.e., of the form:

nonempty(ε) = φ

nonempty(a) = ... where a is an alphabet symbol

nonempty(s|t) = nonempty(s)| nonempty(t)

nonempty(s t) = ...

nonempty(s?) = ...

nonempty(s∗) = ...

nonempty(s+) = ...

where φ is the regular expression for the empty language (see 1.10).

a) Complete the definition of nonempty by replacing the occurrences of “...” in the

rules above by expressions similar to those shown in the rules for ε and s|t.

b) Use this definition to find nonempty(a∗b∗).