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.
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.
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.
You can invent a variety of notations to describe a DFA. But you can't change the formal definition of a DFA, or what kinds of things a DFA can match without making it not a DFA.