How did each class of languages receive their name?

Question

If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable languages. There's also the class of recursive languages (which fits in between CSL and RE), but Chomsky didn't include this class in his hierarchy for whatever reason.

How did each of these classes receive its name? For instance, what does "recursively enumerable" mean in the context of a Turing machine being able to construct a RE language? What is context, and what differentiates "freeness" from "sensitiveness"? I can imagine that a language is "regular" because it can be generated by a regular expression, but I'm not sure if this is the reason behind the name.

(And a bonus question just for the fun of it: why didn't Chomsky include recursive languages in his hierarchy?)

Answer 1

Regular Languages:

There's some good discussion of this here: https://ell.stackexchange.com/questions/83917/how-did-regex-get-its-name

Context-Free vs Context-Sensitive Grammars:

For CFGs and CSGs, the "context" part is the idea that certain rules can be extended to apply based on relative positions of symbols rather than on single specific symbols.

Context-free grammars have substitutions that only allow you to replace single non-terminal characters at a time and does not consider the symbols around it. Since the context of where in a string the symbol occurs does not matter, we call the rule context-free.

Examples:

• $S \rightarrow foo$ is a context-free rule

• $aSb \rightarrow a foo b$ is not context-free due to it only contextually applying when $S$ is surrounded by both an $a$ on the left and $b$ on the right. It is instead, context-sensitive.

Context-sensitive grammars allow you to construct rules that operate on these situations where the relative locations of symbols matter. Since the rules can be specific respective to relative positions of terminal and non-terminal symbols, the rules are said to be context-sensitive.

Recursively Enumerable:

A set (language) is recursive if a Turing machine can tell you if a particular element is a member of that set or not in finite time. The name comes from a field called recursion theory, where recursion is a mathematically formal way to derive what computability is.

For example, the set of even binary numbers ($2\mathbb{Z}$) is a recursive set because I can take any number and test whether or not it is even in finite time on a Turing machine.

A set (language) is recursively enumerable if a Turing machine can enumerate over all the elements of that set. If an element you are testing for is in the set, you will eventually encounter it while enumerating through elements of the set. However, since the set can be infinitely large, you potentially will never be able to look at them all. If your element you are searching for is not actually in the set, you will neither be able to encounter it or know for certain that it is not in there.

Recursive languages are not part of the Chomsky hierarchy because the hierarchy is specific to grammars. It is not known if there is a natural grammar that captures recursive languages. See Decidable languages and unrestricted grammars?

Side Note: Typically we say that Turing machines recognize languages (not construct).