Kompetenz versus Performanz Timm Lichte & Christian Wurmtimm-lichte.de/wp-content/uploads/2017/04/05-kompetenz-performanz.pdfKomplexität und natürliche Sprache Kompetenz versus Performanz

Komplexität und natürliche SpracheKompetenz versus Performanz

Timm Lichte & Christian Wurm

Heinrich-Heine-Universität Düsseldorf

Sommersemester 2017, 24.05.2017

SFB 991

Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 1

Outline

1 Kompetenz versus Performanz

2 Äquivalenz und Normalformen

3 X-bar-Schema

4 Derivational Theory of Complexity


Outline



3 X-bar-Schema



Kompetenz versus Performanz

Kompetenz PerformanzWas wird charakterisiert Wie wird charakterisiertWissensinhalt WissensanwendungSprachklassen Regelmengen von Grammatiken (Kompetenz?)

Regelanwendungen für ein konkretes Wort

Sprachklassen-Komplexität

L1 ist komplexer als L2, falls L1 ⊃ L2.

Grammatik-Komplexität (Regelanzahl)

Sei L(G1) = L(G2), G1 ist komplexer als G2, falls |P1 | > |P2 |.

Grammatik-Komplexität (Ambiguität)

G1 ist komplexer als G2 bezüglich w , falls |PTR1(w)| > |PTR2(w)|.


Kompetenz versus Performanz (cont.)

Grammatik/Wort-Komplexität (Ableitungslänge)

w1 ist komplexer als w2 bezüglich G, falls|S ` ... ` w1 | > |S ` ... ` w2 |


Outline



3 X-bar-Schema



Schwache und starke Äquivalenz von Grammatiken

Gegeben zwei kontextfreie Grammatiken G1 = 〈N1, Σ1,P1, S1〉 undG2 = 〈N2, Σ2,P2, S2〉.

Schwache Äquivalenz

G1 und G2 sind schwach äquivalent gdw. G1 und G2 erzeugendieselbe Sprache.

G1 ≡w G2 ⇔ L(G1) = L(G2)

Starke Äquivalenz

G1 und G2 sind stark äquivalent gdw. G1 und G2 erzeugen dieselbeSprache mit denselben Ableitungen.

G1 ≡s G2 ⇔ P1 = P2 ∧ S1 = S2


Schwache und starke Äquivalenz von Grammatiken (cont.)

Strukturelle Äquivalenz

G1 und G2 sind strukturell äquivalent gdw. G1 und G2 erzeugendieselbe Sprache mit den gleichen Ableitungen.

G1 ≡P G2 ⇔ Es gibt eine Bijektion f : N1 → N2, wobei f (S1) = S2,und eine Bijektion g : P1 → P2, so dass gilt: Wenn α → β1...βn ∈P1 mit α ∈ N1 und βi ∈ Σ1 ∪ N1, dann gibt es g(α → β1...βn) =f (α) → γ1...γn mit γi = βi , falls γi ∈ Σ2, oder γi = f (βi), falls γi ∈ N2.


Schwache und starke Äquivalenz von Grammatikklassen

Gegeben zwei Grammatikklassen G1 und G2.

Schwache Äquivalenz

G1 und G2 sind schwach äquivalent gdw. es gibt eine Bijektionf : G1 → G2, so dass für jedes G ∈ G1 gilt:

G ≡w f (G)

Starke Äquivalenz

G1 und G2 sind stark äquivalent gdw. es gibt eine Bijektion f :G1 → G2, so dass für jedes G ∈ G1 gilt:

G ≡s f (G)

Äquivalenz von Grammatiken aus verschiedenenGrammatikformalismen?


Normalformen für kontextfreie Grammatiken

Normalform heißt: Die Regeln haben eine bestimmte Form.

Chomsky-Normalform (CNF)

A→ B C |a (mit A,B,C ∈ N , a ∈ Σ)

Greibach-Normalform (GNF)

A→ a β (mit A ∈ N , a ∈ Σ, β ∈ N∗)

Lexikalisierung

A→ α a β (mit A ∈ N , a ∈ Σ, α , β ∈ N∗)

Kontextfreie Grammatiken in CNF und GNF und lexikalisiertekontextfreie Grammmatiken sind schwach äquivalent zukontextfreien Grammatiken.





A→ B C |a (mit A,B,C ∈ N , a ∈ Σ)


A→ a β (mit A ∈ N , a ∈ Σ, β ∈ N∗)

Lexikalisierung

A→ α a β (mit A ∈ N , a ∈ Σ, α , β ∈ N∗)






A→ B C |a (mit A,B,C ∈ N , a ∈ Σ)


A→ a β (mit A ∈ N , a ∈ Σ, β ∈ N∗)

Lexikalisierung

A→ α a β (mit A ∈ N , a ∈ Σ, α , β ∈ N∗)



Normalformen für kontextfreie Grammatiken (cont.)

Nicht schwach äquivalent zu kontextfreien Grammatiken:

lineare CFG

A→ a B |B a |a (mit A,B ∈ N , a ∈ Σ)oderA→ a B b |a (mit A,B ∈ N , a, b ∈ Σ)

Lineare CFGs können nicht die Dyck-Sprachen erzeugen.

S → ϵ |SS |(S)


Normalformen für kontextfreie Grammatiken (cont.)

Nicht schwach äquivalent zu kontextfreien Grammatiken:

lineare CFG

A→ a B |B a |a (mit A,B ∈ N , a ∈ Σ)oderA→ a B b |a (mit A,B ∈ N , a, b ∈ Σ)

Lineare CFGs können nicht die Dyck-Sprachen erzeugen.

S → ϵ |SS |(S)


Ordentliche (“proper”) CFGs[8]

Eine kontextfreie Grammatik G = 〈N , Σ,P, S〉 ist ordentlich gdw.:

keine unerreichbare Nich�erminale

∀A ∈ N : ∃α , β ∈ (Σ ∪ N)∗: S `∗G αAβ

keine unproduktive Nich�erminale

∀A ∈ N : ∃w ∈ Σ∗: A `∗G w

keine ϵ-Produktionen

�A ∈ N : A `G ϵ oder

P ⊆ N → (Σ ∪ N \ {S, ϵ})+ ∪ {S → ϵ}

keine Zyklen�A ∈ N : A `+G A


Ordentliche (“proper”) CFGs

Die Klasse der ordentlichen kontextfreien Grammatiken ist schwachäquivalent zur Klasse der kontextfreien Grammatiken.

Unerreichbare und unproduktive Nich�erminale können elim-iniert werden. [5: §7.1.1]

ϵ-Produktionen können eliminiert werden. [5: §7.1.3]

Zyklen (allgemeiner “unit pairs”) können eliminiert werden. [5:§7.1.4]

AberDurch die Eliminierung der ϵ-Produktionen und der Zyklen (bzw.“unit pairs”) kann P erheblich größer werden.


Ordentliche (“proper”) CFGs

Die Klasse der ordentlichen kontextfreien Grammatiken ist schwachäquivalent zur Klasse der kontextfreien Grammatiken.

Unerreichbare und unproduktive Nich�erminale können elim-iniert werden. [5: §7.1.1]

ϵ-Produktionen können eliminiert werden. [5: §7.1.3]

Zyklen (allgemeiner “unit pairs”) können eliminiert werden. [5:§7.1.4]

AberDurch die Eliminierung der ϵ-Produktionen und der Zyklen (bzw.“unit pairs”) kann P erheblich größer werden.


Outline



3 X-bar-Schema



X-bar-Schema

Chomsky (1970)

“To introduce a more uniform notation, letus use the symbol X for a phrase containingX as its head. Then the base rules intro-ducing N , A, and V will be replaced by aschema (48), where in place of . . . thereappears the full range of structures thatserve as complements and X can be any oneof N , A, or V :

(48) X → X . . .

Continuing with the same notation, thephrases immediately dominating N , A and V

will be designated N , A, V respectively.“

X

[Spec,X] X

X Y


Anwendungsbeispiel

ϵ-freie Regeln für NPs

NP → Alpakas | die Alpakas | freche Alpakas | die frechen Alpakas| die hungrigen frechen Alpakas | . . .

x-bar-Regeln für NPs

?Weiterentwicklung in Jackendo� (1977) und Stowell (1981).

Kritische und formal adequate Besprechung in Kornai & Pullum(1990).


Anwendungsbeispiel

ϵ-freie Regeln für NPs

NP → Alpakas | die Alpakas | freche Alpakas | die frechen Alpakas| die hungrigen frechen Alpakas | . . .

x-bar-Regeln für NPs

?Weiterentwicklung in Jackendo� (1977) und Stowell (1981).

Kritische und formal adequate Besprechung in Kornai & Pullum(1990).


X-bar-Schema nach Kornai & Pullum (1990)

Lexicality

A CFG observes Lexicality i� every nonterminal is X i , where X ∈ VT

and i > 0.

SuccessionA Lexicality observing CFG observes Succession i� every rule rewrit-ing some nonterminal Xn has a daughter labeled Xn−1.

Weak SuccessionA Lexicality observing CFG observes Weak Succession i� every rulerewriting some nonterminal Xn has a daughter labeled Xn−1 or Xn.

Uniformity

A Lexicality-observing CFG observes Uniformity i� ∃m ∈ N[VN =

{X i |1 ≤ i ≤ m,X ∈ VT }]


X-bar-Schema nach Kornai & Pullum (1990) (cont.)

Maximality

A CFG observing Lexicality and Succession observes Maximality i�for every rule Xn → YXn−1Z , the strings Y and Z are in V ∗M, whereVM = {Xm |X ∈ VT }.

Centrality

A Lexicality-observing CFG observes Centrality i� the start symbolis the maximal projection of a distinguished preterminal.

Peripherality

A Lexicality-observing CFG observes Peripherality i� in any rulerewriting X 1 as YX 0Z , either Y = ϵ or Z = ϵ .


X-bar-Schema nach Kornai & Pullum (1990) (cont.)

Optionality

A CFG G = 〈VN ,VT , P, S〉 observes Optionality i� for every rule in Pof the form α → W there exist β , W1, W2 such that

1 β ∈ (VN ∪ VT );2 W1,W2 ∈ (VN ∪ VT )∗;3 W = W1βW2; and

4 the rule α → W ′1βW

′2 in P for all strings W ′

1 and W ′2 con-

structible by deleting some elements from W1 and W2, respec-tively. In such rules, β will be called the CORE.


Weniger Komplexität? (Kornai & Pullum 1990)

Standard X-bar Grammar (SXBG)

A Standard X-bar Grammar (SXBG) is a Lexicality-observing CFG inwhich the rules have the form Xn → YXn−1Z , where Y ,Z ∈ V ∗M.

Falls ϵ-frei: Ja! (wenige endliche Sprachen)Beispiel: SXBG mit genau einem Präterminal σ :

Sei G = 〈{σ 1}, {σ }, {σ 1 → σ },σ 1〉, dann L(G) = {σ }.Sei G = 〈{σ 1}, {σ }, {σ 1 → σ 1σ ,σ 1 → σ },σ 1〉, dann L(G) ={σ n |n > 0}.

Standard X-bar Grammar mit ϵ-Produktionen (SXBGϵ )

A Standard X-bar Grammar (SXBG) is a Lexicality-observing CFG inwhich the rules have the form Xn → YXn−1Z , where Y ,Z ∈ V ∗M, orX 0 → ϵ .

Falls nicht ϵ-frei: Nein! (schwach äquivalent zu CFG)Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 20

Weniger Komplexität? (Kornai & Pullum 1990) (cont.)

CAVEATX-bar-Schema wird sehr unterschiedlich eingesetzt.

Optionalität senkt die Ausdrucksstärke, wird aber kaum ver-wendet.

Implizite Grundannahme scheint zu sein: Xn mit n > 0 sindderivationell nicht ambig,

Nur Kompetenz, d.h. Sprachklassen-Komplexität, wird betra-chtet.

Was die Regelanzahl und die Ableitungslänge betri�t, sind SXBGssicherlich nicht optimal.

Anliegen ist, die Ableitungsambiguität (auch grammatik-übergreifend) zu minimieren.


Outline



3 X-bar-Schema



Derivational Theory of Complexity (DTC)

Vermutung bezogen auf die Transformationsgrammatik

Verarbeitungskomplexität korreliert mit der Anzahl der nötigenTransformationen.

Grammatik/Wort-Komplexität (Ableitungslänge)

w1 ist komplexer als w2 bezüglich G, falls|S ` ... ` w1 | > |S ` ... ` w2 |

Ho�nung auf

explizite Performanzmodelle

Adäquatheitstests für linguistische Theorien


Transformationsgrammatik

Chomsky (1957; 1965)CFG Lexikon

Deep Structure “kernel sentences”

Conceptual StructureTransformationen

Surface Structure

Phonological Structure



Chomsky (1957; 1965)“kernel sentences”

S

NP

Peter

VP

V

loves

NP

Susan

=⇒

S

NP

Susan

VP

AUX

is

V

loved

PP

P

by

NP

Peter

NP1 V NP2 → NP2 AUX V by NP1

Komplexitätstheoretisch sehr problematisch: Das Wortproblemfür TG ist unentscheidbar (Peters & Ritchie 1973).



Chomsky (1957; 1965)“kernel sentences”

S

NP

Peter

VP

V

loves

NP

Susan

=⇒

S

NP

Susan

VP

AUX

is

V

loved

PP

P

by

NP

Peter

NP1 V NP2 → NP2 AUX V by NP1

Komplexitätstheoretisch sehr problematisch: Das Wortproblemfür TG ist unentscheidbar (Peters & Ritchie 1973).


Kontra DTC

Gegenevidenz (Fodor, Bever & Garre� 1974):

Passiv(1) a. The first shot the tired soldier the mosquito bit fired missed.

b. The first shot fired by the tired soldier bi�en by themosquito missed.

Ellipse

(2) a. John swims faster than Bob swims.b. John swims faster than Bob.c. John swims faster than Bob does.

Hängt stark von der Analyse ab![10]


Kontra DTC




Ellipse




Kontra DTC




Ellipse




Zusammenfassung

Unterscheidung von “Kompetenz” und “Performanz”

“Performanz” bezieht sich auf Regeln.

Äquivalenz und Normalformen

regelbezogenen Komplexitätsbegri�e (Regelanzahl, Ambiguität,Ableitungslänge)

Beispiele aus der formalen Linguistik: X-bar-Syntax und DTC

Nächste Sitzung: andere wichtige performanzbezogeneKomplexitätsbegri�e (Automatentheorie, Raum- undZeitkomplexität)


Literaturverzeichnis

[1] Chomsky, Noam. 1957. Syntactic structures. Den Haag: Mouton.[2] Chomsky, Noam. 1965. Aspects of the theory of syntax. Cambridge, MA: The MIT Press.[3] Chomsky, Noam. 1970. Remarks on nominalization. In Roderick Jacobs &

Peter Rosenbaum (eds.), Readings in English transformational grammar, 184–221.Waltham, MA: Ginn.

[4] Fodor, Jerry A., Thomas G. Bever & Merrill F. Garre�. 1974. The psychology of language:an introduction to psycholinguistics and generative grammar. McGraw-Hill.

[5] Hopcro�, John E., Rajeev Motwani & Je�rey D. Ullman. 2001. Introduction to automatatheory, languages and computation. Addison-Wesley.

[6] Jackendo�, Ray. 1977. X′ syntax: A case study of phrase structure. Cambridge, MA: MITPress.

[7] Kornai, András & Geo�rey K. Pullum. 1990. The x-bar theory of phrase structure.English. Language 66(1). 24–50. http://www.jstor.org/stable/415278.

[8] Nijholt, Anton. 1980. Context-free grammars: Covers, normal forms, and parsing.(Lecture Notes in Computer Science 93). Berlin: Springer.

[9] Peters, Stanley P. & Robert W. Ritchie. 1973. On the generative power oftransformational grammar. Information Sciences 6. 49–83.

[10] Phillips, Colin. 1996. Order and structure. Cambridge, MA: MIT Doctoral dissertation.http://dspace.mit.edu/handle/1721.1/10666.

[11] Stowell, Timothy A. 1981. Origins of phrase structure. Cambridge, MA: MIT MITdissertation.


http://www.jstor.org/stable/415278

http://dspace.mit.edu/handle/1721.1/10666

Documents

Kompetenz versus Performanz Timm Lichte & Christian Wurmtimm-lichte.de/wp-content/uploads/2017/04/05-kompetenz-performanz.pdfKomplexität und natürliche Sprache Kompetenz versus Performanz