Automated Verification: Assignment 2

Due Date: November 25, 1998
Let e be a regular expression and let E={e1,...ek} be a finite set of regular expressions over a common alphabet Sigma. Let SigmaE be the alphabet {a1,...ak}. Intuitively, SigmaE consists of names for the regular expressions in E. Let f be a regular expression over SigmaE. The regular expression f(E) over the alphabet Sigma is obtained by substituting ei for ai, i=1,...,k, in f.

We say that f is an approximation of e with respect to E if L(f(E)) is contained in L(e). We say that f is a rewriting of e with respect to E if L(f(E)) is equal to L(e). Find algorithms (and analyze their complexity) for the following decision problems:

  1. Given e and E, is there a nonempty approximation of e wrt E?
  2. Given e and E, is there a rewriting of e wrt E?
Note: The assignment needs to be typeset.