the Chomsky hierarchy
/ Chomsky is pronounced CHOM-skee /
The Chomsky hierarchy is the map of the whole subject: a set of four nested boxes that sort languages by how much computational power is needed to handle them. Picture four rings drawn one inside another, like Russian nesting dolls. The innermost ring holds the simplest languages, and each larger ring adds more languages by allowing a more powerful machine. Every later topic in this course lives somewhere on this map, which is why it is worth meeting early.
From smallest to largest, the four classes are: regular languages (innermost), context-free languages, context-sensitive languages, and recursively enumerable languages (outermost). Each is a strict subset of the next, so regular is inside context-free is inside context-sensitive is inside recursively enumerable, and each step really does add new languages that the smaller class cannot reach. Each class comes paired with a kind of machine that recognizes exactly it and a kind of grammar that generates exactly it: regular languages go with finite automata and regular expressions; context-free languages go with pushdown automata (a finite automaton plus one stack) and context-free grammars; context-sensitive languages go with linear-bounded automata; and recursively enumerable languages go with Turing machines, the most general model. So climbing the hierarchy is the same as giving the machine more memory and more freedom.
Two honest points keep this map useful rather than misleading. First, regular does NOT mean small or finite: a regular language can be infinite (for example all strings of a's, a*), it just means recognizable with finite memory. Second, the strictness of the inclusions is a real theorem, proved by exhibiting separating examples: a^n b^n is context-free but not regular, and a^n b^n c^n is context-sensitive but not context-free. Beyond the outermost ring sit the languages that no Turing machine can even recognize, which is where computability theory and the halting problem take over.
a* is regular. a^n b^n is context-free but not regular. a^n b^n c^n is context-sensitive but not context-free. The set of all Turing machines that halt on a given input is recursively enumerable but not decidable.
Four strictly nested classes, each paired with a recognizing machine and a grammar.
Regular does not mean finite. A regular language can be infinite; the word means recognizable by a finite automaton. The four inclusions are strict, a proven fact, not just a convention.