Formale Methoden der Linguistik

ÍÒ Ú Ö× Ø Ø

Ð

Ð

Universität Bielefeld Fakultät für Linguistik und Literaturwissenschaft

Prof. Dr. Walther Kindt Juana Salas Peter Menke

Formale Methoden der Linguistik I

Kurz- usammenstellung Wintersemester 2006/2007

ra 1 2

ma la 3

ding 4 ra

dong 5

Stand: 19. November 2006

Inhaltsverzeichnis

ÁÒ ÐØ×Ú ÖÞ Ò ×

½

1.1 1.2 1.3 1.4

Ò

1.5

Grundlegende Definitionen . . . . . . . . . Axiome . . . . . . . . . . . . . . . . . . . . . Theoreme . . . . . . . . . . . . . . . . . . . . Drei Beweisprinzipien . . . . . . . . . . . . 1.4.1 direkter oder unmittelbarer Beweis . 1.4.2 Indirekter Beweis . . . . . . . . . . . 1.4.3 Beweis durch Umformulierung . . . 1.4.4 Vollständige Induktion . . . . . . . . Anwendungsbeispiele . . . . . . . . . . . . Grundlegende Definitionen . . . . Theoreme . . . . . . . . . . . . . . . Anwendungsbeispiele . . . . . . . 2.3.1 Syntagmatische Relationen 2.3.2 Paradigmatische Relationen

ÖÙÒ Ò

Ü ÓÑ Ø ×

Å Ò ÒØ ÓÖ

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

¿

3 4 4 4 4 5 5 5 6

¾

2.1 2.2 2.3

Ò

ÖÙÒ Ò

ËØÖÙ ØÙÖØ ÓÖ

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

8 9 9 9 9

¿

3.1

Ö ÑÑ Ø

3.2

Grundlegende Definitionen . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Autonome Sequentielle Systeme . . . . . . . . . . . . . . . . . 3.1.2 Ersetzungsgrammatiken . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Sequentielle Input-Systeme . . . . . . . . . . . . . . . . . . . . 3.1.4 Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theoreme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Beschreibungsäquivalente Grammatiken . . . . . . . . . . . . 3.2.3 Beschreibungsäquivalenz von Automaten und Grammatiken

Ò ÙÒ

ÙØÓÑ Ø Ò

½¼

10 10 10 11 11 11 11 12 12

---

1 Einführung in die axiomatische Mengentheorie

½

Ö

Ò

ÖÙÒ

Ò

Ü ÓÑ Ø ×

{u : E(u)} x∈A A=B

Å Ò ÒØ ÓÖ

ÖÙÒ ÓÒÞ ÔØ

Klassenbildung Elementbeziehung Klassengleichheit

½º½

ÖÙÒ Ð

Ò

Ò Ø ÓÒ Ò

MU := {u : u = u} / := {u : u = u} 0 RK := {u : u ∈ u} / A ⊂ B :⇔ für alle u gilt: u ∈ A ⇒ u ∈ B A ∩ B := {u : u ∈ A und u ∈ B} A ∪ B := {u : u ∈ A oder u ∈ B} A B := {u : u ∈ A und u ∈ B} / A und B sind disjunkt : ⇔ A ∩ B = / 0

Mengenuniversum Leere Menge Russellklasse Teilklassenbeziehung Klassendurchschnitt Klassenvereinigung Klassendifferenz Disjunkte Klassen Einerklasse Paarklasse Klasse aus n Elementen Potenzklasse Nachfolgerklasse Induktive Klasse Null Nachfolgerzahlen 1 als Nachfolger von 0 2 als Nachfolger von 1 Natürliche ahlen

{ A} := {u : u = A} { A, B} := {u : u = A oder u = B) { A1 , A2 , . . . , An } := {u : u = A1 oder u = A2 oder . . . oder u = An } Pot A := {u : u ⊂ A} N A := A ∪ { A} A ist induktiv :⇔ / ∈ A und für alle u ∈ A gilt: N u ∈ A 0 0 0 := / n + 1 := Nn 1 : = 0 ∪ {0} = {0} 2 := 1 ∪ {1} = {0} ∪ {1} = {0, 1} ω := {u : u ∈ A für alle induktiven Klassen A}

---