Which regular expression requires backtracking?

Question

There are three different solutions to implement regular expression matching: DFA, NFA and Backtracking. I am looking for examples:

a regexp, which can be solved with a DFA and the reason, why a DFA is sufficient.
a regexp, which requires a NFA and the reason why a NFA is necessary.
a regexp, which requires backtracking and the reason why backtracking is necessary.

A recommendation for some good literature about this topic would be nice, too.

I think you'll have better luck asking this on [cstheory.se]. — Alan Moore, Nov 15 '11 at 07:08
I think this chapter in Mastering Regular Expressions might be of help http://oreilly.com/catalog/regex/chapter/ch04.html — Narendra Yadala, Nov 15 '11 at 07:38
A related (but different) question: https://stackoverflow.com/questions/57731835/why-does-regexp-have-a-timeout-method-while-in-theory-they-shouldnt — Sohail Si, Aug 30 '19 at 19:11

score 4 · Answer 1 · answered Feb 16 '12 at 00:44

i guess there is more than 1 meaning to the word backtracking - even '.*a' has to backtrack to match the string "lalaiiiiiii" (because .* will first match the whole string - so then a won't match anything - and only then it will give up one character at a time, so the final match would be "lala")

i highly recommend http://www.regular-expressions.info/

score -3 · Accepted Answer · answered Dec 13 '11 at 16:31

What I found out so far is:

Every regular expression, which can be implemented with a NFA, can also be implemented with a DFA. Every NFA can be transformed into a DFA.
Regular expressions, which require backtracking, are regular expressions, which contain back references like /(a)\1/.

Which regular expression requires backtracking?

2 Answers2

Linked