Why are regular expressions called regular expressions?
+11
A:
Why are they called "regular expressions?"
Regular expressions trace back to the work of an American mathematician by the name of Stephen Kleene (one of the most influential figures in the development of theoretical computer science) who developed regular expressions as a notation for describing what he called "the algebra of regular sets." His work eventually found its way into some early efforts with computational search algorithms, and from there to some of the earliest text-manipulation tools on the Unix platform (including ed and grep). In the context of computer searches, the "*" is formally known as a "Kleene star."
From here.
Mitch Wheat
2009-06-10 13:13:24
... and that's why we have kleenex (google it) ;-)
corlettk
2009-06-10 13:19:02
+1. Although, most current implementations are not really regular anymore.
Mehrdad Afshari
2009-06-10 13:16:26
So, one might wonder, why regular languages are called "regular". Can you notice a circle in definition here? :P
volodyako
2009-06-10 13:18:24
@volodyako: Because there exists a regular *grammar* for those languages :P
Mehrdad Afshari
2009-06-10 13:23:21
and why is the grammer called 'regular' because of Stephen Kleen's work!
Mitch Wheat
2009-06-10 13:27:16
You've got to love one of the Regular Language definitions in Wikipedia: "... it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet". Of course!
Nick Pierpoint
2009-06-10 14:58:34
@Mehrdad: your reference to grammars is CIRCULAR as well. There exists a regular language for each regular grammar and vice versa; but this does not answer the question why this type of languages and grammars is called "regular".
volodyako
2009-06-10 20:47:53
@volodyako It is no more circular than door and doorway. Related items often contain references to each other. Read the Wikipedia articles for the set of properties that make something regular.
Chas. Owens
2009-06-12 14:00:21
@Chas. Owens (and others), "door" is a SUBstring of "doorway", which, I guess, is a kind of a set-theoretic argument. Assuming you were referring to grammars, there is MORE than a subset relation. In fact, there is an EQUIVALENCE relation (@Chas.: compare "door" and "DOOR", but this is only for you). Please read a more reliable reference, e.g., [S. Yu. Regular languages. Handbook of Formal Languages 1997]. Unfortunately [SO] is not handy enough to carry out such a discussion. In my Firefox, for example, it conceals trailing comments. Cheers :)
volodyako
2009-06-12 21:12:46
+3
A:
Because they used to in fact be regular. See http://en.wikipedia.org/wiki/Regular_language and http://en.wikipedia.org/wiki/Regular_expressions . Larry Wall advocates calling modern ones regexen because they are no longer anything like regular.
Matthew Flaschen
2009-06-10 13:14:43