Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them?
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.