Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A regular expression to check for prime numbers (2007)

noulakaz.net

Post reply on HN
Print view View original

11–20 of 102 posts

Re: A regular expression to check for prime numbers (2007)

#11

Post by wongarsu »

CoastalCoder wrote: post #10
tylerhou wrote: post #7

Technically not a regular expression, as (intuitively) the backreference has to “count” the number of 1’s that were matched. Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers). The 2022 discussion has a more formal proof using the pumping lemma.

Agreed. I read the post because the result was so shocking. TIL that the computer-sciencey definition of RE isn't the only one in use.

When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and time.

https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expres...

Re: A regular expression to check for prime numbers (2007)

#12

Post by disconcision »

wongarsu wrote: post #11
CoastalCoder wrote: post #10

Earlier quoted context omitted.

Agreed. I read the post because the result was so shocking. TIL that the computer-sciencey definition of RE isn't the only one in use.

When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and t…

funnily enough the original POSIX regular expressions (BRE) were strictly less powerful than regular expressions (CS sense), lacking a general alternation operator (though one was provided in ERE)

Re: A regular expression to check for prime numbers (2007)

#13

Post by shagie »

pkoird wrote: post #9

Clever! I'm kinda being pedantic but I guess using \1 makes it a non-regular expression? I'm not even sure if it's CFG anymore.

Correct. The \1 holds some external state... but this can be overcome with a different architecture. If you want to start down that rabbit hole.

Extending finite automata to efficiently match Perl-compatible regular expressions https://www.researchgate.net/publication/221325349_Extending...

> Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of two types of finite state machines. Non-deterministic finite automata (NFAs) have minimal storage demand but have high memory bandwidth requirements. Deterministic finite automata (DFAs) exhibit low and deterministic memory bandwidth requirements at the cost of increased memory space. It has already been shown how the presence of wildcards and repetitions of large character classes can render DFAs and NFAs impractical. Additionally, recent security-oriented rule-sets include patterns with advanced features, namely back-references, which add to the expressive power of traditional regular expressions and cannot therefore be supported through classical finite automata.

> In this work, we propose and evaluate an extended finite automaton designed to address these shortcomings. First, the automaton provides an alternative approach to handle character repetitions that limits memory space and bandwidth requirements. Second, it supports back-references without the need for back-tracking in the input string. In our discussion of this proposal, we address practical implementation issues and evaluate the automaton on real-world rule-sets. To our knowledge, this is the first high-speed automaton that can accommodate all the Perl-compatible regular expressions present in the Snort network intrusion and detection system.

----

The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG (you can write CFGs that can't be matched by a PCRE - ([{}]) matching, a^nb^n and so on). So the question that gets interesting is "can every PCRE be matched by a CFG?"

Is it a fork? or is it a non-integer language?

https://en.wikipedia.org/wiki/Chomsky_hierarchy

> Note that the set of grammars corresponding to recursive languages is not a member of this hierarchy; these would be properly between Type-0 and Type-1.

So there's a language between the Turing machine and the linear bounded Turing machine that matches a context sensitive language.

Is the PCRE something between Type-2 and Type-3? or is it a Type-3+I?

https://en.wikipedia.org/wiki/Formal_grammar#Other_forms_of_...

> Many extensions and variations on Chomsky's original hierarchy of formal grammars have been developed, both by linguists and by computer scientists, usually either in order to increase their expressive power or in order to make them easier to analyze or parse. ...

Re: A regular expression to check for prime numbers (2007)

#16

Post by chrismorgan »

wongarsu wrote: post #11
CoastalCoder wrote: post #10

Earlier quoted context omitted.

Agreed. I read the post because the result was so shocking. TIL that the computer-sciencey definition of RE isn't the only one in use.

When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and t…

Although general PCRE syntax has clearly won, that’s distinct from the infinite-memory-and-time matter. Engines that don’t use backtracking and can search in linear time (O(regex-size × search-text-size)) have been making a serious comeback in recent years, at only the cost of not supporting lookaround assertions or backreferences. For example, the re2 library, or Rust’s regex crate, both of which are very popular.

Re: A regular expression to check for prime numbers (2007)

#17

Post by retrac »

tylerhou wrote: post #7

Technically not a regular expression, as (intuitively) the backreference has to “count” the number of 1’s that were matched. Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers). The 2022 discussion has a more formal proof using the pumping lemma.

> Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers).

The machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high.

Informally, regular expressions like in Perl are a kind of string rewriting. And many string rewriting rules, if they can be iteratively applied, are Turing-complete (with the usual caveat about infinite storage and time). The usual definition of a regular expression excludes that kind of iterative application, though. It's just a matching pattern; rewriting is technically outside of the concept of a regular expression.

Re: A regular expression to check for prime numbers (2007)

#18

Post by aenis »

In case anyone is wondering, gpt4 provides the same solution. It takes some prodding though, and you get treated with a lecture of how inefficient it is before it provides the solution.

"Apologies for any confusion before, and I understand the nature of your request now. It's a fun challenge to think about! While it's not practically useful or efficient, and it is actually quite limited, a creative theoretical solution exists that involves regular expressions. This specific solution only works for very small numbers due to the inherent limitations of regex. It's based on the principle that a number is prime if it cannot be expressed as a product of two smaller natural numbers. We represent the number as a repeated string of 1s, then check for repeating sub-patterns.

For instance, this Perl regex checks if a number, represented as unary (a string of 1s), is prime:

perl Copy code /^1?$|^(11+?)\1+$/ In this regex:

^1?$ checks for the case where you have zero or one '1', which represent the numbers 0 and 1, neither of which are prime. ^(11+?)\1+$ attempts to match the input with a repeating group of '1's. If a match is found, the number is not prime, because a repeating subgroup of '1's represents a divisor. This pattern should be used in a negative sense: if a string of 1s (representing your number in unary form) matches this pattern, it's not prime. If it doesn't match, then it is prime.

Again, this is quite impractical for real use cases as the unary representation is extremely inefficient, and the computation grows quickly with larger numbers, but it's a neat way of showing how flexible and powerful regular expressions can be."

Re: A regular expression to check for prime numbers (2007)

#19

Post by knome »

chrismorgan wrote: post #16
wongarsu wrote: post #11

Earlier quoted context omitted.

When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and t…

Although general PCRE syntax has clearly won, that’s distinct from the infinite-memory-and-time matter. Engines that don’t use backtracking and can search in linear time (O(regex-size × search-text-size)) have been making a serious comeback in recent years, at only the cost of not supporting lookaround assertions or backreferences. For example, the re2 library, or Rust’s regex crate, both of which are very popular.

Russ Cox has an excellent write up on it.

"Regular Expression Matching Can Be Simple And Fast" (2007)

https://swtch.com/~rsc/regexp/regexp1.html

Re: A regular expression to check for prime numbers (2007)

#20

Post by dang »

shric wrote: post #6

(2007) Previous discussions (with >25 comments): 2015: https://news.ycombinator.com/item?id=9039537 (67 comments) 2022: https://news.ycombinator.com/item?id=30564287 (121 comments)

Thanks! Macroexpanded:

A regular expression to check for prime numbers (2007) - https://news.ycombinator.com/item?id=30564287 - March 2022 (121 comments)

A regular expression to check for prime numbers - https://news.ycombinator.com/item?id=9039537 - Feb 2015 (67 comments)

A regular expression to check for prime numbers - https://news.ycombinator.com/item?id=1486158 - July 2010 (13 comments)

Regex to check for prime numbers - https://news.ycombinator.com/item?id=707236 - July 2009 (9 comments)

A regular expression to check for prime numbers - https://news.ycombinator.com/item?id=58780 - Sept 2007 (8 comments)

Post reply on HN