6 ms·

It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http:

It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.

jlarocco 10y ago
That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Obviously not the quickest or most intuitive way to do it, though. There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-Solutions/dp/1887187162/ https://www.amazon.com/Finite-Automata-Regular-Expressions-S...
- Chinjut 10y ago
  Sure, for a fixed arbitrary integer M. (Supposing the input is fed in in big-endian order, you just keep track of the remainder modulo M as each new bit comes in, updating it by turning r into (r * 2 + new bit) mod M. Since this only requires finite state, it is regular). But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in any nontrivial base.
  - deleted 10y ago
    [deleted]
  - jayshua 10y ago
    What do you mean by "non trivial base?"
    - Chinjut 10y ago
      Oh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.
      - jerf 10y ago
        It's worth pointing out that we are talking about representing numbers in unary, though. Or even more directly, plain ol' string length since the RE under discussion doesn't even care what symbols you are using, so "11111" = "abcde" under this RE.
jnordwick 10y ago
One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.
- conistonwater 10y ago
  But why should people care about what is regular in the formal sense? Rather, regular in this context would mean it can be recognized with a restricted type of algorithm, which resembles the formalism.
  - Chinjut 10y ago
    Is there a standard for which additional features one can add on top of regular expressions in the original limited sense and still be considered a regex?
    - conistonwater 10y ago
      I always understood it as being whatever can be straightforwardly tacked onto a typical DFA implementation. I though that's how people came up with it—whichever extras were the easiest to implement without mucking anything else up, so in a way they "came for free". (It's possible I misunderstood, I don't know for sure.)
      - Chinjut 10y ago
        Well, sure, but "whatever can be straightforwardly tacked on" is highly subjective, no?
        conistonwater 10y ago
        I don't think so, not too much anyway, I think the "software engineering" aspects of it would place reasonably strong constraints on what is desirable and on what is feasible (for a DFA). That's probably how the (informal?) consensus emerged.
jdnier 10y ago
For some great exposition on what "regular" actually means, check out http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html http://nikic.github.io/2012/06/15/The-true-power-of-regular-... "Thus the question arises: Can regular expressions match only regular grammars, or can they also match more? The answer to this is both yes and no"...
- umanwizard 10y ago
  "regular" has a fairly simple mathematical definition: the set of languages that can be matched with a finite state automaton. You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched. The following pseudocode is not bounded in memory -- can you guess why? bool is_prime(Number n) { for (Number i = 2; i < n; ++i) { if (n % i == 0) { return false; } } return true; }
  - Chinjut 10y ago
    The value i can take an a priori unbounded amount of memory. It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.
    - OskarS 10y ago
      Yeah, the O(1) refers to the size of the EXTRA memory you need, aside from the input. Defining it any other way would be strange. So, for instance, binary search over a sorted list needs O(log n) of memory (for the same reason as the prime algorithm, the pointer in the array is size O(log n) of the size of the array), even though the input is O(n).
      - Chinjut 10y ago
        Yup. Note that the method of specifically being fed the input sequentially, one by one, means that, for example, "Strings of odd length whose middle character is 'X'" does not comprise a regular language, even though one might naively reason this to be trivial to detect with O(1) memory ("Just go look at the middle character!").
etatoby 10y ago
Back-references may not be part of the mathematical definition of regular language, but they are definitely part of the traditional (UNIX) definition of regular expressions. The regexp in the article is perfectly compatible with UNIX grep: $ s=.; for i in `seq 50`; do echo $s | grep -qE '^.?$|^(..+)\1+$' || echo -n $i\ ; s=$s.; done; echo 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 (Tested on Mac OS X) In this case, bashing PCRE is completely off-topic.
- stplsd 10y ago
  Nobody is bashing PCRE. >but they are definitely part of the traditional (UNIX) definition of regular expressions. This is not exactly true. In 1968 or ealier Ken Thompson wrote first grep implementation using NFA simulation, an algorithm which is now known as Thompson Construction [1][2] There were no back-references in that grep. In 1975 Al Aho wrote an egrep which used DFA instead of NFA [3] (both NFA and DFA accepts regular languages, but in some cases DFA will have exponentially more states than the same regular language accepting NFA automata [4]) This added features such as alternation and grouping which was not supported by grep, but it not supported back-references. Current GNU grep have -E switch which accepts extended regular expressions as described in Posix standard. Theses extended regular expressions supports back-references as do PCRE available in grep with -P switch So no, back-references are not in traditional Unix definition of regular language. [1] https://en.wikipedia.org/wiki/Thompson%27s_construction https://en.wikipedia.org/wiki/Thompson%27s_construction [2] http://dl.acm.org/citation.cfm?doid=363347.363387 http://dl.acm.org/citation.cfm?doid=363347.363387 [3] http://dl.acm.org/citation.cfm?id=55333 http://dl.acm.org/citation.cfm?id=55333 [4] http://cs.stackexchange.com/questions/3381/nfa-with-exponential-number-of-states-when-deteminized http://cs.stackexchange.com/questions/3381/nfa-with-exponent...

jlarocco 10y ago

That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Obviously not the quickest or most intuitive way to do it, though. There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-Solutions/dp/1887187162/ https://www.amazon.com/Finite-Automata-Regular-Expressions-S...

Chinjut 10y ago
Sure, for a fixed arbitrary integer M. (Supposing the input is fed in in big-endian order, you just keep track of the remainder modulo M as each new bit comes in, updating it by turning r into (r * 2 + new bit) mod M. Since this only requires finite state, it is regular). But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in any nontrivial base.
- deleted 10y ago
  [deleted]
- jayshua 10y ago
  What do you mean by "non trivial base?"
  - Chinjut 10y ago
    Oh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.
    - jerf 10y ago
      It's worth pointing out that we are talking about representing numbers in unary, though. Or even more directly, plain ol' string length since the RE under discussion doesn't even care what symbols you are using, so "11111" = "abcde" under this RE.

jnordwick 10y ago

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

conistonwater 10y ago
But why should people care about what is regular in the formal sense? Rather, regular in this context would mean it can be recognized with a restricted type of algorithm, which resembles the formalism.
- Chinjut 10y ago
  Is there a standard for which additional features one can add on top of regular expressions in the original limited sense and still be considered a regex?
  - conistonwater 10y ago
    I always understood it as being whatever can be straightforwardly tacked onto a typical DFA implementation. I though that's how people came up with it—whichever extras were the easiest to implement without mucking anything else up, so in a way they "came for free". (It's possible I misunderstood, I don't know for sure.)
    - Chinjut 10y ago
      Well, sure, but "whatever can be straightforwardly tacked on" is highly subjective, no?
      - conistonwater 10y ago
        I don't think so, not too much anyway, I think the "software engineering" aspects of it would place reasonably strong constraints on what is desirable and on what is feasible (for a DFA). That's probably how the (informal?) consensus emerged.

jdnier 10y ago

For some great exposition on what "regular" actually means, check out http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html http://nikic.github.io/2012/06/15/The-true-power-of-regular-... "Thus the question arises: Can regular expressions match only regular grammars, or can they also match more? The answer to this is both yes and no"...

umanwizard 10y ago
"regular" has a fairly simple mathematical definition: the set of languages that can be matched with a finite state automaton. You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched. The following pseudocode is not bounded in memory -- can you guess why? bool is_prime(Number n) { for (Number i = 2; i < n; ++i) { if (n % i == 0) { return false; } } return true; }
- Chinjut 10y ago
  The value i can take an a priori unbounded amount of memory. It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.
  - OskarS 10y ago
    Yeah, the O(1) refers to the size of the EXTRA memory you need, aside from the input. Defining it any other way would be strange. So, for instance, binary search over a sorted list needs O(log n) of memory (for the same reason as the prime algorithm, the pointer in the array is size O(log n) of the size of the array), even though the input is O(n).
    - Chinjut 10y ago
      Yup. Note that the method of specifically being fed the input sequentially, one by one, means that, for example, "Strings of odd length whose middle character is 'X'" does not comprise a regular language, even though one might naively reason this to be trivial to detect with O(1) memory ("Just go look at the middle character!").

etatoby 10y ago

Back-references may not be part of the mathematical definition of regular language, but they are definitely part of the traditional (UNIX) definition of regular expressions. The regexp in the article is perfectly compatible with UNIX grep: $ s=.; for i in `seq 50`; do echo $s | grep -qE '^.?$|^(..+)\1+$' || echo -n $i\ ; s=$s.; done; echo 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 (Tested on Mac OS X) In this case, bashing PCRE is completely off-topic.

stplsd 10y ago
Nobody is bashing PCRE. >but they are definitely part of the traditional (UNIX) definition of regular expressions. This is not exactly true. In 1968 or ealier Ken Thompson wrote first grep implementation using NFA simulation, an algorithm which is now known as Thompson Construction [1][2] There were no back-references in that grep. In 1975 Al Aho wrote an egrep which used DFA instead of NFA [3] (both NFA and DFA accepts regular languages, but in some cases DFA will have exponentially more states than the same regular language accepting NFA automata [4]) This added features such as alternation and grouping which was not supported by grep, but it not supported back-references. Current GNU grep have -E switch which accepts extended regular expressions as described in Posix standard. Theses extended regular expressions supports back-references as do PCRE available in grep with -P switch So no, back-references are not in traditional Unix definition of regular language. [1] https://en.wikipedia.org/wiki/Thompson%27s_construction https://en.wikipedia.org/wiki/Thompson%27s_construction [2] http://dl.acm.org/citation.cfm?doid=363347.363387 http://dl.acm.org/citation.cfm?doid=363347.363387 [3] http://dl.acm.org/citation.cfm?id=55333 http://dl.acm.org/citation.cfm?id=55333 [4] http://cs.stackexchange.com/questions/3381/nfa-with-exponential-number-of-states-when-deteminized http://cs.stackexchange.com/questions/3381/nfa-with-exponent...