The Question

A regular expression, such as AL+[EYI]+, represents a set of strings.

alleys = { 
    et cetra...   

Let $\mathbb{AS}$ be the set of all strings $\sigma$ such that there exist natural numbers $x_{1}, x_{2}, x_{3}$ such that $x_{1} < x_{2}$ and...

$$ \forall n \in \{1, 2, 3, \cdots\} \sigma(n) \in \begin{cases} \{ “A” \}, & \text{if } n = 1 \\ \{ “L” \}, & \text{if } 1 < n \leq x_{1} \\ \{ “E”, “Y”, “I” \}, & \text{if } x_{1} < n \leq x_{2} \\ \{ \mathtt{NULL} \}, & \text{if } x_{2} < n \\ \end{cases} $$

The question is, if the input is two sets of strings A and B represented by regular expressions, what algorithm will output the following three things:

  1. a regex for (Aᶜ) ⋂ (B)
  2. a regex for (A) ⋂ (B)
  3. a regex for (A) ⋂ (Bᶜ)

Some people will want our algorithm to have only output instead of three separate outputs.

If you want the output to be one single object, then suppose that the algorithm outputs a tuple containing three strings. A function which returns a container wrapping multiple things is supported by many different programming languages.

Additional Explanation

Motivation for the Problem)

As an example application, suppose that a college student is writing a parser for American mailing addresses.

Some people like to write an abbreviation such as ST or AVE.

Other people like to write the whole word spelled out in full English: STREET, AVENUE.

Most high quality parsers need to be able to parse both abbreviations and full-English words.


We begin with a regular expression for all acceptable abbreviations of an English word.

However, two regular expressions might have non-empty intersection.

We need to create new regular expressions which are mutually exclusive (non-overlapping).

Once we partition the space of inputs, we have have each partition of input strings map to a set of output strings.

If the input maps to a set containing one string, then it is a good input.

If the input maps to a set containing more than one string, then the input is bad and we output an error message long with a list of all of the types of street the input abbreviation could have referred to.

We probably want to use the notation for regular expressions instead of the set of strings notation, because the explicit notation of a set of strings will not be finite in length.

  • $\begingroup$ Why do you introduce AL+[EYI]+ or $\mathbb{A}\mathbb{S}$? It does not seem to play any role in the problem statement and thus seems irrelevant. I am suspicious that you have not accurately stated the actual problem you face. For instance, are the regexps for A,B limited in some way to only match strings in $\mathbb{A}\mathbb{S}$? $\endgroup$
    – D.W.
    Commented Jun 5, 2023 at 5:12
  • 1
    $\begingroup$ You seem to be asking for algorithms to compute the complement, intersection, and union of two regexps. Those should be documented in standard places. A simple search should immediately turn up many resources. What research have you done? $\endgroup$
    – D.W.
    Commented Jun 5, 2023 at 5:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.