Unterschied zwischen regulärer Grammatik und kontextfreier Grammatik

Grammatik bedeutet für Linguisten und Computerprogrammierer etwas ganz anderes als für die meisten Menschen. Während die meisten von uns sich Grammatik als eine Reihe von Etikette-Regeln für den gesellschaftlich akzeptablen Sprachgebrauch vorstellen, betrachten Linguisten und Programmierer Grammatik als etwas viel Mächtigeres: Die Reihe von Regeln, die alle möglichen Ausdrücke in einem gegebenen realen oder künstlichen erzeugen können Sprache oder Fragment einer Sprache. Reguläre und kontextfreie Grammatiken sind die beiden logisch möglichen Grammatiktypen und unterscheiden sich in den Arten von Regeln, die sie zulassen, und den Arten von Ausdrücken, die sie erzeugen können.

Ursprünge

Der Linguist Noam Chomsky entwickelte in seinem 1959 erschienenen Werk „On Certain Formal Properties of Grammars“ die Begriffe kontextfreier und regulärer Grammatiken. Er postulierte die Existenz mehrerer grundlegender Grammatiktypen, die sich durch die Komplexität der linguistischen Ausdrücke, die sie erzeugen können, voneinander unterscheiden. Reguläre Grammatiken sind einfacher und weniger produktiv als kontextfreie Grammatiken.

Unterschied zwischen Regeln Rule

Reguläre und kontextfreie Grammatiken unterscheiden sich in der Art der zulässigen Regeln. Die Regeln kontextfreier Grammatiken erlauben mögliche Sätze als Kombinationen von nicht zusammenhängenden Einzelwörtern (die Chomsky „Terminals“ nennt) und Wortgruppen (Phrasen, oder was Chomsky „Nicht-Terminals“ nennt). Kontextfreie Grammatiken erlauben einzelne Wörter und Phrasen in beliebiger Reihenfolge und erlauben Sätze mit beliebig vielen einzelnen Wörtern und Phrasen. Reguläre Grammatiken hingegen lassen nur einzelne Wörter zusammen mit einer einzigen Phrase pro Satz zu. Darüber hinaus müssen Phrasen in regulären Grammatiken in jedem von der Grammatik erzeugten Satz oder jeder Phrase an derselben Position erscheinen.

Strukturen

Da kontextfreie Grammatiken eine größere Bandbreite an Regeln zulassen als reguläre Grammatiken, können sie eine größere Bandbreite an Strukturen erzeugen als reguläre Grammatiken. Sie können beispielsweise verschiedene mögliche Phrasenstrukturen beinhalten, wie zum Beispiel „ein Mädchen aus der Stadt mit Geldproblemen“ (hier variieren die Strukturen je nachdem, ob „mit Geldproblemen“ die Stadt oder das Mädchen beschreibt). Reguläre Grammatiken können dies nicht. Sie können vielmehr nur einfache Ausdrücke erzeugen, die aus einer Kette einzelner, strukturell unabhängiger Wörter und möglicherweise einer einzigen größeren Phrase bestehen (wie „sehr, sehr kluge Leute“).

Verwendet

Kontextfreie Grammatiken werden in der Verarbeitung natürlicher Sprache verwendet, um Sprachdaten zu generieren und zu parsen, da sie viele der definierenden Merkmale der menschlichen Sprache erfassen können, wie beispielsweise ihr Potenzial für unendlich rekursive Strukturen. Reguläre Grammatiken, die nur eine Teilmenge der Ausdrücke kontextfreier Grammatiken erzeugen, werden auch für die Verarbeitung natürlicher Sprache verwendet. Sie können jedoch nur kurze und grammatikalisch einfache sprachliche Ausdrücke replizieren oder verarbeiten, wie z. B. kurze Ausdrücke, die typischerweise im informellen Dialog vorkommen.