3
$\begingroup$

In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes on (in Section 6) to demonstrate that regular (type 2, context-free) grammars can generate more languages than type 3 (finite state) grammars.

However, in every other computer-science reference I've read, type 3 languages (those recognizable by a finite state machine) are called "regular". (For example, see the Wikipedia entry for Chomsky Hierarchy.)

My question is, when did "regular" shift from referring to type 2 languages to type 3 languages? And why? (Was it intentional, or did someone mis-quote Chomsky at some point and that stuck?)

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ You should post your answer as an answer. Also, this might sound crazy, but Chomsky is still alive. Have you considered asking him? He may or may not answer you, but there is no harm in asking. Also, he is probably the only living person who could truly answer your question. linguistics.mit.edu/user/chomsky $\endgroup$
    – Ben I.
    Apr 21, 2017 at 20:58
  • 2
    $\begingroup$ Another thing worth noting: what Chomsky calls a regular grammar soon got to be known as Chomsky Normal Form, while a regular grammar is another form of context-free grammar that does have the property of describing exactly the regular languages. $\endgroup$
    – reinierpost
    Apr 21, 2017 at 22:33
  • $\begingroup$ (This invalidates the question title, as far as I'm concerned: "regular" was used to refer to CNF grammars in this particular paper, but it didn't catch on, so start to is misleading.) $\endgroup$
    – reinierpost
    Apr 21, 2017 at 22:45
  • 1
    $\begingroup$ Thank you, @reinierpost, that what Chomsky called "regular" is now known as CNF helps clarify the terminology puzzle for me. Though I do wonder if Chomsky intended a connection between his "regular grammar" and Kleene's "regular event". I think I will take Choirbean's reasonable advice and ask him via email (I'll update my answer below when/if I hear back). $\endgroup$
    – cristoper
    Apr 21, 2017 at 23:09

1 Answer 1

Reset to default
5
$\begingroup$

I found an answer, at least a partial one, hinted at in Footnote 10 of Chomsky's paper where he refers to a 1956 paper by Kleene in which Kleene describes "regular events" -- a language recognized by finite state machines.

So it would seem the common usage of "regular language" today traces back to Kleene's "regular events" rather than to Chomsky's "regular grammar".

Furthermore, as renierpost pointed out in a comment, what Chomsky called a "regular" grammar in 1959 is now known as Chomsky normal form.

Edit: I asked Professor Chomsky via email whether he intended his "regular grammar" to have a connection to Kleene's "regular events". He replied: "Long time ago and I don't recall. I suppose just a coincidence."

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.