Chomsky Hierarchy
A classification scheme in formal language theory that divides grammars into four levels: regular, context-free, context-sensitive and unrestricted. Each level corresponds respectively to the recognition capability of finite-state automata, pushdown automata, linear bounded automata and Turing machines, yielding a nested hierarchy of increasingly expressive grammar classes.
Timeline (last 90 days)
A formal grammar is a formalized system in computation theory that describes the rules of language generation; the most classic classification is the Chomsky hierarchy: regular grammars, context-free grammars, context-sensitive grammars, and unrestricted grammars, which respectively correspond to the classes of languages recognizable by finite-state automata, pushdown automata, linear bounded automata, and Turing machines.