<p>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.</p>

<p>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?</p>

<p>I have done some trial and errors and it looks like composition in face of the Kleene star operator is problematic.</p>

CC BY-SA 3.0
2014-05-12T10:42:46.763Z
related question : http://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-auto
yago
CC BY-SA 3.0
2014-05-12T12:17:39.060Z
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]+/.
Wickoo
CC BY-SA 3.0
2014-05-13T13:30:38.447Z
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.
yago
CC BY-SA 3.0
2014-05-13T13:33:01.290Z
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
yago
<regular-expressions><dfa>
Composition of regular expressions with lookahead into DFAs
Wickoo
# Composition of regular expressions with lookahead into DFAs

(Asked by: username_0 on 2014-05-11)

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.

**Tags:** regular-expressions, dfa

> **Comments:**
> **username_1**: related question : http://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-auto  
> **username_0**: 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]+/.  
> **username_1**: 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.  
> **username_1**: 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  

---

## 0 answers

