Let's say we have a regular expression ("a" | "b"(~!"b"))*, written in Perl or other similar languages that support lookahead, which should match a list of a and b's where b's are not followed by b's.
The Perl regular expression engine is not based on Thompson DFAs and uses arbitrary backtracking, which I'm not looking for. Do you know of any known method for translating such a regular expression with lookahead into an NFA and then to DFA that accepts the described language? Any papers that describe the challenges of adding lookahead and lookbehind to DFAs and how to compose them?
I have done some trial and errors and it looks like composition in face of the Kleene star operator is problematic.