It is well known that "regex" with back-reference is not a regular expression anymore.
(.*)\1 matches any string repeated twice.
However, is it possible to construct a DFA for regex with lookaround?
Look-ahead and look-behind are nothing special in the world of finite automata as we only match whole inputs here. Therefore, the special semantic of "just check but don't consume" is meaningless; you just concatenate and/or intersect checking and consuming expressions and use the resulting automata.
However, I'm not quite sure how to intersect the checking and matching automata.
For simple cases such as
foo(?=bar), I can just concatenate them (
But this won't work for more complex cases such as
since lookahead will not consume the input,
foo must match both
This answer suggests using Alternating Finite Automaton,
but after reading through the tremendously
unhelpful Wikipedia page,
I am totally confused how this can help turn lookarounds into plain old DFA.