Theoretische Informatik

Kontextfreie Grammatik

 aufwärts

Der wichtigste Grammatiktyp ist die kontextfreie Grammatik. Eine kontextfreie Grammatik entspricht einer Typ-2-Grammatik der Chomsky-Hierarchie. Kontextfreie Grammatiken sind ausdrucks­stark genug für Programmier­sprachen und ermöglichen zugleich effiziente Parsing-Verfahren.

Definition

Definition:  Sei G = (V, T, P, S) eine Grammatik, wobei V die Menge der Variablen ist, T die Menge der Terminal­zeichen, P die Menge der Produktionen und S das Startsymbol. Sei ferner A = V vereinigt T das Gesamt­alphabet.

Eine Produktion heißt kontextfrei, wenn sie von der Form

Xgeht über nachu

mit X Element V und u Element A* ist.

Die Grammatik G heißt kontextfrei, wenn jede ihrer Produktionen kontextfrei ist.

Eine Sprache heißt kontextfrei, wenn es eine kontextfreie Grammatik gibt, die sie erzeugt.

Die Produktionen einer kontext­freien Grammatik zeichnen sich also dadurch aus, dass auf ihrer linken Seite stets nur eine einzelne Variable steht. Auf der rechten Seite darf ein beliebiges Wort stehen, auch das leere Wort. Die Bezeichnung kontextfrei rührt daher, dass die Ersetzung Xgeht über nachu in jedem Kontext zulässig ist; d.h. wenn X irgendwo in einem Wort w vorkommt, darf es durch u ersetzt werden. Im Gegensatz dazu ist etwa aXbgeht über nachaub eine kontext­sensitive Produktion, die eine Ersetzung von X durch u nur im Kontext a...b erlaubt.

 

Beispiele

Beispiel:  Die kontextfreie Grammatik mit den Produktionen

Sgeht über nachaSb  |  ε

erzeugt die Sprache { anbn  |  n Element natürliche Zahlen0 }.

Beispiel:  Die kontextfreie Grammatik mit den Produktionen

expr geht über nachterm  |  term + expr
term geht über nachfactor  |  factor * term
factor geht über nachnumber  |  - number  |  ( expr )
number geht über nachdigit
digit geht über nach0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9

erzeugt die Sprache aller arithmetischen Ausdrücke mit einstelligen Zahlen und den Operationen Addition, Multi­plikation sowie Vorzeichen­umkehr. Die Variablen der Grammatik sind hier Wortsymbole wie expr, term usw. Das Startsymbol ist expr.

Kontextfreie Sprachen

Sprachen, die von kontext­freien Grammatiken erzeugt werden, heißen der Einfachheit halber kontextfreie Sprachen. Um zu zeigen, dass eine Sprache kontextfrei ist, genügt es, eine kontextfreie Grammatik anzugeben, die diese Sprache erzeugt. Wir werden sehen, dass es auch noch eine andere Möglichkeit gibt, und zwar einen nicht­deterministischen Stack­automaten anzugeben, der die Sprache erkennt.

Für den Beweis, dass eine Sprache nicht kontextfrei ist, steht als Hilfsmittel ähnlich wie bei den regulären Sprachen ein Pumping-Lemma für kontextfreie Sprachen, auch uvwxy-Theorem genannt, zur Verfügung. Eine einfache Sprache, die nicht kontextfrei ist, ist die Sprache { anbncn  |  n Element natürliche Zahlen }.

Die kontext­freien Sprachen bilden eine Sprachklasse der Chomsky-Hierarchie, daher werden sie auch als Typ-2-Sprachen bezeichnet.

Normalformen kontextfreier Grammatiken

Auf der linken Seite einer kontext­freien Produktion steht stets eine einzelne Variable. Auf der rechten Seite steht ein beliebiges Wort. Was geschieht, wenn der Form der rechten Seite Beschränkungen auferlegt werden? Wird dadurch die Ausdrucks­stärke der Grammatik einge­schränkt?

Wir haben bereits gesehen, dass die Beschränkung der rechten Seite der Produktionen auf die Form aY oder a oder ε mit a Element T und Y Element V die Ausdrucks­stärke der Grammatik einschränkt, nämlich auf die regulären Sprachen oder Typ-3-Sprachen.

Eine scheinbar geringfügige Lockerung dieser Beschränkung, indem statt aY auch aY0 ... Yk-1 zugelassen wird, führt zu keiner Ein­schränkung der Ausdrucks­stärke der Grammatik. Grammatiken in dieser Form, der sogenannten Greibach-Normalform, sind geeignet, beliebige kontextfreie Sprachen zu erzeugen.

Eine andere wichtige Normalform für kontextfreie Grammatiken ist die Chomsky-Normalform. Bei der Chomsky-Normalform stehen auf der rechten Seite jeder Produktion entweder nur genau zwei Variablen oder ein einzelnes Terminal­zeichen. Als Ausnahme ist die Produktion Sgeht über nachε erlaubt, um das leere Wort zu erzeugen.

 

Weiter mit:  [Chomsky-Normalform]   [Stackautomat]   [Kontextsensitive Grammatik]  oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.01.2003   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik