Transcript
I.5. Kontextfreie Sprachen Zieht man in Betracht, dass BNF-Syteme gerade so beschaffen sind, dass auf der linken Seite immer genau ein Nichtterminal steht, so sind das also gerade die Ableitungsregeln einer kontextfreien Grammatik. Kontextfreie Grammatiken sind also für die Struktur von Programmiersprachen von prinzipieller Bedeutung. (Ein mittels BNF-Regeln abgeleitetes Terminalwort ist ein Programm in der jeweiligen Programmiersprache - mit gewissen Einschränkungen (siehe später).
Ableitungsbäume Ableitungen in kontextfreien Sprachen werden häufig Ableitungsbäume zugeordnet: Sei G = (N, T, S, P) eine kontextfreie Grammatik. Jeder Ableitung S ⇒ w1 ⇒ w2 ⇒ ... ⇒ wn wird ein Ableitungsbaum mit der Wurzel S wie folgt zugeordnet: (induktive Definition über n)
Für n = 0 besteht der Baum nur aus dem Knoten S
Ist Bn-1 der Ableitungsbaum von S ⇒ w1 ⇒ w2 ⇒ ... ⇒ wn-1 und entsteht wn aus wn-1 durch Anwendung der Regel A → w = x1 ... xl, xi ∈ N ∪ T, d.h. wn-1 = w’ A w’’, wn = w’ w w“, so erhält man den Ableitungsbaum Bn von S ⇒ w1 ⇒ ... ⇒ wn aus Bn-1, indem man den Knoten A in Bn-1 ersetzt durch den Baum A
x1
x2
x3
…
xl
Beispiel: Sei G = ({S}, {a}, S, {S → a, S → SS}) Der Ableitungsbaum für die Ableitung S ⇒ SS ⇒ aS ⇒ aa ist S
S
S
a
a
Offenbar können verschiedene Ableitungen den gleichen Ableitungsbaum besitzen; z.B. hat die Ableitung S ⇒ SS ⇒ Sa ⇒ aa den gleichen Ableitungsbaum.
Die Zuordnung von Ableitungen zu den Ableitungsbäumen wird eineindeutig, wenn man nur Linksableitungen zulässt:
Definition: Die Ableitung S ⇒ w1 ⇒ w2 ⇒ ... ⇒ wn heißt Linksableitung, wenn bei jedem Ableitungsschritt das am weitesten links stehende Nichtterminal vermöge einer Regel aus P ersetzt wird. Es ist aber möglich, dass es für ein Wort w ∈ L(G) verschiedene Linksableitungen gibt: Definition: Die (kontextfreie) Grammatik G heißt mehrdeutig, wenn ∃ w ∈ L(G), so dass w 2 verschiedene Linksableitungen besitzt. Anderenfalls heißt G eindeutig. Die kontextfreie Sprache L heißt eindeutig, wenn es eine eindeutige kontextfreie Grammatik G mit L = L(G) gibt. Anderenfalls heißt L mehrdeutig.
Beispiel: Die Grammatik G = ({S}, {a}, S, {S a, S SS}) ist mehrdeutig, denn es gibt für aaa die Linksableitungen S ⇒ SS ⇒ aS ⇒ aSS ⇒ aaS ⇒ aaa S ⇒ SS ⇒ SSS ⇒ aSS ⇒ aaS ⇒ aaa
mit den Ableitungsbäumen
S
S
S
a
S
S
S
S
S
S
S
a
a a a a Es ist L(G) = {ai: i ≥ 1}. L(G) ist (natürlich) regulär und wird z.B. von der Grammatik G1 = ({S}, {a}, S, {S→ a, S→ aS}) erzeugt. G1 ist eindeutig, also auch L(G) = L(G1).
Beispiel:
für eine mehrdeutige kontextfreie Sprache: L = {ai bj ck : i = j oder j = k} (o.B.)
Dagegen gilt: Satz 5.1.:
Jede reguläre Sprache ist eindeutig.
Beweis: Sei L regulär. Dann wird (nach Hauptsatz für die regulären Sprachen) L von einem DA akzeptiert. Im Beweisteil (i) ⇒ (ii) wird dann gerade eine eindeutige Grammatik G mit L = L(G) konstruiert.
Normalformen Es gibt für eine kontextfreie Sprache L viele verschiedene Grammatiken, die L erzeugen. Für Einsichten in die Struktur solcher Sprachen sind gewisse „Normierungen“ für erzeugende Grammatiken relevant. Hier sei nur eine erwähnt:
Definition: Eine kontextfreie Grammatik G = (N, T, S, P} ist in ChomskyNormalform, wenn alle Regeln von der Form X YZ oder X a mit X, Y; Z ∈ N, a ∈T sind.
Satz 5.2.:
Zu jeder kontextfreien Grammatik G = (N, T, S, P) mit ε ∉ L(G) gibt es eine äquivalente kontextfreie Grammatik G’ in Chomsky-Normalform. (o.B.)
Zum Pumping-Lemma für reguläre Sprachen gibt es ein Analogon: Satz 5.3.: (Pumping-Lemma für kontextfreie Sprachen) Sei L kontextfrei. Dann gibt es eine natürliche Zahl n, so dass für jedes Wort w ∈ L mit w ≥ n gilt: Es gibt w1, w2, w3, w4, w5, mit w = w1w2w3w4w5, w2w3w4≤ n, w2w4 ≠ ε,
und w1 w2i w3 w4i w5 ∈ L ∀i ≥ 0 .
Das P.-Lemma erlaubt häufig den Nachweis, dass eine Sprache nicht kontextfrei ist.
L={v v : v ∈ {0,1}*}
Beispiel:
Angenommen L wäre kontextfrei. Dann existierte eine Zahl n mit den Eigenschaften des Pumping-Lemmas. Sei w = 1 ...1 0 ...0 1 ... 1 0 ...0 ∈ L Dann ist also w = w1w2w3w4w5
n n n n mit w2w3w4≤ n.
Wenn w2w3w4 in der 1.Hälfte von w liegt, so endet im für i = 0 erzeugten Wort die 1. Hälfte mit 1, die 2. mit 0 (falls überhaupt: ein Wort gerader Länge entsteht). Wenn w2w3w4 in der 2.Hälfte von w liegt, so beginnt im für i = 0 erzeugten Wort die 1. Hälfte mit 1, die 2. Hälfte mit 0. Wenn w2w3w4 die Mitte überlappt, so beginnt im für i = 0 erzeugten Wort die 1. Hälfte mit n Einsen, die 2. nicht.
Bemerkung: Dieses Beispiel dokumentiert die mangelnde Kopierfähigkeit kontextfreier Grammatiken. Eine Konsequenz ist, dass die meisten Programmiersprachen nicht kontextfrei sind. Z.B. gibt es in Pascal die Bedingung, dass Anzahl und Typen der formalen Parameter und der aktuellen Parameter übereinstimmen müssen. Diese Bedingung lässt sich - unserem obigen Beispiel entsprechend - nicht durch BNF-Regeln formulieren! Bei Programmiersprachen erzeugt man durch kontextfreie Grammatiken (BNFRegeln) eine echte Obermenge der zulässigen Programme, aus denen die Programme durch verbale Einschränkungen ausgesondert werden.
Abschlusseigenschaften Satz 5.4.:
Kontextfreie Sprachen sind abgeschlossen gegenüber den regulären Operationen Vereinigung, Verkettung und Iteration.
Beweis: Seien L1 = L(G1) und L2 = L(G2) erzeugt von den kontextfreien Grammatiken G1= (N1, T1, S1, P1) , G2= (N2, T2, S2, P2) und o.B.d.A. sei N1∩N2 = ∅. Seien S3, S4, S5 neue Nichtterminale. G3 := (N1 ∪ N2 ∪ {S3}, T1 ∪ T2, S3, P3) mit P3 = P1 ∪ P2 ∪ {S3 → S1, S3 → S2}. Offenbar ist L(G3) = L1 ∪ L2.
G4 := (N1 ∪ N2 ∪ {S4}, T1 ∪ T2, S4, P4) mit P4 = P1 ∪ P2 ∪ {S4 → S1S2}. Offenbar ist L(G4) = L1L2. G5 := (N1 ∪ {S5}, T1, S5, P5) mit P5 = P1 ∪ {S5 → ε, S5 → S1S5}. Offenbar ist L(G5) = L1*.
Satz 5.5.:
Die kontextfreien Sprachen sind nicht abgeschlossen gegenüber Durchschnitten.
Beweis: L2 := {ai bi cj : i ≥ 1, j ≥1} L3 := {ai bj cj : i ≥ 1, j ≥1} L2 wird erzeugt von Grammatik mit den Produktionen S AB, A aAbab, B cBc
(Übung!!)
L3 wird erzeugt von Grammatik mit den Produktionen S CD, C aCa, D bDcbc Aber L2 ∩ L3 = { ai bi ci : i ≥ 1} ist nicht kontextfrei
(Übung!!) (Übung!)
