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

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.

• 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 Jul 21 '11 at 12:13
• 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 Jul 21 '11 at 12:17
• 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 Jul 21 '11 at 13:13
• (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 Jul 21 '11 at 14:36
• 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 Jul 21 '11 at 17:27

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.

• 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 Jul 21 '11 at 13:51
• @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 Jul 21 '11 at 14:17
• uckelman, I am pretty sure a+? matches aaaa. I know that Ruby regexpes do. – Raphael Jul 21 '11 at 16:53
• @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 Jul 21 '11 at 16:57
• I missed a + (edited), and Ruby seems to match the whole word (cf rubular.com). – Raphael Jul 21 '11 at 16:58