0
$\begingroup$

We seek an algorithm.

Inputs to the algorithm are a set of strings $A$ and the output of the algorithm $A$ is a regular expression $r$ such that:

  1. The size of regular expression $r$ is minimized.

  2. If $A^{\prime}$ is set of strings described by regular expression $r$, then $A \subseteq A^{\prime}$. In other words, the set of strings described by $r$ is a super-set of set $A$.


Example of Input and Output for the Algorithm

The following list of email addresses would represent the input to our algorithm:

The output from the algorithm might be something similar to the following regular expression, but (and only if you want to) feel free to edit this question to correct the following regex:

[A-Za-z\-]+@[A-Za-z\-]+\.((com)|(org)|(net))

How to quantify the size of the regex a|b

TREE OF THE REGEX "A|B". SHOWS ONE ROOT NODE WITH TWO CHILDREN. THREE NODES IN TOTAL ARE IN THE TREE

For regex $\mathtt{a|b}$ the associated tree has $3$ nodes.

Our algorithm accepts a set of strings as input and outputs a regex for which the corresponding tree has as few nodes as possible.


How to quantify the size of the regex [A-Z]

A TREE OF THE REGEX CHARACTER CLASS [A-Z] letters THE TREE CONTAINS  27 NODES

For the character class $\mathtt{[A-Z]}$ the size of the associated tree is $27$.

Our algorithm accepts a set of strings as input and outputs a regex for which the corresponding tree has as few nodes as possible.


In general, for a regular expression character class containing $n$ characters, the number of nodes in the tree associated with the character class is $n + 1$.

  • There are $n$ children of the root node

  • The root node represents logical-disjuction and/or the union of sets. In regular expressions logical-disjuction is usually written as | or or.


Given that there are many different flavors of regex, please assume that we the flavor of regular expressions used in the Java SE 19 standard.


Generating a regex from a large set of examples is an important problem because writing regular expressions for practical applications by hand is difficult.

The following is a popular standard for email addresses. Most people would have more difficulty writing the following regex by hand than they would amassing large lists of valid email addresses.

\A(?:[a-z0-9!#$%&'*+/=?^_‘{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_‘{|}~-]+)*
 |  "(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]
      |  \\[\x01-\x09\x0b\x0c\x0e-\x7f])*")
@ (?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?
  |  \[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}
       (?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:
          (?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]
          |  \\[\x01-\x09\x0b\x0c\x0e-\x7f])+)
     \])\z
$\endgroup$

1 Answer 1

1
$\begingroup$

The minimal regular expression is [abcd...]*, where abcd... is the list of characters that appear in the input. This always accepts a superset of the specified strings.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.