Syntax, Syntaxtypen, Normalform

Vorlesung	Notizen zum Thema	von - bis
Thümmel: Formale Syntax	Syntax-Typen	23. Okt. 1997 - 27. Nov. 1997

Übersicht zu den Übungsaufgaben usw. - Schlagwortverzeichnis

Syntax, Syntaxtypen, Normalform

Definition: S = < V_T, V_N, S, R > heißt formale Syntax, wenn

V_T Ç V_N = Æ
S Î V_N (oder S Ì V_N)
R Ì (V_T È V_N)* V_N (V_T È V_N)* x (V_T È V_N)*
R endliche Menge

Man nennt V := V_T È V_N das Vokabular, V_T das terminale Vokabular, V_N das nicht terminale Vokabular, S das Anfangs- oder Startsymbol (falls S Î V_N) und R die Menge der Regeln.

Begriffe

Rechts-Konstituente

siehe Konstituentenbaum

Lexikonregeln

Regeln, bei denen links ein preterminales Symbol steht
Das w Î V_T muß lexikalischen Charakter haben.

preterminale Symbole

vermutlich folgt aus (c, w) Î R und c preterminales Symbol, daß w Î V_T
evtl. muß c Î V_N gelten (schließlich wäre c sonst eine Kette und kein "Symbol")

Definition: Ein Paar (V, R) heißt Ersetzungs- oder Produktionssystem, wenn

V ¹ Æ (V ist Vokabular)
j -> y, j, y Î V* (Menge von Regeln)

siehe Bäume und Ableitungen

Definition: Eine Regelsyntax (Regelgrammatik) ist ein Ersetzungssystem mit ausgezeichneter Kette.
Siehe auch: Typ 0 Syntax

Definition: Eine Syntax ist eine Typ 0 Syntax (Regelgrammatik, Ersetzungssyntax, Erzeugungssyntax) wenn für alle Regeln j -> y gilt:

j, y Î V*
j Ï V_T*

Anders geschrieben: " r Î R : r = (j, y) mit j Î V* V_NV*, y Î V*
Anmerkung: Aus 2. folgt j ¹ l.

Definition: Eine Syntax ist eine Typ 1^nr Syntax (beschränkte / nicht-kontrahierende Syntax), wenn sie eine Typ 0 Syntax ist, und jedes r Î R eine der beiden folgenden Formen hat:

S -> e
j -> y mit lg(j) £ lg(y) und y Î ((V_NÈV_T) \ {S})* falls (1) Î R, sonst y Î V*

Anmerkung: j ¹ l Þ lg(j) ³ 1 Þ lg(y) ³ 1 Þ y ¹ e
Siehe auch die im folgenden definierten Typ 1 Syntaxen.

Definition: Eine Syntax ist eine Typ 1^e Syntax (kontextsenitive Syntax), wenn sie Typ 1^nr Syntax ist, und zusätzlich jedes r Î R eine der beiden folgenden Formen hat:

S -> e
xAy -> xzy mit A Î V_N, x, y Î V* und z Î (V* \ {e})

Frage: Gilt die strenge Bedingung für z immer oder analog zur Definition von Typ 1^nr nur, wenn (1) Î R? Oder anderherum: Folgt nicht sowieso schon z ¹ e aus lg(A) £ lg(z)?

Anmerkung: Bei der Regel xAy -> xzy bezeichnet man A -> z als Kern und notiert für die Regel auch A -> z / x _ y. Beispiel: N -> Hund / ein _ VP

Definition: Eine Syntax ist eine Typ 1^Ï Syntax, wenn sie Typ 1^nr Syntax mit (S -> e) Ï R ist.

Definition: Eine Syntax ist eine Typ 1^Î Syntax, wenn sie Typ 1^nr Syntax mit (S -> e) Î R ist.

Definition: Eine Syntax ist eine kontextsensitive ^{59 Ch} Typ 1 Syntax, wenn sie sowohl vom Typ 1^e als auch vom Typ 1^Ï ist.
Anmerkung: Also handelt es sich um eine kontextsensitive Syntax mit (S -> e) Ï R (lambdafrei, epsilonfrei).

Definition: Eine Syntax ist eine kontextsenitive ^e Typ 1 Syntax, wenn sie sowohl vom Typ 1^e als auch vom Typ 1^Î.
Anmerkung: Weil eine kontextsenitive ^e Typ 1 Syntax vom Typ 1^e ist, ist sie auch eine Typ 1^nr Syntax. Daher hat jede Regel eine der beiden folgenden Formen:

S -> e
j₁ c j₂ -> j₁ w j₂ wobei

Bedingung	Ursprung
j₁ c j₂Î V* V_NV*	Typ 0
lg(c) £ lg(w)	Typ 1^nr
j₁ w j₂ Î ((V_NÈV_T) \ {S})*	Typ 1^nr
c Î V_N	Typ 1^e
j₁, j₂ Î V*	Typ 1^e
w Î (V* \ {e})	Typ 1^e

(1) Î R wegen Typ 1^Î

Wegen der dritten Bedingung muß w ¹ S sein. Ebenso folgt aus der letzten Bedingung w ¹ e.
Frage: War das so gemeint, oder müssen die Bedingungen für Typ 1^e (kontextsensitive Syntax) weggelassen werden?

Definition: Eine Syntax ist eine kontextfreie ^{59 Ch} Typ 2 Syntax, wenn sie eine kontextsenitive ^e Typ 1 Syntax ist, und jede Regel eine der beiden folgenden Formen hat:

S -> e
j₁ c j₂ -> j₁ w j₂ wobei j₁ = l und j₂ = l

Anmerkung: Für den Fall, daß die Definition der kontextsenitiven ^e Typ 1 Syntax fehlerhaft ist, sei folgende alternative Definition angegeben:
Eine Syntax ist eine kontextfreie ^{59 Ch} Typ 2 Syntax, wenn sie Typ 1^nr Syntax ist, und jede Regel eine der beiden folgenden Formen hat:

S -> e
j₁ c j₂ -> j₁ w j₂ wobei

j₁ = l und j₂ = l
w ¹ l
c Î V_N
w Î V*

Definition: Eine Syntax ist eine kontextfreie ^l Typ 2 Syntax, wenn sie Typ 1^nr Syntax ist, und jede Regel eine der beiden folgenden Formen hat:

S -> e
j₁ c j₂ -> j₁ w j₂ wobei

j₁ = l und j₂ = l
c Î V_N
w Î V*

Frage: Wenn eine Typ 2 Syntax zugeleich auch eine Typ 1 Syntax ist, dann ist w = l ausgeschlossen, da aus lg(c) = 1 £ lg(w) folgt, daß w ¹ l.Worin unterscheidet sich dann aber eine kontextfreie ^l Typ 2 Syntax von einer kontextfreie ^{59 Ch} Typ 2 Syntax?

Definition: Eine Syntax heißt separiert, wenn " r Î R : r = (j, y) mit y Î V_N* oder y Î V_T*.

Definition: Eine Syntax hat Normalform (heißt Normalsyntax), wenn " r Î R : r = (j, y) mit lg(y) £ 2.

Definition: Eine Syntax ist eine Typ 3 Syntax (kontextfreie ^Ch, rechtslineare ^Ch, rechtsprädikative Syntax), wenn sie eine Typ 2 Syntax ist, und w = w¹w² mit w¹ Î V_T und w² Î V_N. Entsprechend definiert man linkslineare, linksprädikative und beidseitige Syntaxen.

Anmerkung: Alternativ läßt man auch V_N* zu. Dann hat die Syntax aber nicht mehr zwingend Normalform.

Joachim Wagner
Osnabrück, den 04. Februar 1998