Einführung in die Computerlinguistik

Übung 7

Jan Hendrik Dithmar

Matrikelnummer 2031259

Übung 7  Dithmar (2031259)

Aufgabe 7.1

(a)

NP → ART NN  NP → NP PP
NP → ART ADJA NN PP → PRP NP
ADJA → ADJA ADJA NP → PN
NP → PRO NN  NP → PRO ADJA NN

(b)

S → NP VP  VP → VT NP VP → VI
NP → ART NN NP → PN NP → NP PP
PP → PRP NP  VP → VP PP NP → ART ADJA NN
ADJA → ADJA ADJA NP → PRO NN NP → PRO ADJA NN

1. Peter fuhr mit seinem roten Auto auf den großen neuen Parkplatz.

2. Er mag seine Uhr.

3. Das größte Konzert von Hans war in dem schönen heißen Sommer vor der

größten Kirche in der Stadt. Hinweis: Alle Bäume wurden von mir nicht bis ins kleinste Detail ausgeführt. Um zu zeigen, dass das Prinzip (hoffentlich) klar ist, wird ein kleiner, überschaubarer Baum in Aufgabe 7.1 (c) in voller Schönheit dargestellt.

1.

S

Peter

VP

VP fuhr

PP mit

NP

seinem roten Auto

PP

auf NP

dem großen neuen Parkplatz

2.

S

Er

VP

mag NP _{seine Uhr}

3.

S

NP

NP

Das größte Konzert

PP

von  Hans

VP

VP

VP

war

PP

in

NP

dem schönen heißen Sommer

PP

vor

NP der größten Kirche

PP in

NP

der  Stadt

(c)

Mit der Grammatik gibt es Probleme. Die Grammatik kann z.B. keine Sätze der Form

Auch ohne Payback-Karte können Sie beim Einkauf sparen.

erzeugen (zumindest habe ich keine passende Ableitung gefunden), obwohl diese grammatikalisch korrekt wären. Ein mögliches Beispiel für einen Satz, der kein grammatischer Satz des Deutschen ist, aber von der Grammatik erzeugt wird, ist der folgende:

Hans mit Peter läuft ohne Otto.

Erzeugt wurde der Satz wie folgt:

S

NP

NP {PN \atop Hans}

PP

{PRP \atop mit} NP {PN \atop Peter}

VP

VP {VI \atop läuft}

PP

{PRP \atop ohne} NP {PN \atop Otto}

Aufgabe 7.2

Umschreibungen:

1. Peter telefonierte mit seinem Handy von München aus und benachrichtigte den Kollegen.

2. Peter benachrichtigte von München aus den Kollegen, der ein Handy besitzt.

3. Peter benachrichtigte den Kollegen, der ein Handy besitzt und aus München stammt.

4. Peter telefonierte mit seinem Handy, welches aus München kommt (welches in München produziert wurde), und benachrichtigte den Kollegen.

5. Peter benachrichtige den Kollegen, der ein Handy besitzt, welches aus München kommt (welches in München produziert wurde).

Strukturbäume:

1.

S

Peter

PP

PP

VP

benachrichtigte den Kollegen

mit dem Handy aus München

Übung 7  Dithmar (2031259)

2.

S

Peter

VP

VP

benachrichtigte

NP

den Kollegen mit dem Handy

aus München

3.

S

Peter

VP

benachrichtigte

NP

NP

den Kollegen mit dem Handy

aus München

4.

S

Peter

VP

VP

benachrichtigte den Kollegen

PP mit

NP

dem Handy aus München
Einf. i. d. Computerlinguistik  Seite 4  WS 2006/2007

5.

S

Peter

VP

benachrichtigte

NP

den Kollegen

PP

mit

NP

dem Handy aus München

Aufgabe 7.3

(a)

S → A S A S → B S B S → c A → a B → b

(b)

Angenommen, die Sprache L = {wcw^{R}|w, w^{R} ∈ {a, b}^{∗}} wird von einem endlichen Automaten akzeptiert. Nach dem Pumping Lemma gibt es dann eine Zahl k, sodass für jedes Wort x mit |x| ⩾ k eine Zerlegung u_{p}v_{p}^{i}w_{p} mit i ⩾ 0 möglich ist, sodass u_{p}v_{p}^{i}w_{p} ∈ L. Betrachten wir das Wort wcw^{R} mit |w| = |w^{R}| = k, sodass das Wort die Gesamtlänge 2k + 1 ⩾ k hat. Es gibt 3 Fälle:

• v_{p} liegt in dem w-Teil (also im linken Teil): die Länge des Wortes links ist länger als rechts von dem c, d.h. |w| = k + |v| ≠ |w^{R}|. ⇒ Wort nicht in L.

• v_{p} liegt in dem w^{R}-Teil (also im rechten Teil): die Länge des Wortes rechts ist länger als links von dem c, d.h. |w^{R}| = k + |v| ≠ |w|. ⇒ Wort nicht in L.

• v_{p} geht über die Wortmitte hinaus: dies ist nicht möglich, da die Wortmitte nicht mehr durch c gekennzeichnet wäre. ⇒ Wort nicht in L.

(c)

1  2 ⟨c, ε, ε⟩ ⟨b, b, ε⟩ ⟨b, ε, b⟩ ⟨a, ε, a⟩  ⟨a, a, ε⟩