Chomsky hierarchy
The Chomsky hierarchy is a classification of formal languages based on their generative power. It consists of four levels: Type 0 (recursively enumerable languages), Type 1 (context-sensitive languages), Type 2 (context-free languages), and Type 3 (regular languages). Each level can generate languages that the levels below it can also generate, but not vice versa.
At the top of the hierarchy, Type 0 languages can be recognized by a Turing machine, while Type 3 languages can be recognized by finite automata. This hierarchy helps in understanding the complexity of different languages and the computational models that can process them.