4 ms·

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

by 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...

by etatoby 10y ago

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...