Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi-Thue-Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau angewandt, um zum einen eine formale Sprache eindeutig zu beschreiben (d. h. um eindeutig festzulegen, ob ein Wort Element einer Sprache ist, oder nicht) und um zum anderen Eigenschaften dieser formalen Sprachen zu untersuchen bzw. zu beweisen. Formale Grammatiken werden in der Chomsky-Hierarchie klassifiziert.