13
$\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$
5
  • 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, 2015 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, 2015 at 12:01
  • 1
    $\begingroup$ Related questions: 1, 2, 3. $\endgroup$
    – Raphael ♦
    Feb 16, 2015 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, 2015 at 16:09
  • 3
    $\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, 2019 at 11:48

1 Answer 1

Reset to default
16
$\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$
4
  • 1
    $\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, 2015 at 12:40
  • 2
    $\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, 2015 at 0:19
  • $\begingroup$ Look-around aren't always a simple intersection: ^A*(?=AB)B matches nothing, while the intersection of ^A*AB and ^A*B matches AAB. Though I'm pretty sure they're still regular. $\endgroup$
    – assembly_wizard
    May 14, 2022 at 23:36
  • $\begingroup$ @assembly_wizard yeah I was assuming that there is no overlap where A and B could be. More formally A(?=B)C is A concatenated with intersection of B and C. (with the same reasoning) $\endgroup$
    – ratchet freak
    May 16, 2022 at 11:46

Your Answer

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

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