Since Regular languages $\subset$ Context-free languages, then Regular languages are Context-free languages?

Why is the terminology so different then?

To me these seem like a totally different class of languages, based on the terminology, even though they're "variations" of Context-free languages.

How about calling Regular languages Regular context-free languages?


closed as unclear what you're asking by David Richerby, Shaull, Anton Trunov, Evil, D.W. Dec 29 '15 at 5:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ What terminology do you mean? $\endgroup$ – Hendrik Jan Dec 28 '15 at 12:09
  • $\begingroup$ A language is just a set of words, so the "terminology", i.e. the corresponding computational model, is irrelevant. As it turns out, regular languages are indeed context free. The two easiest way to see this is either via pushdown automata, which can easily simulate standard automata (simply by not using the stack), or via context-free grammars, which can simulate automata as right-linear grammars. $\endgroup$ – Shaull Dec 28 '15 at 12:10
  • $\begingroup$ @HendrikJan The terminology where "regular languages" and "context-free languages" are terms. I think it's confusing not to declare "regular languages" as "regular context-free languages". $\endgroup$ – mavavilj Dec 28 '15 at 12:10
  • 2
    $\begingroup$ @mavavilj By that logic, even the Chomsky hierarchy would mandate REG to be called "regular context-free context-sensitive type-0 language" (not accounting for nesting), and there are many, many more classes that contain REG. In other words, your questions becomes nonsensical once you realize that there are more than two classes of languages. $\endgroup$ – Raphael Dec 28 '15 at 12:47

Much of the terminology is due to historic accidents, cast in marble well before the relationship between the different sets of languages was considered, let alone known. Nobody is able to change it now, get over it.

Many labels in mathematics are mostly arbitrary, not unlike people's names. Yes, regularity would be nicer. No, it isn't a realistic option.

  • 1
    $\begingroup$ Whether you define regular and context-free langauges in terms of automata or grammars, it's trivial to see that every regular langauge is context-free. So I doubt there's ever been a time when regular and context-free languages were both known but the relationship between them wasn't. But +1 anyway since this is a good description of the general situation. $\endgroup$ – David Richerby Dec 28 '15 at 14:34

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