Die Chomsky-Hierachie umfasst vier Typen von Grammatiken:
- Typ-o-Grammatik
- Typ-1-Grammatik
- Typ-2-Grammatik
- Typ-3-Grammatik
Typ-0-Grammatik
Die Menge der durch die Typ-0-Grammatik erzeugbaren Wörter stellt die größte Menge an erzeugbaren Wörtern dar. Die Typ-0-Grammatik ist nicht eingeschränkt und umfasst somit alle anderen Grammatiken. Eine Grammatik vom Typ 0 ist ganz einfach eine formale Grammatik.
Typ-1-Grammatik
Die Menge der durch die Typ-1-Grammatik der Chomsky-Hierachie erzeugbaren Wörter stellt eine Teilmenge der Menge der von der Typ-0-Grammatik erzeugbaren Wörter dar. Eine Typ-1-Grammatik der Chomsky-Hierachie ist kontextsensitiv.
Typ-2-Grammatik
Eine Typ-2-Grammatik der Chomsky-Hierachie ist kontextfrei und die Menge der durch die Typ-2-Grammatik erzeugbaren Wörter stellt eine Teilmenge der Wörter dar, die durch die Typ-0- und Typ-1-Grammatik erzeugt werden können.
Typ-3-Grammatik
Eine Typ-3-Grammatik kann durch einen regulären Ausdruck dargestellt werden, erzeugt eine reguläre Sprache und stellt die am stärksten eingeschränkte Grammatik der Chomsky-Hierachie dar. Typ-3-Grammatiken sind die regulären Grammatiken.
Zusammenfassend gilt also:
Typ-3-Sprachen sind Teilmenge der Typ-2-Sprachen sind Teilmenge der Typ-1-Sprachen sind Teilmenge der Typ-0-Sprachen
Diese Aufteilung bzgl. der Mächtigkeit der Mengen orientiert sich also an der generativen Kapazität der Grammatiken.