Index

Wahlpflichtthemen

2. Formale Sprachen (9)


Chomsky-Grammatiken

Einführung

Um den Aufbau von Sprachen und deren Kategorisierung besser verstehen zu können, hat Chomsky (1959) neue Ideen entwickelt, die zur Einteilung in die Chomsky-Grammatiken verschiedener Typen führten.

Die Grundlage der Chomsky-Grammatiken besteht in der Einteilung des Alphabets E in Terminalsymbole und Nichtterminalsymbole.
Terminalsymbole sind hierbei die Zeichen und Wörter, aus denen eine Sprache letzendlich aufgebaut ist.
Nichtterminalsymbole stellen eine Abstrahierung der Wörter zu Klassen von Wörtern ähnlicher Bedeutung dar. Man spricht auch von syntaktischen Kategorien. Hierdurch wird der korrekte Aufbau, also die Syntax einer Sprache beschrieben.

Als Beispiel diene ein Satz der deutschen Sprache:
"Die Frau liest ein Buch."
Die aufgeführten Wörter und der Punkt sind hierbei Terminalsymbole.
Die Syntax könnte zunehmend verfeinert beschrieben werden durch:
<Aussagesatz>
<Aussage>.
<Subjekt> <Prädikat> <Objekt>.
<Artikel><Nomen> <Verb> <Artikel> <Nomen>.
<bestimmter Artikel> Frau liest <unbestimmter Artikel> Buch.
Die Frau liest ein Buch.

An diesem Beispiel ist die Ableitungstechnik bereits erkennbar:
Nichtterminalsymbole können wieder durch Nichtterminalsymbole oder durch Terminalsymbole ersetzt werden. Terminalsymbole werden nicht weiter ersetzt, die Ersetzung wird hier also beendet (terminiert). Es können hierzu Ersetzungsregeln angegeben werden, wie sie bereits bei den Semi-Thue-Systemen eingeführt wurden. Eine andere Darstellung ist die Backus-Naur-Form (BNF), die häufig bei den Syntaxregeln von Programmiersprachen Verwendung findet.

 

[Index] [Zurück/Semi-Thue-Systeme]


Autor: Jürgen Dehmer
Letzte Änderung: