Chomsky-Hierarchie
Chomsky-Hierarchie

==== Definition ====
Typ-2-Grammatiken werden auch ''kontextfreie Grammatiken'' genannt. Es sind Grammatiken, für die gelten muss:  In jeder Regel der Grammatik muss also auf der linken Seite genau ein nicht-terminales Symbol stehen und auf der rechten Seite kann eine beliebige nicht-leere Folge von terminalen und nichtterminalen Symbolen aus dem gesamten Vokabular  stehen.
Außerdem kann wie bei Typ-1-Grammatiken die Ausnahmeregel  zugelassen werden, wenn  auf keiner rechten Seite einer Regel vorkommt.
Kontextfreie Grammatiken werden oft so definiert, dass die rechte Seite auch leer sein darf, also . Solche Grammatiken erfüllen nicht mehr alle Eigenschaften von Typ-2-Grammatiken und stünden nicht mehr in der von Chomsky definierten Hierarchie. Sie erfüllen aber die Bedingungen von monotonen Grammatiken.