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:37PM (#12459086)

I'll say to you what I said above, but even moreso: Er... I'm not sure what you're saying here, 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 DasIch on Friday September 09, 2016 @04:25AM (#12460429)

You can actually quite easily add features to regular expressions, that are typically excluded while still being actually regular. Examples would be an `and` or a `not` operator.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by btilly on Friday September 09, 2016 @04:59PM (#12466003)

What I am saying is that you can come up with a lot of extensions of the basic regular expression language. But there is no subjectivity at all in whether the extensions can be implemented by a DFA. Either you can, or you can't.

[ Parent | on HN ]