The regular, context-free, decidable, and recognizable language-class ladder

For a fixed finite alphabet $\mathrm{\Sigma }$, the language-class ladder used on this page records the containments $\{\text{regular languages over }\mathrm{\Sigma }\}\subseteq \{\text{context-free languages over }\mathrm{\Sigma }\}\subseteq \{\text{decidable languages over }\mathrm{\Sigma }\}\subseteq \{\text{recognizable languages over }\mathrm{\Sigma }\}\mathrm{.}$

Here:

• regular means recognized by some DFA, by Regular languages;
• context-free means generated by some CFG, by The language generated by a CFG;
• decidable means decided by some Turing machine, and
• computably enumerable means recognizable by some Turing machine, by Languages recognized and decided by a Turing machine.

• On this page, "computably enumerable" and "recognizable" are synonymous.

• This four-class ladder is not the classical Chomsky hierarchy. The classical hierarchy inserts the context-sensitive languages as its type-$1$ class; decidable languages are used here instead as a broader comparison class.

• The hierarchy concerns classes of languages, not classes of machine descriptions.