Regular Expression That Checks If A Number Is Prime

Re:Regular Expression That Checks If A Number Is Prime by Chinjut on Thursday September 08, 2016 @09:36PM (#12459083)

Er... I'm not sure what you're saying here, in that it doesn't seem to be engaging with what I was saying, or trying to say, so I'll clarify what I was saying. What I mean is, we all agree on what DFAs are, and so we all agree on what regular languages in the original, Kleene sense are. But once we start admitting non-regular languages into our notion of "regular expression" because they're "straightforwardly tacked on", it's unclear what the limits are supposed to be.

I'm not actually a fan of using "regular expressions" in a sense broader than that of Kleene's regular, DFA-accepted languages, to be clear. That is exactly what I've been questioning.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by JoshTriplett on Thursday September 08, 2016 @09:46PM (#12459126)

I think the intent of the parent comments was to say that it's fine to consider a regex a standard "regular expression" in the mathematical sense if it still translates to a DFA and matches a regular language. For instance, mathematical regular expressions typically only include '*' (0 or more), not '+' (1 or more). However, you can still translate a regex including '+' to a DFA. Likewise arbitrary repetition mechanisms like {m,n}, case-insensitivity, and other features that add convenience without actually matching non-regular languages.

On the other hand, backreferences can allow matching non-regular languages.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by Chinjut on Thursday September 08, 2016 @09:55PM (#12459159)

Ah, yeah, I see now that that is indeed probably what they meant; thanks! In that case, yes, I'm sympathetic to that, using regex to just mean "Anything that ultimately describes a regular language".

[ Parent | on HN ]