Re:Regular Expression That Checks If A Number Is Prime
by Chinjut on Thursday September 08, 2016 @09:21PM
(#12459011)
Well, sure, but "whatever can be straightforwardly tacked on" is highly subjective, no?
[ Parent
| on HN ]
Re:Regular Expression That Checks If A Number Is Prime
by btilly on Thursday September 08, 2016 @09:26PM
(#12459032)
No, it is not.
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.
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.
Re:Regular Expression That Checks If A Number Is Prime
by duaneb on Thursday September 08, 2016 @09:29PM
(#12459046)
Not really. A graph is either a valid DFA or it is not. At that point, it's a matter of tooling in terms of "straightforward"ness.
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.
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.
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".
Re:Regular Expression That Checks If A Number Is Prime
by conistonwater on Thursday September 08, 2016 @09:23PM
(#12459018)
I don't think so, not too much anyway, I think the "software engineering" aspects of it would place reasonably strong constraints on what is desirable and on what is feasible (for a DFA). That's probably how the (informal?) consensus emerged.