1
$\begingroup$

Consider the following string:

stryng = "{\"Jordi\", \"Jordy\", \"Jorde\", \"Jordie\", \"Jordee\", \"Joardi\", \"Joardy\", \"Joarde\", \"Joardie\", \"Joardee\"}"

That string represents a mathematical set of strings.

$\begin{Bmatrix} \mathtt{Jordi}, \mathtt{Jordy}, \mathtt{Jorde}, \mathtt{Jordie}, \mathtt{Jordee}, \mathtt{Joardi}, \mathtt{Joardy}, \mathtt{Joarde}, \mathtt{Joardie}, \mathtt{Joardee}\end{Bmatrix}$

If you have a string representation for a set of strings, such as {"i", "y", "ee"}, how do you convert that set of strings into a regular expression without the logical-disjunction vertical bar |?

I was hoping to have something like a character class except that instead of characters we used strings such that some of the strings were longer than one letter each.

For example, something close to a regular expression might be:

Joa?r{"i", "y", "ee"}

That fake regex was intended to represent the set of all strings σ such that...

  1. The leftmost part of σ is J
  2. The part of σ second from the left is o
  3. The part of σ third from the left is zero or one instance of the letter a
  4. The fourth part of σ is the letter r
  5. The fifth part of σ is exactly one of the strings i, or y, or ee.

There is a regular expression [iye]e? which is somewhat like the following set:

{"i", "y", "e", "ie", "ye", "ee"}

We want to forbid the string ye.

In a python-flavored regex used in the library named re, can we write a set of strings, or do we have to write something else?

Improve this question
$\endgroup$
6
  • $\begingroup$ What do you mean by "a regular expression without the logical-disjunction vertical bar |"? | is part of the syntax of regular expressions. It's not clear what is allowed. If we take the standard syntax for regexps and remove |, all that is left is grouping ((...)) and Kleene star (*), which doesn't seem very expressive, but there are multiple different definitions of regexp syntax. Can you provide a self-contained definition of what you are looking for, and what definition of regular expression you are using and what syntax is allowed? $\endgroup$ Commented Apr 4, 2023 at 3:54
  • 3
    $\begingroup$ I wonder if it might be helpful to provide the motivation for not allowing use of |, and for using a regexp for this. I wonder if this might be a XY problem, but it's hard to know. $\endgroup$ Commented Apr 4, 2023 at 3:55
  • $\begingroup$ If Jordye was in the set too, then Joa+rd[iye]e+ would work, where [iye] means "one character which can be i, y or e", and a+ means "zero or one a". But without Jordye in the set I'm afraid you have to content with Joa+rd(i|y|e|ie|ee) or Joa+rd([iye]|[ie]e). $\endgroup$ Commented Apr 4, 2023 at 9:27
  • $\begingroup$ @D.W. You said it might be helpful to provide the motivation for not allowing use of |, and for using a regexp for this. The reason is that in general, I want to convert sets containing thousands of strings into regular expressions so that the regular expressions are short in length. How do we find a reasonably short regex $r$ such that $\forall \sigma \in A$, $\sigma$ and regex $r$ match. Additionally, $\forall \sigma^{\prime} \in A^{-1}$, $\sigma^{\prime}$ and regex $r$ do not match. Note that $A$ is a set of strings and $\sigma$ is a string in set $A$. $\endgroup$ Commented Apr 5, 2023 at 1:23
  • $\begingroup$ @SamuelMuldoon Importantly, note that "regular expression" typically has two distinct meanings. The theoretical meaning, where they are restricted to expressing regular languages; and the meaning from the programming world, whose regexps are like theoretical regexps but with many added superpowers. Here on this site, in the absence of more context, people are going to assume you mean regexps in the sense used in theory, not in the superpowered sense used in programming languages. $\endgroup$ Commented Apr 5, 2023 at 7:12

1 Answer 1

Reset to default
1
$\begingroup$

If Jordye was in the set too, then Joa+rd[iye]e+ would work, where:

  • [iye] means "one character which can be i, y or e";
  • a+ means "zero or one a".

But without Jordye in the set I'm afraid you have to content with either

Joa+rd(i|y|e|ie|ee)

or

Joa+rd([iye]|[ie]e)

or

Joar+rd(y|[ie]e+)

The last one translated directly to a deterministic automaton:

 >O y / J o r d / --->o--->o--->o--->o--->o--->O /^ ie /^ \/a \/e
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.