<p><em>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.</em></p>

<hr>

<p>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.</p>

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

<p>Whether quantifiers are greedy or reluctant affects what the <em>first match</em> 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.</p>

CC BY-SA 3.0
2011-07-21T13:51:57.583Z
No, I'm *not* talking about the set of matches that an unanchored pattern will get on a given string. I am talking about the set of strings for which a given pattern will match those strings in their entirety. In other words, I am interested in rewriting patterns to maintain equivalence over the set of strings for which the *first match* is the *entire string*. `a+` and `a+?` are not equivalent in this sense: `aaaa` is not a match for the latter.
uckelman
CC BY-SA 3.0
2011-07-21T14:17:10.517Z
@uckelman: According to your definition, the string `abbb` is not in L(`a*(..)*`) because the first match in the the string `abbb` to the regex `a*(..)*` is `abb`.  That is not the standard definition of the language recognized by a regular expression.  If that is really what you are interested in, you should name it differently.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T16:53:25.697Z
uckelman, I am pretty sure `a+?` matches `aaaa`. I know that Ruby regexpes do.
Raphael
CC BY-SA 3.0
2011-07-21T16:57:33.340Z
@Raphael: I guess that you are talking about `"aaaa" =~ /a?/` returning true in Ruby, but that is because the pattern matches a _substring of_ `aaaa`, not because it matches `aaaa`.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T16:58:46.287Z
I missed a `+` (edited), and Ruby seems to match the whole word (cf rubular.com).
Raphael
CC BY-SA 3.0
2011-07-21T13:31:00.713Z
2011-07-21T14:53:39.240Z
2011-07-21T14:53:39.240Z
Tsuyoshi Ito
<p>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.)</p>

<p>A <em>match</em> $[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$.</p>

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

<ul>
<li><p>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.</p></li>
<li><p>If $R = ST$:</p>

<ul>
<li>The leading portion of $a$ is a better match for $S$ than the leading
portion of $b$, or</li>
<li>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$.</li>
</ul></li>
<li><p>If $R = S|T$: </p>

<ul>
<li>$a$ is a match for $S$ and $b$ is not, or</li>
<li>$a$ and $b$ are equally good matches for $S$ and $a$ is a better match for $S$ than $b$ is, or</li>
<li>$a$ and $b$ are not matches for $S$ but are matches for $T$, and $a$ is a
better match for $T$ than $b$ is.</li>
</ul></li>
</ul>

<p>All other syntactic forms reduce to the above three for purposes of match
priority:</p>

<ul>
<li>$R = S{*}$: $R \equiv S^0|S^1|\dots$</li>
<li>$R = S{*}?$: $R \equiv \dots|S^1|S^0$</li>
</ul>

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

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

<p>Call two regexes $S,T$ <em>match-equivalent</em> 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$.</p>

<p><strong>Q:</strong> 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?</p>

<p><strong>Edit:</strong> This is a complete rewrite of the question to clarify what was being
asked.</p>

CC BY-SA 3.0
2011-07-21T12:13:57.490Z
I tried to correct LaTeX in the question, but please check that it is what you meant.  (`\tt` does not prevent LaTeX from interpreting special characters and control sequences!)
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T12:17:06.863Z
You have to be careful what you mean by “expressive power” of a regular expression.  If you only consider which language the regular expression recognizes, then it is trivial that reluctant quantifiers do not add any additional power because they do not change the language the regular expression recognizes in the first place.  But I think that you are thinking about finer properties of regular expressions such as which substrings are captured and so on.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T12:53:34.007Z
Reluctant quantifiers *do* affect what language is recognized. For example, $L(a{+}) = \{ \underbrace{a\dots a}_n : n \in \mathbb{N}^+\}$, while $L(a+?) = \{ a \}$.
uckelman
CC BY-SA 3.0
2011-07-21T13:13:10.503Z
No, L(`a+?`) is still {a^n: n≥1}.  If you perform an _unanchored_ regex match (such as `'aaaa' =~ /a+?/` in Perl), you will not get `aaaa` as a result, but that is just because branches are tried in a different order from `a+`.  If you do it appropriately with anchors (such as `'aaaa' =~ /^a+?\z/` in Perl), you get `aaaa` as a result.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T13:21:33.323Z
When I'm talking about the language of a pattern, I mean the set of strings which that pattern will match in their entirety. There's not an implicit anchor at the ends of the patterns I'm considering. `a+?` is not the same pattern as `a+?\z`, they have different matches.
uckelman
CC BY-SA 3.0
2011-07-21T14:36:46.440Z
(1) I am glad to see that my comments and answer were helpful for you to restate the question better (even though you have not admitted it).  (2) I hope that you are aware that “the sets of nonoverlapping matches which S and T have on t” is not well-defined because there can be several sets of nonoverlapping matches.  Are you talking about the list which a global regex match (`//g` in Perl) would return?
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T14:44:05.063Z
I've added a further clarification that the matches should be leftmost longest, which should make the match sets unique. This is why I stated the problem originally as having to do with complete matches, as the statement is more straightforward that way.
uckelman
CC BY-SA 3.0
2011-07-21T14:47:09.180Z
Thanks for the edit.  Now I find the question interesting, but unfortunately I do not know the answer.  My _guess_ would be that it is not always possible to remove reluctant quantifiers without changing the set of leftmost nonoverlapping matches in your sense, but I do not have a counterexample.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T16:57:31.933Z
I still don't get it. If you look for *longest* partial matches, `aaaa` is certainly a match for `a+?`. I think you should add a precise definition of when a substring is matched by a pattern (because `a+` certainly matches any single `a`, too).
Raphael
CC BY-SA 3.0
2011-07-21T17:00:20.443Z
@Raphael: You are right.  The word “longest” should not be there.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-21T17:09:36.110Z
@Raphael: Longest should instead be "best".
uckelman
CC BY-SA 3.0
2011-07-21T17:27:11.067Z
You question needs clearing up; you're still talking of "accepting" a match when greedy vs. non-greedy doesn't change what's accepted; it's just a means to specify which match to locate when searching for a match and finding many.
Eamon Nerbonne
CC BY-SA 3.0
2011-07-21T17:29:53.167Z
BTW, you might be interesting in reading about weighted transducers; these may be relevant to the issue of preferential matching and have been studied in the literature.
Eamon Nerbonne
CC BY-SA 3.0
2011-07-22T16:22:57.240Z
uckelman, what would be a "best" match? What makes one match better than another?
Raphael
CC BY-SA 3.0
2011-07-25T11:45:36.603Z
I've entirely rewritten the question to be clearer about what I'm after (including what counts as "best").
uckelman
CC BY-SA 3.0
2011-07-26T09:16:12.397Z
I think this is a good question, certainly non-trivial and definitely on-topic for this site. But I think the question could be simplified a bit: I would remove the reference to "pairwise disjoint best matches" and simply define that S and T are match-equivalent if the best match is the same for any input string; then we would have a well-defined question. (Even if this seemingly simpler version is not what you want to know, I think it is good to try to first resolve the simplest possible variant, before introducing any extensions.)
Jukka Suomela
CC BY-SA 3.0
2011-07-26T15:04:23.470Z
As you wrote, R?, R??, R+, R+?, R{m,n}, and R{m,n}? are redundant for the purpose of this question.  You can probably make the question simpler by not introducing these redundant notations at all.
Tsuyoshi Ito
<fl.formal-languages><regular-expressions>
Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them?
uckelman
# Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them?

(Asked by: username_0 on 2011-07-21)

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.

**Tags:** fl.formal-languages, regular-expressions
> **Comments:**
> **username_1**: I tried to correct LaTeX in the question, but please check that it is what you meant.  (`\tt` does not prevent LaTeX from interpreting special characters and control sequences!)  
> **username_1**: You have to be careful what you mean by “expressive power” of a regular expression.  If you only consider which language the regular expression recognizes, then it is trivial that reluctant quantifiers do not add any additional power because they do not change the language the regular expression recognizes in the first place.  But I think that you are thinking about finer properties of regular expressions such as which substrings are captured and so on.  
> **username_0**: Reluctant quantifiers *do* affect what language is recognized. For example, $L(a{+}) = \{ \underbrace{a\dots a}_n : n \in \mathbb{N}^+\}$, while $L(a+?) = \{ a \}$.  
> **username_1**: No, L(`a+?`) is still {a^n: n≥1}.  If you perform an _unanchored_ regex match (such as `'aaaa' =~ /a+?/` in Perl), you will not get `aaaa` as a result, but that is just because branches are tried in a different order from `a+`.  If you do it appropriately with anchors (such as `'aaaa' =~ /^a+?\z/` in Perl), you get `aaaa` as a result.  
> **username_0**: When I'm talking about the language of a pattern, I mean the set of strings which that pattern will match in their entirety. There's not an implicit anchor at the ends of the patterns I'm considering. `a+?` is not the same pattern as `a+?\z`, they have different matches.  
> **username_1**: (1) I am glad to see that my comments and answer were helpful for you to restate the question better (even though you have not admitted it).  (2) I hope that you are aware that “the sets of nonoverlapping matches which S and T have on t” is not well-defined because there can be several sets of nonoverlapping matches.  Are you talking about the list which a global regex match (`//g` in Perl) would return?  
> **username_0**: I've added a further clarification that the matches should be leftmost longest, which should make the match sets unique. This is why I stated the problem originally as having to do with complete matches, as the statement is more straightforward that way.  
> **username_1**: Thanks for the edit.  Now I find the question interesting, but unfortunately I do not know the answer.  My _guess_ would be that it is not always possible to remove reluctant quantifiers without changing the set of leftmost nonoverlapping matches in your sense, but I do not have a counterexample.  
> **username_2**: I still don't get it. If you look for *longest* partial matches, `aaaa` is certainly a match for `a+?`. I think you should add a precise definition of when a substring is matched by a pattern (because `a+` certainly matches any single `a`, too).  
> **username_1**: @Raphael: You are right.  The word “longest” should not be there.  
> **username_0**: @Raphael: Longest should instead be "best".  
> **username_3**: You question needs clearing up; you're still talking of "accepting" a match when greedy vs. non-greedy doesn't change what's accepted; it's just a means to specify which match to locate when searching for a match and finding many.  
> **username_3**: BTW, you might be interesting in reading about weighted transducers; these may be relevant to the issue of preferential matching and have been studied in the literature.  
> **username_2**: uckelman, what would be a "best" match? What makes one match better than another?  
> **username_0**: I've entirely rewritten the question to be clearer about what I'm after (including what counts as "best").  
> **username_4**: I think this is a good question, certainly non-trivial and definitely on-topic for this site. But I think the question could be simplified a bit: I would remove the reference to "pairwise disjoint best matches" and simply define that S and T are match-equivalent if the best match is the same for any input string; then we would have a well-defined question. (Even if this seemingly simpler version is not what you want to know, I think it is good to try to first resolve the simplest possible variant, before introducing any extensions.)  
> **username_1**: As you wrote, R?, R??, R+, R+?, R{m,n}, and R{m,n}? are redundant for the purpose of this question.  You can probably make the question simpler by not introducing these redundant notations at all.  

---

## 1 answers

### Answer by username_1 on 2011-07-21. Score: 3

*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.

> **Comments:**
> **username_0**: No, I'm *not* talking about the set of matches that an unanchored pattern will get on a given string. I am talking about the set of strings for which a given pattern will match those strings in their entirety. In other words, I am interested in rewriting patterns to maintain equivalence over the set of strings for which the *first match* is the *entire string*. `a+` and `a+?` are not equivalent in this sense: `aaaa` is not a match for the latter.  
> **username_1**: @uckelman: According to your definition, the string `abbb` is not in L(`a*(..)*`) because the first match in the the string `abbb` to the regex `a*(..)*` is `abb`.  That is not the standard definition of the language recognized by a regular expression.  If that is really what you are interested in, you should name it differently.  
> **username_2**: uckelman, I am pretty sure `a+?` matches `aaaa`. I know that Ruby regexpes do.  
> **username_1**: @Raphael: I guess that you are talking about `"aaaa" =~ /a?/` returning true in Ruby, but that is because the pattern matches a _substring of_ `aaaa`, not because it matches `aaaa`.  
> **username_2**: I missed a `+` (edited), and Ruby seems to match the whole word (cf rubular.com).  

---

