ChomskyHierarchie

ChomskyHierarchie, commonly known as the Chomsky hierarchy, is a framework for classifying formal grammars according to restrictions on their production rules. Introduced by Noam Chomsky in 1956, it identifies four levels of increasing expressive power: Type-3 regular grammars, Type-2 context-free grammars, Type-1 context-sensitive grammars, and Type-0 unrestricted grammars.

Each level corresponds to a class of formal languages and an associated automaton. Regular languages are recognized by finite automata (deterministic or nondeterministic). Context-free languages are recognized by pushdown automata and are generated by context-free grammars. Context-sensitive languages are recognized by linear bounded automata and generated by context-sensitive grammars. Unrestricted languages are recognized by unrestricted grammars and correspond to Turing machines.

The hierarchy forms a chain of inclusions: every regular language is context-free, every context-free language is context-sensitive, and every context-sensitive language is recursively enumerable. These inclusions are proper, meaning there exist languages that belong to a level but not to the preceding one. Classic examples illustrate the separations: regular languages include sets like (a|b)*, context-free languages include balanced parentheses like a^n b^n, and context-sensitive languages include a^n b^n c^n.

The Chomsky hierarchy is foundational in formal language theory, automata theory, and compiler design, where it helps guide the choice of grammars and parsing techniques. While it provides a useful map of computational power, it does not by itself capture all aspects of natural languages, which may require additional formalisms and probabilistic methods.