Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them?

Question

Consider a regex language with the greedy quantifier $*$, the nongreedy quantifier ${*}?$, ordered alternation, and character classes. (This is essentially a sublanguage of PCRE without backreferences, look-around assertions, or some of the other fancier bits.)

A match $[a_0,a_1)$ for for a regex $R$ on a string $s = s_0\dots s_n$ is a half-open interval over $\mathbb{N}$ such that $s_{a_0}\dots s_{a_1-1}$ is accepted by $R$.

We give a recursive definition of what makes one match better than another. A match $a = [a_0,a_1)$ for regex $R$ on a string is better than another match $b = [b_0,b_1)$ if $a_0 < b_0$ or, if $a_0 = b_0$ and:

• If $R$ is a character class: Character classes have unique matches, so all matches at the same position for $R$ are equal. Hence this case is impossible.

• If $R = ST$:

  • The leading portion of $a$ is a better match for $S$ than the leading portion of $b$, or
  • The leading portions of $a$ and $b$ are equally good matches for $S$, and the trailing portion of $a$ is a better match for $T$ than the trailing portion of $b$.

• If $R = S|T$:

  • $a$ is a match for $S$ and $b$ is not, or
  • $a$ and $b$ are equally good matches for $S$ and $a$ is a better match for $S$ than $b$ is, or
  • $a$ and $b$ are not matches for $S$ but are matches for $T$, and $a$ is a better match for $T$ than $b$ is.

All other syntactic forms reduce to the above three for purposes of match priority:

• $R = S{*}$: $R \equiv S^0|S^1|\dots$
• $R = S{*}?$: $R \equiv \dots|S^1|S^0$

These infinitary patterns are used for purposes of match priority only---they are not part of the match language under consideration.

The "better" relation is a weak linear order over all possible matches for a given pattern.

Call two regexes $S,T$ match-equivalent if, for every finite input string, the set of pairwise disjoint best matches for $S$ equals the set of pairwise disjoint best matches for $T$.

Q: Is it the case that for every regex $S$ containing the nongreedy quantifier ${*}?$ there is a match-equivalent regex $T$ which contains no nongreedy quantifiers?

Edit: This is a complete rewrite of the question to clarify what was being asked.

Answer 1

This answer is based on the assumption that equivalence of two regexes is defined as they recognize the same language. It does not answer the current question.

---

You have a common misunderstanding that reluctant quantifiers change the set of strings a regular expression matches. It does not, and it only changes which options are tried first.

For example, if you perform a regex match 'aaaa' =~ /a+/ in Perl, it finds the first match in the string aaaa, and remembers which substring it matched in a special variable. Even if there are more than one substring of aaaa which matches the given regex, the matches other than the first match are ignored.

Whether quantifiers are greedy or reluctant affects what the first match is among many matches, but the set of matches does not change. In this sense, the set of strings which a regex matches is unchanged no matter whether you use usual greedy quantifiers or reluctant quantifiers.