TEIL 3: FORMALE SPRACHEN

15. Termersetzungssysteme und

Chomsky-Grammatiken

In der Linguistik beschreibt man die Syntax von Sprachen mit Hilfe von Gram-matiken. Definiert man eine Sprache als die Menge ihrer Satze, so kann maneine Grammatik als Regelwerk zur Beschreibung der syntaktisch korrektenSatze der Sprache, d.h. der Syntax der Sprache, auffassen:

Durch eine Folge von Anwendungen von Regeln der Grammatik lasst sichdie syntaktische Korrektheit eines gegebenen Satzes nachweisen (Verifikati-on, Akzeptor), oder – alternativ – lassen sich durch Ausfuhrung aller mogli-chen Anwendungsfolgen der Regeln alle korrekten Satze der Sprache erzeugen(Aufzahlung, Erzeugendensystem, generative Grammatik).

In der Theorie der formalen Sprachen betrachtet man verschiedene Typenvon Grammatiken zur Beschreibung von formalen Sprachen und vergleichtdie hierdurch gegebenen Sprachdarstellungen bezuglich ihrer Machtigkeit undQualitat.

Hierbei werden wir uns auf generative Grammatiken beschranken, d.h. aufGrammatiken als Erzeugendensysteme, und hierbei insbesondere die verschie-denen Typen von Chomsky-Grammatiken diskutieren. Korrespondierende Ve-rifikationsmethoden oder Akzeptoren werden durch Angabe aquivalenter Ma-schinenkonzepte gegeben.

1

Wir werden im Folgenden einen Satz als Zeichenreihe, d.h. als

ein Wort auffassen. Die korrekt gebildeten Satze einer Sprache

bilden daher eine Menge von Wortern, d.h. eine Sprache (in dem

von uns benutzten formalen Sinn).

Die formale, mathematische Beschreibung von generativen Gram-

matiken basiert auf Termersetzungssystemen (oder Semi-Thue-

Systemen).

2

TERMERSETZUNGSSYSTEME (SEMI-THUE-SYSTEME)

DEFINITION. Ein Termersetzungssystem oder Semi-Thue-

System ist ein Paar E = (Σ, P ) bestehend aus

• einem Alphabet Σ und

• einer endlichen Relation P ⊆ Σ∗ ×Σ∗.Die Elemente r = (u, v) von P heißen die Regeln

(oder Produktionen) von E, wobei u die Pramisse

und v die Konklusion von r ist.

Fur eine Regel r schreiben wir meist u → v statt (u, v).

3

SEMANTIK VON E = (Σ, P )

Die Semantik eines Termersetzungssystems E = (Σ, P ) lasst sich auf dieEinschritt-Relation ⇒E ⊆ Σ∗ ×Σ∗ mit

w ⇒E w′ ⇔ ∃(u, v) ∈ P ∃x, y ∈ Σ∗(w = xuy & w′ = xvy)

zuruckfuhren, die einen Herleitungsschritt (Ersetzungsschritt) beschreibt.

Hieraus erhalt man wie ublich (durch n-fache bzw. endliche Iteration) dien-Schritt- und Mehrschritt-Relationen ⇒n

E bzw. ⇒∗E .

Gilt w ⇒∗E w′ (w ⇒n

E w′), so sagt man, dass w′ aus w (in n-Schritten) herleitbarist.

Eine Herleitung (der Lange n) ist eine Folge von Wortern w0, . . . , wn mitw0 = w, wi ⇒E wi+1 (i < n) und wn = w′.

Weiter nennt man w′ eine Normalform von w, wenn w′ aus w herleitbar istund nicht weiter umgeformt werden kann, d.h. es kein w′′ mit w′ ⇒E w′′ gibt.

4

BEISPIEL: ARITHMETISCHE TERME

Als Beispiel geben wir ein Termersetzungssystem zur Beschreibung der korrektgeklammerten, variablenfreien arithmetischen Terme uber den Binarzahlen an.

Induktive Definition der Terme:

(T1) Jede Binarzahl ist ein Term.(T2) Sind t1, t2 Terme, so ist auch (t1 + t2) ein Term.(T3) Sind t1, t2 Terme, so ist auch (t1 ∗ t2) ein Term.

Diese Definition basiert noch auf der folgenden induktiven Definition von(Binarwortern und) Binarzahlen:

(Z1) 0 und 1 sind Binarzahlen und Binarworter.(Z2) Ist w ein Binarwort, so sind 0w und 1w ebenfalls Binarworter

und 1w eine Binarzahl.

Wir wandeln nun diese induktiven Definitionen in ein entsprechendes Termer-setzungssystem um.

5

Termersetzungssystem E = (Σ, P ) zur Beschreibung der arithmetischen Ter-me:

• Alphabet Σ = {0,1,+, ∗, (, ), T, Z, W}(T = Term, Z= Binarzahl, W = Binarwort)

• Die Regeln P entsprechen gerade den Klauseln der induktiven Definition:

(R1) T → Z (T1)(R2) T → (T + T ) (T2)(R3) T → (T ∗ T ) (T3)(R4) Z → 0 (Z1)(R5) Z → 1 (Z1)(R6) W → 0 (Z1)(R7) W → 1 (Z1)(R8) W → 0W (Z2)(R9) W → 1W (Z2)(R10) Z → 1W (Z2)

Die Normalformen von W , Z und T sind dann gerade die nichtleeren Binar-worter, die Binarzahlen und die Terme.

6

Eine Herleitung eines Terms t aus T erhalt man, indem man den Strukturbaumvon t von oben nach unten (top down) durchlauft und die entsprechenden Re-geln anwendet. Z.B. besitzt der Term t = ((10∗0)+11) folgende Herleitung:

T ⇒ (T + T ) (R2)⇒ ((T ∗ T ) + T ) (R3)⇒ ((Z ∗ T ) + T ) (R1)⇒ ((Z ∗ Z) + T ) (R1)⇒ ((Z ∗ Z) + Z) (R1)⇒ ((1W ∗ Z) + Z) (R10)⇒ ((1W ∗ 0) + Z) (R4)⇒ ((1W ∗ 0) + 1W ) (R10)⇒ ((10 ∗ 0) + 1W ) (R6)⇒ ((10 ∗ 0) + 11) (R7)

(Die Stelle, an der die angegebene Regel angewendet wird, ist jeweils unterstrichen.)

Man kann diese Herleitung auch durch einen Herleitungsbaum darstellen, da die Pramissen nuraus einem Buchstaben bestehen (s. Tafel / Skript). Dabei enthalten die Sohne die Konklusioneiner Regel, der Vater deren Pramisse. Die Blatter von links nach rechts gelesen ergebendann das hergeleitete Wort. (In seiner Grundstruktur entspricht dieser Herleitungsbaum demStrukturbaum von t.)

7

In dem vorhergehenden Beispiel werden zu den Grundzeichen, die in denTermen vorkommen, (syntaktische) Variablen hinzugenommen, die fur dasgewunschte syntaktische Objekt (T = Term) bzw. die benotigten Hilfsobjekte(W = Binarwort, Z = Binarzahl) stehen. Die aus dem Zeichen T herleitbarenWorter, die nur die eigentlichen Grundzeichen enthalten, sind dann geradedie arithmetischen Terme.

Da man ahnliche Beobachtungen allgemein macht, hat Chomsky den Be-griff des Termersetzungssystems entsprechend erweitert, und so den fur dieSprachtheorie grundlegenden, nach ihm benannten Grammatikbegriff gepragt:

• Das Alphabet wird in zwei Teile aufgeteilt: Das Alphabet derTerminalzeichen bestehend aus den eigentlichen Zeichen und dasAlphabet der (syntaktischen) Variablen oder Nichtterminalzeichen.

• Eine der Variablen wird als Startzeichen oder Axiom ausgezeichnet.

• Die dargestellte Sprache besteht gerade aus den Terminalwortern(d.h. den aus Terminalzeichen gebildeten Wortern), die aus demAxiom herleitbar sind.

8

CHOMSKY-GRAMMATIKEN

DEFINITION. Eine (Chomsky-)Grammatik G = (N, T, P, S) besteht aus:

• dem (nichtterminalen) Alphabet N bestehend aus den(syntaktischen) Variablen (oder Nichtterminalzeichen),

• dem (terminalen) Alphabet T bestehend aus den Terminalzeichen ,

• der endlichen Menge P ⊆ ((N ∪ T )∗ − T ∗)× (N ∪ T )∗ vonRegeln oder Produktionen und

• dem Axiom oder Startzeichen S ∈ N .

Von der Pramisse u einer Regel (u, v) verlangt man hier also, dass sie zumin-dest eine Variable enthalt, wahrend die Konklusion v ein beliebiges (mogli-cherweise leeres) Wort aus Terminal- und/oder Nichtterminalzeichen ist.(Wir schreiben wieder i.a. u → v statt (u, v)).

Ein nur aus Terminalzeichen bestehendes Wort heißt auch Terminalwort (oderSatz), ein beliebiges Wort w (das moglicherweise auch Variablen enthalt)Satzform. Kommt hierbei in w tatsachlich eine Variable vor, sprechen wir voneiner echten Satzform.

9

DIE VON EINER GRAMMATIK ERZEUGTE SPRACHE

Der Grammatik G = (N, T, P, S) liegt das Termersetzungssystem

EG = (N ∪ T, P )

zugrunde.

Der Herleitungsbegriff fur EG wird hiermit direkt auf G ubertragen. Z.B.schreiben wir

w∗⇒G

w′

(und sagen, dass w′ in G aus w herleitbar ist), falls

w∗⇒

EG

w′

gilt, also w′ in EG aus w herleitbar ist.

Die von G erzeugte Sprache L(G) (uber dem Alphabet T ) ist die Menge deraus dem Axiom herleitbaren Terminalworter, d.h.

L(G) = {w ∈ T ∗ : S∗⇒G

w}.

10

BEMERKUNGEN. Ist die Grammatik G aus dem Kontext bekannt, so schrei-ben wir ⇒∗ statt ⇒∗

G(etc.).

Weiter sagen wir, dass L eine Chomsky-Sprache ist, falls L von einer Chomsky-Grammatik erzeugt wird, und bezeichnen mit CH (CHk) die Menge allerChomsky-Sprachen (uber dem k-aren Alphabet).

11

BEISPIELE

BEISPIEL 1. Das Termersetzungssystem zur Erzeugung der arithmetischenTerme lasst sich in folgende Grammatik G = (N, T ′, P, S) uberfuhren:

• N = {T, W, Z}

• T ′ = {0,1,+, ∗, (, )}

• P enthalt die Regeln (R1)-(R10) von oben

• S = T

12

BEISPIEL 2. Die Sprache L = {0m1n : m, n ≥ 1} wird von der GrammatikG = (N, {0,1}, P, S) erzeugt, wobei N = {S, T} und P aus den vier Regeln

(G1) S → 0S(G2) S → 0T(G3) T → 1T(G4) T → 1

besteht.

BEMERKUNG. 1. Enthalt eine Grammatik mehrere Regeln mit derselbenPramisse, so fasst man diese mitunter zusammen. Im obigen Beispiel schreibtman z.B.:

S → 0S | 0TT → 1T | 1.

2. Um zu zeigen, dass eine Grammatik G eine Sprache L erzeugt, d.h., dassL = L(G) gilt, muss man die Inklusionen L ⊆ L(G) und L(G) ⊆ L zeigen. ZumNachweis von L ⊆ L(G) muss man zu jedem Wort w ∈ L eine G-Herleitungangeben. Dies lasst sich i.a. leicht zeigen, da die Grammatik ja gerade soentworfen wurde, dass dies moglich ist. Der Nachweis von L(G) ⊆ L ist meistschwieriger. Hier zeigt man in der Regel durch die geeignete Wahl von Inva-rianten, dass keine ungewunschten Worter in G herleitbar sind.

13

Wir illustrieren einen (einfachen) Korrektheitsbeweis am BEISPIEL 2:

L ⊆ L(G): Fur gegebenes m, n ≥ 1 mussen wir eine Herleitung von 0m1n aus S angeben:

S ⇒m−1 0m−1S (m− 1× (G1))⇒ 0mT (1× (G2))⇒n−1 0m1n−1T (n− 1× (G3))⇒ 0m1n (1× (G4))

L ⊆ L(G): Zum Nachweis von L(G) ⊆ L charakterisieren wir durch Herleitungsinduktion, d.h.durch Induktion nach k, die in k Schritten aus S herleitbaren Satze und Satzformen:

S ⇒k w ⇒ w = 0kS oder

∃m ≥ 1 ∃n ≥ 0 (k = m + n & w = 0m1nT ) oder

∃m ≥ 1 ∃n ≥ 1 (k = m + n & w = 0m1n)

(1)

Fur terminales w zeigt dies, dass S ⇒k w impliziert, dass w ∈ L gilt. Fur k = 0 ist dieBehauptung klar, da S ⇒0 w nur fur w = S = 00S gilt. Im Induktionsschritt von k nach k +1betrachtet man den letzten Schritt in der Herleitung S ⇒k+1 w, d.h. S ⇒k w′ ⇒ w. Wirdeine der Regeln (G1) oder (G2) angewendet, so muss w′ die Variable S enthalten, also nachInduktionsvoraussetzung w′ = 0kS gelten. Es ist dann aber w = 0k+1S bzw. w = 0k+1T vonder verlangten Gestalt. Wurde die Regel (G3) oder (G4) angewendet, muss entsprechend Tin w′ vorkommen und daher w′ = 0m1nT fur geeignete m ≥ 1, n ≥ 0 mit m + n = k gelten.Hier gilt dann w = 0m1n+1T oder w = 0m1n+1, weshalb wegen m + (n + 1) = k + 1 das Wortw wieder eine der gewunschten Gestalten hat.

14

BEISPIEL 3. Die Sprache L = {0n1n : n ≥ 1} variiert die Sprache in Beispiel2, indem zusatzlich gefordert wird, dass der 0-Block und der 1-Block gleicheLange haben. Diese Sprache wird von der Grammatik G = ({S}, {0,1}, P, S)mit der Produktionenmenge

S → 0S1 | 01

erzeugt.

BEISPIEL 4. Die Sprache L = {0n1n0m : n, m ≥ 1} wird von der GrammatikG mit Axiom S und Regeln

S → TU

T → 0T1 | 01

U → 0U | 0erzeugt. Alternativ konnte man auch folgende Regeln wahlen:

S → U0

U → U0 | 0T1

T → 0T1 | λ

15

Bei den bisherigen Beispielen haben die Pramissen der Regeln

jeweils nur aus einer Variablen bestanden. Wir betrachten nun

noch eine Sprache, bei der dies nicht moglich ist:

16

BEISPIEL 5. Die Sprache L = {0n1n0n : n ≥ 1} unterscheidet sich vomvorhergehenden Beispiel dadurch, dass alle Blocke nun gleich lang sind. EineGrammatik G = (N, {0,1}, P, S), die L erzeugt, besitzt die Variablen

N = {S, A, B, C, A, B, C}

und enthalt folgende Regeln:

(E1) S → SABC(E2) S → ABC

(V1) BA → AB(V2) CA → AC(V3) CB → BC

(S1) AA → 0A(S2) AB → 0B(S3) BB → 1B(S4) BC → 1C(S5) CC → 0C(S6) C → 0

17

IDEE: Die Variablen A, A bzw. B, B bzw. C, C sind jeweils Platzhalter fur eine 0

im 1. Teil bzw. eine 1 im 2. Teil bzw. eine 0 im 3. Teil eines hergeleiteten Worts

w = 0n1n0n (n ≥ 1). In der 1. Phase der Herleitung wird mit Hilfe der Erzeu-

gungsregeln (E1) und (E2) die erforderliche Anzahl von Platzhaltern geschaf-

fen (S ⇒∗ ABC(ABC)n−1). In der 2. Phase werden die Variablen mit Hilfe der

Vertauschungsregeln (V1) - (V3) sortiert (ABC(ABC)n−1 ⇒∗ AAn−1BnCn).

Schließlich werden in der 3. Phase die Variablen mit Hilfe der Substitutions-

regeln (S1)-(S6) durch ihre terminalen Werte ersetzt. Dabei darf nur die am

Anfang dieser Phase ganz links stehende uberstrichene Variable ersetzt wer-

den. Gleichzeitig wird die rechte Nachbarvariable uberstrichen, sodass diese im

nachsten Schritt ersetzt werden kann, usw. bis die letzte Variable C uberstri-

chen und im letzten Schritt direkt durch 0 ersetzt wird. D.h. die Ersetzung der

Variablen erfolgt durchgehend von links nach rechts (AAn−1BnCn ⇒∗ 0n1n0n).

18

ZUR MACHTIGKEIT DER CHOMSKY-GRAMMATIKEN

SATZ. Zu jeder Turingmaschine M kann man effektiv eine Chom-

sky-Grammatik G angeben, die die von M akzeptierte Sprache er-

zeugt, und umgekehrt. Insbesondere sind also die von Chomsky-

Grammatiken erzeugten Sprachen gerade die rekursiv aufzahlba-

ren Sprachen: CH = RA.

Hierbei konnen wir o.B.d.A. davon ausgehen, dass die von einer (nichttota-len) Turingmaschine M akzeptierte oder erkannte Sprache genau die Einga-beworter enthalt, fur die die Maschine terminiert. (D.h. wir ersetzen eventuellvorkommende verwerfende Stoppzustande durch Endlosschleifen.)

19

BEWEISIDEE

1. Jede Chomsky-Sprache L(G) ist rekursiv aufzahlbar.

Sei G = (N, T, P, S). Eine Herleitung eines Wortes w ∈ T ∗ in G hat die Form

S ⇒ v1 ⇒ v2 ⇒ . . . ⇒ vn ⇒ w (n ≥ 0, vi ∈ (N ∪ T )∗),

kann also als Wort uber dem Alphabet Σ = N ∪ T ∪ {⇒} aufgefasst werden. Da wir furWorter v und v′ durch Mustervergleich uberprufen konnen, ob v durch Anwendung einerRegel in v′ uberfuhrbar ist, also v ⇒ v′ gilt, kann man effektiv feststellen, ob ein Wort z ∈ Σ∗

eine Herleitung beschreibt, und im positiven Fall lasst sich das hergeleitete Wort effektivbestimmen. D.h. die Menge

H = {(w, z) : w ∈ T ∗, z ∈ Σ∗, z Herleitung von w}

ist entscheidbar - also nach der Church-Turing-These rekursiv. Da

w ∈ L(G) ⇔ ∃z((w, z) ∈ H)

gilt, ist also L(G) nach dem Projektionslemma rekursiv aufzahlbar.

Durch Formalisierung des Arguments erhalt man eine (nichttotale) TM M , die L(G) akzep-tiert.

20

BEWEISIDEE (Fortsetzung)

2. Jede von einer (nichttotalen) 1-Band-Turingmaschine M erkannte Sprache

L(M) ⊂ Σ∗ wird von einer Chomsky-Grammatik G erzeugt.

Wie wir schon fruher gesehen haben, konnen die Konfigurationen von M durch Worterbeschrieben werden. Weiter kann wegen der Lokalitat der Turingmaschinen-Operationen derUbergang von einer Konfiguration zur Nachfolgekonfiguration durch eine Regel beschriebenwerden. Wir konnen daher M als ein Termersetzungssystem auffassen.

Eine Grammatik G, die L(M) erzeugt, arbeitete anschaulich wie folgt, wobei eine Spurendar-stellung mit 2 Spuren verwendet wird:

(a) Aus dem Axiom S lasst sich fur jedes Wort w ∈ Σ∗ das Wort w erzeugen, bei dem in deroberen Spur w und in der unteren Spur die zugehorige Startkonfiguration steht.

(b) In einem Wort in Spurendarstellung lasst sich die in der unteren Spur stehende Konfigu-ration durch ihre Nachfolgekonfiguration ersetzen (s.o.).

(c) In einem Wort in Spurendarstellung, dessen untere Spur eine akzeptierende Stoppkon-figuration enthalt, kann die untere Spur geloscht werden. D.h. man erhalt das Wort in deroberen Spur als Terminalwort.

Details: s. Skript

21

Mit diesem Satz ubertragt sich die Unentscheidbarkeit semanti-

scher Eigenschaften von Turingmaschinen auf Grammatiken. Ins-

besondere ist das Wortproblem fur Chomsky-Grammatiken, d.h.

die Frage, ob ein Wort w von einer Grammatik G erzeugt wird,

unentscheidbar, und es gibt nicht-rekursive, d.h. unentscheidbare

Chomsky-Sprachen.

Beispiele nichtrekursiver Probleme (fur Chomsky-Grammatiken G und belie-biges terminales Alphabet Σ):

WΣ = {(G, w) : w ∈ L(G)} (Wortproblem)

EMPTYΣ = {G : L(G) = ∅} (Leerheitsproblem)

TOTΣ = {G : L(G) = Σ∗} (Totalitatsproblem)

EQΣ = {(G, G′) : L(G) = L(G′)} (Aquivalenzproblem)

Beweis: Durch Reduktion des Halteproblems bzw. der entsprechenden Index-mengen (fur Turingmaschinen).

22

Stellt man eine Sprache durch eine Chomsky-Grammatik dar,

so kann man also die wesentlichen Fragen uber die dargestellte

Sprache i.a. nicht entscheiden.

In der Praxis schrankt man daher die zulassigen Regeln in ei-

ner Grammatik in geeigneter Weise ein. Hierdurch erhalt man

Darstellungen, die mehr uber die dargestellte Sprache verraten.

Generell gilt aber, je mehr Information man der Grammatik uber

die erzeugte Sprache effektiv oder gar effizient entnehmen kann,

um so weniger Sprachen lassen sich mit Grammatiken diesen

Typs darstellen.

Wir werden dem Rechnung tragen und eine Hierarchie von Choms-

ky-Grammatiken und zugehorigen Sprachen einfuhren.

23