27
$\begingroup$

Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages.

I suppose that, in the beginning, the adjective "regular" has been used to differentiate that type of languages from other "non-regular" or somehow abnormal languages. If so, what where these other types, and what was their non-regularity?

$\endgroup$
39
$\begingroup$

A quick check of the sources reveals that Chomsky called the levels of his hierarchy just “type 0, type 1, type 2, type 3”. He mentions in a footnote that his type 3 corresponds to “regular events” of Kleene. Kleene wrote there: 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.)

It would thus appear that the term is a historical accident, and in any case has no bearing on the relation of regular languages to context-free languages.

$\endgroup$
  • 6
    $\begingroup$ The Kleene's paper (an awesome paper, thank you!) contrasts "regular" events with "indefinite" events (that depend on another event that may have happened in an infinite past) and "definite" events (that depend on at most $p-l-1$ past moments). "Regular" events are those who depend on "the value" of the last moment $p$. $\endgroup$ – gioele Oct 26 '11 at 17:06
  • 9
    $\begingroup$ The paper also shows that we must thank Kleen if regular languages are called "regular" and not "prehensible". $\endgroup$ – gioele Oct 26 '11 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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