Theoretische Informatik

Kontextsensitive Grammatik

 aufwärts

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, ferner A = V vereinigt T das Gesamt­alphabet.

Die Grammatik G heißt kontext­sensitiv, wenn jede Produktion von der Form

uXvgeht über nachuyv

mit X Element Vy Element A+ und u, v Element A* ist.

Als Ausnahme ist die Produktion S Pfeil nach rechts ε erlaubt, wobei dann S nicht auf der rechten Seite einer Produktion vorkommen darf.

Eine Sprache heißt kontext­sensitiv, wenn es eine kontext­sensitive Grammatik gibt, die sie erzeugt.

Die Bezeichnung kontext­sensitiv (im Gegensatz zu kontextfrei) rührt daher, dass die Ersetzung X Pfeil nach rechts y nur im Kontext u...v zulässig ist; d.h. wenn X irgendwo in einem Wort w vorkommt, darf es nur dann durch y ersetzt werden, wenn direkt links von X das Teilwort u und direkt rechts von X das Teilwort v steht.

 

Kuroda-Normalform

Definition:  Eine kontext­sensitive Grammatik ist in Kuroda-Normalform, wenn jede Produktion von der Form

Xgeht über nacha    ,
Xgeht über nachY    ,
Xgeht über nachYZ    oder
WXgeht über nachYZ

mit a Element T und W, X, Y, Z Element V ist.

Als Ausnahme ist die Produktion Sgeht über nachε erlaubt, um das leere Wort ε zu erzeugen; dann darf S aber nicht auf der rechten Seite einer Produktion vorkommen.

 

Satz:  Zu jeder kontext­sensitiven Sprache gibt es eine kontext­sensitive Grammatik in Kuroda-Normalform.

Eine kontextfreie Grammatik in Chomsky-Normalform ist offen­sichtlich in Kuroda-Normalform.

Monotone Grammatik

Definition:  Eine Grammatik heißt monoton, wenn für alle Produktionen ugeht über nachv gilt

|ukleiner gleich |v|

Bei einer Ersetzung von u durch v in einem Wort w wird also w niemals kürzer.

Als Ausnahme ist die Produktion Sgeht über nachε erlaubt; dann darf S aber nicht auf der rechten Seite einer Produktion vorkommen.

Satz:  Zu jeder kontext­sensitiven Sprache gibt es eine monotone Grammatik.

Eine kontext­sensitive Grammatik in Kuroda-Normalform ist offen­sichtlich monoton. Kontextfreie Grammatiken in Chomsky- und in Greibach-Normalform sowie rechts­lineare Grammatiken sind ebenfalls monoton.

Beispiele

Die Sprache L = { anbncn  |  n Element natürliche Zahlen } ist nicht kontextfrei. Dies lässt sich mit dem Pumping-Lemma für kontextfreie Sprachen zeigen. L ist aber kontext­sensitiv.

Eine monotone Grammatik für L ist die folgende:

Sgeht über nachaSBc  |  abc
cBgeht über nachBc
bBgeht über nachbb

Eine Grammatik in Kuroda-Normalform für L ist folgende:

Sgeht über nachAX  |  AY
Xgeht über nachSY
Ygeht über nachZC
AZgeht über nachAB
BZgeht über nachBB
CZgeht über nachZC
Ageht über nacha
Bgeht über nachb
Cgeht über nachc

 

Weiter mit:  up

 

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

Hochschule Flensburg
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