PS Grundlagen wissenschaftlichen Arbeitens

1

Iris Meyer

PräsentationGruppe 6

Iris Meyer

Elisabeth Grill

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

SS 2003

PS Grundlagen wissenschaftlichen Arbeitens

2

Iris Meyer

Aussagenlogik

Iris Meyer

PS Grundlagen wissenschaftlichen Arbeitens

SS 2003

PS Grundlagen wissenschaftlichen Arbeitens

3

Iris Meyer

Aussagenlogik

Der Begriff der „Aussage“

1. Grammatikkriterium

2. Wahrheitskriterium

- Tertium non datur

- Satz vom ausgeschlossenen Widerspruch

PS Grundlagen wissenschaftlichen Arbeitens

4

Iris Meyer

Aussagenlogik

Die Sprache der Aussagenlogik

(a) Das Alphabet einer aussagenlogischen Sprache besteht aus:– Den aussagenlogischen Variablen pi, i N

– Den aussagenlogischen Junktoren T, , , , , und – Den Klammern ( und )

(b) Die Menge der aussagenlogischen Formeln ist rekursiv definiert:– Jede aussagenlogische Variable ist eine aussagenlogische Formel

– Die aussagenlogische Junktoren T und sind aussagenlogische Formeln

– Ist φ eine aussagenlogische Formel, dann auch φ– Sind φ und ψ aussagenlogische Formel, dann auch (φ ψ), (φ ψ),

(φ ψ) und (φ ψ)

PS Grundlagen wissenschaftlichen Arbeitens

5

Iris Meyer

Aussagenlogik

Das Argument

Gültigkeit eines Arguments:

(a) Semantisch gültig |=

(b) Syntaktisch gültig |–

(1) Alle Menschen sind sterblich.

(2) Sokrates ist ein Mensch.

(3) Also ist Sokrates sterblich.

Prämissen

Konklusion

PS Grundlagen wissenschaftlichen Arbeitens

6

Iris Meyer

Aussagenlogik

BeispielIst das Argument (p1 p2) |─ p1 p2 semantisch gültig?

Wir überprüfen mit Hilfe einer Wahrheitstafel:

p1 p2 (p1 p2) |─ p1 p2

F F W F F F W W W

F W F F W W W F F

W F F W W F F F W

W W F W W W F F F

PS Grundlagen wissenschaftlichen Arbeitens

7

Iris Meyer

Aussagenlogik

BeispielIst das Argument (p1 p2) |─ p1 p2 semantisch gültig?

Wir überprüfen mit Hilfe einer Wahrheitstafel:

Das Argument ist semantisch gültig, wir schreiben: (p1 p2) |= p1 p2

p1 p2 (p1 p2) |─ p1 p2

F F W F F F W W W

F W F F W W W F F

W F F W W F F F W

W W F W W W F F F

PS Grundlagen wissenschaftlichen Arbeitens

8

Iris Meyer

Aussagenlogik

Das Resolutionsverfahren

...ist eine Methode zum automatischen Beweisen

Grundidee:

Das Argument φ1,..., φn |= φ ist genau dann richtig, wenn die Formelmenge {φ1,..., φn, φ} unerfüllbar ist.

Vorraussetzung für die Anwendung der Resolution:Die Formel muss in Klausel-Repräsentation (= konjunktive Normalformen in Mengenschreibweise) gegeben sein.

PS Grundlagen wissenschaftlichen Arbeitens

9

Iris Meyer

Aussagenlogik

1. Umwandlung in Klausel-Repräsentation

Um die Richtigkeit der Formel

p q r, (p q r) (p q r), (p q r) (p q r) |= r

nachzuweisen,

gilt die Unerfüllbarkeit von

(p q r) (p q r) (p q r) (p q r) (p q r) r

zu beweisen.

Wir schreiben in Klausel-Repräsentation:

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

PS Grundlagen wissenschaftlichen Arbeitens

10

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

PS Grundlagen wissenschaftlichen Arbeitens

11

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

PS Grundlagen wissenschaftlichen Arbeitens

12

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

13

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

14

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

15

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r}

PS Grundlagen wissenschaftlichen Arbeitens

16

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r}

PS Grundlagen wissenschaftlichen Arbeitens

17

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r}

PS Grundlagen wissenschaftlichen Arbeitens

18

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

19

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

20

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

21

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

PS Grundlagen wissenschaftlichen Arbeitens

22

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

PS Grundlagen wissenschaftlichen Arbeitens

23

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

PS Grundlagen wissenschaftlichen Arbeitens

24

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

25

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

26

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

PS Grundlagen wissenschaftlichen Arbeitens

27

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

PS Grundlagen wissenschaftlichen Arbeitens

28

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

PS Grundlagen wissenschaftlichen Arbeitens

29

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

PS Grundlagen wissenschaftlichen Arbeitens

30

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r}

PS Grundlagen wissenschaftlichen Arbeitens

31

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r}

PS Grundlagen wissenschaftlichen Arbeitens

32

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r}

PS Grundlagen wissenschaftlichen Arbeitens

33

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r} {r}

PS Grundlagen wissenschaftlichen Arbeitens

34

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r} {r}

PS Grundlagen wissenschaftlichen Arbeitens

35

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r} {r}

PS Grundlagen wissenschaftlichen Arbeitens

36

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r}{r}

{ }

PS Grundlagen wissenschaftlichen Arbeitens

37

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r}{r}

{ }

PS Grundlagen wissenschaftlichen Arbeitens

38

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r}{r}

{ }

PS Grundlagen wissenschaftlichen Arbeitens

39

Iris Meyer

Aussagenlogik

2. Anwendung der Resolventenregel

{{p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {p, q, r}, {r}}

{p, q, r} {p, q, r}

{q, r} {p, q, r}

{p, r}

{p, q, r} {p, q, r}

{p, r}

{r}{r}

{ } leere Klausel wurde gefunden

PS Grundlagen wissenschaftlichen Arbeitens

40

Iris Meyer

Aussagenlogik

3. Ergebnis

Die leere Klausel wurde gefunden:- Die Formelmenge {φ1,..., φn, φ} ist unerfüllbar

- Die Korrektheit der Folgerungsbeziehung φ1,..., φn |= φ ist somit bewiesen

PS Grundlagen wissenschaftlichen Arbeitens

41

Iris Meyer

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

SS 2003

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

42

Iris Meyer

Berechnungsmodelle

Berechnung:

Ausführung eines Programms durch eine Maschine

Berechnungsmodelle dienen der Abstraktion:

3 verschiedene Modelle:

- Speicherorientiert

- Funktionale Modelle

- Kommunikation und verteilte Systeme

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

43

Iris Meyer

Speicherorientierte Modelle:

Berechnung = schrittweise Veränderung des Speichers

Beispiel Turingmaschine:

Speicher besteht aus Bändern, mit kleinen Speichereinheiten,

keine direkte Adressierung, nur schrittweises Durchlaufen des Speichers möglich.

In jeder Speicherzelle: ein Buchstabe des endlichen Alphabets.

Speicherorientierte Modelle Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

44

Iris Meyer

Funktionsweise einer Turingmaschine:

Speicherorientierte Modelle

BandA AGS SZ O L J

Steuerwerk

Schreib-Lesekopf

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

45

Iris Meyer

Funktionsweise einer Turingmaschine:

Speicherorientierte Modelle

A AGS SZ O L J

SteuerwerkVom Band lesen!

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

46

Iris Meyer

Funktionsweise einer Turingmaschine:

Speicherorientierte Modelle

A AGS SZ O L J

Steuerwerk

Daten bearbeiten!

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

47

Iris Meyer

Funktionsweise einer Turingmaschine:

Speicherorientierte Modelle

A AGS SZ O L J

SteuerwerkDaten auf Band speichern!

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

48

Iris Meyer

Funktionsweise einer Turingmaschine:

Speicherorientierte Modelle

A AGS SZ O L J

Steuerwerk

Zu nächsten Speicherzelle

springen!

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

49

Iris Meyer

Anweisungen für die Turingmaschine:

Vorbedingung + Aktion

Vorbedingung:

- aktuelles Zeichen in der Zelle,

- Zustand des Steuerwerks

Aktion:

- Zeichen, welches geschrieben wird

- nach links oder rechts weiterspringen

- Zustand, in den Steuerwerk wechselt

Speicherorientierte Modelle Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

50

Iris Meyer

Berechnungen:

- Schreib- Lesekopf über dem ersten Zeichen

- Steuerwerk im Anfangszustand

- es wird nach aufeinanderpassende Anweisungen gesucht

(Reihenfolge der Anweisungen im Programm unwichtig!)

- wenn keine Anweisung mehr auf die letzte „passt“ Ende

Speicherorientierte Modelle Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

51

Iris Meyer

Vorteile:

- jeder bis heute untersuchte Formalismus lässt sich simulieren

- einfache Berechnungsschritte

- direkt in die Praxis übersetzbar

Nachteile:

- unendliche Bänder nicht realisierbar ( unendl. Speicher)

- wenig Ähnlichkeit mit v. Neumann- Architektur

- Programmstruktur macht Ergebnis nicht sichtbar

Speicherorientierte Modelle Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

52

Iris Meyer

Funktionale Modelle:

WAS wird berechnet?

Beispiel:

Bereich der Nat. Zahlen, nur 0 und „Nachfolgefunktion“ bekannt.

In diesem Fall lautet die Grundfrage funkt. Berechungsmodelle:

Gibt es eine Funktion, und wenn ja welche, die sich aus 0 und der Nachfolgefunktion berechnen lassen UND sich effektiv auswerten lassen.

Funktionale Modelle Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

53

Iris Meyer

Wichtig:

Regeln

Arbeitsweise völlig egal. Nur Ergebnis zählt!

Funktionale Modelle Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

54

Iris Meyer

Kommunikation und verteilte Systeme:

Prozess + Programm + Umgebung + Komunikation mit Umgebug = wichtig

EA- Turingmaschine: = Variante der vorgestellten Turingmaschine, mehrere

Bänder die miteinander arbeiten.

Kommunikation und vert. Systeme Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

55

Iris Meyer

EA- Turingmaschine:

Kommunikation und vert. Systeme

A RMÄ SZ O L J Eingabeband

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

56

Iris Meyer

EA- Turingmaschine:

Kommunikation und vert. Systeme

A AKS VJ J L J

A RMÄ SZ O L J

Arbeitsband

Eingabeband

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

57

Iris Meyer

EA- Turingmaschine:

Kommunikation und vert. Systeme

W RGS CH O T B

A AKS VJ J L J

A RMÄ SZ O L J

Ausgabeband

Arbeitsband

Eingabeband

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

58

Iris Meyer

EA- Turingmaschine:

Kommunikation und vert. Systeme

W RGS CH O T B

A AKS VJ J L J

A RMÄ SZ O L J

Ausgabeband

Arbeitsband

Eingabeband

Steuerwerk

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

59

Iris Meyer

EA- Turingmaschine:

Kommunikation und vert. Systeme

W RGS CK O T B

A AKS VJ J L J

A RMÄ SZ O L J

Ausgabeband

Arbeitsband

Eingabeband

Steuerwerk

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

60

Iris Meyer

EA- Turingmaschine:

Kommunikation und vert. Systeme

W RGS CK O T B

A AKS VJ J L J

A RMÄ SZ O L J

Ausgabeband

Arbeitsband

Eingabeband

Steuerwerk

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

61

Iris Meyer

EA- Turingmaschine:

Kommunikation und vert. Systeme

W RGS CH O T B

A AKS VJ J L J

A RMÄ SZ O L J

Ausgabeband

Arbeitsband

Eingabeband

Steuerwerk

Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

62

Iris Meyer

Verteilte Systeme:

Ausgabeband = Eingabeband

Synchronisierung nicht notwendig, Zwischenraum zwischen Ausgabe und Eingabe als Pufferspeicher

Datenflussnetz

Kommunikation und vert. Systeme Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

63

Iris Meyer

W RGS CH O T B

A AKS VJ J L J

A RMÄ SZ O L J

Ausgabeband

Arbeitsband

Eingabeband

Steuerwerk

Kommunikation und vert. Systeme Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

64

Iris Meyer

W G CT B

A AKS VJ J L J

A RMÄ SZ O L J

Ein- und Ausgabeband

Arbeitsband

Eingabeband

Steuerwerk

W RGS CH O T B

A AKS VJ J L J

A M Z O

Ausgabeband

Arbeitsband

Steuerwerk

Kommunikation und vert. Systeme Berechnungsmodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

65

Iris Meyer

Grenzen der Berechenbarkeit

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

SS 2003

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

66

Iris Meyer

Grenzen d. Berechenbarkeit

Haben moderne Rechner Grenzen?

Dürfen sie alles, was sie können?

Wo liegen die Grenzen?

Kann ein Computer einen Menschen simulieren?

Rechnermodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

67

Iris Meyer

Grenzen d. Berechenbarkeit

Universelle Rechner:

- frei programmierbar (vgl. Turingmaschine hat festgelegte Programme). universelle Programme

- können mehrere Probleme lösen.

- spezielle Programme können auf spezielle Daten angewendet werden.

Rechnermodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

68

Iris Meyer

Grenzen d. Berechenbarkeit

Simulationen: Programme für einen Rechnertyp können auf einem

anderen Rechner simuliert werden (gleiche Ein- und Ausgabewerte).

dann auch gleiche Probleme lösen.

einheitliche Theorie der Berechenbarkeit

Beispiel: Ersetzen einer Turingmaschine mit mehreren Bändern

durch eine Turingmaschine mit einem Band. Zeitaufwand wächst um einen konstanten Faktor (Speicherverwaltung).

Rechnermodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

69

Iris Meyer

Grenzen d. Berechenbarkeit

Churchsche These:

Die Klasse der wirklich berechenbaren Funktionen ist gleich groß wie die Klasse der Turing- berechenbaren Funktionen.

Es gibt bis heute keine Funktion, die ein moderner Computer berechnen kann, welche aber auf einer Turingmaschine nicht berechenbar sind.

Rechnermodelle

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

70

Iris Meyer

Grenzen d. Berechenbarkeit

Existenz nicht berechenbarer Funktionen:

Axiome der Mathematik (z.B.) gelten, obwohl sie niemand beweisen kann. Es ist hier nur wichtig, dass ein Programm diese Axiome kennt, nicht aber, ob man sie berechnen kann.

Nicht. Berechenbare Fkt.

Katrin Zöchmeister

PS Grundlagen wissenschaftlichen Arbeitens

71

Iris Meyer

Formale Sprachen und Automaten

Grill Elisabeth

PS Grundlagen wissenschaftlichen Arbeitens

SS 2003

PS Grundlagen wissenschaftlichen Arbeitens

72

Iris Meyer

Formale Sprachen und Automaten

Inhalt:

• Allgemeines

• Grundbegriffe

• Grammatiken

• Chomsky-Hierarchie

• reguläre Sprachen

• endliche Automaten

PS Grundlagen wissenschaftlichen Arbeitens

73

Iris Meyer

Formale Sprachen und Automaten

Allgemeines:

In der Theorie der formalen Sprachen wird die Struktur von

Zeichenketten untersucht.

Mengen von Zeichenketten

Sprachen

Sprachklassen

Sprachklassen sind definiert durch:

• Erzeugungsverfahren

• Erkennungsverfahren

PS Grundlagen wissenschaftlichen Arbeitens

74

Iris Meyer

Formale Sprachen und Automaten

Erzeugung und Erkennung können durch Grammatiken und abstrakte Maschinen, Automaten, beschrieben werden.

Klassen der Grammatiken und Sprachen (Chomsky Hierarchie) und Automaten werden alle hierarchisch eingeteilt

daher eng miteinander verwandt

PS Grundlagen wissenschaftlichen Arbeitens

75

Iris Meyer

Formale Sprachen und Automaten

Grundbegriffe:

: Alphabet, endliche Menge von Zeichen; z.B. ={a,

b, c}

Ketten: aa, ab, ca, aaa, ...

: leere Kette

|w|: Wortlänge

*: Menge aller Ketten, einschließlich leerer Kette

+: Menge aller nichtleeren Ketten

L: formale Sprache über dem Alphabet

Elemente der Sprache: Sätze/Wörter (Zeichenketten)

PS Grundlagen wissenschaftlichen Arbeitens

76

Iris Meyer

Formale Sprachen und Automaten

Grammatiken:

Grammatiken bestehen aus Regeln mit 2 Arten von Symbolen:

• Terminalsymbole (in der Zeichenkette selbst)

• Nonterminalsymbole (zur Strukturbeschreibung)

Eine Grammatik G ist ein Quadrupel G=(N, T, P,S)

N = Alphabet der Nonterminalsymbole,T = Alphabet der Terminalsymbole,P = Menge von Ersetzungsregeln der Form ,S = Satzsymbol (Startsymbol) aus N

PS Grundlagen wissenschaftlichen Arbeitens

77

Iris Meyer

Formale Sprachen und Automaten

Chomsky- Hierarchie:

Chomsky´s Grammatik-Typen in 4 Stufen:

• Typ 0 oder unbeschränkt

• Typ 1 oder kontextsensitiv

• Typ 2 oder kontextfrei

• Typ 3 oder regulär

PS Grundlagen wissenschaftlichen Arbeitens

78

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

Gegeben sei G = (N, T, P, S) mit

N = {<Name>, <Buchstabe>, <Ziffer>}

T = {a,b,c,0,1,2,3,4,5}

P: <Name> -> <Buchstabe><Name> -> <Name><Ziffer><Buchstabe> -> a|b|c<Ziffer> -> 0|1|2|3|4|5

S = <Name>

PS Grundlagen wissenschaftlichen Arbeitens

79

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

80

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>-> <Name><Ziffer><Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

81

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>-> <Name><Ziffer><Ziffer>-> <Name><Ziffer><Ziffer><Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

82

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>-> <Name><Ziffer><Ziffer>-> <Name><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer><Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

83

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>-> <Name><Ziffer><Ziffer>-> <Name><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer>5

PS Grundlagen wissenschaftlichen Arbeitens

84

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>-> <Name><Ziffer><Ziffer>-> <Name><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer>5-> <Buchstabe><Ziffer>05

PS Grundlagen wissenschaftlichen Arbeitens

85

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>-> <Name><Ziffer><Ziffer>-> <Name><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer>5-> <Buchstabe><Ziffer>05-> <Buchstabe>205

PS Grundlagen wissenschaftlichen Arbeitens

86

Iris Meyer

Formale Sprachen und Automaten

Beispiel zur Chomsky- Hierarchie:

z.B.b205 L(G) da folgende Ableitung möglich ist:

<Name>-> <Name><Ziffer>-> <Name><Ziffer><Ziffer>-> <Name><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer><Ziffer>-> <Buchstabe><Ziffer><Ziffer>5-> <Buchstabe><Ziffer>05-> <Buchstabe>205-> b205

PS Grundlagen wissenschaftlichen Arbeitens

87

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

PS Grundlagen wissenschaftlichen Arbeitens

88

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name> <Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

89

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name>

<Name> <Ziffer>

<Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

90

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name>

<Name>

<Name> <Ziffer>

<Ziffer>

<Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

91

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name>

<Name>

<Name>

<Buchstabe>

<Ziffer>

<Ziffer>

<Ziffer>

PS Grundlagen wissenschaftlichen Arbeitens

92

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name>

<Name>

<Name>

<Buchstabe>

<Ziffer>

<Ziffer>

<Ziffer>

b

PS Grundlagen wissenschaftlichen Arbeitens

93

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name>

<Name>

<Name>

<Buchstabe>

<Ziffer>

<Ziffer>

<Ziffer>

b 2

PS Grundlagen wissenschaftlichen Arbeitens

94

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name>

<Name>

<Name>

<Buchstabe>

<Ziffer>

<Ziffer>

<Ziffer>

b 02

PS Grundlagen wissenschaftlichen Arbeitens

95

Iris Meyer

Formale Sprachen und Automaten

Zur graphischen Darstellung:

der dazugehörige Ableitungsbaum

<Name>

<Name>

<Name>

<Name>

<Buchstabe>

<Ziffer>

<Ziffer>

<Ziffer>

b 502

PS Grundlagen wissenschaftlichen Arbeitens

96

Iris Meyer

Formale Sprachen und Automaten

Reguläre Sprachen:

(Satz von Kleene) Eine Sprache ist genau dann regulär, wenn sie von einem

endlichen Automaten akzeptiert wird.

reguläre Ausdrücke:

• und jedes Element des Alphabets ist ein regulärer Ausdruck

• Wenn und reguläre Ausdrücke sind, dann sind auch (), (), und * reguläre Ausdrücke.

PS Grundlagen wissenschaftlichen Arbeitens

97

Iris Meyer

Formale Sprachen und Automaten

Reguläre Sprachen:

- (Satz von Kleene) Eine Sprache ist genau dann regulär, wenn sie von einem

endlichen Automaten akzeptiert wird.

- reguläre Ausdrücke:

• und jedes Element des Alphabets ist ein regulärer Ausdruck

• Wenn und reguläre Ausdrücke sind, dann sind auch (), (), und * reguläre Ausdrücke.

Mit regulären Ausdrücken lassen sich unendliche Sprachen mit

endlichen Mitteln generieren.

PS Grundlagen wissenschaftlichen Arbeitens

98

Iris Meyer

Formale Sprachen und Automaten

Endliche Automaten:

mathematische Modelle zur Beschreibung des Verhaltens digitaler Systeme

liefern während des Lesens/Verarbeitens keine Ausgabe

• haben einen Anfangszustand in dem sie starten,einen Endzustand in dem sie anhalten können, wodurch sie die eingegebene Zeichenkette als erkannt signalisieren.

• existieren in zwei Varianten:

- deterministischer-Automat (DEA)

- nichtdeterministischer-Automat (NEA)

PS Grundlagen wissenschaftlichen Arbeitens

99

Iris Meyer

Formale Sprachen und Automaten

Endliche Automaten:

mathematische Modelle zur Beschreibung des Verhaltens digitaler Systeme

liefern während des Lesens/Verarbeitens keine Ausgabe

• haben einen Anfangszustand in dem sie starten,einen Endzustand in dem sie anhalten können, wodurch sie die eingegebene Zeichenkette als erkannt signalisieren.

• existieren in zwei Varianten:

- deterministischer-Automat (DEA)

- nichtdeterministischer-Automat (NEA)

PS Grundlagen wissenschaftlichen Arbeitens

100

Iris Meyer

Ende der PräsentationGrill Elisabeth

Meyer Iris

Zöchmeister Katrin

PS Grundlagen wissenschaftlichen Arbeitens

SS 2003