29
$\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?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
40
$\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.

Improve this answer
$\endgroup$
2
  • 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, 2011 at 17:06
  • 10
    $\begingroup$ The paper also shows that we must thank Kleen if regular languages are called "regular" and not "prehensible". $\endgroup$
    – gioele
    Oct 26, 2011 at 17:07

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.