Regular Expression That Checks If A Number Is Prime

Re:Regular Expression That Checks If A Number Is Prime by etatoby on Friday September 09, 2016 @05:46AM (#12460715)

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.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by stplsd on Friday September 09, 2016 @06:54AM (#12460983)

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

[2] http://dl.acm.org/citation.cfm?doid=363347.363387

[3] http://dl.acm.org/citation.cfm?id=55333

[4] http://cs.stackexchange.com/questions/3381/nfa-with-exponent...

[ Parent | on HN ]