Why are regular expressions called "regular" expressions?

Asked 10/6, 2009 at 13:11 Answered 10/6, 2009 at 13:14

Why are regular expressions called regular expressions?

Matchmark answered 10/6, 2009 at 13:11 Comment(6)

After reading the links, I still don't know if the name came from regular sets or regular languages. – Bailsman 10/6, 2009 at 13:19

@Nick Pierpoint: "Regular expressions are "regular" because they are defined by a finite set of symbols - a formal language." THIS IS WRONG. Regular expressions easily define infinite languages. Example: a* => {"", "a", "aa", ...} – Cyclone 10/6, 2009 at 15:51

@volodyako - I see that they define an infinite language, but aren't they defined by a finite number of symbols - granted you could put an infinite number of these symbols together. Is that what you mean by wrong? I suppose I meant a "finite set of distinct symbols". – Matchmark 10/6, 2009 at 16:32

@Nick Pierpoint: the way you are trying to give an informal definition is highly ambiguous. See your favourite wikipedia definition that you quoted below: "the free monoid on a finite alphabet", - and try to understand it because it makes much more sense than what you've written. – Cyclone 10/6, 2009 at 19:44

Regular Expressions are equivalent to DFA's...Deterministic FINITE Automaton. They are buy definition finite...just because you can endlessly pumps values into one doesn't make them infinite. – Horodko 6/5, 2011 at 22:31

In case you're still active and - like me - are not satisfied with the deferral that they describe regular languages (...then why are regular languages called "regular"?), it appears to be a historic vestige due to Kleene who first described regular languages and could not come up with something more descriptive. – Duna 22/8, 2014 at 23:26

They are based on regular languages.

Overword answered 10/6, 2009 at 13:14 Comment(12)

Why did it take 3 answers to get to "regular languages" :P – Noah 10/6, 2009 at 13:14

i wondered that as well, was just about to post the same link, +1 – Pocket 10/6, 2009 at 13:16

+1. Although, most current implementations are not really regular anymore. – Southing 10/6, 2009 at 13:16

So, one might wonder, why regular languages are called "regular". Can you notice a circle in definition here? :P – Cyclone 10/6, 2009 at 13:18

@volodyako: Because there exists a regular grammar for those languages :P – Southing 10/6, 2009 at 13:23

and why is the grammer called 'regular' because of Stephen Kleen's work! – Cribriform 10/6, 2009 at 13:27

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! – Matchmark 10/6, 2009 at 14:58

@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". – Cyclone 10/6, 2009 at 20:47

@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. – Cutout 12/6, 2009 at 14:0

@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 Stack Overflow is not handy enough to carry out such a discussion. In my Firefox, for example, it conceals trailing comments. Cheers :) – Cyclone 12/6, 2009 at 21:12

Oliver N., was that a joke or do you really not grasp the circularity of your non-answer? Same question for @volodyako. Life's questions must be so clear to you guys, like, why is an orange called an orange? Why because they are orange of course -- jeez. – Massie 14/2, 2018 at 17:32

@RickO'Shea There is nothing circular about this answer. – Hennebery 14/2, 2018 at 17:36

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.

Cribriform answered 10/6, 2009 at 13:13 Comment(1)

... and why are the sets regular? I wonder if the inability to recognize a circular solution is some sort of adaptation to prevent brain-lock. Maybe those folks would become catatonic if their brains could not accept a "it's turtles all the way down" style response. – Massie 14/2, 2018 at 17:37

What Kleene meant by “regular events” was an event processed by a set of nerve cells–an event of perception or of thought. Kleene’s paper says nothing about computers, programming, matching patterns in text or searching for text on a computer the paper was not even composed on or near a computer, as the typescript would indicate.

As you may read in an excellent history of Regular Expressions, in the fine Christopher M. Kelty's book [Logical Instruments: Regular Expressions, AI and thinking about thinking] (2011)1

Regular Expressions originate in neurology and neurobiology in the work of McCulloch in 1930s. Later in 1940s, what McCulloch and Pitts achieved was far more influential in engineering, computer science and mathematics than it was in biology or neuroscience. Works that take McCulloch and Pitts logical calculus of nerve nets as a starting point have been extraordinarily bountiful in mathematics and computer science. Formalization entirely, beginning at least with McCulloch and Pitts themselves, whose 1947 paper “How we know universals” and the 1959 paper they wrote with Lettvin and Maturana, “What the Frogs Eye Tells the Frog’s brain” [Lettvin et al., 1959, Pitts and McCulloch, 1947] both abandon the strict formal equivalence with propositional calculi or the Turing machine, in favor of more complex biological models which are less amenable to logical manipulation.

McCulloch’s interest was initially in finding what he hypothesized as a “psychon”—or atomic unit of neural activity, which he first sought in his physiological research conducted during the 1930s in partnership with Yale physiologist J.G. Dusser de Barenne. In the early 1940s, McCulloch was introduced to Walter Pitts by Jerome Lettvin, and thereby to Nicholas Rashevsky’s Mathematical Biology group at the University of Chicago, where Walter Pitts had been actively working on models of neural activity with Rashevsky and mathematician Alston Householder.

The collaboration between the two was lopsided, at best. McCulloch was in his forties, Pitts was 17; McCulloch had spent his career in physiology and philosophy, Pitts was by various and sometimes unreliable accounts a mathematical prodigy who had run away from his home in Detroit and met Bertrand Russell in a park in Chicago [Smalheiser, 2000, Schlatter and Aizawa, 2008]. Together, however, they managed to piece together something that met in the middle, a paper that demonstrated the formal equivalence between a plausible model of neural activity, and a logical calculus.

Part of McCulloch and Pitts inspiration for their paper was Turing’s machine. As Tara Abraham puts it “Turing was able to define the complicated process of computation in ’mechanical’ terms, with the notion of a simple algorithm so exhaustive, rigorous and unambiguous that the executor would need no ’mathematical knowledge’ to carry out its task.” [Abraham, 2003, 18] This identification of computation with an automatic procedure provided the inspiration for McCulloch and Pitts to model a set of nerves as something that could also calculate “in the absence of mathematical knowledge.”

In hindsight, what McCulloch and Pitts achieved was far more influential in engineering, computer science and mathematics than it was in biology or neuroscience.

Kleene, Stephen C. (1956), "Representation of events in nerve nets and finite automata"

famous 1959 paper by J. Y. Lettvin, H. R. Maturana, W. S. McCulloch and W. H. Pitts, What the Frog's Eye Tells the Frog's Brain

In 1968, Ken Thompson published a short “Programming Techniques” paper for the CACM in which he described the “Regular Expression Search Algorithm”

Thimbu answered 10/6, 2009 at 13:11 Comment(0)

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.

Orlov answered 10/6, 2009 at 13:14 Comment(0)

A brief history of regular expressions

Welldone answered 10/6, 2009 at 13:13 Comment(0)

Recommended topics

Hot tags