9
$\begingroup$

Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a regexp. As I said, a regexp, not a regular expression. Since a regular expression can match strings computed by a Finite State Automata and finding a prime number can't be done by a FSA, the regexp shown in the blog post is not entirely a regular expression since it does backtracking to match the string.

Since I've never really used any regular expression, now, my question:

How can I immediately recognize a regexp from a "true" regular expression just by looking at it?

Definitions: By regular expression, I refer to the notion as defined in formal languages. By regexp, I mean the notion supported by modern programming languages; the regexp syntax often contains additional features, such as backreferences. Regexps as seen in programming languages are strictly more powerful than formal languages style regular expressions.

$\endgroup$

migrated from programmers.stackexchange.com Feb 16 '15 at 13:36

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • 5
    $\begingroup$ Regexp is just an abbreviation of regular expression. The prime numbers calculation is based on a Perl hack, not on regular expressions. $\endgroup$ – user773 Feb 13 '15 at 11:27
  • 1
    $\begingroup$ It's rather simple. Regular languages employ concatenation, repetition and alternation. Anytime an engine supports something not equivalent to these, it's non-regular. $\endgroup$ – Kilian Foth Feb 13 '15 at 12:01
  • 1
    $\begingroup$ Related questions: 1, 2, 3. $\endgroup$ – Raphael Feb 16 '15 at 16:08
  • $\begingroup$ @Yannis If you jump over the fence to CS, that's no longer true. Regexps as seen in programming languages are strictly more powerful than (formal languages style) regular expressions, and the short form "regexp" is by convention (I don't know how widespread a one it is) used for the former, not the latter kind. $\endgroup$ – Raphael Feb 16 '15 at 16:09
  • $\begingroup$ @KilianFoth That's not really a helpful description, though. For example, you can add negation (or, indeed, any finite set of Boolean connectives) to regular expressions without increasing their power. $\endgroup$ – David Richerby Mar 1 at 11:48
13
$\begingroup$

tl;dr backrefs.

As soon as there is a \1 (or any number that isn't used to escape unicode) in the regexp it is not a regular expression.

Backrefs allows you to match (a+)b\1 which matches n times a followed by b followed by n times a for any n>1. This is not a regular language (it's the poster child of a non regular language).

It is necessary and nearly sufficient that the backref references a group that contains a regexp that matches an arbitrarily long string or that it contains a * or +. The only exception (that I found) of a regexp of the form (A)B\1 where A is a finite language (could be replaced by a enumeration of all words that accepts them). You can convert it to word1+Bword1|word2+Bword2 etc. because A is finite.

Look-around groups don't remove the regularness of the regexp. A(?=B)C is the cross-section of regexes AB.* and AC and the cross-section of 2 regular languages is regular. Negative lookahead is similar except using the complement of B.* (complements of regular languages being regular). Lookbehind is exactly the same as well A(?<=B)C is the cross-section of AC and .*BC.

$\endgroup$
  • $\begingroup$ Is this necessary and sufficient? It looks to me like (a)\1, while using a backref, is equivalent to aa and therefore trivially Regular. I'm also wondering if lookahead assertions can use to recognize non-Regular languages. $\endgroup$ – MSalters Feb 13 '15 at 12:40
  • 1
    $\begingroup$ @MSalters: If you want to get really technical, (a)\1 is not a regular expression, but recognizes a regular language. $\endgroup$ – Jörg W Mittag Feb 14 '15 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.