Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata.
He defines a regular language as anything that can be described by a finite automata. But I could not find where he explains why a regular language is called "regular?" What is the origin of the term "regular" in this context?
NOTE: I am a novice so please try to explain in simple terms!
As Kaveh says in a comment, Kleene bestowed the name way back when he kicked off automata theory and formal languages. I believe the term was arbitrary, though it has been many years since I read his original paper.
Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such as geometric or other analogies or metaphors, and sometimes arbitrarily. Just look at "group", "ring", "space", "sheaf", "atlas", "manifold", "field" and so on.
In fact, the term "regular" for finite-state languages, while still prevalent in automata theory, is not used very much in its algebraic cousin, finite semigroup theory or abstract algebra in general. Why? Because the term was already taken for a semigroup that is close to a group in a specific technical sense, so you couldn't match up a regular language in Kleene's sense with a corresponding regular semigroup. Third, Kleene defined another kind of event called "definite", which was much studied for a while, but has turned out to be not particularly fruitful. Today, finite sets of language play the role of definite events as the basis for regular events.
The preferred term in algebra is "rational" for both Kleene's class of languages and the more general semigroups and monoids. That usage also reflects an important analogy between the term "rational" in algebra as the solution of a linear equation with integer coefficients and the concept of rational power series in automata and formal language theory.
Additional information. Kleene's original paper of 1951, entitled "Representation of events in nerve nets and finite automata" may be found here. On p. 46 it settles the arbitrariness of the term "regular" with this statement:
We shall presently describe a class of events which we will call "regular events". (We would welcome any suggestions as to a more descriptive term.)
Apparently, nobody came up with a more descriptive term. ;-)
As is often the case with seminal papers which lead to the intensive development of whole new areas, the terminology and concepts are almost unrecognizable in today's terms. First, the paper was about models of neurons, hence the use of "events" instead of "languages" or "sets". The term "events" persisted well into the 60's and 70's, even after the importance of Kleene's concepts for automata and formal languages vastly outweighed any value for neuroscience.
Second, there are some mathematical differences, such as defining what came to be called "Kleene Closure" as a binary operation, equivalent to $a^*b$, instead of the simpler unary operation $a^*$ or $a^+$ that we use today. Kleene's motivation was to avoid the empty string (or event with duration zero in his terms). That was a remarkably prescient intuition since subsequent theory has shown how crucial the choice is to include or exclude the empty string from definitions in many contexts. Third, Kleene defined a concept called "definite events" and developed regular events from them, but nowadays we use finite sets for the purpose. Definite events were studied for a while, but have turned out to be far less important than regular events/sets/languages.
Anyway, a complete reading of this paper is probably not worth anyone's time today, except for historical purposes. I just skimmed it for the crucial definitions and ideas, and that was fun.
I have always understood the term "regular" to mean that it is based on a pattern repeating itself. After you have enumerated all strings of a certain length, you have seen them all. There will be nothing new afterwards.
(It is only a vague intuition of course.)
