Does lookaround affect which languages can be matched by regular expressions?

by

The answer to the question you ask, which is whether a larger class of languages than the regular languages can be recognised with regular expressions augmented by lookaround, is no.

A proof is relatively straightforward, but an algorithm to translate a regular expression containing lookarounds into one without is messy.

First: note that you can always negate a regular expression (over a finite alphabet). Given a finite state automaton that recognises the language generated by the expression, you can simply exchange all the accepting states for non-accepting states to get an FSA that recognises exactly the negation of that language, for which there are a family of equivalent regular expressions.

Second: because regular languages (and hence regular expressions) are closed under negation they are also closed under intersection since A intersect B = neg ( neg(A) union neg(B)) by de Morgan’s laws. In other words given two regular expressions, you can find another regular expression that matches both.

This allows you to simulate lookaround expressions. For example u(?=v)w matches only expressions that will match uv and uw.

For negative lookahead you need the regular expression equivalent of the set theoretic A\B, which is just A intersect (neg B) or equivalently neg (neg(A) union B). Thus for any regular expressions r and s you can find a regular expression r-s which matches those expressions that match r which do not match s. In negative lookahead terms: u(?!v)w matches only those expressions which match uw – uv.

There are two reasons why lookaround is useful.

First, because the negation of a regular expression can result in something much less tidy. For example q(?!u)=q($|[^u]).

Second, regular expressions do more than match expressions, they also consume characters from a string – or at least that’s how we like to think about them. For example in python I care about the .start() and .end(), thus of course:

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

Third, and I think this is a pretty important reason, negation of regular expressions does not lift nicely over concatenation. neg(a)neg(b) is not the same thing as neg(ab), which means that you cannot translate a lookaround out of the context in which you find it – you have to process the whole string. I guess that makes it unpleasant for people to work with and breaks people’s intuitions about regular expressions.

I hope I have answered your theoretical question (its late at night, so forgive me if I am unclear). I agree with a commentator who said that this does have practical applications. I met very much the same problem when trying to scrape some very complicated web pages.

EDIT

My apologies for not being clearer: I do not believe you can give a proof of regularity of regular expressions + lookarounds by structural induction, my u(?!v)w example was meant to be just that, an example, and an easy one at that. The reason a structural induction won’t work is because lookarounds behave in a non-compositional way – the point I was trying to make about negations above. I suspect any direct formal proof is going to have lots of messy details. I have tried to think of an easy way to show it but cannot come up with one off the top of my head.

To illustrate using Josh’s first example of ^([^a]|(?=..b))*$ this is equivalent to a 7 state DFSA with all states accepting:

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

The regular expression for state A alone looks like:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

In other words any regular expression you are going to get by eliminating lookarounds will in general be much longer and much messier.

To respond to Josh’s comment – yes I do think the most direct way to prove the equivalence is via the FSA. What makes this messier is that the usual way to construct an FSA is via a non-deterministic machine – its much easier to express u|v as simply the machine constructed from machines for u and v with an epsilon transition to the two of them. Of course this is equivalent to a deterministic machine, but at the risk of exponential blow-up of states. Whereas negation is much easier to do via a deterministic machine.

The general proof will involve taking the cartesian product of two machines and selecting those states you wish to retain at each point you want to insert a lookaround. The example above illustrates what I mean to some extent.

My apologies for not supplying a construction.

FURTHER EDIT:
I have found a blog post which describes an algorithm for generating a DFA out of a regular expression augmented with lookarounds. Its neat because the author extends the idea of an NFA-e with “tagged epsilon transitions” in the obvious way, and then explains how to convert such an automaton into a DFA.

I thought something like that would be a way to do it, but I’m pleased that someone has written it up. It was beyond me to come up with something so neat.

More Related Contents:

  1. How does the regular expression ‘(?
  2. Regex lookahead, lookbehind and atomic groups
  3. Regular Expressions: Is there an AND operator?
  4. Regular expression negative lookahead
  5. Regular Expression Lookbehind doesn’t work with quantifiers (‘+’ or ‘*’)
  6. Regex to match all permutations of {1,2,3,4} without repetition
  7. What’s the technical reason for “lookbehind assertion MUST be fixed length” in regex?
  8. Lookbehind on regex for VBA?
  9. Does lookbehind work in sed?
  10. How to match the first word after an expression with regex?
  11. Reg-ex to validate a sting with digits only but all Zeros are not allowed [closed]
  12. Why doesn’t [01-12] range work as expected?
  13. Regular expression for a string containing one word but not another
  14. How do I use regex in a SQLite query?
  15. MongoDB Regex Search on Integer Value
  16. Regular expression for letters, numbers and – _
  17. How to replace all strings to numbers contained in each string in Notepad++?
  18. How do I make case-insensitive queries on Mongodb?
  19. Why does character range class [A-z] match underscore?
  20. How do I find and remove duplicate lines from a file using Regular Expressions? [closed]
  21. How to match a regex with backreference in Go?
  22. Regex to first occurrence only? [duplicate]
  23. What’s the difference between () and [] in regular expression patterns?
  24. Regular expression for password (at least 2 digits and one special character and minimum length 8)
  25. How does one escape backslashes and forward slashes in VIM find/search?
  26. Find the location of a character in string
  27. Regular Expression only match if String ends with target
  28. How can I match a string with a regex in Bash?
  29. Regular expression for a hexadecimal number?
  30. Why does sed require 3 backslashes for a regular backslash?

Leave a Comment