Theoretische Informatik - ganz praktisch

4Grammatiken und die Chomsky-Hierarchie

Für eine Menge von „Zeichenketten“ oder „Wörtern“ haben wir in den vorausgegangenen Kapiteln den Namen „formale Sprache“ kennengelernt. Eine natürliche Sprache wie Deutsch oder Englisch besteht aber nicht nur aus einer festen Menge an Zeichenketten (das sind sowohl Vokabeln, umgangssprachlich „Wörter“, als auch ganze Sätze), sondern es gehören auch Grammatiken dazu, die festlegen, wie korrekte Zeichenketten (sowohl Vokabeln als auch Sätze) gebildet werden. Nach dem Philosophen und Linguisten Noam Chomsky (*1928) sind die sogenannten Chomsky-Grammatiken benannt, welche einen formalen Rahmen zur Generierung von Wörtern einer (formalen) Sprache bieten.

Historisch war ihr Zweck durchaus, als Grammatiken für ...