WEBVTT

00:00.000 --> 00:00.320
Meine Damen und Herren,

00:05.510 --> 00:08.710
zunächst Entschuldigung, die Technik hat uns einen Streich gespielt

00:08.710 --> 00:12.850
und wie Sie sehen, der eine Projektor ist kaputt.

00:13.390 --> 00:14.250
Ich kann es nicht ändern.

00:14.970 --> 00:15.590
Tut mir leid.

00:17.710 --> 00:22.090
Wir waren stehen geblieben bei Grammatiken und Herr Gelhausen hat

00:22.090 --> 00:26.830
Ihnen am Freitag in der Übung die Klassifikation vorgeführt, die ich

00:26.830 --> 00:28.190
jetzt ganz kurz nochmal wiederhole.

00:28.190 --> 00:35.730
Wir unterscheiden bei Grammatiken, abhängig von der Art der Regeln,

00:36.570 --> 00:37.930
insgesamt vier Klassen.

00:39.630 --> 00:46.630
Die allgemeinste Klasse sind die Chomsky-Null-Grammatiken, die in der

00:46.630 --> 00:51.070
Lage sind, alles zu machen, was man mit beliebigen Semitudesystemen

00:51.070 --> 00:55.490
auch machen kann, also beliebige Art von Textersetzung.

00:56.670 --> 01:01.750
Das Problem mit dieser allgemeinen Klasse ist, dass ich zwar berechnen

01:01.750 --> 01:12.970
kann, ob irgendein Y aus meinem Stattsymbol S ableitbar ist, aber wie

01:12.970 --> 01:15.550
lange ich dazu brauche, keine Ahnung.

01:16.730 --> 01:22.510
Und insbesondere gibt es im allgemeinen Fall kein Verfahren, mit dem

01:22.510 --> 01:25.510
ich bestimmen könnte, und das Y, das geht bestimmt nicht.

01:28.230 --> 01:31.790
Das heißt, es ist nicht entscheidbar, wie die Sprache aussieht,

01:31.930 --> 01:37.990
sondern es ist nur berechenbar, ob ich irgendein Y ableiten kann.

01:39.050 --> 01:43.770
Das bessert sich bei allen weiteren Klassen, die jetzt Teilklassen von

01:43.770 --> 01:44.730
Chomsky -Null sind.

01:45.070 --> 01:50.150
Zunächst die Klasse der kontextsensitiven Grammatiken, bei denen ich

01:50.150 --> 01:59.310
verlange, dass die Produktionen alle von der Bauart sind, dass hier

01:59.310 --> 02:00.830
ein Nicht-Terminal steht

02:09.720 --> 02:16.840
und dass es hier drumherum einen Kontext geben kann, der muss nicht da

02:16.840 --> 02:20.820
sein, der sich auf der rechten Seite wiederholt.

02:23.760 --> 02:29.580
Also ich habe eingekleidet eine Produktion, die eigentlich heißt, aus

02:29.580 --> 02:37.020
dem Nicht-Terminal A leite R ab, mit der Bedienung, aber nur dann,

02:37.140 --> 02:39.980
wenn U vorangeht und V hintendran folgt.

02:39.980 --> 02:41.420
Und das schreiben wir auch wieder hin.

02:46.700 --> 02:52.900
Also Schema, einer von Ihnen schreibt hier mit und ich sage, ja, du

02:52.900 --> 02:56.500
darfst mitschreiben mit dem, was du da hast, aber nur, wenn dein

02:56.500 --> 03:01.700
linker Nachbar Anton heißt und dein rechter Nachbar Rolf heißt.

03:02.540 --> 03:03.680
Andernfalls darfst du das nicht.

03:04.480 --> 03:08.080
Ich weiß nicht, ob die Bedienung auf irgendjemand von Ihnen zutrifft,

03:09.400 --> 03:13.600
aber das ist plastisch gesehen die Bedienung, die wir bei

03:13.600 --> 03:16.540
kontextsensitiven Grammatiken haben.

03:18.160 --> 03:24.080
Man kann dieselbe Klasse von Sprachen und Grammatiken auch mit einer

03:24.080 --> 03:25.900
anderen Bedienung definieren.

03:26.340 --> 03:30.560
Nämlich, du kannst hier beliebige Regeln hinschreiben.

03:33.200 --> 03:38.080
Aber du musst garantieren, dass auf der linken Seite mindestens ein

03:38.080 --> 03:38.920
Zeichen steht.

03:39.320 --> 03:41.940
Bei Jobs 4.0 habe ich das nicht verlangt.

03:42.120 --> 03:44.240
Da könnte auch Epsilon auf der linken Seite stehen.

03:45.140 --> 03:49.840
Und die rechte Seite muss mindestens so lang sein wie die linke Seite.

03:51.140 --> 03:54.240
Das führt zur gleichen Art von Definition.

03:55.980 --> 04:02.440
Sprich also, eine Folge von Produktionsanwendungen bei einer

04:02.440 --> 04:07.740
kontextsensitiven Grammatik kann immer nur dazu führen, dass entweder

04:07.740 --> 04:14.480
die Länge des Textes, ausgehend vom Stattsymbol, sich verlängert oder

04:14.480 --> 04:15.420
gleiche Länge hat.

04:17.800 --> 04:19.600
Aber sie kann sich niemals verkürzen.

04:21.020 --> 04:23.360
Das hat sofort drastische Konsequenzen.

04:23.360 --> 04:29.000
Da ich also für irgendeine Länge N, sagen wir N gleich 10 Zeichen,

04:29.660 --> 04:35.620
bequem hinschreiben kann, wie viele Texte der Länge N es gibt über

04:35.620 --> 04:37.900
meinem Zeichnungsvorrat.

04:39.680 --> 04:45.420
Und ich außerdem weiß, sobald irgendeine Ableitung mal eine

04:45.420 --> 04:49.860
Zeichenreihe erzeugt hat, der Länge 11, kann sie niemals mehr auf 10

04:49.860 --> 04:50.440
runterkommen.

04:52.980 --> 04:57.680
Dann kann ich in endlicher Zeit entscheiden, ob irgendein Wort der

04:57.680 --> 05:00.680
Länge 10 zur Sprache gehört oder nicht zur Sprache gehört.

05:01.000 --> 05:03.880
Ich muss bloß alles einfach ableiten, was die Länge 10 hat.

05:04.380 --> 05:05.100
Dann bin ich fertig.

05:05.680 --> 05:08.680
Und das geht natürlich für die Länge 100 und für die Länge 100

05:08.680 --> 05:09.980
Millionen ganz genau so.

05:10.980 --> 05:16.220
Das heißt also, im Unterschied zu Chomsky-Null-Grammatiken, wo es

05:16.220 --> 05:24.760
unentscheidbar war, ob das Y zu ableitbar ist oder nicht, nur die eine

05:24.760 --> 05:29.680
Richtung war da, kann ich es jetzt entscheiden, weil ich einfach die

05:29.680 --> 05:32.720
endlich vielen Ableitungen, die überhaupt zum Erfolg führen könnten,

05:33.020 --> 05:34.120
auch hinschreiben kann.

05:35.120 --> 05:36.800
Und damit geht's.

05:37.660 --> 05:40.720
Sie werden sagen, praktisch geht's nicht, das ist richtig, es geht

05:40.720 --> 05:42.260
theoretisch.

05:43.320 --> 05:48.660
Denn wenn die Länge 100 Millionen ist, dann schreiben sich die

05:48.660 --> 05:52.520
Fingerbund und ihre Kinder und Enkelkinder schreiben sich immer noch

05:52.520 --> 05:54.220
die Fingerbund, weil sie immer noch nicht fertig sind.

06:00.880 --> 06:01.900
Bei Null.

06:03.380 --> 06:08.720
Bei Chomsky-Null ist berechenbar, ob Y in der Sprache ist.

06:09.480 --> 06:11.680
Aber die Umkehrung ist nicht berechenbar.

06:14.040 --> 06:19.080
Er fragt, ob es nie berechenbar ist und die Antwort ist dieselbe, die

06:19.080 --> 06:20.370
ich einige Folien früher...

06:20.370 --> 06:25.370
Jetzt weiß ich die Foliennummer nicht, aber ich gehe mal zurück, ob

06:25.370 --> 06:26.010
ich es finde.

06:39.700 --> 06:40.480
Hier steht es, ja.

06:41.340 --> 06:45.200
Hier hatten wir also, das ist also Folie 64, ja.

06:46.060 --> 06:49.600
Hier hatten wir definiert, was berechenbar heißt und hier hatten wir

06:49.600 --> 06:51.340
definiert, was entscheidbar heißt.

06:52.160 --> 06:56.720
Und hatten eingesehen, dass Entscheidbarkeit bedeutet, sowohl die

06:56.720 --> 07:02.620
Menge M muss berechenbar sein, also muss gerade die Funktionswerte

07:02.620 --> 07:08.700
einer Funktion F enthalten, als auch das Kompliment der Menge M.

07:08.880 --> 07:13.480
Also in diesem Fall heißt Kompliment, man nehme sämtliche möglichen

07:13.480 --> 07:18.200
Zeichen rein, die es gibt und streiche diejenigen raus, die zu M

07:18.200 --> 07:18.600
gehören.

07:18.600 --> 07:23.320
Dann habe ich das Kompliment und beides muss berechenbar sein.

07:23.820 --> 07:28.320
Und die Feststellung lautete an dieser Stelle, es gibt keinen

07:28.320 --> 07:37.020
allgemeinen Algorithmus, der berechnet, ob irgendetwas entscheidbar

07:37.020 --> 07:40.800
ist, wenn es nur berechenbar ist.

07:45.570 --> 07:50.710
Allgemein heißt ein Algorithmus, der in diesem Beispiel hier jetzt auf

07:50.710 --> 07:55.290
beliebige Semituessysteme, im Fall der Grammatiken, auf beliebige

07:55.290 --> 07:57.910
Jomskenui -Grammatiken anwendbar ist.

07:58.310 --> 08:00.510
Akzent und Betonung auf beliebige.

08:03.010 --> 08:06.870
Sobald Sie mir irgendeinen Spezialfall vorgeben, also eine konkrete

08:06.870 --> 08:11.690
Grammatik oder eine Teilklasse der Jomskenui-Grammatiken, dann kann es

08:11.690 --> 08:14.130
durchaus sein, dass ich einen solchen Algorithmus angeben kann.

08:14.730 --> 08:16.810
Aber im allgemeinen Fall geht es nicht.

08:18.290 --> 08:19.930
Das ist die Aussage, die wir haben.

08:21.710 --> 08:23.850
Macht das die Sache klar oder gibt es jetzt weitere Fragen?

08:35.150 --> 08:35.690
Noch Fragen?

08:40.540 --> 08:43.480
Gut, dann wissen wir also jetzt, bei Jomski 1 ist die Sache

08:43.480 --> 08:47.860
entscheidbar, bei Jomski 0 ist es nicht entscheidbar und bei

08:47.860 --> 08:51.300
Kontextsensitiv haben wir also gesehen, wir haben eigentlich eine

08:51.300 --> 08:58.380
solche Produktion ab Pfeil R vorliegen, aber wir können dazu sagen,

08:58.480 --> 09:01.620
die wenden Sie bitte schön nur an in einem gewissen Kontext.

09:02.240 --> 09:07.000
Wenn ich jetzt den Kontext weglasse, dann komme ich zu Jomski 2

09:07.000 --> 09:10.580
-Grammatiken, die im Allgemeinen als kontextfreie Grammatiken

09:10.580 --> 09:16.440
bezeichnet werden und jetzt lasse ich einfach das U und V weg und

09:16.440 --> 09:18.080
schreibe nur noch hin ab Pfeil R.

09:19.260 --> 09:22.520
Wenn alle Produktionen von dieser Bauart sind, dann nenne ich das

09:22.520 --> 09:24.400
ganze Ding kontextfrei.

09:26.960 --> 09:31.420
Kontextfreie Grammatiken sind verglichen mit den zwei vorangehenden

09:31.420 --> 09:37.680
Gruppen, Kontextsensitiv und Jomski 0, aus zwei Gründen von großer

09:37.680 --> 09:38.260
Bedeutung.

09:39.480 --> 09:44.780
Der eine Grund ist, wenn Sie mir eine Jomski 0 oder eine Jomski 1

09:44.780 --> 09:51.140
Grammatik vorlegen und sagen, sieh mal nach, ob irgendein Satz

09:51.140 --> 09:55.320
reduzierbar ist auf das Startsymbol S.

09:57.340 --> 10:02.180
Dann kann ich zwar Automaten konstruieren, die das zu tun versuchen,

10:03.040 --> 10:05.360
aber die arbeiten mit riesigem Zeitaufwand.

10:07.620 --> 10:12.200
Und wenn Sie mir also ein Wort vorlegen der Länge N, dann ist

10:12.200 --> 10:16.220
keineswegs gewährleistet, dass ich in N Zeiteinheiten, egal wie die

10:16.220 --> 10:19.980
Zeiteinheit gewählt ist, zum Ziel komme.

10:21.480 --> 10:26.680
Bei Jomski 0 kann das also sogar exponentiell ansteigen oder

10:26.680 --> 10:27.020
überexponentiell.

10:28.180 --> 10:34.120
Und das bedeutet, dass Jomski 0 und Jomski 1 für praktische Zwecke der

10:34.120 --> 10:37.320
Textverarbeitung eigentlich keine Rolle spielen.

10:37.440 --> 10:39.180
Es sind wichtige theoretische Klassen.

10:40.920 --> 10:46.360
Aber da ich keine vernünftigen Programme angeben kann, um solche

10:46.360 --> 10:49.700
Grammatiken und die Sprachen zu verarbeiten, und vernünftig heißt

10:49.700 --> 10:56.340
jetzt hier, Verfahren, die mit linearem Zeitaufwand gemessen in der

10:56.340 --> 11:00.860
Länge der Eingabe arbeiten, scheide ich die praktisch aus.

11:02.060 --> 11:03.460
Bei Jomski 2 geht das.

11:06.920 --> 11:09.300
Jomski 2 ist eine Unterklasse von Jomski 1.

11:09.400 --> 11:12.560
Wir werden gleich noch sehen, dass ich das ein bisschen zurückhaltend

11:12.560 --> 11:13.380
beurteilen muss.

11:15.200 --> 11:22.380
Und bei dieser Unterklasse kann ich jetzt Programme angeben, die mit

11:22.380 --> 11:28.980
linearem Zeitaufwand gerechnet in der Länge feststellen, ob ein Satz

11:28.980 --> 11:32.180
zur Sprache gehört oder nicht zur Sprache gehört, und ich kann ihn

11:32.180 --> 11:32.940
auch ableiten.

11:33.800 --> 11:36.460
Wir werden uns das hinterher klar machen, intuitiv, wie das

11:36.460 --> 11:37.000
funktioniert.

11:38.420 --> 11:40.060
Das ist die eine wichtige Eigenschaft.

11:40.240 --> 11:43.520
Das heißt, es ist die größte Klasse von diesen ganzen Klassen, mit

11:43.520 --> 11:45.140
denen ich noch vernünftig arbeiten kann.

11:45.140 --> 11:51.160
Die zweite zentrale Eigenschaft ist, viel kleiner geht es nicht.

11:54.000 --> 11:58.720
Denn, wie wir ebenfalls hinterher an Beispielen sehen werden, wenn ich

11:58.720 --> 12:03.500
Klammernstrukturen verarbeiten will, und garantieren will, dass

12:03.500 --> 12:06.720
irgendein arithmetischer Ausdruck richtig geklammert ist, also zu

12:06.720 --> 12:09.580
jeder öffnenden Klammer gibt es eine schließende Klammer, und

12:09.580 --> 12:10.300
umgekehrt.

12:11.540 --> 12:15.080
Dann geht das mit Chomsky 0, dann geht das mit Chomsky 1, dann geht

12:15.080 --> 12:19.520
das mit Chomsky 2, aber mit wesentlich kleineren Klassen, zum Beispiel

12:19.520 --> 12:21.460
der Klasse Chomsky 3, geht das nicht.

12:24.000 --> 12:29.260
Das heißt, bei den kontextfreien Grammatiken bleibe ich stehen, weil

12:29.260 --> 12:35.180
das einige Eigenschaften hat, die ich unbedingt brauche.

12:36.040 --> 12:38.020
Klammerstruktur ist also prüfbar

12:48.600 --> 12:53.420
und mit linearem Zeitaufwand

13:00.930 --> 13:03.630
bearbeitbar.

13:11.060 --> 13:13.440
Das sind die ganz wesentlichen Eigenschaften.

13:14.360 --> 13:18.880
Ganz befriedigend ist es nicht, denn es stellt sich heraus, dass

13:18.880 --> 13:22.160
unsere Programmiersprachen, wenn da irgendwelche Vereinbarungen drin

13:22.160 --> 13:24.780
entstehen, eigentlich kontextsensitiv sind.

13:24.780 --> 13:28.020
Aber dann muss ich mich halt irgendwie nach der Decke strecken.

13:28.860 --> 13:31.960
Ich kann nicht kontextsensitive Grammatiken nehmen, das funktioniert

13:31.960 --> 13:33.280
nicht mit vernünftigem Aufwand.

13:34.800 --> 13:38.120
Also muss ich da zu irgendwelchen anderen Tricks greifen, die wir hier

13:38.120 --> 13:38.940
jetzt nicht besprechen.

13:40.660 --> 13:43.800
Es gibt dann eine weitere Unterklasse, nämlich die Chomsky 3

13:43.800 --> 13:47.360
Grammatiken, die auch reguläre Grammatiken heißen.

13:48.060 --> 13:51.960
Bei denen vereinfache ich die ganze Geschichte jetzt noch weiter.

13:52.460 --> 13:57.500
Sprich also, ich bleibe bei meinen kontextfreien Produktionen

13:57.500 --> 14:01.020
einerseits, aber jetzt mache ich Vorschriften, wie das R aufgebaut

14:01.020 --> 14:01.480
ist.

14:02.380 --> 14:09.120
Und ich lasse nur zwei verschiedene Formen zu, oder drei verschiedene

14:09.120 --> 14:09.940
Formen von R.

14:10.400 --> 14:16.260
Nämlich, ich lasse zu, dass die ganze Geschichte rechtslinear ist.

14:19.550 --> 14:23.070
Also die Produktion hat die Form, da kommt zuerst ein terminales

14:23.070 --> 14:24.470
Zeichen, das ist aus Sigma.

14:25.130 --> 14:28.390
Und dann kommt ein einziges nicht terminales Zeichen.

14:28.870 --> 14:32.550
Keine zwei, keine drei, genau eines.

14:34.610 --> 14:39.330
Zweitens lasse ich zu, dass dieses nicht-terminale Zeichen B sogar

14:39.330 --> 14:40.070
fehlen könnte.

14:42.730 --> 14:46.170
Ja, und je nach Geschmack, manchmal brauche ich es, manchmal mache ich

14:46.170 --> 14:48.270
das nicht, lasse ich auch noch das zu.

14:48.450 --> 14:50.030
Ich versuche das mal mit Fragezeichen.

14:54.690 --> 15:01.230
Das ist die Definition von linkslinearen Produktionen.

15:02.170 --> 15:06.170
Und das führt zur Definition von regulären Grammatiken.

15:06.610 --> 15:12.810
Wenn ich dann frage, du hast irgendeine solche linkslineare Grammatik

15:12.810 --> 15:16.370
mit linkslinearen Produktionen, hätten wir denn nicht auch die anderen

15:16.370 --> 15:17.190
nehmen können?

15:21.320 --> 15:25.220
Also hätten wir das nicht auch so machen können, dass wir diese Gruppe

15:25.220 --> 15:25.740
hier nehmen?

15:27.380 --> 15:33.980
Also die linkslinearen Produktionen gegen die rechtslinearen

15:33.980 --> 15:35.480
austauchen oder umgekehrt?

15:36.020 --> 15:37.240
Die Antwort lautet, das geht auch.

15:40.580 --> 15:42.040
Aber bitte nicht beide gemischt.

15:44.580 --> 15:48.360
Sie müssen eine Wahl treffen zwischen linkslinear und rechtslinear,

15:48.780 --> 15:50.400
beides zusammen dürfen Sie nicht nehmen.

15:56.230 --> 15:57.170
Gibt es dazu Fragen?

16:01.640 --> 16:05.760
Schön, da also die kontextfreien Grammatiken schon mit linearem

16:05.760 --> 16:10.360
Aufwand bearbeitbar sind, sind das natürlich die Chomsky-3-Grammatiken

16:10.360 --> 16:11.000
erst recht.

16:12.220 --> 16:16.280
Bleibt uns eine subtile Frage, die wir jetzt durch alle diese Dinge

16:16.280 --> 16:19.500
nochmal durchverfolgen müssen, und das ist die Frage, wie wir mit dem

16:19.500 --> 16:20.460
leeren Wort umgehen.

16:21.980 --> 16:28.080
Die ursprüngliche Definition von Herrn Chomsky sagte, bei Chomsky-0

16:28.080 --> 16:29.810
-Grammatiken ist alles zulässig.

16:30.300 --> 16:34.100
Also die linke Seite und die rechte Seite sind aus V-Stern.

16:34.440 --> 16:37.680
Du kannst links Epsilon schreiben, du kannst rechts Epsilon schreiben,

16:37.960 --> 16:38.520
wenn du willst.

16:41.460 --> 16:46.840
Bei Chomsky-1-Grammatiken muss auf der linken Seite auf jeden Fall ein

16:46.840 --> 16:48.260
Nicht -Terminal stehen.

16:50.460 --> 16:52.560
Also da ist kein Epsilon mehr zulässig.

16:53.300 --> 16:57.060
Und Herr Chomsky hat jetzt gesagt, die rechte Seite muss mindestens

16:57.060 --> 16:58.380
Länge 1 haben.

16:59.640 --> 17:03.620
Weshalb an dieser Stelle jetzt nicht mehr V-Stern steht, sondern V

17:03.620 --> 17:04.000
-Plus.

17:04.120 --> 17:05.980
Mindestens ein Zeichen muss da sein.

17:08.910 --> 17:12.270
Das ist offensichtlich notwendig, wenn die Eigenschaft erreicht werden

17:12.270 --> 17:19.790
soll, die wir vorhin diskutierten, dass nämlich kontextsensitive

17:19.790 --> 17:21.950
Produktionen niemals verkürzen können.

17:23.890 --> 17:24.910
Sonst könnten sie verkürzen.

17:26.810 --> 17:33.970
Bei Chomsky-2 steht bei R wieder V-Stern.

17:35.290 --> 17:36.750
Da ist das Epsilon zulässig.

17:38.650 --> 17:42.450
Und das bedeutet also eigentlich, dass nicht jede kontextfreie

17:42.450 --> 17:44.790
Grammatik automatisch auch kontextsensitiv ist.

17:47.770 --> 17:51.150
Und wenn Sie in den Lehrbüchern nachschauen, dann finden Sie zahllose

17:51.150 --> 17:56.590
Lehrbücher, die bei Chomsky-3 wieder sagen, den Pfeil da unten,

17:57.690 --> 18:00.810
Abpfeil Epsilon, den haben wir gar nicht auf der Rechnung.

18:01.330 --> 18:02.290
Den mögen wir auch nicht.

18:03.970 --> 18:05.730
Jetzt ist das Durcheinander allzu groß.

18:07.170 --> 18:11.510
Chomsky-0 lässt rechts Epsilon zu, Chomsky-1 tut es nicht, Chomsky-2

18:11.510 --> 18:13.270
tut es, Chomsky-3 tut es nicht.

18:16.790 --> 18:20.710
Das ist für theoretische wie für praktische Zwecke unbefriedigend.

18:21.750 --> 18:27.390
Und daher verfeinert man die Definitionen heute sehr häufig wie folgt.

18:29.450 --> 18:36.350
Ich lasse bei Chomsky-1 auch das Epsilon zu, aber bitte nur ein

18:36.350 --> 18:37.050
einziges Mal.

18:39.110 --> 18:44.270
Und dieses eine Mal muss auf der linken Seite das Stadtsymbol S

18:44.270 --> 18:44.710
stehen.

18:45.750 --> 18:48.970
Das heißt, ich verlange dann, dass an dieser Stelle das Stadtsymbol

18:48.970 --> 18:49.410
steht.

18:51.750 --> 18:54.950
Das Stadtsymbol kommt nirgends auf der rechten Seite vor.

18:57.110 --> 18:59.090
Diese Konstruktion ist verboten.

19:01.570 --> 19:06.410
Und das bedeutet dann, dass eine solche kontextsensitive Grammatik

19:06.410 --> 19:10.850
zwar in der Lage ist, den leeren Satz zu erzeugen, aber sobald Sie mal

19:10.850 --> 19:14.890
beschlossen haben, der leere Satz ist es nicht, hat es die schöne

19:14.890 --> 19:17.150
Eigenschaft, dass es niemals die Länge verkürzt.

19:20.500 --> 19:24.660
Und gleichzeitig haben wir mit dieser Eigenschaft, jetzt wenn wir zu

19:24.660 --> 19:30.520
Chomsky -2 übergehen, das wird Ihnen im dritten Semester bewiesen

19:30.520 --> 19:36.400
werden, die Eigenschaft, dass die Tatsache, dass ich hier R aus V

19:36.400 --> 19:40.940
stand zulasse, also Epsilon an beliebiger Stelle, das kann ich wieder

19:40.940 --> 19:45.600
auf den Fall zurückführen, dass ich Epsilon nur beim Stadtsymbol an

19:45.600 --> 19:48.900
einer Regel zulasse und sonst nirgends.

19:50.140 --> 19:55.840
Allerdings in der praktischen Anwendung ist diese Spezialisierung von

19:55.840 --> 19:58.680
kontextfreien Grammatiken ziemlich unsinnig.

19:58.780 --> 20:00.800
Wir werden das noch am praktischen Beispiel sehen.

20:01.280 --> 20:04.840
Das Epsilon ist für uns unverzichtbar in der Beschreibung von

20:04.840 --> 20:05.780
Programmiersprachen.

20:06.520 --> 20:10.060
Immer dann, wenn wir hinschreiben wollen und optional kannst du auch

20:10.060 --> 20:11.120
noch das und das schreiben.

20:12.500 --> 20:15.540
Dann wird es in der Grammatik beschrieben mit einer Produktion, bei

20:15.540 --> 20:17.360
der ein Epsilon vorkommt.

20:18.420 --> 20:19.920
Dafür braucht man es praktisch.

20:21.440 --> 20:26.300
Hingegen ist diese Regel ab Fall Epsilon in der praktischen

20:26.300 --> 20:31.880
Konstruktion ziemlich uninteressant bei regulären Grammatiken, denn da

20:31.880 --> 20:35.220
kann ich nachweisen, du kannst die Epsilons hinschreiben oder du

20:35.220 --> 20:36.500
kannst sie auch nicht hinschreiben.

20:36.900 --> 20:40.640
Ich sorge auf jeden Fall dafür, dass mein Rechner in der Lage ist, das

20:40.640 --> 20:42.960
so zu transformieren, dass die Epsilons nicht mehr da sind.

20:44.220 --> 20:46.360
Da brauche ich also nicht mal nachdenken drüber.

20:46.880 --> 20:49.740
Das ist nicht mal eine Übungsaufgabe wert, sondern das ist eine Sache,

20:49.860 --> 20:50.820
die der Rechner machen kann.

20:51.460 --> 20:51.700
Frage.

20:56.080 --> 20:58.540
Epsilon heißt, ich bin das leere Wort.

20:59.580 --> 21:00.620
Länge 0.

21:02.920 --> 21:03.860
So war es definiert.

21:04.920 --> 21:09.960
Also ist Epsilon, enthält kein Terminalzeichen und es enthält kein

21:09.960 --> 21:11.180
Nicht -Terminalzeichen.

21:11.180 --> 21:13.280
Es enthält Nullzeichen.

21:17.380 --> 21:25.600
Also wenn die erste Bank hier vorne leer ist, dann dürfen Sie also

21:25.600 --> 21:29.000
gerne fragen, sitzt in der ersten Bank ein Professor oder sitzt ein

21:29.000 --> 21:30.080
Student in der ersten Bank?

21:30.920 --> 21:32.040
Die erste Bank ist leer.

21:34.100 --> 21:35.560
Daher ist die Frage sinnlos.

21:41.650 --> 21:42.090
Klar?

21:47.390 --> 21:51.730
So, dieses Bild zeigt jetzt also die Enthaltenseinsrelation.

21:54.050 --> 21:59.950
Mit den Zusatzangaben hier unten, dass das also voraussetzt, dass ich

21:59.950 --> 22:03.950
die Chomsky 1 entsprechend definiert habe, sodass dann Chomsky 2

22:03.950 --> 22:05.530
reinkommt.

22:07.250 --> 22:09.810
Und das ist also die Einschränkung dieser ganzen Geschichte.

22:12.150 --> 22:17.390
Folglich, wenn Sie also eine Frage bekommen, gegeben eine Grammatik,

22:17.690 --> 22:21.650
bestimmen Sie zu welcher Chomsky-Klasse das gehört.

22:23.230 --> 22:26.610
Dann ist entsprechend der Enthaltenseinsrelation, die wir hier sehen,

22:27.010 --> 22:28.710
natürlich eine Antwort immer richtig.

22:28.850 --> 22:29.430
Chomsky 0.

22:30.970 --> 22:32.050
Können Sie nichts falsch machen.

22:33.450 --> 22:35.450
Aber das ist nicht die Frage auf die Antwort.

22:36.310 --> 22:40.570
Sondern wenn eine solche Frage gestellt wird, dann ist immer gefragt

22:40.570 --> 22:46.510
nach der kleinsten Klasse, die die vorgegebene Produktionenmenge noch

22:46.510 --> 22:46.870
enthält.

22:48.370 --> 22:51.710
Also wenn Sie in der Prüfung sowas gefragt werden, dann ist die

22:51.710 --> 22:54.570
Antwort richtig, ich gebe die kleinste Klasse an.

22:54.570 --> 22:59.810
Wenn das als regulär ist, dann ist die Antwort Chomsky 3 oder regulär

22:59.810 --> 23:04.590
richtig und die Antworten Chomsky 2, Chomsky 1, Chomsky 0 sind falsch.

23:04.950 --> 23:07.050
Obwohl sie natürlich eigentlich auch richtig sind, aber es ist nicht

23:07.050 --> 23:07.790
die kleinste Klasse.

23:12.620 --> 23:17.200
Die Folie brauche ich jetzt gar nicht mehr diskutieren, die stellt

23:17.200 --> 23:20.820
Ihnen bloß zu merken zusammen, was ich für verschiedene Arten von

23:20.820 --> 23:25.320
Produktionen also jetzt unterschieden habe, damit man das hinterher

23:25.320 --> 23:26.040
gut lernen kann.

23:28.020 --> 23:35.340
Damit kommen wir jetzt zu den praktischen Anwendungen von

23:35.340 --> 23:40.120
kontextfreien Grammatiken und das erste Beispiel, was wir behandeln,

23:40.340 --> 23:44.580
ist eines, was wir auch immer und immer wieder sehen werden, auch im

23:44.580 --> 23:45.260
Programmieren.

23:46.380 --> 23:54.420
Wir möchten arithmetische Ausdrücke beschreiben und zwar so, dass da

23:54.420 --> 23:58.660
erlaubt ist Addition und Multiplikation, die Subtraktion und Division

23:58.660 --> 24:00.200
lasse ich jetzt mal weg.

24:00.940 --> 24:04.620
Ich möchte haben, dass die richtigen Vorrangregeln gelten, also A plus

24:04.620 --> 24:09.340
B mal C soll geklammert werden in A plus Klammer auf B mal C, Klammer

24:09.340 --> 24:09.560
zu.

24:12.120 --> 24:16.200
Klammern sind zulässig und außerdem lasse ich Variable zu.

24:16.810 --> 24:23.300
Da müsste ich also jetzt hinschreiben, das ist eine Grammatik D mit

24:23.300 --> 24:32.160
einem nicht-terminalen Zeichenvorrat Sigma, einem nicht-terminalen

24:32.160 --> 24:39.400
Zeichenvorrat N, einem Produktionenmenge P und irgendeinem Start- oder

24:39.400 --> 24:40.560
Zielsymbol Z.

24:41.340 --> 24:43.200
Und das muss ich alles genau aufschreiben.

24:44.700 --> 24:46.620
Das ist mir praktisch zu langweilig.

24:49.220 --> 24:53.280
Denn ich überlege mir als erstes, wenn du die Produktionen

24:53.280 --> 24:57.100
hingeschrieben hast, dann musst du alles andere irgendwie schließen

24:57.100 --> 24:57.520
können.

24:59.160 --> 25:02.220
Du musst schließen können, wie Sigma aussieht, du musst schließen

25:02.220 --> 25:05.500
können, wie die Nicht-Terminale aussehen, du musst schließen können,

25:05.680 --> 25:07.760
wie das Symbol Z aussieht.

25:07.760 --> 25:11.940
Und dazu hat man die folgenden Konventionen.

25:12.160 --> 25:18.280
Man gibt nur die Produktionen an und sagt als erstes mal, die linke

25:18.280 --> 25:24.540
Seite der ersten Produktion, das ist das Start-Symbol Z.

25:26.780 --> 25:28.340
Das ist einfach eine Konvention.

25:32.340 --> 25:36.600
Wenn ich also hier unten jetzt diese Grammatik betrachte, dann schaue

25:36.600 --> 25:40.620
ich da bloß hin und stelle als erstes fest, aha, das Start-Symbol Z

25:40.620 --> 25:43.900
heißt hier A, denn das ist das allererste Symbol, was vorkommt.

25:48.680 --> 25:52.440
Dann verlange ich, dass alle nicht-terminalen Zeichen wenigstens

25:52.440 --> 25:54.740
einmal auf der linken Seite einer Produktion vorkommen.

25:56.480 --> 26:00.500
Und jetzt kann ich sofort sagen, was denn überhaupt alles vorkommt.

26:00.600 --> 26:03.300
Es kommen Terminale und Nicht-Terminale Zeichen vor.

26:04.220 --> 26:09.900
Und ich brauche bloß die verschiedenen Zeichen mir anschauen und

26:09.900 --> 26:13.700
klassifizieren, kommt es auf der linken Seite vor, kommt es nicht auf

26:13.700 --> 26:14.640
der linken Seite vor.

26:14.980 --> 26:18.160
Wenn es links vorkommt, ist es ein Nicht-Terminal, wenn es nicht links

26:18.160 --> 26:19.440
vorkommt, ist es ein Terminal.

26:20.680 --> 26:25.080
Das heißt Sigma wird einfach bestimmt, das sind alle die Zeichen, die

26:25.080 --> 26:26.680
nur auf rechten Seiten vorkommen.

26:30.560 --> 26:33.040
Und alles andere sind Nicht-Terminale.

26:33.160 --> 26:35.100
Also wieder bei diesem Beispiel hier unten.

26:35.680 --> 26:43.400
Die Nicht-Terminale sind offensichtlich A, T, F, denn das ist alles,

26:43.520 --> 26:45.100
was auf der linken Seite vorkommt.

26:46.400 --> 26:51.320
Das Z, das Symbol A ist, hatten wir bereits festgestellt.

26:52.660 --> 26:54.860
Ja, und was kommt auf der rechten Seite vor?

26:55.200 --> 27:00.000
Da kommt dann zusätzlich das Plus-Zeichen, das Mal-Zeichen, das eine

27:00.000 --> 27:02.560
Symbol BEZ und die Klammern vor.

27:03.040 --> 27:09.940
Also weiß ich jetzt, dass Sigma gleich ist, Plus, Mal-Zeichen, Klammer

27:09.940 --> 27:15.860
auf, Klammer zu und das Symbol BEZ.

27:17.460 --> 27:20.280
Warum habe ich den senkrechten Strich nicht gerechnet?

27:20.740 --> 27:24.240
Weil ich noch eine weitere Produktion habe, es ist mir zu langweilig,

27:24.600 --> 27:27.660
immer zu schreiben A-Pfeil mit irgendetwas.

27:28.940 --> 27:34.360
Ich bin in der Lage mehrere Produktionen mit gleicher linker Seite

27:34.360 --> 27:39.020
zusammenzufassen zu einer Produktion, bei der ich die rechten Seiten

27:39.020 --> 27:41.840
hintereinander hinschreibe und einen senkrechten Strich dahinter.

27:42.840 --> 27:43.500
Dazwischen.

27:44.720 --> 27:51.380
Und diesen senkrechten Strich lese ich also dementsprechend als Oder.

27:59.150 --> 28:03.170
Also kann ich an dem Beispiel hier unten jetzt feststellen, die erste

28:03.170 --> 28:09.910
Produktion heißt A-Pfeil-T oder A-T.

28:11.310 --> 28:12.670
So lese ich das vor.

28:16.030 --> 28:20.590
Und statt A-Pfeil sage ich oft A-Ist-Ein.

28:20.790 --> 28:24.270
Das heißt also den Pfeil hier lese ich als Ist.

28:30.360 --> 28:34.160
Womit ich meine, wenn du A hast, dann kannst du das ersetzen durch.

28:35.200 --> 28:38.140
Ja und danach ist es natürlich das, was auf der rechten Seite steht.

28:42.770 --> 28:44.950
Soviel zu den Konventionen, wie man sowas liest.

28:45.930 --> 28:48.410
Und jetzt schauen wir uns das Beispiel genauer an.

28:49.810 --> 28:54.990
Und stellen fest, was ich hier beschrieben habe, ist, dass wenn ich

28:54.990 --> 28:58.330
einen einfachen Bezeichner, und für Bezeichner schreibe ich jetzt

28:58.330 --> 29:02.410
irgendwelche Buchstaben hin, A für sich alleine habe.

29:03.970 --> 29:05.730
Das ist dann mein Bezeichner.

29:06.190 --> 29:08.710
Weil es ein Bezeichner ist, ist es ein F.

29:08.710 --> 29:12.710
Das F dürfen Sie in diesem Beispiel lesen wie Faktor.

29:14.550 --> 29:15.820
So wird es dann hinterher ausgeschrieben.

29:18.210 --> 29:23.190
Und ein Faktor könnte ein T sein und das T, wenn ich es ausschreibe,

29:23.670 --> 29:24.710
lese ich als Term.

29:28.370 --> 29:31.950
Und ein Term ist ein arithmetischer Ausdruck, ein A.

29:31.950 --> 29:32.790
Und

29:42.030 --> 29:46.690
ich stelle jetzt zunächst fest, dass wenn ich einfach nur einen

29:46.690 --> 29:51.010
einzelnen Buchstaben hinschreibe, eine einfache Variable, dann ist das

29:51.010 --> 29:52.470
ein arithmetischer Ausdruck.

29:52.990 --> 29:55.030
Wenn ich hinschreibe A plus B,

30:00.030 --> 30:05.130
dann stelle ich fest, dass A, das wissen wir schon bereits, ist ein

30:05.130 --> 30:06.610
arithmetischer Ausdruck.

30:07.790 --> 30:11.070
Auf einem arithmetischen Ausdruck kann nach dieser Regel ein

30:11.070 --> 30:12.050
Pluszeichen folgen.

30:12.950 --> 30:15.030
Und dann könnte ein Term folgen.

30:15.450 --> 30:18.750
Und ein Term ist ein Faktor und ein Faktor ist ein Bezeichner und B

30:18.750 --> 30:19.690
ist ein Bezeichner.

30:20.650 --> 30:22.990
Also ist A plus B auch eine korrekte Konstruktion.

30:24.350 --> 30:28.030
Völlig analog schließe ich, dass A mal B eine korrekte Konstruktion

30:28.030 --> 30:28.410
ist.

30:29.170 --> 30:32.790
Nur wende ich dann nicht die Regel A plus T an, sondern ich bleibe

30:32.790 --> 30:37.250
stehen und sage, ich weiß ja schon, dass das A ein Term ist und dass

30:37.250 --> 30:41.030
das B ein Faktor ist und dann ist also Term mal Faktor offensichtlich

30:41.030 --> 30:41.630
ein Term.

30:42.050 --> 30:44.430
Und ein Term ist ein arithmetischer Ausdruck, also das ist auch

30:44.430 --> 30:44.830
korrekt.

30:46.650 --> 30:50.970
Und selbstverständlich ist demnach auch A plus B in Klammern korrekt.

30:52.530 --> 30:57.270
Denn da fabrizieren wir zuerst einen arithmetischen Ausdruck A und

30:57.270 --> 30:59.430
dann setzen wir ihn in Klammern und dann haben wir plötzlich wieder

30:59.430 --> 30:59.970
einen Faktor.

31:02.010 --> 31:04.450
Ja, ein Faktor ist ein Term und ein Term ist ein arithmetischer

31:04.450 --> 31:04.870
Ausdruck.

31:07.470 --> 31:12.310
Und A plus B mal C ist ebenfalls korrekt.

31:14.710 --> 31:17.890
Denn wir wissen bereits, der Klammerausdruck ist ein Faktor, daher

31:17.890 --> 31:18.630
auch ein Term.

31:20.390 --> 31:26.230
Und auf einem Term kann ein Malzeichen folgen und auf dem kann ein

31:26.230 --> 31:28.390
Faktor folgen und ein Bezeichner ist ein Faktor.

31:30.890 --> 31:35.630
Sprich, also ich kann solche Beispiele mit Hilfe dieser Grammatik

31:35.630 --> 31:36.230
ableiten.

31:37.670 --> 31:40.650
Und man kann auf die Umkehrung sich schnell überlegen.

31:40.770 --> 31:45.230
Sämtliche Ausdrücke, bei denen die Elementaroperanten nur Bezeichner

31:45.230 --> 31:53.770
sind und als Operatoren nur Plus und Mal zugelassen sind, die kann ich

31:53.770 --> 31:55.110
auf diese Art und Weise herleiten.

31:56.330 --> 32:01.510
Nun haben wir zur Einleitung der Grammatik uns überlegt, dass wir

32:01.510 --> 32:06.710
diesen Satz, ein Informatiker isst Schokolade, als Baum hinschreiben

32:06.710 --> 32:07.150
können.

32:07.750 --> 32:10.870
Und jetzt erinnern wir uns daran und versuchen dasselbe Spielchen mal

32:10.870 --> 32:14.890
mit den Beispielen, die wir da gerade haben.

32:15.250 --> 32:19.810
Ich habe mir hier herausgesucht den arithmetischen Ausdruck A plus B

32:19.810 --> 32:22.090
mal C plus D.

32:22.090 --> 32:26.570
Und beachten Sie, das heißt also A plus B ist geklammert, wird mit C

32:26.570 --> 32:31.070
multipliziert und zu diesem Multiplikationsergebnis wird D addiert.

32:31.550 --> 32:34.590
Dass mir ja niemand auf die Idee kommt zu sagen, das wird

32:34.590 --> 32:36.090
multipliziert mit C plus D.

32:37.570 --> 32:40.230
Das sollte man schon in der Schule gelernt haben, dass das nicht der

32:40.230 --> 32:40.730
Fall ist.

32:43.970 --> 32:46.550
So und jetzt wollen wir mal nachschauen, wie die Struktur aussieht.

32:46.850 --> 32:49.430
Die Regeln habe ich hier oben nochmal hingeschrieben, das sind

32:49.430 --> 32:51.430
dieselben Regeln wie auf der letzten Folie.

32:56.010 --> 32:59.300
Der oberste Operator, der alles regiert, ist das Pluszeichen.

32:59.970 --> 33:03.930
Also nehme ich mal für meinen arithmetischen Ausdruck an, dass das A

33:03.930 --> 33:06.070
plus T sei, das ist die erste Regel.

33:06.830 --> 33:14.190
Und dann kann ich als Baum hinmalen ein A plus T in der zweiten Reihe.

33:16.350 --> 33:19.050
Das müsste dieses Pluszeichen gewesen sein.

33:19.950 --> 33:24.830
Also schaue ich mir mal das T hier an und stelle fest, das T ist ein

33:24.830 --> 33:25.690
Term hier.

33:26.930 --> 33:30.390
Das kann ein Faktor sein und ein Faktor kann der bezeichnete T sein.

33:32.390 --> 33:36.230
Also wenn ihr schon da droben Flieger fliegen lassen wollt, dann ist

33:36.230 --> 33:39.430
die erste Bitte, sammelt sie hinterher wieder ein und lasst sie nicht

33:39.430 --> 33:40.630
den Hausmeister einsammeln.

33:41.430 --> 33:45.570
Und wenn ihr schöne Späße habt, dann melde sich bitte einer und

33:45.570 --> 33:46.530
erzähle sie laut.

33:47.790 --> 33:50.130
Alle anderen sind auch daran interessiert, sie zu hören.

33:53.390 --> 33:55.710
Und derjenige, der jetzt telefoniert, geht bitte raus.

34:01.050 --> 34:01.950
Also soviel zum T.

34:05.170 --> 34:10.210
Und der erste Operant dieser Addition ist also A plus B mal C.

34:11.070 --> 34:14.610
Das habe ich hier jetzt hingeschrieben, aus dem A kann es zu T

34:14.610 --> 34:18.270
ableiten und T könnte ein Multiplikationszeichen enthalten.

34:18.270 --> 34:19.610
Das steht jetzt hier.

34:21.830 --> 34:25.970
Und wenn T ein Multiplikationszeichen enthält, dann kann ich zum

34:25.970 --> 34:28.330
Beispiel hinschreiben, der erste Term ist ein Faktor.

34:29.090 --> 34:29.970
Das steht hier.

34:32.330 --> 34:36.050
Und dieser Faktor, das könnte ein Klammerausdruck sein, das habe ich

34:36.050 --> 34:36.430
hier hingeschrieben.

34:37.410 --> 34:38.930
Und das steht im Baum an dieser Stelle.

34:43.530 --> 34:47.510
Ja, und den arithmetischen Ausdruck drinnen, A plus B, das haben wir

34:47.510 --> 34:49.810
ja gerade schon gesehen, den können wir darstellen.

34:50.170 --> 34:53.030
Und das führt zu diesem Teilbaum, das ist also A plus B.

34:54.510 --> 34:58.570
Und das C, für einen Faktor kann ich immer einen Bezeichner einsetzen.

34:59.890 --> 35:04.210
Das heißt, ich habe hier rechts hingeschrieben, den sogenannten

35:04.210 --> 35:05.370
Ableitungsbaum.

35:06.070 --> 35:10.130
Für die Ableitung, die ich hier auf der linken Seite hingeschrieben

35:10.130 --> 35:14.130
habe und die Nummern in Kreisen, ich hoffe, dass das jetzt richtig

35:14.130 --> 35:17.790
ist, geben jeweils die Regelnummer an.

35:18.110 --> 35:23.090
Wenn das die Regelnummer 1 ist, das die Regelnummer 2, das die

35:23.090 --> 35:27.610
Regelnummer 3, 4, 5 und 6.

35:31.600 --> 35:34.620
Da scheint aber irgendwo ein Fehler zu sein

35:38.100 --> 35:40.700
in der Nummerierung.

35:41.280 --> 35:47.980
Ah ja, hier sind nur die, das als 1, das als 2, das als 3 nummeriert.

35:48.920 --> 35:52.280
Das ist der Unterschied.

35:53.980 --> 35:55.240
Fragen zu diesem Beispiel.

36:01.310 --> 36:06.310
Dringend bitte, nehmen Sie sich einen beliebigen Ausdruck zu Hause vor

36:06.310 --> 36:09.970
für dieses elementare Beispiel und konstruieren Sie das Beispiel

36:09.970 --> 36:10.470
selbst.

36:11.810 --> 36:13.530
Sie müssen es begriffen haben.

36:13.530 --> 36:17.530
Am Ende des Semesters müssen Sie solche Beispiele vorwärts und

36:17.530 --> 36:18.690
rückwärts im Schlaf können.

36:19.990 --> 36:22.770
Sie werden es noch für viele Zwecke in der Informatik brauchen.

36:25.810 --> 36:28.710
Und es ist ein reines Spiel mit diesen Produktionen.

36:29.250 --> 36:30.630
Gedacht wird nicht viel dabei.

36:45.870 --> 36:49.530
Er fragt, woher weiß ich denn, dass ich mit dem Plus anfangen soll?

36:51.650 --> 36:54.090
Und darauf habe ich zwei verschiedene Antworten.

36:55.250 --> 36:59.670
Die eine Antwort lautet, ich weiß es nicht, wir fangen nämlich mit dem

36:59.670 --> 37:00.130
A an.

37:01.630 --> 37:04.930
Und wir setzen einfach mal nach unten irgendetwas fort.

37:06.590 --> 37:08.990
Und dann sehen wir schon, bei was wir rauskommen.

37:10.870 --> 37:14.710
Und ob wir bei A plus B mal C plus D rauskommen, das ist reiner

37:14.710 --> 37:15.150
Zufall.

37:16.610 --> 37:17.910
Das ist die eine Antwort.

37:20.210 --> 37:23.290
Da müsste ich nämlich jetzt richtig vorhersagen, was ich tun muss.

37:24.610 --> 37:27.670
Und das richtige Vorhersagen gelingt mir bei dem Weg von oben nach

37:27.670 --> 37:32.390
unten hier nur, wenn ich sage, aha, auf das willst du raus.

37:32.930 --> 37:37.250
Und aus meiner Schulweisheit weiß ich schon, das Pluszeichen ist der

37:37.250 --> 37:38.250
regierende Operator.

37:41.810 --> 37:43.590
Also musst du auf A plus D kommen.

37:44.350 --> 37:47.730
Wenn du solche Kenntnisse aus der Schule mitbringst, dann kannst du es

37:47.730 --> 37:48.750
richtig vorhersagen.

37:49.550 --> 37:53.110
Erinnern Sie sich bitte, der Rechner ist ein Vollidiot mit

37:53.110 --> 37:54.130
Spezialbegabung.

37:54.850 --> 37:57.770
Der Rechner weiß das nicht, der ist nämlich nicht in die höhere Schule

37:57.770 --> 37:58.150
gegangen.

37:59.490 --> 38:02.410
Und in der Tat, der Rechner hat riesige Schwierigkeiten bei der

38:02.410 --> 38:03.010
Vorhersage.

38:04.770 --> 38:07.790
Der Rechner betrachtet solche Dinge in Folge dessen lieber von unten

38:07.790 --> 38:11.510
nach oben und sagt, du hast mir doch schon gesagt, dass A plus B mal C

38:11.510 --> 38:12.550
plus D vorliegt.

38:14.310 --> 38:17.010
Und jetzt baue ich die ganze Geschichte von unten auf.

38:18.310 --> 38:21.150
Und merke mir mal, da habe ich eine Klammer, mit der kann ich noch

38:21.150 --> 38:23.710
nichts anfangen, sondern keine schließende Klammer habe.

38:24.390 --> 38:28.930
Und das A, das kann ich zu einem F machen und das kann ich zu einem T

38:28.930 --> 38:29.330
machen.

38:29.730 --> 38:31.930
Und dann können wir es zum Schluss mal mit dem Pluszeichen

38:31.930 --> 38:32.730
zusammensetzen.

38:34.550 --> 38:36.790
Und von unten nach oben geht es allzu leichter.

38:40.540 --> 38:43.060
Das Dumme ist nur, es geht auch nicht befriedigend.

38:43.940 --> 38:45.780
Wieder für diesen Vollidioten-Rechner.

38:47.200 --> 38:51.080
Denn, und das sehen wir an dieser Stelle hier mit dem Malzeichen, wenn

38:51.080 --> 38:54.740
der auf die Idee gekommen ist, aus dem F kannst du ein T machen und

38:54.740 --> 38:57.460
aus dem T kannst du doch ein A machen, haben wir doch gerade eben da

38:57.460 --> 38:58.100
unten gemacht.

38:59.580 --> 39:01.720
Dann steht er plötzlich im Regen.

39:02.000 --> 39:04.420
Denn mit A mal kann er überhaupt gar nichts anfangen.

39:04.960 --> 39:06.580
Dafür hat er keine weitere Regel.

39:09.620 --> 39:13.520
Das heißt, wir haben die große Schwierigkeit, dass von oben nach unten

39:13.520 --> 39:19.460
eine Vorhersage geleistet werden muss, die eigentlich ein Vollidiot

39:19.460 --> 39:20.300
nicht leisten kann.

39:21.280 --> 39:24.420
Und daher kann er mit beliebigem enden, wenn man ihm nicht doch einige

39:24.420 --> 39:25.260
Anleitungen gibt.

39:25.940 --> 39:31.340
Und wenn er von unten nach oben läuft, dann kann er zwar richtig

39:31.340 --> 39:34.660
arbeiten, aber er könnte sich auch verirren, z.B.

39:34.840 --> 39:39.140
indem er eben hier von F nach T und dann von T nach A geht.

39:40.600 --> 39:42.020
Man nennt das eine Sackgasse.

39:43.080 --> 39:44.560
Kommt gleich auf einer der nächsten Folien.

39:48.230 --> 39:52.310
Und die Frage für die rechnergestützte Verarbeitung solcher Ausdrücke

39:52.310 --> 39:56.950
lautet also, auf der einen Seite, wie kannst du denn die Vorhersage

39:56.950 --> 40:00.110
leisten, wenn das überhaupt geht?

40:00.770 --> 40:03.470
Und die zweite Frage lautet, und wenn du die Vorhersage nicht

40:03.470 --> 40:06.650
leistest, kannst du dafür sorgen, wenn du von unten nach oben gehst,

40:06.710 --> 40:07.890
dass du Sackgassen vermeidest.

40:08.910 --> 40:12.010
Bei diesem Beispiel ist beides möglich.

40:13.190 --> 40:15.850
Wir werden das im Januar sehen, auf welche Art und Weise das

40:15.850 --> 40:16.390
funktioniert.

40:17.490 --> 40:21.730
Aber vorläufig kann ich Sie also nur warnen, das Spiel ist nicht für

40:21.730 --> 40:21.950
Vollidioten.

40:26.650 --> 40:31.510
Hier steht also, was eine Sackgasse ist, wenn ich das Ganze von unten

40:31.510 --> 40:33.130
nach oben mache.

40:34.610 --> 40:39.590
Und außerdem sehe ich natürlich, dass das ganze Ding hier unheimlich

40:39.590 --> 40:40.570
langweilig ist.

40:40.670 --> 40:44.770
Aus A wird ein Faktor und ein Term und ein arithmetischer Ausdruck und

40:44.770 --> 40:45.870
Plus und irgendetwas.

40:46.390 --> 40:48.970
Warum eigentlich haben wir das nicht einfacher hingeschrieben?

40:51.770 --> 40:56.850
Was stünde eigentlich dagegen, dass ich hingeschrieben hätte, ein

40:56.850 --> 41:03.390
arithmetischer Ausdruck ist ein Bezeichner oder ein arithmetischer

41:03.390 --> 41:07.830
Ausdruck in Klammern oder ein arithmetischer Ausdruck multipliziert

41:07.830 --> 41:11.270
mit einem anderen arithmetischen Ausdruck oder ein arithmetischer

41:11.270 --> 41:13.430
Ausdruck plus einem arithmetischen Ausdruck.

41:17.350 --> 41:18.910
Was steht dem entgegen?

41:18.910 --> 41:24.710
Wenn ich das geschrieben hätte, dann hätte ich sämtliche

41:24.710 --> 41:29.510
Kettenproduktionen von der Bauart links ein Nicht-Terminal und rechts

41:29.510 --> 41:32.990
ein Nicht-Terminal, die äußerst langweilig sind, die hätte ich einfach

41:32.990 --> 41:33.710
ausgelassen.

41:35.890 --> 41:37.130
Was steht dem entgegen?

41:41.350 --> 41:43.910
Dann könnte man falsche Sachen einsetzen, auch das werde ich Ihnen

41:43.910 --> 41:44.650
gleich vorführen.

41:46.150 --> 41:48.890
Bevor wir das tun, noch zwei Begriffe.

41:49.330 --> 41:54.130
Wir nennen eine kontextfreie Grammatik anständig, wenn sie keine Y

41:54.130 --> 41:57.750
-Produktionen enthält und wenn sie keine Kettenproduktionen enthält.

41:57.930 --> 42:04.930
Also das hier ist eine anständige Grammatik, wohingegen diese

42:04.930 --> 42:09.010
Grammatik nicht anständig ist, die ich hier habe, weil sie

42:09.010 --> 42:10.210
Kettenproduktionen enthält.

42:10.210 --> 42:16.930
Und idealerweise möchte ich also die Kettenproduktionen loswerden,

42:17.090 --> 42:18.750
weil sie mich einfach langweilen.

42:22.470 --> 42:25.450
Das heißt, Anständigkeit wäre ein hübsches Ziel, aber wir werden

42:25.450 --> 42:27.330
gleich sehen, dass das nicht immer erreichbar ist.

42:27.330 --> 42:39.290
Hingegen ist die Reduktion, nämlich das Ziel kommt nicht auf der

42:39.290 --> 42:41.110
rechten Seite einer Produktion vor.

42:42.170 --> 42:45.410
Und jedes Lichtterminal kommt mindestens in der Ableitung eines Wortes

42:45.410 --> 42:46.190
der Sprache vor.

42:46.590 --> 42:49.590
Das ist immer erreichbar, allerdings nicht in den

42:49.590 --> 42:50.330
Vorlesungsbeispielen.

42:50.870 --> 42:54.610
Wenn Sie hingegen hinterher solche Grammatiken mit dem Rechner

42:54.610 --> 42:59.330
verarbeiten, dann setzen Sie voraus, dass die Grammatik reduziert ist.

43:00.550 --> 43:03.830
Und zwar setzen Sie das so stillschweigend voraus, dass es meistens

43:03.830 --> 43:05.630
noch nicht einmal in den Voraussetzungen entsteht.

43:06.090 --> 43:09.690
Die Leute haben es simpel vergessen, weil sie das für ganz normal

43:09.690 --> 43:10.230
hielten.

43:11.850 --> 43:14.050
Schauen wir uns also jetzt unser Beispiel an.

43:14.850 --> 43:17.570
Hier steht diese verkürzte Grammatik, die ich gerade hingeschrieben

43:17.570 --> 43:17.930
habe.

43:19.090 --> 43:23.990
Und ich versuche es wieder mit A plus B mal C plus D.

43:24.750 --> 43:27.310
Und sehe, das funktioniert glänzend.

43:29.690 --> 43:31.490
Ich kann das direkt ableiten.

43:34.330 --> 43:37.190
Und der Baum ist viel übersichtlicher, viel einfacher.

43:38.650 --> 43:39.650
Geht alles prima.

43:42.410 --> 43:44.570
Also was habe ich gegen das Beispiel einzuwenden?

43:44.670 --> 43:47.550
Was hat der Herr da oben gegen das Beispiel einzuwenden?

43:47.930 --> 43:49.410
Nun das sehen wir an dieser Stelle.

43:51.950 --> 43:53.030
Selbes Beispiel.

43:53.630 --> 43:55.370
A plus B mal C plus D.

43:57.690 --> 44:00.080
Bloß jetzt habe ich nach dieser Grammatik anders zusammengefasst.

44:01.070 --> 44:05.050
Und habe behauptet, das Malzeichen sei der regierende Operator.

44:06.870 --> 44:10.150
Und rechts steht ein arithmetischer Ausdruck und links steht die

44:10.150 --> 44:10.470
Gramme.

44:11.050 --> 44:14.390
Und der arithmetische Ausdruck auf der rechten Seite, das ist eine

44:14.390 --> 44:15.030
Addition.

44:16.310 --> 44:19.530
Und die hat zwei Operanten, der eine heißt ein Bezeichner und der

44:19.530 --> 44:20.750
andere ist auch ein Bezeichner.

44:21.010 --> 44:22.190
Und dann kriege ich diesen Baum.

44:24.270 --> 44:25.670
Und das ist auch legal.

44:27.790 --> 44:32.610
Aber Ihnen ist wiederum aus der Schule bekannt, dass das natürlich

44:32.610 --> 44:36.070
eine völlig falsche Interpretation von A plus B in Klammern mal C plus

44:36.070 --> 44:36.530
D ist.

44:36.990 --> 44:40.870
Weil ich jetzt die Vorrangregel zwischen Mal und Plus nicht mehr

44:40.870 --> 44:41.810
richtig befolgt habe.

44:41.810 --> 44:43.430
Wenn ich das also nebeneinander sehe.

44:44.830 --> 44:46.910
Hier sind jetzt beide Bäume nebeneinander.

44:49.830 --> 44:55.590
Dann ist der linke Baum derjenige, der die Operatorprioritäten erhält.

44:56.070 --> 44:57.310
So wie Sie sie gelernt haben.

44:57.790 --> 44:58.870
Der rechte tut es nicht.

45:02.720 --> 45:05.680
Der rechte ist insoweit, wie wir sagen, semantisch falsch.

45:06.260 --> 45:09.180
Weil er Ihnen was anderes suggeriert als das, was Sie eigentlich an

45:09.180 --> 45:10.480
Operationen ausführen wollen.

45:11.140 --> 45:12.080
Also das ist falsch.

45:14.480 --> 45:16.340
Und zwar semantisch falsch.

45:17.080 --> 45:19.940
Aber der Grammatik können Sie es nicht ansehen, dass das semantisch

45:19.940 --> 45:20.600
falsch ist.

45:21.920 --> 45:23.240
Sie müssen es vorher gewusst haben.

45:25.440 --> 45:30.360
Und das bedeutet für den vollidioten Rechner, er kommt mit dieser

45:30.360 --> 45:31.760
Grammatik nicht zurande.

45:32.080 --> 45:35.500
Denn da kann er falsche Sachen ableiten und niemand schreit.

45:38.120 --> 45:39.260
Wenn er das tut.

45:41.080 --> 45:42.180
Denn Sie sehen es ja nicht.

45:42.240 --> 45:43.740
Das macht er im Mikrosekundenbereich.

45:44.140 --> 45:45.600
Und so schnell können Sie gar nicht schreien.

45:46.500 --> 45:47.620
Da hat er schon einen Fehler gemacht.

45:50.380 --> 45:53.800
Und der ganze Zirkus mit den Kettenproduktionen, die wir in unserem

45:53.800 --> 45:58.120
ersten Beispiel hatten, der liegt nur daran begründet, dass wir mit

45:58.120 --> 46:00.720
Hilfe dieser Kettenproduktionen garantieren, dass die

46:00.720 --> 46:02.780
Operatorpriorität richtig gemacht wird.

46:04.360 --> 46:06.260
Das ist der eigentliche Grund für die Kettenproduktionen.

46:08.080 --> 46:11.400
Sobald wir die Prioritäten richtig auseinandersortiert haben, können

46:11.400 --> 46:14.240
wir auf die Kettenproduktionen komplett verzichten.

46:15.760 --> 46:17.640
Und das bedeutet jetzt zweierlei,

46:23.360 --> 46:29.100
wenn wir einen solchen arithmetischen Ausdruck wie A plus B mal C plus

46:29.100 --> 46:35.310
D analysieren und erkennen wollen, wie das alles zusammengehört.

46:37.440 --> 46:41.000
Dann müssen wir offensichtlich diese Art von Grammatik einsetzen, die

46:41.000 --> 46:43.260
wir hier haben, mit Kettenproduktionen.

46:45.740 --> 46:49.800
Sobald wir aber das auseinandersortiert haben und fertig sind und

46:49.800 --> 46:55.560
wissen, was da richtig sich gehört, dann könnten wir das ganze Ding

46:55.560 --> 46:57.120
radikal vereinfachen.

46:57.220 --> 46:59.160
Dann könnten wir uns auf den linken Baum beschränken.

47:00.160 --> 47:06.340
Also lautet unsere Konklusion aus der ganzen Geschichte.

47:07.220 --> 47:09.100
Erster Schritt in der Analyse,

47:13.080 --> 47:15.680
Grammatik mit Kettenproduktionen benutzen.

47:31.490 --> 47:36.530
Zweiter Schritt, wenn wir alles wissen, dann können wir das Ergebnis

47:36.530 --> 47:40.990
vereinfacht darstellen.

47:43.430 --> 47:48.750
Und vereinfacht heißt hier, ohne Kettenproduktionen

47:58.180 --> 48:00.540
darstellen.

48:01.440 --> 48:03.580
Das können wir sogar noch einen Schritt weiter treiben.

48:04.880 --> 48:07.600
Also auch diese Bäume, die ich hier auf diesem Bild habe, sind mir

48:07.600 --> 48:08.480
noch zu kompliziert.

48:09.440 --> 48:12.340
Und ich gehe über zu sogenannten Kantorowitsch-Bäumen.

48:12.960 --> 48:15.500
Ob Sie den Herrn Kantorowitsch, wie es in der korrekten deutschen

48:15.500 --> 48:20.400
Umsprache schreibt, wie er heißt, mit T-S-C-H am Ende schreiben, oder

48:20.400 --> 48:25.600
ob Sie ihn mit C schreiben, oder ob Sie ihn mit C-Z schreiben.

48:25.720 --> 48:28.020
Alle möglichen Schreibweisen sind da üblich.

48:31.120 --> 48:36.800
Das war ursprünglich ein Wirtschaftswissenschaftler und Mathematiker.

48:37.820 --> 48:42.900
Und der kam, noch bevor die Informatiker draufkamen, wie man solche

48:42.900 --> 48:47.100
Ausdrücke verarbeiten kann, erst mal auf die Idee, wie man solche

48:47.100 --> 48:51.420
Ausdrücke als Bäume so einfach wie möglich darstellt.

48:53.580 --> 48:56.260
Ausgangspunkt ist, wir haben die Analyse bereits geleistet.

48:57.000 --> 49:01.260
Wir kennen jetzt unseren Ableitungsbaum und kennen die Vorrangregeln.

49:04.260 --> 49:07.700
Und jetzt überlegen wir uns als erstes, wenn ich mir das hier nochmal

49:07.700 --> 49:13.240
anschaue, das erste, was hier überflüssig ist, ist eigentlich diese

49:13.240 --> 49:15.160
Klammersetzung an dieser Stelle.

49:17.220 --> 49:23.340
Wenn ich das hier einfach rausstreiche, auch den Zwischenschritt

49:23.340 --> 49:30.200
rausstreiche, dann würde dastehen, der erste Ausdruck ist die Addition

49:30.200 --> 49:33.500
zweier Terme und das ist genau das, was wir wollen.

49:35.000 --> 49:37.400
Das heißt, die Klammern sind eigentlich überflüssig.

49:37.640 --> 49:38.340
Im Baum.

49:39.040 --> 49:40.600
In der Hinschreibe brauche ich sie.

49:41.180 --> 49:42.580
Zur Analyse brauche ich sie.

49:43.380 --> 49:45.820
Aber sobald ich beim Baum angelangt bin, kann ich sie eigentlich

49:45.820 --> 49:46.460
rausstreichen.

49:47.640 --> 49:51.300
Das hat Herr Kantorowitsch auch gemacht.

49:52.720 --> 49:54.340
Er hat jetzt die Klammern gestrichen.

49:55.780 --> 49:59.000
Dann hat er die Kettenproduktionen rausgeschmissen, das haben wir

49:59.000 --> 49:59.940
gerade auch gemacht.

50:01.180 --> 50:08.140
Und dann hat er, ich gehe nochmal zurück, gesagt, ja, wozu hast du

50:08.140 --> 50:09.800
denn hier überall A hingeschrieben?

50:11.580 --> 50:16.060
Ich mache die Augen zu und sage, du hast in jeder Ecke A geschrieben.

50:16.660 --> 50:18.040
Und das ist richtig für alle Beispiele.

50:20.520 --> 50:22.020
Also brauche ich es nicht hinschreiben.

50:23.600 --> 50:25.860
Etwas, was sich von selbst versteht, brauche ich nicht hinschreiben.

50:26.560 --> 50:29.980
Wie wäre es, wenn wir das besser machen würden und stattdessen noch

50:29.980 --> 50:33.240
die Operatoren streichen und die Operatoren da oben reinschreiben

50:33.240 --> 50:33.560
würden?

50:35.880 --> 50:38.940
Dann hätten wir wenigstens etwas Sinnvolles geleistet und hätten den

50:38.940 --> 50:40.240
Baum noch weiter vereinfacht.

50:41.460 --> 50:43.620
Und das ist genau der letzte Schritt.

50:44.940 --> 50:47.960
Ersetze die Nicht-Terminale, die in diesen Beispielen immer

50:47.960 --> 50:52.360
einheitlich A heißen, dadurch, dass du die Operatoren hinschreibst.

50:53.960 --> 50:59.300
Und dann sieht unser Beispiel, was also nach Analyse so aussah mit all

50:59.300 --> 51:00.360
den Kettenproduktionen,

51:08.970 --> 51:11.610
vereinfacht so aus und das ist der Kantorowicz-Baum.

51:25.370 --> 51:27.990
Und jetzt sehen Sie ganz einfach, was Sie tun sollen.

51:28.290 --> 51:29.070
Steht alles da.

51:31.090 --> 51:33.550
Die Addition kannst du gar nicht ausführen, weilst du die

51:33.550 --> 51:34.830
Multiplikation auch brauchst.

51:35.210 --> 51:38.410
Die Multiplikation kannst du nicht ausführen, weilst du diese Addition

51:38.410 --> 51:38.890
brauchst.

51:38.890 --> 51:43.670
Also heißt der Ausdruck A plus B in Klammern mal C plus D, addiere

51:43.670 --> 51:50.050
erst A und B, multipliziere das Ergebnis mit C und dann addiere zu dem

51:50.050 --> 51:50.790
Ergebnis D.

51:52.470 --> 51:55.290
Ja, das haben Sie auch schon in der Schule gelernt gehabt, dass das so

51:55.290 --> 51:55.650
auch geht.

51:57.170 --> 52:00.790
Und hier steht es jetzt in größtmöglicher Vereinfachung da.

52:02.470 --> 52:06.210
Also der Kantorowicz-Baum gibt genau wieder, was wir an der Stelle

52:06.210 --> 52:07.170
eigentlich haben wollen.

52:09.310 --> 52:11.490
Gibt es Fragen zu dieser Konstruktion?

52:15.480 --> 52:15.920
Lauter?

52:18.820 --> 52:23.380
Nein, das ist kein Bezug auf dieses eine Beispiel, sondern das gilt

52:23.380 --> 52:24.120
generell.

52:25.640 --> 52:29.900
Wenn immer Sie zu einer Grammatik einen Kantorowicz-Baum konstruieren

52:29.900 --> 52:36.700
wollen, dann können Sie den hinterher lesen, von unten nach oben.

52:38.420 --> 52:43.080
Nimmt die Elementarenoperanten und führt die Operation aus, die diese

52:43.080 --> 52:44.940
Elementarenoperanten zusammenführt.

52:46.220 --> 52:49.620
Und wenn das Ergebnis dann als Operant auftritt in einer nächsten

52:49.620 --> 52:51.860
Operation, kann Sie die nächste Operation ausführen.

52:59.370 --> 53:04.190
Er sagt, das ist auch als polnische Notation bekannt, oder als postfix

53:04.190 --> 53:04.770
Notation.

53:05.030 --> 53:05.830
Kommen wir gleich drauf.

53:12.090 --> 53:13.070
Noch Fragen?

53:18.750 --> 53:21.690
Wenn die Herrschaften leise wären, könnten wir den Herrn auch

53:21.690 --> 53:22.090
verstehen.

53:30.010 --> 53:30.890
Diktieren Sie mal.

53:32.170 --> 53:32.850
Also, los.

53:42.050 --> 53:42.650
Aha.

53:43.690 --> 53:45.230
Ja, das ist kein arithmetischer Ausdruck.

53:48.130 --> 53:49.310
Ja, das ist wichtig.

53:51.590 --> 53:53.170
Also, er meinte ein Mahlzeichen.

53:54.270 --> 53:57.210
Der Rechner ist ein Vollidiot, tut mir leid.

54:02.100 --> 54:04.420
Ja, ist doch ganz klar, was wir damit machen.

54:05.200 --> 54:08.080
Wir meinen hier, du sollst A und B addieren.

54:13.260 --> 54:16.460
Und das Mahl kannst du noch nicht durchführen, weil du den zweiten

54:16.460 --> 54:17.420
Operanten nicht hast.

54:17.760 --> 54:19.920
Also musst du auch C und D addieren.

54:20.780 --> 54:21.300
Falsch.

54:35.900 --> 54:37.620
Und jetzt kannst du multiplizieren.

54:39.640 --> 54:41.040
Und sieht das so aus.

54:50.640 --> 54:52.760
Wenn in der ersten Klammer was steht...

54:56.330 --> 54:58.270
Ich verstehe Sie akustisch immer noch nicht.

55:12.400 --> 55:15.900
Diktieren Sie mal

55:28.720 --> 55:31.780
A plus B.

55:33.740 --> 55:34.440
In Klammern.

55:40.720 --> 55:42.120
Also, kommen Sie her, schreiben Sie.

55:56.480 --> 55:58.740
Ich muss das erstmal alles wieder durchtun.

56:07.880 --> 56:08.440
Ja, sicher.

56:12.130 --> 56:12.910
Also, da hinstellen.

56:48.370 --> 56:51.890
Es ist klar, es gibt den selben Baum, den wir hier schon für dieses

56:51.890 --> 56:52.630
Beispiel haben.

56:52.950 --> 56:56.670
Nur müssen wir an der Stelle C schreiben, an der Stelle B, an der

56:56.670 --> 56:58.990
Stelle A und an der Stelle schreiben wir wieder D.

56:59.350 --> 57:02.650
Denn die Struktur mit Plus, Mal und Plus ist natürlich identisch.

57:05.190 --> 57:06.690
Also keine Neuigkeit.

57:09.530 --> 57:12.830
Es scheint, dass die Frage folgende ist.

57:13.830 --> 57:15.890
Sind denn diese Bäume alle gleich?

57:16.010 --> 57:17.350
Und die Antwort lautet Nein.

57:18.730 --> 57:22.510
Was immer Sie an Ausdruck hinschreiben, der Baum hat zunächst mal

57:22.510 --> 57:23.630
Neuigkeitswert.

57:25.050 --> 57:29.230
Es kann sein, wie in diesem Beispiel, dass er seiner Struktur nach

57:29.230 --> 57:31.090
identisch ist mit einem anderen Baum.

57:31.090 --> 57:35.390
Und nur die Operanten anders dargestellt sind.

57:37.790 --> 57:41.330
Aber im Prinzip können Sie da also beliebig viele Bäume konstruieren.

57:41.890 --> 57:43.670
Und die können auch sehr, sehr groß werden.

57:45.670 --> 57:48.070
Wenn Sie lange arithmetische Ausdrücke hinschreiben.

57:53.000 --> 57:53.780
Soviel zum Prinzip.

57:56.730 --> 58:06.110
Wir haben also gesehen, ich gehe zurück zu der ursprünglichen

58:06.110 --> 58:11.130
Grammatik, dass dieser und dieser Ableitungsbaum offensichtlich der

58:11.130 --> 58:14.130
Klammerung und der Vorrangregelung zwei verschiedene Ausdrücke

58:14.130 --> 58:14.670
darstellt.

58:15.590 --> 58:20.850
Und wir merken uns also, wenn wir Grammatiken hinschreiben für

58:20.850 --> 58:27.290
Analysezwecke, dann müssen wir sehr genau darauf achten, dass die

58:27.290 --> 58:28.450
Struktur erhalten bleibt.

58:30.550 --> 58:32.670
Und dass die richtigen Vorrangregeln gelten.

58:34.210 --> 58:39.170
Und in diesem Zusammenhang ist eine Eigenschaft in der Informatik sehr

58:39.170 --> 58:39.690
wichtig.

58:39.690 --> 58:44.830
Wenn irgendjemand in der Mathematik hinschreiben würde, A plus B plus

58:44.830 --> 58:49.690
C, dann habe ich also irgendwo mal was gehört.

58:50.910 --> 58:55.790
Da gibt es ein Assoziativgesetz in der Mathematik.

58:57.770 --> 59:01.370
Und die Mathematik sagt infolgedessen, ob Sie das Ding so

59:01.370 --> 59:06.010
interpretieren, addiere zuerst A und B und dann addiere C.

59:06.010 --> 59:15.910
Oder ob Sie das so interpretieren, addiere erst B und C und dann A als

59:15.910 --> 59:17.990
linken Operanten davor.

59:19.570 --> 59:20.850
Das ist mir gleichgültig.

59:21.010 --> 59:22.230
So sagt die Mathematik.

59:25.570 --> 59:27.770
Das heißt mathematisch habe ich hier ein Gleichheitszeichen stehen.

59:29.030 --> 59:31.170
In der Informatik habe ich das leider nicht.

59:33.830 --> 59:38.610
In der Informatik wünsche ich mir zwar, dass dieses Gleichheitszeichen

59:38.610 --> 59:40.890
gilt, aber das ist nur ein Wunsch.

59:44.850 --> 59:48.650
Und normalerweise habe ich leider kein Gleichheitszeichen, sondern ich

59:48.650 --> 59:51.630
habe stattdessen ein verschieden Zeichen an dieser Stelle stehen.

59:52.290 --> 59:57.570
Das wird besonders exkratant, wenn Sie Gleitpunkt-Operationen

59:57.570 --> 01:00:02.550
durchführen, wo Sie das direkt nachrechnen können, dass das

01:00:02.550 --> 01:00:03.950
Assoziativgesetz nicht gilt.

01:00:04.290 --> 01:00:07.370
Wir werden aber auch noch Beispiele sehen, die zeigen, dass es nicht

01:00:07.370 --> 01:00:09.930
einmal mit ganzen Zahlen und Rechnerarithmetik vernünftig

01:00:09.930 --> 01:00:10.550
funktioniert.

01:00:11.290 --> 01:00:13.050
Sondern dass wir auch da Ärger bekommen können.

01:00:14.250 --> 01:00:17.010
Wir müssen uns also im Allgemeinen darauf einstellen, dass das

01:00:17.010 --> 01:00:18.510
Assoziativgesetz nicht gilt.

01:00:20.890 --> 01:00:26.890
Und das bedeutet, wenn wir A plus B plus C sehen, dann müssen wir uns

01:00:26.890 --> 01:00:28.810
jetzt auf irgendeine Regel festlegen.

01:00:28.910 --> 01:00:30.330
Wie sollen wir es denn interpretieren?

01:00:31.990 --> 01:00:36.730
Und die Antwort lautet in der Informatik, wenn nichts anderes gesagt

01:00:36.730 --> 01:00:40.270
wird, dann wird immer linksassoziativ geklammert.

01:00:40.650 --> 01:00:44.490
Sprich also diesen Ausdruck, den werde ich sofort so interpretieren.

01:00:45.330 --> 01:00:50.730
Zuerst A und B zusammenfassen und dann hinterher C.

01:00:51.150 --> 01:00:53.510
Das ist der Baum, den ich für die linke Seite hier habe.

01:00:56.090 --> 01:00:57.790
Das ist die Standardinterpretation.

01:01:00.770 --> 01:01:06.490
Und wie Sie an diesen Beispielen sehen, die Grammatik hier oben wird

01:01:06.490 --> 01:01:09.690
also nicht diese Standardinterpretation herbeiführen, sondern wird mir

01:01:09.690 --> 01:01:11.150
beide Möglichkeiten erlauben.

01:01:11.390 --> 01:01:12.330
Das mag ich nicht.

01:01:13.470 --> 01:01:17.830
Das führt allgemeiner zum Begriff der mehrdeutigen Grammatik.

01:01:18.330 --> 01:01:22.890
Die Grammatik hier oben, weil sie eben für einen und denselben Satz,

01:01:22.910 --> 01:01:26.190
wie hier zum Beispiel A plus B plus C, zwei verschiedene

01:01:26.190 --> 01:01:29.750
Interpretationen erlaubt, ist mehrdeutig.

01:01:30.290 --> 01:01:34.930
Es gibt mehrere Ableitungsbäume zum gleichen Satz.

01:01:36.010 --> 01:01:40.490
Das mögen wir normalerweise nicht, können es aber nicht verhindern.

01:01:40.490 --> 01:01:44.290
Und in der Theorie werden Sie im dritten Semester lernen, dass das

01:01:44.290 --> 01:01:48.010
sogar ein Grundübel ist, was man nicht ausmerzen kann.

01:01:50.110 --> 01:01:56.810
Es gibt Beispiele von Sprachen, bei denen können Sie keine eindeutige

01:01:56.810 --> 01:01:57.630
Grammatik herstellen.

01:02:00.330 --> 01:02:05.330
Also kontextfreie Grammatiken, für die der einfache Kantorowicz-Baum

01:02:05.330 --> 01:02:09.650
zwar angehbar ist, aber dann kommt immer gleich ein anderer und sagt,

01:02:09.690 --> 01:02:11.610
ich habe noch einen anderen und der ist auch richtig.

01:02:15.790 --> 01:02:17.050
Das ist unvermeidbar.

01:02:17.530 --> 01:02:19.450
Das nennt man dann inhärent mehrdeutig.

01:02:21.570 --> 01:02:27.790
Damit kommen wir zu der Frage, wie das Ganze jetzt angewandt wird zur

01:02:27.790 --> 01:02:29.330
Beschreibung von Programmiersprachen.

01:02:29.810 --> 01:02:33.390
Und zunächst habe ich auf dieser Folie nur Konventionen stehen.

01:02:34.770 --> 01:02:39.970
Man hat kontextfreie Grammatiken erfunden 1955-56 und gleich

01:02:39.970 --> 01:02:46.130
anschließend sind die Programmiersprachenleute hergekommen und haben

01:02:46.130 --> 01:02:48.050
gesagt, das ist prima, das können wir gebrauchen.

01:02:49.030 --> 01:02:52.470
Und derjenige, der das als erstes sagte, war ein Herr namens John

01:02:52.470 --> 01:02:52.930
Beckles.

01:02:53.570 --> 01:02:57.850
Der Mann ist uns in mehrerlei Hinsicht in der Informatik bekannt.

01:02:58.330 --> 01:03:03.130
Das ist der Chef gewesen der Entwicklung von FORTRAN, das heißt der

01:03:03.130 --> 01:03:06.190
ersten höhere Programmiersprache, das hat er 1954 gemacht.

01:03:06.870 --> 01:03:11.530
Dann hat er 1958 sich in die Entwicklung von ALGOL eingemischt und 20

01:03:11.530 --> 01:03:13.770
Jahre später hat er funktionale Sprachen erfunden.

01:03:16.990 --> 01:03:21.330
Das heißt, das ist ein Mann mit großer Vergangenheit in

01:03:21.330 --> 01:03:22.170
Programmiersprachen.

01:03:23.850 --> 01:03:27.610
Und der hat gesagt, dass diese Kurzformen, wie wir sie hier stehen

01:03:27.610 --> 01:03:30.550
haben, das können wir nicht gebrauchen, das kann niemand lesen.

01:03:31.550 --> 01:03:34.690
Ich muss Ihnen ja vorhin auch sagen, das A steht für Ausdruck und das

01:03:34.690 --> 01:03:35.970
C steht für Term usw.

01:03:36.370 --> 01:03:38.290
Und warum schreiben wir das nicht explizit hin?

01:03:39.650 --> 01:03:44.590
Und dann hat er eine extensive Notation gefunden, die von dem Dänen

01:03:44.590 --> 01:03:49.950
Peter Nauer zur Definition von ALGOL 58, einer Programmiersprache,

01:03:50.330 --> 01:03:53.850
1958, eingesetzt wurde.

01:03:55.030 --> 01:03:59.510
Und der hat als erstes gesagt, dieses komische Zeichen, das gibt es

01:03:59.510 --> 01:04:00.730
nicht auf meiner Tastatur.

01:04:02.650 --> 01:04:04.430
Das kann ich nicht gebrauchen.

01:04:04.430 --> 01:04:08.690
Also schreiben wir statt diesem Pfeil, Doppelpunkt, Doppelpunkt ist

01:04:08.690 --> 01:04:09.090
gleich.

01:04:12.990 --> 01:04:19.310
Und das A für sich alleine kann ich auch nicht gebrauchen, denn das

01:04:19.310 --> 01:04:20.750
ist kein richtiges Wort.

01:04:21.470 --> 01:04:23.970
Wenn ich aber da jetzt hingeschrieben hätte, das ist ein

01:04:23.970 --> 01:04:28.170
arithmetischer Ausdruck, dann hätte ich nicht mehr gewusst, was meint

01:04:28.170 --> 01:04:29.030
er denn jetzt eigentlich?

01:04:29.030 --> 01:04:32.730
Meint er die Buchstabenfolge A, U, S, D, R, U, C, K?

01:04:34.130 --> 01:04:35.030
Oder meint er das Wort?

01:04:35.710 --> 01:04:37.430
Also müssen wir das Wort kennzeichnen.

01:04:38.130 --> 01:04:41.910
Und daher wurde eingeführt, nicht Terminale werden in spitze Klammern

01:04:41.910 --> 01:04:43.950
geschrieben, so wie Sie das hier sehen.

01:04:44.330 --> 01:04:48.170
Also statt Pfeil A plus A schreibe ich Ausdruck in spitzen Klammern.

01:04:49.490 --> 01:04:52.970
Doppelpunkt, Doppelpunkt ist gleich, Ausdruck in spitzen Klammern,

01:04:53.610 --> 01:04:56.090
Pluszeichen, Ausdruck in spitzen Klammern.

01:04:57.710 --> 01:05:03.670
Das, was ich beibehalte, ist, dass senkrechte Striche als oder gelesen

01:05:03.670 --> 01:05:05.850
werden und Alternativen trennen.

01:05:06.130 --> 01:05:08.770
Die kann ich natürlich auch auf mehrere Zeilen hinschreiben.

01:05:11.090 --> 01:05:14.610
Das heißt, das, was Sie hier sehen, hier unten, ist nur eine andere

01:05:14.610 --> 01:05:18.070
Schreibweise für

01:05:24.530 --> 01:05:28.550
kontextfreie Grammatiken.

01:05:33.260 --> 01:05:38.440
Und es ist nicht mehr, ich habe inhaltlich überhaupt nichts geändert.

01:05:40.160 --> 01:05:43.120
Ich habe das ganze Ding nur anders benannt.

01:05:44.160 --> 01:05:48.380
Ja, und nach den Erfindern wird das also als Bacchus-Nauer-Form

01:05:48.380 --> 01:05:51.400
bezeichnet, abgekürzt BNF.

01:05:54.630 --> 01:05:58.970
Jetzt ist mir der Gramm immer noch zu aufwendig.

01:06:00.150 --> 01:06:03.610
Und ich möchte das also noch weiter verkürzen in der Schreibweise.

01:06:06.070 --> 01:06:09.350
Und daraufhin hat man erweiterte Bacchus-Nauer-Formen oder Englisch

01:06:09.350 --> 01:06:13.590
Extended Bacchus-Nauer-Formen erfunden.

01:06:14.390 --> 01:06:23.370
Und dafür führt man zusätzlich noch weitere Metazeichen ein, nämlich

01:06:23.370 --> 01:06:26.270
die spitze Klammer, die eckige Klammer, Entschuldigung.

01:06:27.330 --> 01:06:32.810
Und außerdem reservieren wir jetzt die runden Klammern ebenfalls als

01:06:32.810 --> 01:06:34.630
Metazeichen, genauso wie das Oder.

01:06:35.630 --> 01:06:37.670
Geraten damit aber jetzt in Schwierigkeiten.

01:06:37.810 --> 01:06:40.410
Wenn ich eine runde Klammer hinschreibe, meine ich jetzt eine runde

01:06:40.410 --> 01:06:43.910
Klammer, die in dem Ausdruck vorkommt, oder meine ich irgend solch ein

01:06:43.910 --> 01:06:45.630
Metazeichen, wie der Oder-Strich.

01:06:47.710 --> 01:06:49.970
Und da greift man zu einem Hilfsmittel.

01:06:49.970 --> 01:06:58.070
Man sorgt dafür, dass man sämtliche normalen Zeichen mit Apostrophen

01:06:58.070 --> 01:06:58.430
schreibt.

01:06:59.290 --> 01:07:05.150
Und bekommt dann also für einen solchen arithmetischen Ausdruck, A

01:07:05.150 --> 01:07:09.410
-Pfeil T oder A plus T, folgende Aussage.

01:07:09.910 --> 01:07:13.050
Das ist ein Term, haben wir schon auf der letzten Folie uns

01:07:13.050 --> 01:07:14.050
vorgestellt.

01:07:15.350 --> 01:07:17.670
Und ich erweitere das ganze Ding jetzt.

01:07:17.670 --> 01:07:19.470
Ich lasse jetzt auch Minuszeichen zu.

01:07:20.230 --> 01:07:23.150
Auf dem Term könnte folgen Plus oder Minus.

01:07:25.450 --> 01:07:26.410
Und noch ein Term.

01:07:29.810 --> 01:07:38.810
Und mit der Klammer, die ich hier habe, mit dieser inneren Klammer,

01:07:41.110 --> 01:07:44.990
sage ich jetzt, dass Plus oder Minus zusammengehören.

01:07:47.150 --> 01:07:49.150
Also das eine oder das andere.

01:07:49.550 --> 01:07:50.370
Dann aber geht es weiter.

01:07:52.250 --> 01:07:54.670
Also die Klammer klammert jetzt einen Teilausdruck.

01:07:56.050 --> 01:07:59.690
Und da ein O da drin steht, heißt das, du kannst eines von den beiden

01:07:59.690 --> 01:08:00.070
wählen.

01:08:02.710 --> 01:08:04.610
Und dann geht es weiter mit dem nächsten Term.

01:08:06.470 --> 01:08:09.550
So, und jetzt habe ich da noch eine weitere Klammer.

01:08:12.070 --> 01:08:14.550
Und hinter der steht ein Stern, hochgestellt.

01:08:16.930 --> 01:08:20.090
Ja, und bei Sternen haben wir bisher gelernt, wenn das hochgestellt da

01:08:20.090 --> 01:08:23.910
steht, dann heißt das immer Null oder mehrmaliges Vorkommen von dem,

01:08:24.010 --> 01:08:24.670
was davor steht.

01:08:25.950 --> 01:08:27.150
Das ist hier auch so.

01:08:28.010 --> 01:08:32.170
Das heißt, wir lernen, hier steht, du hast einen Term.

01:08:34.070 --> 01:08:39.150
Und dahinter kann Null oder mehrmals Vorkommen noch Plus oder Minus

01:08:39.150 --> 01:08:39.930
ein weiterer Term.

01:08:42.490 --> 01:08:44.170
Und wenn ich jetzt mein Beispiel...

01:08:53.710 --> 01:09:02.030
Mein Beispiel A plus B an C, plus C, dann lese ich, dass hier steht,

01:09:02.190 --> 01:09:03.710
dass A ist ein Term.

01:09:04.970 --> 01:09:09.230
Und auf dem kann Plus ein weiterer Term folgen, das wäre dann das Plus

01:09:09.230 --> 01:09:09.590
B.

01:09:13.510 --> 01:09:17.050
Und da kann dann noch ein weiterer Term folgen mit dem Plus Sachen

01:09:17.050 --> 01:09:17.390
davor.

01:09:19.270 --> 01:09:20.730
Und das wäre das Plus C.

01:09:22.590 --> 01:09:26.850
Und das ist genau die linksassoziative Klammerung von A plus B plus C.

01:09:27.790 --> 01:09:34.490
Das heißt, diese Schreibweise Term, dann Operator, Plus Term und

01:09:34.490 --> 01:09:38.090
gefolgt von Term und das Ganze in Klammern mit einem Stern hintendran.

01:09:38.310 --> 01:09:43.410
Das bedeutet, du kannst das wiederholen und es führt, so wie es da

01:09:43.410 --> 01:09:45.950
steht, automatisch zur linksassoziativen Klammerung.

01:09:47.130 --> 01:09:50.790
Schön, ich habe das ganze Beispiel jetzt noch komplettiert, um das,

01:09:50.930 --> 01:09:52.850
was zusätzlich notwendig ist.

01:09:52.850 --> 01:09:59.790
Wir dürfen natürlich auch hinschreiben, Plus C oder Minus C als Term.

01:10:00.230 --> 01:10:02.850
Und das heißt also, vorne dran könnte auch noch ein Plus oder Minus

01:10:02.850 --> 01:10:03.430
Zeichen stehen.

01:10:03.870 --> 01:10:06.370
Wenn das vorne dran steht, dann ist es aber optional, du kannst es

01:10:06.370 --> 01:10:06.730
weglassen.

01:10:08.590 --> 01:10:12.270
Und die eckige Klammer bedeutet immer optional.

01:10:14.850 --> 01:10:17.550
Du kannst das, was da drinnen steht, schreiben oder du kannst es auch

01:10:17.550 --> 01:10:17.930
weglassen.

01:10:20.930 --> 01:10:25.250
Ja, und beim Faktor sehen wir das also ganz genau so.

01:10:26.050 --> 01:10:32.010
Das ist ein Faktor und darauf folgt ein Malzeichen und ein weiterer

01:10:32.010 --> 01:10:32.350
Faktor.

01:10:32.450 --> 01:10:36.590
Das Ganze wiederum in geschweiften Klammern, äh, in runden Klammern.

01:10:39.310 --> 01:10:43.630
Wohingegen bei der elementaren Produktion nichts Besonderes los ist,

01:10:43.950 --> 01:10:46.710
da steht hier unser einzelner Buchstabe oder Bezeichner.

01:10:46.710 --> 01:10:49.330
Und hier steht der Ausdruck.

01:10:49.690 --> 01:10:52.410
Und jetzt muss ich die Klammern an der Stelle in Apostrophe setzen,

01:10:52.670 --> 01:10:54.710
damit ich sie nicht mit dieser Klammerart verwechsele.

01:10:56.690 --> 01:10:59.410
Das ist die Klammer, die tatsächlich vorkommt.

01:11:00.570 --> 01:11:04.410
Das ist die Meta-Klammer, die nur sagt, du sollst die Grammatik so

01:11:04.410 --> 01:11:07.130
lesen, dass man das richtig verstehen kann.

01:11:08.390 --> 01:11:11.110
Das ist eine weitere Bakus-Nauer-Form.

01:11:11.110 --> 01:11:16.990
Und wenn Sie jetzt ein beliebiges Buch über Programmiersprachen

01:11:16.990 --> 01:11:23.670
aufschlagen und sich anschauen, wie dort die Grammatik beschrieben

01:11:23.670 --> 01:11:30.490
ist, dann ist das immer irgendeine Variation dieser erweiterten Bakus

01:11:30.490 --> 01:11:30.970
-Nauer -Form.

01:11:32.430 --> 01:11:35.010
Man kann das auf verschiedene Arten und Weisen schreiben.

01:11:35.990 --> 01:11:40.750
Also für diesen Faktor finden Sie zum Beispiel auch noch Schreibweisen

01:11:40.750 --> 01:11:41.610
von der Bauart.

01:11:41.930 --> 01:11:48.150
Das ist Faktor oder Malzeichen, Faktor.

01:11:50.730 --> 01:11:53.030
Und jetzt haben die Leute nicht so richtig verstanden, was mit diesem

01:11:53.030 --> 01:11:54.030
Stern gemeint ist.

01:11:54.410 --> 01:11:56.250
Und dann schreiben sie bloß Punkt, Punkt, Punkt.

01:11:58.170 --> 01:11:59.910
Meinen aber dasselbe wie mit dem Stern.

01:12:01.050 --> 01:12:04.050
Also es gibt verschiedene Variationen heißt das dieser Schreibweise.

01:12:04.050 --> 01:12:07.910
Aber die Grundgesetze haben Sie hier an diesem Beispiel kennengelernt.

01:12:08.910 --> 01:12:14.330
Und wenn Sie es angenehmer haben wollen, dann können Sie es auch

01:12:14.330 --> 01:12:15.190
grafisch darstellen.

01:12:15.330 --> 01:12:16.650
Und das ist immer noch dieselbe Story.

01:12:19.970 --> 01:12:23.050
Sie können das hinmalen als ein sogenanntes Syntax-Diagramm.

01:12:24.170 --> 01:12:26.670
Die Grammatik, die ich habe, ist immer noch die gleiche.

01:12:29.630 --> 01:12:32.390
Und ein solches Syntax-Diagramm wird gelesen.

01:12:33.370 --> 01:12:39.470
Du fängst auf der linken Seite an und folgst einem Weg.

01:12:41.970 --> 01:12:46.510
Zulässig sind alle Wege, die links anfangen und rechts enden.

01:12:48.550 --> 01:12:52.290
Und wenn du also diesen Weg hast, dann kannst du hinschreiben einen

01:12:52.290 --> 01:12:52.850
Ausdruck.

01:12:53.570 --> 01:12:54.990
Ja, was ist denn ein Ausdruck?

01:12:56.010 --> 01:12:58.430
Ah, hier oben drüber steht, das ist ein Ausdruck.

01:12:58.690 --> 01:13:00.350
Das ist das Syntax-Diagramm für Ausdrücke.

01:13:02.390 --> 01:13:06.370
Und das bedeutet, wenn an der Stelle innerhalb eines eckigen Kastens

01:13:06.370 --> 01:13:11.850
wieder das Wort Ausdruck vorkommt, dann kannst du dieses ganze Bild an

01:13:11.850 --> 01:13:12.770
der Stelle einsetzen.

01:13:15.710 --> 01:13:21.330
Ja, plus Ausdruck oder mal oder dieselbe Sache in Klammern oder der

01:13:21.330 --> 01:13:22.210
einzelne Bezeichner.

01:13:23.310 --> 01:13:27.410
Und wir sehen also, diese Dinge hier, das sind Alternativen.

01:13:27.730 --> 01:13:30.010
Da führen Wege auseinander, die verzweigen sich.

01:13:31.850 --> 01:13:36.690
Und da drinnen stehen entweder in Kreisen oder Ovalen elementare

01:13:36.690 --> 01:13:37.210
Konstruktionen.

01:13:38.990 --> 01:13:46.630
Oder es stehen Dinge drinnen, für die wir wieder solch ein Syntax

01:13:46.630 --> 01:13:48.130
-Diagramm einsetzen müssen.

01:13:50.010 --> 01:13:53.510
Syntax-Diagramme sind die einfachste Form und lesbarste Form der

01:13:53.510 --> 01:13:54.050
Darstellung.

01:13:54.690 --> 01:13:57.750
Aber wie man sich leicht überlegen kann, für technische Verarbeitung

01:13:57.750 --> 01:14:00.490
durch diesen Vollidioten-Rechner wenig geeignet.

01:14:01.370 --> 01:14:04.010
Dazu braucht man zu viel Intelligenz, um das zu begreifen.

01:14:07.130 --> 01:14:11.330
Und für den Rechner ist also eine Darstellung, wie wir sie hier sehen,

01:14:11.450 --> 01:14:12.310
besser geeignet.

01:14:12.610 --> 01:14:15.250
Auf der anderen Seite, die Menschen beklagen sich drüber und sagen,

01:14:15.310 --> 01:14:16.330
das ist mir zu kompliziert.

01:14:17.110 --> 01:14:20.370
Das ist der Unterschied zwischen einfacher technischer Verarbeitung

01:14:20.370 --> 01:14:25.930
und vernünftiger Schnittstelle für den Menschen.

01:14:27.130 --> 01:14:28.590
Gibt es Fragen dazu?

01:14:31.530 --> 01:14:33.650
Hier sind die Regeln zusammengestellt.

01:14:52.940 --> 01:14:56.720
Wenn es keine Fragen gibt, dann sind wir mit diesem Thema fertig.

01:14:56.720 --> 01:15:00.040
Wir haben also bei Semitui-Systemen gelernt.

01:15:02.720 --> 01:15:06.720
Ein Markov-Algorithmus mit Schiffchen, das ist die allgemeinste Form

01:15:06.720 --> 01:15:08.560
von Algorithmen.

01:15:09.900 --> 01:15:12.660
Alles, was ich damit berechnen kann, kann ich auch mit einer Chomsky

01:15:12.660 --> 01:15:15.760
-Null -Grammatik beschreiben.

01:15:18.000 --> 01:15:21.860
Chomsky-Null ist mir aber sonst zu allgemein und ich beschränke mich

01:15:21.860 --> 01:15:25.060
lieber auf kontextfreie und reguläre Grammatiken.

01:15:25.060 --> 01:15:27.940
Die regulären Grammatiken werden wir nochmal bekommen, wenn wir

01:15:27.940 --> 01:15:29.300
endliche Automaten besprechen.

01:15:31.700 --> 01:15:38.180
Kontextfreie Grammatiken sind genau das, was ich brauche für die

01:15:38.180 --> 01:15:41.900
Beschreibung von Programmiersprachen mit ihren Klammerstrukturen.

01:15:43.360 --> 01:15:46.180
Weil ich die Forderung zu jeder schließenden Klammer gehört, eine

01:15:46.180 --> 01:15:47.680
öffnende Klammer und umgekehrt.

01:15:47.960 --> 01:15:51.740
Die kann ich kontextfrei ausdrücken, aber die kann ich nicht mit

01:15:51.740 --> 01:15:53.120
regulären Grammatiken ausdrücken.

01:15:55.060 --> 01:15:58.060
Und dementsprechend brauche ich für kontextfreie Grammatiken jetzt

01:15:58.060 --> 01:16:02.800
noch vernünftige Schreibweisen für Menschen wie für Rechner, die es

01:16:02.800 --> 01:16:07.080
mir gestatten, möglichst konzise solche Grammatiken hinzuschreiben für

01:16:07.080 --> 01:16:08.360
irgendwelche Programmiersprachen.

01:16:08.940 --> 01:16:12.460
Und bloß um Ihnen einen Begriff zu geben, wenn Sie beispielsweise zur

01:16:12.460 --> 01:16:19.380
SAP gehen und fragen, was ist denn die Sprache, die das R3-System, Ihr

01:16:19.380 --> 01:16:21.820
Gesamtsystem oder MySAP, versteht.

01:16:23.220 --> 01:16:25.540
Dann können die Ihnen eine Grammatik produzieren.

01:16:27.620 --> 01:16:30.280
Wir haben das selber mal gemacht, da haben Sie es vorher nicht

01:16:30.280 --> 01:16:30.700
gewusst.

01:16:31.300 --> 01:16:33.680
Die hat 1.500 Produktionen.

01:16:34.940 --> 01:16:35.900
1.500.

01:16:36.620 --> 01:16:38.480
Das ist also kein kleines Ding mehr.

01:16:40.040 --> 01:16:41.820
Und das wird von solchen Systemen verarbeitet.

01:16:42.580 --> 01:16:47.340
Und die übliche Kenntnis, die wir haben, lautet, eine übliche

01:16:47.340 --> 01:16:52.020
Programmiersprache lässt sich beschreiben so etwas wie 300, 400

01:16:52.020 --> 01:16:53.100
Produktionen.

01:16:54.000 --> 01:16:58.040
Ganz kleine Sprachen, Pascal gehört dazu, da komme ich mit 100 aus.

01:17:00.640 --> 01:17:05.720
Und unförmige Sprachen beginnen so bei 800 oder 900 Produktionen, aber

01:17:05.720 --> 01:17:07.100
davon habe ich eine ganze Menge Beispiele.

01:17:08.120 --> 01:17:09.640
Insbesondere in der kommerziellen Welt.

01:17:14.670 --> 01:17:16.470
Soviel zu diesen Dingen.

01:17:17.430 --> 01:17:19.450
Und damit sind wir mit diesem Kapitel fertig.

01:17:29.580 --> 01:17:32.960
Wenn aber jetzt jemand meint, er könnte nach Haus gehen.

01:17:34.200 --> 01:17:36.440
Ich habe noch weitere Unterhaltung für Sie.

01:17:44.730 --> 01:17:46.790
Ich gehe über zu meinem nächsten Kapitel.

01:17:49.170 --> 01:17:50.670
Halbgruppen und Relationen.

01:17:52.350 --> 01:17:57.610
Und nur zum Verständnis, ich werde jetzt erst mal nur die Punkte 2.1,

01:17:57.750 --> 01:17:59.870
2.2, 2.3 abhandeln.

01:18:00.270 --> 01:18:03.570
Danach breche ich das zweite Kapitel ab und verschiebe den Rest auf

01:18:03.570 --> 01:18:03.990
später.

01:18:04.410 --> 01:18:08.890
Der Grund ist, das ist ein didaktisches Experiment, dass wir möglichst

01:18:08.890 --> 01:18:10.390
schnell zum Programmieren kommen wollen.

01:18:10.870 --> 01:18:16.550
Und infolgedessen wird 2.4, 2.5, 2.6 auf Weihnachten oder später

01:18:16.550 --> 01:18:16.990
verschoben.

01:18:20.730 --> 01:18:22.030
Aber fangen wir zuerst mal an.

01:18:24.570 --> 01:18:26.950
Ich habe es ja schon öfters mit den Häusern gehabt.

01:18:29.090 --> 01:18:36.270
Und betrachte als erstes mal zwei Sätze, in denen das Wort Haus

01:18:36.270 --> 01:18:36.790
vorkommt.

01:18:37.230 --> 01:18:39.910
Das eine ist der Satz, das Haus hat vier Wände.

01:18:41.190 --> 01:18:44.010
Das zweite ist der Satz, das Haus hat vier Buchstaben.

01:18:45.370 --> 01:18:46.630
Beide Sätze sind richtig.

01:18:48.130 --> 01:18:52.610
Was ist das Gemeinsame an diesen beiden Sätzen?

01:18:56.290 --> 01:18:57.670
Was ist das Trennende?

01:19:00.370 --> 01:19:12.420
Das Gemeinsame ist, dass ich da also das Wort Haus habe und mit dem

01:19:12.420 --> 01:19:17.060
Wort hat sage, dieses Wort Haus steht in einer Relation zu

01:19:17.060 --> 01:19:17.400
irgendetwas.

01:19:18.040 --> 01:19:19.820
Vier Wänden, vier Buchstaben.

01:19:21.560 --> 01:19:22.660
Das ist das Gemeinsame.

01:19:24.900 --> 01:19:28.080
Wenn ich aber jetzt frage, und in welchem Kontext ist denn diese

01:19:28.080 --> 01:19:34.940
Aussage richtig, dann ist klar, der zweite Satz, das Haus hat vier

01:19:34.940 --> 01:19:40.620
Buchstaben, der ist dann, wenn ich sage, ja und das hier ist ein Haus,

01:19:42.060 --> 01:19:43.040
ist der gerade falsch.

01:19:44.480 --> 01:19:45.780
Dieses Haus hier hat vier Wände.

01:19:46.840 --> 01:19:48.240
Oder sogar noch einige mehr.

01:19:52.210 --> 01:19:53.310
Aber es hat nicht vier Buchstaben.

01:19:54.510 --> 01:19:57.290
Sondern um vier Buchstaben zu haben, muss ich ganz offensichtlich das

01:19:57.290 --> 01:19:59.350
Wort Haus wörtlich nehmen.

01:19:59.470 --> 01:20:01.570
H-A-U-S, dann sehe ich die vier Buchstaben.

01:20:03.150 --> 01:20:06.610
Dann kann es aber nicht nur dieses eine Haus gewesen sein.

01:20:07.230 --> 01:20:12.730
Umgekehrt, wenn ich versuche, den Satz ins Englische zu übersetzen,

01:20:13.770 --> 01:20:16.530
dann ist der zweite Satz, das Haus hat vier Buchstaben, falsch.

01:20:18.270 --> 01:20:21.930
The house has not four letters, but five.

01:20:26.550 --> 01:20:31.910
Das heißt, wenn ich die Sprache wechsle, den Kontext der Sprache

01:20:31.910 --> 01:20:34.730
wechsle, dann wird die zweite Relation falsch.

01:20:35.450 --> 01:20:36.610
Die erste bleibt richtig.

01:20:38.770 --> 01:20:43.470
Ich muss also, und das haben wir ja auch diskutiert gehabt, immer

01:20:43.470 --> 01:20:47.770
sehen, dass ich solche Interpretationen mache im geeigneten Kontext,

01:20:47.950 --> 01:20:50.970
und ich habe also hier unterschiedliche Kontexte.

01:20:50.970 --> 01:20:54.550
Aber das, was mich jetzt hier eigentlich interessiert, ist nicht die

01:20:54.550 --> 01:20:56.490
Unterschiede, sondern das Gemeinsame.

01:20:57.850 --> 01:21:02.010
Und das Gemeinsame ist, dass ich also das Wort Haus in beiden Sätzen,

01:21:02.110 --> 01:21:08.970
die ich habe, in Relation setze zu irgendwelchen anderen Begriffen.

01:21:10.610 --> 01:21:14.870
Und das, was wir hier jetzt zunächst diskutieren wollen, ist, was

01:21:14.870 --> 01:21:21.350
wissen wir über Relationen, und was können wir darüber aussagen, und

01:21:21.350 --> 01:21:22.970
wie funktioniert das eigentlich.

01:21:24.890 --> 01:21:29.630
Und Relationen kommen bei uns überall vor, zum Beispiel als so kausale

01:21:29.630 --> 01:21:29.970
Abhängigkeiten.

01:21:31.850 --> 01:21:35.310
Weil der Herr da oben vorhin einen Flieger hat fliegen lassen, wird er

01:21:35.310 --> 01:21:37.730
nachher nicht den Hörsaal verlassen, sondern darunter gehen und den

01:21:37.730 --> 01:21:39.050
Flieger aufheben.

01:21:39.510 --> 01:21:41.090
Das ist eine Relation.

01:21:43.370 --> 01:21:48.010
Er befindet sich im Zustand, er sitzt da oben, und anschließend

01:21:48.010 --> 01:21:52.530
befindet er sich in dem Zustand, er geht darunter und bückt sich.

01:21:55.650 --> 01:21:57.990
Das ist ein anderer Zustand.

01:21:59.590 --> 01:22:02.110
Und dazwischen herrscht eine kausale Abhängigkeit.

01:22:06.410 --> 01:22:08.190
Zumindest, wenn die Leute sich anständig benehmen.

01:22:11.770 --> 01:22:14.930
Das, was wir gerade in Grammatik kennengelernt haben, ein

01:22:14.930 --> 01:22:18.310
arithmetischer Ausdruck ist ein arithmetischer Ausdruck gefolgt von

01:22:18.310 --> 01:22:20.130
einem Plus-Sachen und einem Term.

01:22:20.990 --> 01:22:21.950
Das ist auch eine Relation.

01:22:22.730 --> 01:22:23.560
Das nennen wir Ableitungsrelation.

01:22:25.250 --> 01:22:32.390
Die Umkehrung, du kannst den Ausdruck A plus B zusammenfassen zum

01:22:32.390 --> 01:22:34.190
Begriff arithmetischer Ausdruck.

01:22:34.910 --> 01:22:38.450
Auch eine Relation, das ist die Umkehrung der Ableitungsrelation.

01:22:39.710 --> 01:22:42.630
Diese Arten von Relationen sind universell.

01:22:43.290 --> 01:22:46.670
Und wenn wir in die Datenbanktheorie gehen oder Praxis, dann finden

01:22:46.670 --> 01:22:51.150
wir dort aller Orten relationale Datenbanken.

01:22:51.270 --> 01:22:53.790
Und was ist eine solche relationale Datenbank?

01:22:53.790 --> 01:22:57.750
Die heißt, du hast irgendwelche Tupel.

01:22:59.490 --> 01:23:06.370
T1, T2, T3 und so weiter bis Tn.

01:23:08.510 --> 01:23:13.990
Und die sagen, T1 bis Tn bestehen in einer bestimmten Relation.

01:23:13.990 --> 01:23:23.750
Und wenn du also andere Tupel hast, X1, X2 und so weiter bis Xm.

01:23:26.070 --> 01:23:28.870
Dann ist das eine andere solche Relation.

01:23:29.690 --> 01:23:31.710
Und die eine ist schwarz, die andere ist rot.

01:23:32.050 --> 01:23:34.910
Nun also im Rechner kann ich dummerweise Farben nicht unterscheiden.

01:23:35.770 --> 01:23:39.390
Infolgedessen schreibe ich das jetzt alles einheitlich und sage, das

01:23:39.390 --> 01:23:42.590
ist die Relation R und das ist die Relation S.

01:23:44.510 --> 01:23:48.450
Das sind dann unterschiedliche Relationen.

01:23:48.610 --> 01:23:53.610
Und auf solchen Relationen baue ich die ganze Technik der Datenbanken

01:23:53.610 --> 01:23:53.950
auf.

01:23:54.950 --> 01:23:56.170
Solche Tupel zu definieren.

01:23:58.270 --> 01:24:01.110
Wir können das also für verschiedenste Zwecke nutzen.

01:24:02.290 --> 01:24:07.690
In der Spezifikationstechnik nutzen wir es für endliche Automaten, ein

01:24:07.690 --> 01:24:10.650
Ablaufmodell oder für sogenannte Petri-Netze.

01:24:11.650 --> 01:24:15.470
In der grafischen Darstellung stellt sich heraus, dass solche

01:24:15.470 --> 01:24:19.970
Relationen eigentlich Grafen entsprechen.

01:24:20.090 --> 01:24:22.030
Die kann ich bildlich aufmalen.

01:24:23.270 --> 01:24:27.770
Und das womit wir beginnen und was wir uns als erstes anschauen, ist

01:24:27.770 --> 01:24:31.070
die einfachste Relation, die wir uns überhaupt vorstellen können.

01:24:32.450 --> 01:24:38.110
Wenn ich frage, du hast den Buchstaben A und du hast den Buchstaben B.

01:24:39.470 --> 01:24:41.210
Und in welcher Relation stehen die?

01:24:41.870 --> 01:24:44.650
Dann stelle ich als erstes fest, sie stehen hintereinander.

01:24:50.590 --> 01:24:53.890
Das Nebeneinanderschreiben von Buchstaben in Texten, das ist die

01:24:53.890 --> 01:24:54.910
einfachste Relation.

01:24:55.270 --> 01:24:58.170
Und wir studieren als erstes mal, was sind die mathematischen

01:24:58.170 --> 01:25:00.230
Eigenschaften dieses Nebeneinanderschreibens.

01:25:02.110 --> 01:25:03.850
Das ist unsere erste Aufgabe.

01:25:05.790 --> 01:25:08.230
Und das führt also zu Halbgruppen und Monoiden.

01:25:09.450 --> 01:25:13.390
Ausgangspunkt ist die Untersuchung der Struktur von Zeichenreihen oder

01:25:13.390 --> 01:25:13.970
Texten.

01:25:14.330 --> 01:25:19.630
Wir werden hinterher feststellen, dass die Halbgruppen noch an vielen

01:25:19.630 --> 01:25:20.870
anderen Stellen vorkommen.

01:25:21.730 --> 01:25:25.710
Und für die mathematisch Begabten, warum heißt das Kind Halbgruppe?

01:25:25.710 --> 01:25:28.090
Das ist ein bisschen amputiert.

01:25:29.670 --> 01:25:32.370
Das ist keine ganze Gruppe, das kann bestimmte Dinge nicht.

01:25:33.410 --> 01:25:34.470
Was kann es denn nicht?

01:25:36.010 --> 01:25:38.490
Es ist eine Gruppe, die keine Inverse kann.

01:25:40.490 --> 01:25:46.690
Das ist also für die mathematisch Inklinierten die Feststellung, die

01:25:46.690 --> 01:25:47.710
wir zunächst einmal haben.

01:25:50.350 --> 01:25:52.750
Und bei mir ist es noch nicht so viel.

01:25:58.130 --> 01:26:03.050
Die Grundoperation des Nebeneinanderschreibens, die muss ich, wenn ich

01:26:03.050 --> 01:26:06.430
sie jetzt untersuchen will, erstmal mit einem Namen belegen.

01:26:07.730 --> 01:26:09.310
Und ich nenne sie Verkettung.

01:26:10.430 --> 01:26:14.090
Und schreibe sie in diesem Beispiel jetzt erstmal mit dem Zeichen

01:26:14.090 --> 01:26:14.910
Punkt.

01:26:15.290 --> 01:26:16.190
Hochgestellter Punkt.

01:26:27.080 --> 01:26:29.080
Und das soll ja zu der Verkettung entsprechen.

01:26:35.170 --> 01:26:42.050
Und wenn ich jetzt zwei Zeichen hinschreibe, 3 Punkt 7, dann ist das

01:26:42.050 --> 01:26:45.130
die Zahl 37, wenn ich sie ohne den Punkt schreibe, hintereinander

01:26:45.130 --> 01:26:45.570
geschrieben.

01:26:46.270 --> 01:26:49.630
Dass mir ja niemand auf die Idee kommt, 3 mal 7 sei doch 21.

01:26:51.910 --> 01:26:54.450
Ich habe kein Malzeichen geschrieben, ich habe einen Punkt

01:26:54.450 --> 01:26:54.970
geschrieben.

01:26:56.690 --> 01:26:59.810
Und es war ihre Einbildung, dass sie meinten, das sei ein Malzeichen.

01:27:01.010 --> 01:27:04.870
Sie sollen aber nicht auf sich was einbilden, sondern sie sollen ganz

01:27:04.870 --> 01:27:06.810
genau alles wörtlich nehmen.

01:27:07.930 --> 01:27:11.110
So wie es ein Rechner auch tut, und der ist ein Vollidiot, der weiß

01:27:11.110 --> 01:27:12.290
gar nicht, was ein Malzeichen ist.

01:27:13.730 --> 01:27:14.970
Sie sind also viel zu schlau.

01:27:17.750 --> 01:27:20.430
Und daher kann der Rechner das genau interpretieren.

01:27:20.430 --> 01:27:25.230
Die Überlegung, die dahinter steht, ist die, als Informatiker müssen

01:27:25.230 --> 01:27:31.010
Sie lernen, dass wir bei weitem zu wenig Operatorzeichen haben.

01:27:31.770 --> 01:27:36.630
Und dass die Informatik daher Plus- und Minuszeichen und Malzeichen,

01:27:36.770 --> 01:27:40.890
egal ob es Sterne sind oder Punkte sind und so weiter, andauernd noch

01:27:40.890 --> 01:27:42.710
für ganz andere Zwecke gebraucht.

01:27:43.230 --> 01:27:47.070
Und wenn Sie irgendeinen Ausdruck sehen, bei dem Sie zunächst meinen,

01:27:47.230 --> 01:27:49.530
das sei eine Addition, da steht also A plus B.

01:27:50.790 --> 01:27:53.610
Dann gibt es Programmiersprachen, bei denen das keineswegs eine

01:27:53.610 --> 01:27:54.370
Addition ist.

01:27:55.890 --> 01:28:00.390
Sondern bei denen A plus B heißt, schreibe A und B hintereinander.

01:28:02.330 --> 01:28:06.190
Und dann gibt es andere Programmiersprachen, da heißt A plus B, A und

01:28:06.190 --> 01:28:09.290
B sind Mengen und A plus B heißt, vereinige die beiden Mengen.

01:28:11.270 --> 01:28:14.650
Also auch das Pluszeichen als Addition zu lesen, kann an vielen

01:28:14.650 --> 01:28:15.570
Stellen falsch sein.

01:28:15.570 --> 01:28:19.170
Und so verhält sich es auch hier mit dem Punkt.

01:28:20.070 --> 01:28:23.650
Und Sie sehen das am nächsten, dem Wort Informatik.

01:28:25.290 --> 01:28:29.510
Und natürlich, also ich kann auch nicht nur Einzelzeichen verketten,

01:28:29.650 --> 01:28:31.570
sondern ich kann das sofort verallgemeinern.

01:28:31.870 --> 01:28:35.670
Und kann Zeichenreihen verketten und kann also dieses Beispiel auch

01:28:35.670 --> 01:28:38.570
schreiben als Informatik.

01:28:38.570 --> 01:28:43.210
Und jetzt habe ich mal zur Deutlichkeit 30 Klammern hingeschrieben.

01:28:44.550 --> 01:28:47.070
Und es gibt immer noch dieselbe Geschichte.

01:28:47.590 --> 01:28:50.630
Und die Klammern sind hier offensichtlich Einzelmetazeichen, genauso

01:28:50.630 --> 01:28:53.890
wie der Punkt, der die Konstruktion bezeichnet.

01:28:54.910 --> 01:29:00.450
Das führt uns zu der Definition, was eine Halbgruppe ist.

01:29:01.150 --> 01:29:04.910
Das ist eine Menge U mit binärer Operation, die ich hier jetzt als

01:29:04.910 --> 01:29:05.850
Punkt schreibe.

01:29:07.450 --> 01:29:12.890
Und wie in der Mathematik auch, erwarte ich, wenn das eine vernünftige

01:29:12.890 --> 01:29:20.970
Struktur ist, dass mit Elementen A und B, auch A verknüpft mit B, zu

01:29:20.970 --> 01:29:21.890
der Menge U gehört.

01:29:22.110 --> 01:29:23.870
Das ist die algebraische Abgeschlossenheit.

01:29:26.110 --> 01:29:30.470
Und bei Halbgruppen verlange ich zusätzlich, dass das Assoziativgesetz

01:29:30.470 --> 01:29:30.810
gilt.

01:29:32.510 --> 01:29:34.930
Und das sind alle Gesetze, die ich fordere.

01:29:35.550 --> 01:29:36.450
Mehr fordere ich nicht.

01:29:37.630 --> 01:29:40.770
Wenn Sie die Gruppendefinition anschauen in der Mathematik, dann geht

01:29:40.770 --> 01:29:44.950
es jetzt weiter mit der Forderung, und es gibt ein Einzelement und es

01:29:44.950 --> 01:29:47.890
gibt ein Inversus zu jedem Element.

01:29:49.650 --> 01:29:51.970
Die Forderungen erhebe ich bei Halbgruppen nicht.

01:29:54.190 --> 01:29:58.310
Ich fordere im allgemeinen Fall noch nicht einmal die Kommutativität,

01:29:58.310 --> 01:30:01.170
sondern wenn ich Kommutativität fordere, dann ist das ein

01:30:01.170 --> 01:30:02.590
Zusatzgesetz.

01:30:03.910 --> 01:30:07.790
Und in der Informatik ist dieses Zusatzgesetz meistens nicht erfüllt.

01:30:08.610 --> 01:30:11.070
Also es ist nicht so schön wie in der Mathematik, die sehr, sehr

01:30:11.070 --> 01:30:13.150
häufig mit kommutativen Strukturen zu tun hat.

01:30:14.070 --> 01:30:20.410
Sondern wir haben es meistens mit nicht-kommutativen Dingen zu tun,

01:30:20.610 --> 01:30:22.490
wie Sie schon an den Zeichenreihen sehen.

01:30:23.210 --> 01:30:26.570
A, B und B, A sind eben zwei verschiedene Zeichenreihen.

01:30:26.570 --> 01:30:27.930
Und die sind nicht gleich.

01:30:29.610 --> 01:30:32.730
Und das führt zum Abschluss zu der Definition, was ist jetzt eine

01:30:32.730 --> 01:30:33.190
Algebra?

01:30:34.430 --> 01:30:38.130
Und eine Algebra besteht aus einer Menge, die ich als Trägermenge

01:30:38.130 --> 01:30:44.970
bezeichne, einer Menge O von Operationen, hier habe ich eine einzelne,

01:30:44.990 --> 01:30:49.590
die Verknüpfung, und alle diese Operationen, von denen verlange ich,

01:30:49.630 --> 01:30:53.110
dass sie algebraisch abgeschlossen sind, dass also diese Regel hier

01:30:53.110 --> 01:30:53.630
oben gilt.

01:30:55.150 --> 01:31:04.430
Und dann gibt es noch in Algebren keine oder mehrere Gesetze, wie zum

01:31:04.430 --> 01:31:08.570
Beispiel das Assoziativgesetz oder das Kommutativgesetz, die sagen,

01:31:09.010 --> 01:31:11.350
wann bestimmte Arten von Verknüpfungen gleich sind.

01:31:12.370 --> 01:31:15.450
Und das ist alles, was ich über eine Algebra weiß, und eine Halbgruppe

01:31:15.450 --> 01:31:16.270
ist ein Beispiel.

01:31:17.310 --> 01:31:22.690
Und der Schlusssatz der Vorlesung lautet, das ist alles, was ich über

01:31:22.690 --> 01:31:24.070
eine Algebra weiß.

01:31:24.690 --> 01:31:26.390
Und mehr weiß ich nicht.

01:31:27.790 --> 01:31:34.130
Und wenn irgendjemand von Ihnen jetzt meint, Algebra ist doch etwas

01:31:34.130 --> 01:31:36.730
ganz Kompliziertes, das haben mir meine Schullehrer schon klar

01:31:36.730 --> 01:31:39.550
gemacht, wie kompliziert das ist, oder irgendwelche

01:31:39.550 --> 01:31:44.550
Mathematikprofessoren machen mir das auch klar, dann kann ich Ihnen

01:31:44.550 --> 01:31:49.730
nur sagen, Algebra ist genau das, was hier steht, und mehr ist es

01:31:49.730 --> 01:31:50.070
nicht.

01:31:50.710 --> 01:31:53.770
Und es ist extrem wichtig, damit ich Sie im weiteren Verlauf nicht

01:31:53.770 --> 01:31:57.150
abhänge, dass Sie begriffen haben, dass eine Algebra nicht

01:31:57.150 --> 01:31:59.670
komplizierter ist, als das, was ich hier in der Definition gesagt

01:31:59.670 --> 01:32:00.810
habe. Dankeschön.