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.

  • $\begingroup$ related question : cs.stackexchange.com/questions/2557/… $\endgroup$
    – yago
    May 12, 2014 at 10:42
  • $\begingroup$ I've seen that post. In the end, the author says that there should be some nondeterminism involved. Does it mean that we cannot create a DFA? Also, I couldn't fully follow the example in the link. If you know how the example works, could you please explain to me how he deducts that {a,b,c}∗c{a,b}+{a,b,c}∗ is equal to /(?=c)[ab]+/. $\endgroup$
    – Wickoo
    May 12, 2014 at 12:17
  • $\begingroup$ From what I understood, he says that when you want to get back the word that matches the expression, then you need to keep traces of index when the match begin, and when it ends. But I guess this is not specific to lookahead/behind, since an automata is just decisionnal (word is accepted or not), while when matching in real life, you also want the corresponding position of word in text. $\endgroup$
    – yago
    May 13, 2014 at 13:30
  • $\begingroup$ For the expression, he says that you try to match a whole text with your expression at once, hence you could replace /(?=c)[ab]+/ by /.*c[ab]+.*/ and the result of the match (yes or no) will be the same. I guess his point is that lookahead/lookbehind doesn't change anything from the decisionnal point of view (matching or not), but only on the index you store to retrieve the matches, that is something apart from automata stuff. But I may be totally wrong though $\endgroup$
    – yago
    May 13, 2014 at 13:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.