WEBVTT

00:04.880 --> 00:05.940
Schönen guten Tag.

00:07.680 --> 00:14.360
Lassen Sie uns anfangen mit der nächsten Vorlesung und weitermachen,

00:14.560 --> 00:17.960
da wo wir am Mittwoch aufgehört haben, bei kontextfreien Grammatiken.

00:20.640 --> 00:24.420
Da hat man also so zwei Sorten Symbole.

00:24.520 --> 00:27.420
Die Terminalsymbole, aus denen die Wörter sind, die einen am Ende

00:27.420 --> 00:28.040
interessieren.

00:28.180 --> 00:30.580
Und so Hilfssymbole, Nicht-Terminalsymbole.

00:31.860 --> 00:37.680
Und Produktionen, die einem erlauben, ein Nicht-Terminalsymbol, wo

00:37.680 --> 00:41.480
auch immer es vorkommt, zu ersetzen durch ein anderes Wort.

00:41.640 --> 00:44.560
Also jetzt hier zum Beispiel diese einfache Grammatik.

00:44.700 --> 00:47.180
Das einzige Nicht-Terminalsymbol ist das große X.

00:47.940 --> 00:51.520
Und Sie können es ersetzen durch zwei große X oder Klammer auf, X,

00:51.640 --> 00:52.160
Klammer zu.

00:53.000 --> 00:56.120
Klammer auf und Klammer zu sind die beiden Terminalsymbole, die wir

00:56.120 --> 00:57.060
zur Verfügung haben.

00:57.680 --> 00:59.280
Oder durch das leere Wort.

01:01.020 --> 01:03.240
Und das leere Wort ist...

01:04.940 --> 01:06.740
auch eine erlaubte rechte Seite.

01:06.900 --> 01:10.700
Da darf jede beliebige Folge aus Terminal- und Nicht-Terminalsymbolen

01:10.700 --> 01:11.000
stehen.

01:12.340 --> 01:15.900
Und wir schreiben dafür halt immer hier so ein kleines griechisches

01:15.900 --> 01:16.380
Epsilon.

01:17.480 --> 01:21.000
Aber das ist etwas, was wir schreiben, um auszudrücken, hier ist das

01:21.000 --> 01:21.580
leere Wort.

01:21.580 --> 01:27.380
Also dieses Epsilon ist niemals dieses Zeichen, das wir so in

01:27.380 --> 01:30.540
Anführungszeichen umgangssprachlich oder umgangsschriftlich benutzen,

01:31.280 --> 01:36.180
ist niemals Element irgendeines Alphabets, ist das leere Wort.

01:36.340 --> 01:40.260
Dieses Epsilon ist kein Terminalsymbol und auch kein Nicht

01:40.260 --> 01:40.980
-Terminalsymbol.

01:41.140 --> 01:44.360
Wir benutzen das nur, um deutlich zu machen, wir meinen hier das leere

01:44.360 --> 01:44.660
Wort.

01:47.020 --> 01:49.420
Und dann kann man... Ups, falsche Richtung.

01:52.540 --> 01:55.460
Dann gibt es immer noch ein ausgezeichnetes Startsymbol, mit dem man

01:55.460 --> 01:56.240
immer anfängt.

01:56.900 --> 01:59.960
Naja gut, wenn man nur ein Nicht-Terminalsymbol hat, das Startsymbol

01:59.960 --> 02:02.780
ist ein Nicht-Terminalsymbol, dann muss man halt mit dem einen

02:02.780 --> 02:03.940
anfangen, also hier das X.

02:04.680 --> 02:07.920
Und wenn man dann so Ableitungsschritte, so Ersetzungen der Reihe nach

02:07.920 --> 02:13.220
durchführt, dann häufig die übersichtlichste Art und Weise, das

02:13.220 --> 02:17.460
hinzuschreiben oder zu malen, ist so ein sogenannter Ableitungsbaum,

02:17.760 --> 02:21.740
also oben bei diesem Informatikerbaum oben ist die Wurzel.

02:22.200 --> 02:25.340
Und dann immer, wenn ich ein Symbol, also zum Beispiel hier das Groß

02:25.340 --> 02:28.820
-X, jetzt das Startsymbol ersetze durch die rechte Seite, die aus zwei

02:28.820 --> 02:34.720
großen X besteht, dann malt man da eben drunter in einem Abstand, der

02:34.720 --> 02:39.680
irgendwie passend ist, wie man will, die Symbole der rechten Seite,

02:39.820 --> 02:44.380
also hier zwei X, und malt so Striche von dem Nicht-Terminalsymbol

02:44.380 --> 02:47.060
oben drüber zu den Symbolen der rechten Seite.

02:48.660 --> 02:51.840
Und dann das linke von den beiden X ersetzt man vielleicht durch

02:51.840 --> 02:55.380
Klammer auf, X, Klammer zu, also schreibt man da Klammer auf, X,

02:55.520 --> 02:58.500
Klammer zu, diese drei Symbole der rechten Seite hin und macht drei

02:58.500 --> 03:02.060
Schritte, drei Striche zu den Symbolen der rechten Seite.

03:02.660 --> 03:03.880
Und so weiter und so weiter.

03:05.160 --> 03:09.000
Und solche Ableitungen sollen immer endlich sein.

03:09.060 --> 03:12.800
Man macht das so lange, bis keine Nicht-Terminalsymbole mehr da sind,

03:12.920 --> 03:14.740
alles nur noch Terminalsymbole sind.

03:16.260 --> 03:20.340
Und das Wort, das dann entsteht, das kann man dann an dem

03:20.340 --> 03:21.840
Ableitungsbaum auch ablesen.

03:21.940 --> 03:24.660
Also da steht dann unten, wo es nicht mehr weitergeht, entweder ein

03:24.660 --> 03:26.200
einzelnes Terminalsymbol.

03:27.020 --> 03:28.780
Terminalsymbole darf man nicht weiter ersetzen.

03:29.040 --> 03:31.900
Die heißen so, weil es da zu Ende ist mit dem Ableiten.

03:31.900 --> 03:37.320
Und falls man das hat, das leere Wort, wenn das mal auf der rechten

03:37.320 --> 03:37.960
Seite steht.

03:38.620 --> 03:44.100
Und wenn Sie dann ablesen wollen, welches Wort wird jetzt erzeugt

03:44.100 --> 03:47.420
durch diesen Ableitungsbaum, dann müssen Sie eben sozusagen von ganz

03:47.420 --> 03:51.620
links nach ganz rechts an dem ganzen Baum langgehen, an den Blättern

03:51.620 --> 03:53.120
und die der Reihe nach aufsammeln.

03:54.660 --> 03:57.640
Also, das ist so ein bisschen ein Anführungszeichen, also Klammer auf.

03:57.740 --> 04:00.800
Hier, das ist das am weitesten links stehende Terminalsymbol, also

04:00.800 --> 04:01.460
Klammer auf.

04:01.460 --> 04:05.680
Dann kommt die Klammer auf, dann Klammer zu, Klammer zu, Klammer auf,

04:05.820 --> 04:07.340
Klammer zu, Klammer auf, Klammer zu.

04:08.320 --> 04:10.040
Das ist das Wort, das hier abgeleitet wird.

04:11.800 --> 04:13.460
So, das sind Ableitungsbäume.

04:15.100 --> 04:18.280
Und diese Beispielgrammatik erzeugt das, was man korrekte

04:18.280 --> 04:19.960
Klammerausdrücke oder so nennt.

04:21.220 --> 04:24.180
Und das kann man noch verallgemeinern, indem man sagt, naja, ich

04:24.180 --> 04:28.040
erlaube nicht nur hier runde Klammern, sondern vielleicht zusätzlich

04:28.040 --> 04:30.860
auch noch eckige Klammern und hat dann auch noch eine Produktion, x

04:30.860 --> 04:34.860
kann ich ersetzen durch eckige Klammer auf, x eckige Klammer zu oder

04:34.860 --> 04:35.100
so.

04:35.720 --> 04:37.880
Und vielleicht auch noch geschweifte Klammern oder was auch immer.

04:38.880 --> 04:41.740
Und dann kriegen Sie also ein bisschen allgemeiner so Klammersprachen,

04:41.840 --> 04:46.220
wo Sie immer so schön ordentlich in Anführungszeichen ineinander

04:46.220 --> 04:48.560
geschachtelt so Klammerpaare haben.

04:49.260 --> 04:51.900
Und das sind ganz, ganz wichtige Beispiele.

04:51.900 --> 04:55.380
Also wenn man Theorieformaler Sprachen macht, sieht man das dann ganz

04:55.380 --> 04:55.580
schnell.

04:56.080 --> 04:59.200
Ganz wichtige Beispiele für solche kontextfreie Sprachen.

04:59.660 --> 05:03.320
Kontextfreie Sprachen sind Sprachen, die man mit einer kontextfreien

05:03.320 --> 05:04.640
Grammatik erzeugen kann.

05:06.020 --> 05:07.500
Solche Sprachen gibt es.

05:08.660 --> 05:09.640
Hier ist ein Beispiel.

05:09.820 --> 05:11.180
Ja, jede Grammatik erzeugt irgendwas.

05:12.960 --> 05:15.220
Und es gibt auch formale Sprachen, die sind nicht kontextfrei.

05:15.220 --> 05:19.600
Die sind sozusagen zu kompliziert für diesen in Anführungszeichen

05:19.600 --> 05:21.300
relativ einfachen Mechanismus.

05:21.660 --> 05:23.740
Da gucken wir uns dann gleich auch noch ein Beispiel an.

05:24.880 --> 05:25.480
So.

05:26.980 --> 05:30.420
Und für zum Beispiel arithmetische Ausdrücke kann man halt dann auch

05:30.420 --> 05:31.380
irgendwas hinmalen.

05:31.720 --> 05:35.460
Diese Grammatik hier ist übrigens nicht so toll.

05:36.460 --> 05:37.440
Wo haben wir es?

05:39.240 --> 05:44.500
Wenn Sie dann nämlich gucken, den Ableitungsbaum zu dieser Folge von

05:44.500 --> 05:49.940
Terminalsymbolen 3 plus 2 mal 5, dann kriegen Sie den Ableitungsbaum,

05:50.020 --> 05:51.280
der da links hingemalt ist.

05:52.700 --> 05:56.940
Und da sehen Sie, dieser Ableitungsbaum, also in Anführungszeichen

05:56.940 --> 06:01.780
suggeriert jedenfalls irgendwie, dass dieses 3 plus 2 enger

06:01.780 --> 06:05.620
zusammengehört, als dann da hinten dran noch dieses mal 5.

06:07.300 --> 06:11.560
Und in der Praxis, also in Java, wenn Sie sowas hinschreiben wie 3

06:11.560 --> 06:18.420
plus 2 mal 5 ohne Klammern, was Sie erwarten, ist, wenn der Rechner

06:18.420 --> 06:21.780
das auswertet, dass da erst 2 mal 5 gerechnet wird.

06:21.780 --> 06:24.600
Ja, diese Regelpunktvorstrich, die man so kennt.

06:25.280 --> 06:30.620
Also 2 mal 5 plus 3 gibt 13, aber der Baum sieht mir aus nach 3 plus 2

06:30.620 --> 06:32.940
ist 5 mal 5 ist 25.

06:34.460 --> 06:37.220
Und deswegen, also die Grammatik wird man nicht nehmen für

06:37.220 --> 06:38.320
arithmetische Ausdrücke.

06:38.780 --> 06:43.320
Ich habe Ihnen hier spaßhalber mal eine hingemalt, wo das sozusagen

06:43.320 --> 06:48.740
mit diesen Vorrangregeln, Multiplikation und Division, diese Zeichen

06:48.740 --> 06:53.220
binden irgendwie stärker als Addition und Subtraktion, eine Grammatik

06:53.220 --> 06:53.920
mal hingemalt.

06:54.000 --> 06:57.540
Sie können ja mit der mal rumspielen, wenn Sie wollen, und da dieses

06:57.540 --> 06:59.660
Wort 3 plus 2 mal 5 ableiten.

07:00.320 --> 07:03.900
Das geht auch bei der Grammatik hier unten nur auf eine Art und Weise.

07:05.200 --> 07:08.740
Und da werden Sie sehen, das ist die, wo Sie einen Teilbaum haben für

07:08.740 --> 07:09.660
2 mal 5.

07:09.660 --> 07:11.840
Das ist irgendwie enger zusammen.

07:15.440 --> 07:23.660
Ein anderes einfaches Beispiel war Erzeugung von allen syntaktisch

07:23.660 --> 07:26.660
korrekten Aussagen, logischen Formeln, wenn Sie sich daran erinnern.

07:27.420 --> 07:32.680
Da gab es also Aussagevariablen und dann konnte man eben, wenn man

07:32.680 --> 07:37.120
schon eine Formel hat, Negationszeichen davor machen oder ein Und oder

07:37.120 --> 07:40.580
ein Oder oder einen Implikationspfeil zwischen zwei Aussagen, logische

07:40.580 --> 07:43.140
Formeln, nur noch Klammer außenrum, auch wieder Klammern.

07:43.580 --> 07:47.760
Und das, was wir im fünften Kapitel da so umgangssprachlich

07:47.760 --> 07:51.180
beschrieben haben, das kann man jetzt ganz kompakt hier mit einer

07:51.180 --> 07:54.560
kleinen kontextfreien Grammatik ausdrücken.

07:54.760 --> 07:59.280
Das sind die syntaktisch korrekten aussagelogischen Formeln.

08:03.100 --> 08:05.020
Und das wird hier nochmal erwähnt.

08:05.120 --> 08:07.980
Also zum einen, bitte schlagen Sie nochmal nach im fünften Kapitel,

08:08.060 --> 08:09.760
was wir da aufgeschrieben haben.

08:10.280 --> 08:13.100
Und dann vergleichen Sie die, ich weiß nicht, halbe Seite oder

08:13.100 --> 08:16.660
Drittelseite, die da steht, mit den zwei Zeilen und machen Sie sich

08:16.660 --> 08:16.980
klar.

08:17.500 --> 08:21.960
Tatsächlich, da steht inhaltlich im Wesentlichen, also inhaltlich

08:21.960 --> 08:24.340
bedeutet es das exakt das Gleiche.

08:24.860 --> 08:28.920
Nur das hier ist kürzer, aber nicht kürzer, weil es besonders

08:28.920 --> 08:31.660
kryptisch geworden ist, sondern einfach, weil man sich auf das

08:31.660 --> 08:33.580
Wesentliche beschränken konnte mit dem Formalismus.

08:34.280 --> 08:35.660
Das ist einfach hilfreich.

08:38.020 --> 08:41.840
Und das erwähne ich hier nochmal, weil wir dann im nächsten Kapitel zu

08:41.840 --> 08:43.540
komplizierteren logischen Formeln kommen.

08:44.640 --> 08:48.560
Und da kann man dann froh sein, dass wir das alles mit ein paar

08:48.560 --> 08:53.100
Produktionen hinschreiben können und nicht seitenweise Text auf

08:53.100 --> 08:54.480
Deutsch oder Englisch oder irgendwas.

08:57.630 --> 09:01.830
Also wichtig, ja, kontextfreie Grammatiken kommen ständig überall vor.

09:02.550 --> 09:05.050
Wenn Sie zum Beispiel nachschlagen, wie ist Java syntaktisch

09:05.050 --> 09:08.990
festgelegt, im Wesentlichen steht da eine kontextfreie Grammatik.

09:10.550 --> 09:12.350
Also soweit es die Syntax betrifft.

09:15.750 --> 09:19.530
Und da muss man halt so ein bisschen üben, wenn da so ein paar

09:19.530 --> 09:23.230
Produktionen stehen, zu verstehen, was bedeutet das denn eigentlich

09:23.230 --> 09:25.670
und gucken, welche Wörter kann ich denn ableiten.

09:26.590 --> 09:30.110
Also was einen immer interessiert, sind die Wörter, die man aus dem

09:30.110 --> 09:33.270
Startsymbol ableiten kann und die nur noch aus Terminalsymbolen

09:33.270 --> 09:33.670
bestehen.

09:35.130 --> 09:40.370
Und das Umgekehrte natürlich auch, wenn man einen Plan davon hat, ich

09:40.370 --> 09:44.470
möchte gerne beschreiben, diese Menge von Wörtern, wie könnte denn

09:44.470 --> 09:46.570
eine kontextfreie Grammatik dazu aussehen.

09:48.050 --> 09:53.590
Wenn es eine solche kontextfreie Grammatik gibt, wenn man Pech hat,

09:53.630 --> 09:54.170
gibt es keine.

09:55.010 --> 10:01.630
Und da gibt es auch relativ übersichtliche Beispiele von formalen

10:01.630 --> 10:05.450
Sprachen, wo man denkt, das sieht ja nicht so wild aus, aber man kann

10:05.450 --> 10:07.810
es eben nicht mit kontextfreien Grammatiken beschreiben.

10:09.470 --> 10:14.710
Das betrifft sogar so Dinge, die man gerne ausdrücken wollte, wie jede

10:14.710 --> 10:17.230
Variable, die in einem Java Programm benutzt wird, muss vorher

10:17.230 --> 10:18.090
deklariert sein.

10:18.250 --> 10:21.010
Das können Sie mit kontextfreien Grammatiken nicht ausdrücken.

10:21.930 --> 10:22.330
Leider.

10:23.610 --> 10:24.130
Gut.

10:26.050 --> 10:29.190
Und wir werden uns dann im letzten Abschnitt gleich ein Beispiel

10:29.190 --> 10:34.910
angucken, einer formalen Sprache, die nicht kontextfrei ist.

10:35.090 --> 10:38.110
Und Sinn der Aktion ist dann tatsächlich einfach mal zu beweisen,

10:38.910 --> 10:42.750
diese formale Sprache, um die es dann da geht, ist nicht kontextfrei.

10:44.090 --> 10:45.930
Damit Sie mal sehen.

10:47.810 --> 10:51.250
Also erstens, es gibt nicht nur Beweise durch vollständige Induktion.

10:53.410 --> 10:56.630
Zweitens, es gibt Beweise, die passen nicht in drei Zeilen, sondern

10:56.630 --> 10:58.910
das ist dann schon ein bisschen längere Argumentation.

10:59.590 --> 11:02.390
Aber das ist dann auch, was wir uns da angucken, werden gleich so

11:02.390 --> 11:03.750
kompliziert.

11:03.750 --> 11:07.390
Da müssen Sie nicht Angst haben, dass man erwarten würde von Ihnen,

11:07.490 --> 11:09.670
Sie könnten von selber auf so etwas kommen.

11:09.770 --> 11:11.930
Also nicht im ersten Semester nach sechs Wochen.

11:13.170 --> 11:13.690
Gut.

11:14.110 --> 11:18.530
Bevor wir uns das im letzten Abschnitt angucken, kurz noch ein paar

11:18.530 --> 11:23.970
Worte zu einer Verallgemeinerung von dem, was wir gerade bei

11:23.970 --> 11:25.690
kontextfreien Grammatiken gemacht haben.

11:26.290 --> 11:30.310
Man hat definiert erstmal, was kann ich in einem Schritt ableiten aus

11:30.310 --> 11:31.730
einem Wort, welche anderen Worte.

11:31.850 --> 11:34.810
Und dann will man gerne reden über, was kann ich in beliebig vielen

11:34.810 --> 11:35.650
Schritten ableiten.

11:39.830 --> 11:44.530
Und die Ableitungsrelation ist eine Relation, also zu erinnern, eine

11:44.530 --> 11:50.030
Relation R, das ist also jetzt, wenn wir uns auf den Standardfall von

11:50.030 --> 11:55.290
zweistelligen Relationen beschränken, erstmal eine Teilmenge von einem

11:55.290 --> 11:57.450
kathesischen Produkt M1 kreuz M2.

11:59.290 --> 12:03.370
M1 und M2 können natürlich gleich sein, sind es auch oft, aber im

12:03.370 --> 12:05.510
Allgemeinen verschieden.

12:06.530 --> 12:09.810
Also denken Sie an so etwas wie kleinergleich auf den natürlichen

12:09.810 --> 12:10.810
Zahlen oder so etwas.

12:10.810 --> 12:15.530
Und wenn man eine Relation R hat und eine zweite Relation S, Teilmenge

12:15.530 --> 12:20.650
von M2 kreuz M3 und der Witz ist jetzt hier, dass M2, der erste Faktor

12:20.650 --> 12:23.430
hier bei dem zweiten kathesischen Produkt, ist gleich dem zweiten

12:23.430 --> 12:25.170
Faktor beim ersten kathesischen Produkt.

12:25.170 --> 12:30.750
Wenn man so etwas hat, also bildlich hingemalt, wenn Sie für M1, M2,

12:30.950 --> 12:33.890
M3 so drei Kringel hinmalen für die drei Mengen.

12:34.610 --> 12:40.930
Jede Relation legt so ein paar Pfeile fest von Elementen in M1 zu

12:40.930 --> 12:42.030
Elementen in M2.

12:42.930 --> 12:47.450
Und die Relation S, so etwas können Sie, wenn die Mengen endlich sind,

12:47.590 --> 12:51.950
irgendwie hinmalen durch eben alle Pfeile, die von den jeweiligen

12:51.950 --> 12:55.070
Elementen aus M2 zu denen in M3 gehen.

12:55.390 --> 12:58.810
Also vorausgesetzt, die beiden Elemente stehen halt in der Relation.

13:00.370 --> 13:04.530
Wenn Sie so etwas haben, dann können Sie das machen, was wir im

13:04.530 --> 13:08.870
einfachen Fall, wir haben es mit Abbildungen zu tun, schon im früheren

13:08.870 --> 13:10.130
Kapitel auch definiert haben.

13:10.130 --> 13:16.430
Sie können so ein Produkt oder Komposition von den beiden Relationen

13:16.430 --> 13:17.590
definieren.

13:18.530 --> 13:21.830
Und wie bei Funktionen, die Reihenfolge der Faktoren ist jetzt so ein

13:21.830 --> 13:24.130
bisschen kontraintuitiv.

13:25.110 --> 13:27.930
Also da steht links das S und dann so ein kleiner Kringel und dann das

13:27.930 --> 13:28.250
R.

13:29.390 --> 13:33.410
Und das soll wieder eine Relation sein und zwar eine Relation, die

13:33.410 --> 13:36.570
beinhaltet Paare aus M1 kreuz M3.

13:36.570 --> 13:40.710
Also da stehen jetzt Elemente in M1 in Beziehung zu Elementen in M3.

13:41.690 --> 13:46.190
Und zwar genau dann, also Sie kriegen genau dann hier diese roten

13:46.190 --> 13:47.810
Pfeile, so für S-Kringel-R.

13:49.590 --> 13:56.450
Wenn es ein Y in M2 gibt, so dass Sie, also wenn Sie da von X nach Y

13:56.450 --> 14:01.990
kommen in Relation R und dann von Y nach Z in der Relation S, dann und

14:01.990 --> 14:06.090
nur dann sagt man, okay, das Paar XZ steht in der Relation S-Kringel

14:06.090 --> 14:06.250
-R.

14:06.390 --> 14:10.250
Also Sie kriegen dann in dem Beispielbildchen genau die drei roten

14:10.250 --> 14:14.470
Pfeile von M1 nach M3, weil Sie in genau den drei Fällen sozusagen

14:14.470 --> 14:19.670
einen Pfad von einem Element in M1 über einen Y in M2 zu einem Element

14:19.670 --> 14:20.590
in M3 finden.

14:21.110 --> 14:22.210
Das sind die drei Möglichkeiten.

14:23.410 --> 14:23.870
So.

14:25.110 --> 14:27.210
Und das ist einfach Verallgemeinerung der...

14:30.110 --> 14:33.510
Also erstmal syntaktisch sieht es aus wie Komposition von Funktionen.

14:33.550 --> 14:36.410
Und Funktionen kann man ja auch als spezielle Relationen auffassen.

14:37.030 --> 14:39.850
Und die Definition ist auch so, dass Sie, wenn Sie jetzt diese

14:39.850 --> 14:43.850
Definition anwenden auf Abbildungen, Sie kriegen genau das, was wir

14:43.850 --> 14:47.790
bei Abbildungen für den gleichen aussehenden Kringel schon definiert

14:47.790 --> 14:48.050
haben.

14:48.330 --> 14:50.110
Also da widerspricht sich nichts.

14:53.250 --> 14:57.250
Bei Relationen ist es öfter mal so, dass man da nicht schreibt

14:57.250 --> 15:01.230
irgendwie ein Paar XY ist Element der Relation sowieso.

15:01.410 --> 15:05.310
Keiner schreibt 5,7 ist Element der kleinergleich Relation.

15:05.790 --> 15:07.750
Sondern man schreibt einfach 5 kleinergleich 7.

15:08.770 --> 15:10.310
Das nennt man Infix-Schreibweise.

15:10.430 --> 15:11.710
Also das machen wir dann auch ab und zu.

15:11.930 --> 15:15.950
Statt XY ist Element von R schreiben wir einfach XRY.

15:17.150 --> 15:20.650
Und statt YZ ist Element von S schreiben wir YSZ.

15:20.650 --> 15:24.490
Denken Sie an sowas wie kleinergleich oder gleich oder größergleich

15:24.490 --> 15:25.310
oder was auch immer.

15:29.710 --> 15:34.090
Wenn Sie jetzt hier noch eine dritte Relation T hätten zwischen M3 und

15:34.090 --> 15:39.570
M4, dann könnten Sie zwei so Produkte T-Kringel-S-Kringel-R und T

15:39.570 --> 15:43.090
-Kringel -S-Kringel-R angucken, wo die Klammerung unterschiedlich ist.

15:44.000 --> 15:50.010
Und scharfes Hinsehen und langweilige Schreiberei über mehrere Zeilen

15:50.010 --> 15:53.470
zeigt Ihnen dann mehr oder weniger schnell, da kommt das Gleiche raus.

15:53.530 --> 15:58.430
Das ist die gleiche Relation, die gleichen Paare von erster Komponente

15:58.430 --> 16:00.870
in M1, zweiter in M4 sind da drin.

16:02.110 --> 16:07.290
Letzten Endes liegt das daran, dass Sie bei so Aussagen, Aussage 1 und

16:07.290 --> 16:11.710
Aussage 2 und Aussage 3, dass Sie da bei dem und die Klammern hin und

16:11.710 --> 16:12.430
her schieben können.

16:13.790 --> 16:19.190
Das ist wenig aufschlussreich, also es gilt einfach und man kann sich

16:19.190 --> 16:20.670
freuen, dass man das immer machen darf.

16:21.150 --> 16:23.750
Und deswegen braucht man in Wirklichkeit, wenn man da mehrere Faktoren

16:23.750 --> 16:25.250
hat, auch gar keine Klammern hinschreiben.

16:25.350 --> 16:27.090
Es ist sowieso egal, wie man sie schreibt.

16:29.070 --> 16:35.290
Und das heißt dann, diese Operation, die aus zwei Relationen eine

16:35.290 --> 16:38.330
dritte macht, ist assoziativ, wie man sagt.

16:38.330 --> 16:39.730
Sie dürfen Klammern verschieben.

16:41.350 --> 16:44.110
Dann bei Abbildungen hat man auch schon die identische Abbildung, das

16:44.110 --> 16:47.030
ist natürlich insbesondere eine Relation.

16:47.390 --> 16:51.570
Und wir hatten damals, ich hatte zumindest behauptet, identische

16:51.570 --> 16:54.990
Abbildung ist neutrales Element bezüglich Funktionskomposition.

16:55.610 --> 16:59.470
Das ist sogar allgemeiner, wenn Sie das mit irgendeiner Relation

16:59.470 --> 17:02.750
komponieren, da kommt einfach die Relation immer raus.

17:02.750 --> 17:06.670
Also Sie müssen natürlich immer die Identität nehmen mit den richtigen

17:06.670 --> 17:13.450
zwei Mengen, also M1, wenn Sie es vor R haben wollen und M2, wenn Sie

17:13.450 --> 17:14.710
es hinter R haben wollen.

17:16.650 --> 17:20.230
Beweis, Elementare, Sinschreiben, einfach Definition ausschreiben und

17:20.230 --> 17:22.730
dann gucken Sie sich das an und sagen, ach so, ist ja klar.

17:23.550 --> 17:25.190
Also es ist wirklich überhaupt nichts dahinter.

17:25.990 --> 17:26.590
Gut.

17:29.450 --> 17:33.430
Jetzt ein Fall, der häufig vorkommt, den wir gerade auch bei

17:33.430 --> 17:34.690
kontextfreien Grammatiken hatten.

17:36.530 --> 17:41.950
Die beiden Komponenten von den Paaren, die in der Relation sind, die

17:41.950 --> 17:45.530
sind aus der gleichen Menge, also M1 ist gleich M2.

17:46.290 --> 17:51.850
Also man hat dann Relationen von M kreuz M, Teilmengen von M kreuz M

17:51.850 --> 17:57.230
und dann haben Sie die Situation, dass Sie sowas wie R kringel R

17:57.230 --> 18:02.330
hinschreiben dürfen und das ist definiert, weil dann nämlich die erste

18:02.330 --> 18:05.430
Komponente von dem zweiten R ist das gleiche wie die zweite Komponente

18:05.430 --> 18:06.250
von dem ersten R.

18:09.910 --> 18:13.790
Und R kringel R kringel R, dafür schreibt man dann abkürzend R hoch 3

18:13.790 --> 18:16.590
und das definiert man dann wieder wie gehabt.

18:17.010 --> 18:20.910
Also man definiert für binäre Relationen auf einer Menge M, R hoch 0

18:20.910 --> 18:22.230
ist einfach die Identität.

18:22.710 --> 18:27.750
Also Identität, alle Paare, XX für jedes X in M.

18:27.750 --> 18:32.110
Also jedes X steht in Relation zu sich selbst, wie Sie das zum

18:32.110 --> 18:33.630
Beispiel bei kleiner gleich kennen.

18:33.890 --> 18:36.430
Jedes X ist kleiner gleich X, jede natürliche Zahl.

18:37.570 --> 18:42.030
Und höhere Potenzen naheliegend R hoch I plus 1 ist R hoch I kringel

18:42.030 --> 18:42.230
R.

18:46.250 --> 18:49.110
Diese Definition wird Sie, denke ich, nicht mehr besonders verwundern.

18:51.310 --> 18:57.850
Und das ist nichts anderes als das, was wir auch schon letztes Mal

18:57.850 --> 19:01.890
definiert hatten für Ableitungspfeil und dann oben noch ein Exponent

19:01.890 --> 19:04.930
dran mit der Bedeutung in I Ableitungsschritten komme ich von dem

19:04.930 --> 19:05.770
einen zum anderen.

19:06.270 --> 19:07.530
Das ist genau das hier.

19:09.150 --> 19:14.550
Sie kommen in I plus 1 Schritten von X nach Z, wenn Sie in einem

19:14.550 --> 19:19.730
Schritt von X zu einem Y kommen und dann in I Schritten von dem Y zu

19:19.730 --> 19:20.150
dem Z.

19:21.110 --> 19:23.130
Das ist genau das, was wir das letzte Mal hatten.

19:23.870 --> 19:26.210
Und dann hatten wir das letzte Mal definiert, Pfeil mit einem Stern

19:26.210 --> 19:31.310
oben dran als eine Folge von Ableitungsschritten und wie viele ist uns

19:31.310 --> 19:33.790
egal, eine beliebig lange Folge von Ableitungsschritten.

19:34.650 --> 19:37.810
Und das jetzt halt nicht für Ableitung, sondern für beliebige

19:37.810 --> 19:38.530
Relationen.

19:38.630 --> 19:42.450
R mit einem Stern oben dran in der Bedeutung, das ist die große

19:42.450 --> 19:45.190
Vereinigung aller R hoch I für I aus N Null.

19:45.510 --> 19:48.490
Also das ist R hoch 0 vereinigt R hoch 1 vereinigt R hoch 2.

19:50.110 --> 19:54.790
R hoch 0 ist die Identität, deswegen R hoch 1, elementares

19:54.790 --> 19:58.230
Nachrechnen, ist dann einfach R, so wie man das erwartet.

19:58.390 --> 20:02.950
R hoch 1 ist immer R und R hoch 2, R hoch 3 und so weiter.

20:02.950 --> 20:08.790
Die Vereinigung von allem, dafür schreiben wir R-Stern und dieses

20:08.790 --> 20:12.670
Gebilde heißt reflexiv-transitive Hülle von R.

20:14.210 --> 20:14.850
Warum?

20:15.230 --> 20:17.030
Kommt auf der nächsten Folie, meine ich.

20:17.110 --> 20:18.510
Ah, erst mal Beispiele.

20:21.710 --> 20:25.870
Also nehmen Sie als R eine einfache Relation auf den natürlichen

20:25.870 --> 20:29.950
Zahlen, nämlich alle Paare, wo die zweite Komponente genau eins größer

20:29.950 --> 20:30.710
ist als die erste.

20:32.310 --> 20:36.990
Das ist die Relation R, also 0 steht in Relation zu 1, 1 steht in

20:36.990 --> 20:41.950
Relation zu 2, 17 in Relation zu 18, aber nicht 9 in Relation zu 53.

20:43.810 --> 20:45.550
Dann was ist R-Kringel-R?

20:45.690 --> 20:49.210
Das sind also alle Paare N, M mit der Eigenschaft, es gibt ein K,

20:49.350 --> 20:54.730
sodass NK in Relation R steht und das KM auch in Relation R.

20:55.550 --> 20:59.910
Und damit NK in Relation R steht, muss also das K gerade N plus 1

20:59.910 --> 21:00.210
sein.

21:01.730 --> 21:05.830
Und wenn KM in der Relation R steht, dann muss das M gerade K plus 1

21:05.830 --> 21:06.150
sein.

21:07.150 --> 21:11.930
Und mit anderen Worten, das M muss K plus 1 sein, also das M muss N

21:11.930 --> 21:12.890
plus 2 sein.

21:13.210 --> 21:15.910
Also das sind alle Paare N, N plus 2.

21:17.390 --> 21:21.250
Naja, und dann ahnt man schon, also R hoch 0 ist die Identität, das

21:21.250 --> 21:22.450
sind alle Paare N, N.

21:22.590 --> 21:26.310
R hoch 1 ist R, das sind alle Paare N, N plus 1.

21:26.450 --> 21:29.210
R hoch 2 sind alle Paare N, N plus 2.

21:30.330 --> 21:33.930
Und so weiter, wie man leicht nachrechnet, wenn man noch was rechnen

21:33.930 --> 21:34.110
will.

21:34.810 --> 21:38.370
Und das heißt R-Stern, das ist also die Vereinigung von allen diesen

21:38.370 --> 21:42.250
Mengen, da haben Sie dann alle Paare von Zahlen, wo die zweite

21:42.250 --> 21:44.130
Komponente größer gleich der ersten ist.

21:45.910 --> 21:49.830
Also das ist die Menge aller Paare mit N kleiner gleich M.

21:50.210 --> 21:53.610
Das heißt, dieses R-Stern ist einfach die bekannte Kleiner-Gleich

21:53.610 --> 21:56.410
-Relation auf den nicht-negativen ganzen Zahlen.

21:57.810 --> 21:59.850
Wenn man das dann unbedingt so hinschreiben will.

22:02.610 --> 22:07.050
Und jetzt zu diesem R-Stern heißt reflexiv-transitive Hülle.

22:09.690 --> 22:15.290
Also, das liegt daran, dass R-Stern zwei Eigenschaften hat, die man

22:15.290 --> 22:17.370
reflexiv und transitiv nennt.

22:17.870 --> 22:19.790
Wie die definiert sind, gucken wir uns gleich an.

22:22.090 --> 22:24.130
Und, ups, falsch.

22:25.210 --> 22:28.010
Also R-Stern hat diese beiden Eigenschaften.

22:28.930 --> 22:35.030
Und drittens, wenn Sie R haben und das hat noch nicht diese

22:35.030 --> 22:38.630
Eigenschaft und Sie wollen jetzt aber das ein bisschen größer machen,

22:38.730 --> 22:42.130
aber so wenig wie möglich, nur so viel, dass es gerade reflexiv und

22:42.130 --> 22:45.490
transitiv wird, dann kriegen Sie R-Stern.

22:46.530 --> 22:49.470
Also R-Stern ist, wie wir uns gleich überlegen werden, in einem

22:49.470 --> 22:53.750
gewissen Sinne die kleinste Relation, die erstens ganz R enthält, die

22:53.750 --> 22:57.770
Menge der Paare, die schon in R sind, und dann möglichst wenig dazu,

22:57.890 --> 23:00.370
sodass es dann aber reflexiv und transitiv ist.

23:02.210 --> 23:04.310
So, und was heißt das reflexiv und transitiv?

23:04.310 --> 23:09.850
Eine Relation heißt reflexiv, wenn, also kurz gesagt, die Identität

23:09.850 --> 23:11.710
auf der Grundmenge Teilmenge von R ist.

23:11.810 --> 23:16.050
Das heißt, wenn für jedes Element x aus M gilt, x steht in Relation zu

23:16.050 --> 23:16.630
sich selbst.

23:17.350 --> 23:17.910
xRx.

23:18.770 --> 23:20.050
Zum Beispiel bei kleiner gleich.

23:20.430 --> 23:22.650
Jede Zahl ist kleiner gleich sich selbst.

23:24.430 --> 23:27.950
Aber nicht reflexiv ist zum Beispiel echt größer.

23:28.270 --> 23:30.650
Keine Zahl ist echt größer als sie selbst.

23:31.630 --> 23:33.170
Also es gibt auch nicht reflexive.

23:34.330 --> 23:36.270
So, also das ist Reflexivität.

23:36.410 --> 23:38.350
Jedes Element steht in Relation zu sich selber.

23:40.070 --> 23:44.270
Und Transitivität kann man jetzt auch mit Relationen-Kompositionen

23:44.270 --> 23:45.170
einfach hinschreiben.

23:45.390 --> 23:48.850
Transitiv heißt, R-Kringel-R ist Teilmenge von R.

23:50.210 --> 23:51.450
Was heißt das?

23:53.410 --> 23:58.670
Das heißt, jedes Mal, wenn Sie ein x und ein y und ein z haben, sodass

23:58.670 --> 24:04.370
x in Relation zu y steht und y in Relation zu z, dann haben Sie also

24:04.370 --> 24:06.970
so ein paar xz aus R-Kringel-R.

24:07.730 --> 24:09.770
Dann muss das auch schon in R sein.

24:10.990 --> 24:14.650
Also dann muss dieses paar xz auch schon in R sein.

24:14.810 --> 24:19.110
Also wenn x in Relation zu y steht und y in Relation zu z, dann x

24:19.110 --> 24:20.330
steht in Relation zu z.

24:20.890 --> 24:23.570
Zum Beispiel kleiner gleich.

24:24.430 --> 24:29.490
Wenn x kleiner gleich y ist und y kleiner gleich z, dann ist x kleiner

24:29.490 --> 24:30.010
gleich z.

24:30.950 --> 24:34.010
Das ist ein klassisches Beispiel von Transitivität.

24:36.970 --> 24:42.450
Oder bei kontextfreien Grammatiken, wenn Sie aus einem Wort x ein Wort

24:42.450 --> 24:46.790
y ableiten können in irgendeiner Anzahl Schritten und aus y ein Wort z

24:46.790 --> 24:50.230
in irgendeiner Anzahl Schritten, dann können Sie aus x in irgendeiner

24:50.230 --> 24:52.490
Anzahl Schritten, indem Sie erst die von der einen Ableitung machen

24:52.490 --> 24:54.410
und die von der anderen, können Sie das z ableiten.

24:55.430 --> 24:56.310
Ganz naheliegend.

24:57.630 --> 24:59.450
Das ist Transitivität.

25:03.290 --> 25:05.850
Für beliebige Relationen kann man das definieren.

25:06.150 --> 25:09.010
Und Reflexivität bedeutet das eine, Transitivität das andere.

25:09.430 --> 25:11.150
Und das eine geht auch ohne das andere.

25:11.270 --> 25:13.770
Sie können auch Relationen finden, die nur reflexiv sind, nicht

25:13.770 --> 25:16.030
transitiv oder nur transitiv und nicht reflexiv.

25:16.090 --> 25:16.690
Das geht alles.

25:16.690 --> 25:20.090
So und jetzt zu R-Sternen.

25:20.370 --> 25:24.410
Also gegeben eine beliebige Relation R, die ist im Allgemeinen nicht

25:24.410 --> 25:27.070
reflexiv, die ist im Allgemeinen nicht transitiv.

25:27.290 --> 25:28.690
Irgendwas ganz komisches.

25:29.510 --> 25:34.830
Zum Beispiel bei kontextfreien Grammatiken, Sie kommen von einem Wort

25:34.830 --> 25:37.830
mit genau einem Ableitungsschritt zu einem anderen Wort.

25:37.830 --> 25:42.010
Haben Sie eine Relation, die ist im Allgemeinen nicht reflexiv, die

25:42.010 --> 25:43.050
ist nicht transitiv.

25:44.250 --> 25:45.570
Ach, das kommt gleich in der großen Übung.

25:45.570 --> 25:50.850
So, aber jetzt, wenn Sie dann übergehen zu R-Sternen.

25:51.030 --> 25:55.010
Behauptung, egal wie R ist, R-Sternen ist immer reflexiv.

25:55.690 --> 25:56.750
Woran liegt das?

25:57.110 --> 25:59.490
Naja, was ist die Definition von R-Sternen?

25:59.830 --> 26:02.130
Das ist die Vereinigung aller R hoch I.

26:03.090 --> 26:08.470
Das heißt insbesondere R hoch 0 ist Teilmenge von R-Sternen und R hoch

26:08.470 --> 26:10.850
0 ist gerade die Menge aller Paare XX.

26:14.710 --> 26:18.250
Also die Identität ist Teilmenge von R-Sternen und das war gerade

26:18.250 --> 26:20.330
sozusagen die Definition von Reflexivität.

26:20.510 --> 26:22.110
Also das ist offensichtlich der Fall.

26:22.110 --> 26:27.910
Das zweite, das steht hier nur so als Mitteilung, das ist auch wieder

26:27.910 --> 26:30.570
irgendwie ein Induktionsbeweis, kann man nachrechnen.

26:30.910 --> 26:35.830
Es gilt etwas naheliegendes und viele Notationen sind halt so, dass

26:35.830 --> 26:41.030
praktisch fast alles naheliegende richtig ist.

26:41.930 --> 26:48.290
Wenn Sie für eine Relation R, R hoch I und R hoch J zwei so Potenzen

26:48.290 --> 26:55.010
nehmen und dann Kringel, dann haben Sie also R hoch I ist I mal so ein

26:55.010 --> 26:59.250
Faktor R, Kringel, Kringel, Kringel und dann dahinter noch J mal gibt

26:59.250 --> 27:01.350
insgesamt I plus J solche Faktoren.

27:01.670 --> 27:04.530
Also R hoch I, Kringel, R hoch J ist R hoch I plus J.

27:05.110 --> 27:07.850
Können Sie mit Induktion beweisen, wenn Sie wollen.

27:08.530 --> 27:10.370
Das nehmen wir jetzt einfach mal so hin.

27:10.650 --> 27:11.730
Das können Sie glauben.

27:14.930 --> 27:18.230
Dann zu der zweiten Eigenschaft Transitivität.

27:18.330 --> 27:23.510
Behauptung, egal wie R ist, R-Stern ist immer transitiv.

27:24.790 --> 27:26.030
Warum ist das so?

27:26.030 --> 27:34.250
Nehmen Sie an, Sie haben ein Paar XY aus R-Stern und ein Paar YZ aus R

27:34.250 --> 27:34.610
-Stern.

27:35.350 --> 27:39.350
Für Transitivität müssen Sie dann beweisen, das Paar XZ ist auch in R

27:39.350 --> 27:39.750
-Stern.

27:40.810 --> 27:41.870
Warum ist das so?

27:41.870 --> 27:47.170
Wenn XY in R-Stern ist, dann R-Stern ist die Vereinigung der R hoch I.

27:47.770 --> 27:52.970
Also XY muss in einer dieser Relationen R hoch I sein und genauso YZ

27:52.970 --> 27:56.490
muss in einer dieser Relationen R hoch irgendwas sein.

27:57.430 --> 28:00.330
Das muss jetzt nicht der gleiche Exponent I sein, das ist vielleicht

28:00.330 --> 28:01.950
eine andere Zahl J.

28:04.290 --> 28:09.910
Und dann ist aber offensichtlich XY aus R hoch I, YZ aus R hoch J, XZ

28:09.910 --> 28:11.490
aus...

28:12.770 --> 28:17.590
Also eigentlich wäre es besser, wenn hier stünde R hoch J kringel R

28:17.590 --> 28:19.010
hoch I, aber das ist das Gleiche.

28:19.810 --> 28:24.530
Also das ist Element von R hoch I plus J, also auch eine Potenz von R

28:24.530 --> 28:27.490
und das ist natürlich Teil von R-Stern, also dann steht das auch

28:27.490 --> 28:28.110
sofort da.

28:28.110 --> 28:29.750
R ist transitiv.

28:30.310 --> 28:33.550
Denken Sie an die Ableitungsrelationen bei Grammatiken.

28:33.930 --> 28:37.790
I-Schritte und dann J-Schritte macht I plus J-Schritte.

28:38.690 --> 28:41.810
Das ist natürlich auch eine Anzahl Schritte.

28:42.650 --> 28:45.030
So und das Letzte ist, warum heißt das Hülle?

28:46.790 --> 28:49.930
Das ist so in dem Sinne, man macht es nur so ein kleines bisschen

28:49.930 --> 28:54.570
größer, bis man so gerade R eingehüllt hat und so viel dazu, dass das

28:54.570 --> 28:56.190
Ganze reflexiv und transitiv wird.

28:57.070 --> 29:01.950
Also die Behauptung ist, R-Stern ist die kleinste Relation, die

29:01.950 --> 29:07.630
erstens alles aus R enthält, R umfasst, und reflexiv ist und transitiv

29:07.630 --> 29:07.950
ist.

29:09.890 --> 29:17.310
Das R-Stern R enthält ist klar, denn R ist R hoch I und R hoch I ist

29:17.310 --> 29:18.390
Teilmenge von R-Stern.

29:20.090 --> 29:23.050
Dass R-Stern reflexiv und transitiv ist, haben wir uns gerade

29:23.050 --> 29:23.650
überlegt.

29:24.130 --> 29:27.250
Das ist alles schon erledigt oder evident.

29:27.250 --> 29:32.050
Bleibt noch, es ist sozusagen die kleinste solche Relation.

29:32.250 --> 29:39.970
Also Behauptung, wenn Sie irgendeine Relation S haben, die auch alles

29:39.970 --> 29:47.890
aus R enthält und reflexiv ist und transitiv ist, dann nicht nur es

29:47.890 --> 29:52.970
enthält R, sondern sogar das ganze R-Stern, mindestens das, sonst

29:52.970 --> 29:54.210
würde das nicht klappen.

29:56.050 --> 30:01.750
Und das ist das, was man noch beweisen muss, dass R-Stern Teilmenge

30:01.750 --> 30:06.430
von S ist, wenn S R entumfasst und reflexiv und transitiv ist.

30:06.890 --> 30:07.950
Und wie beweist man das?

30:08.070 --> 30:11.810
Man beweist einfach, dass jedes R hoch I Teilmenge von S ist, dann die

30:11.810 --> 30:13.610
Vereinigung von allen R hoch I auch.

30:14.070 --> 30:17.410
Und wie beweist man, dass jedes R hoch I Teilmenge von S ist?

30:17.570 --> 30:18.590
Naja, Induktion.

30:19.070 --> 30:22.170
Und jetzt habe ich mich wirklich schon beschränkt, also den Kern des

30:22.170 --> 30:24.350
Induktionsschrittes nur noch hinzuschreiben.

30:25.830 --> 30:29.990
Was ist... da muss man dann zeigen, also angenommen R hoch I ist

30:29.990 --> 30:33.550
Teilmenge von S, R hoch I plus 1 ist auch Teilmenge von S.

30:34.550 --> 30:35.990
Na, was ist R hoch I plus 1?

30:36.090 --> 30:37.530
Das ist R hoch I Kringel R.

30:39.050 --> 30:43.110
Jetzt ist R hoch I ein Teil von S und R ist ein Teil von S.

30:43.830 --> 30:47.030
Und wenn Sie jetzt bei beiden Relationen auf einmal mehr Möglichkeiten

30:47.030 --> 30:51.250
haben, was Sie dann kriegen in der Komposition, sind höchstens mehr

30:51.250 --> 30:53.290
Paare, aber sicher nicht weniger.

30:53.830 --> 30:57.230
Das heißt, R hoch I Kringel R ist dann auch sicher Teilmenge von S

30:57.230 --> 30:57.850
Kringel S.

30:58.690 --> 31:02.830
Ach so, und da S ja transitiv ist, ist das Teilmenge von S.

31:02.910 --> 31:05.290
Na, steht schon da, R hoch I plus 1 ist Teilmenge von S.

31:09.650 --> 31:14.510
Also R-Stern ist auch wirklich die einfachste Möglichkeit, nur ganz

31:14.510 --> 31:19.050
wenig zu R, also wenig in Anführungszeichen, zu R dazu zu machen, bis

31:19.050 --> 31:20.770
es reflexiv und transitiv ist.

31:21.170 --> 31:25.550
Und wenn R selber schon reflexiv und transitiv ist und Sie bilden R

31:25.550 --> 31:28.490
-Stern, das können Sie natürlich immer noch hinschreiben und

31:28.490 --> 31:30.770
ausrechnen, wenn Sie wollen, was rauskommt, ist halt R.

31:31.810 --> 31:32.930
Nichts Größeres.

31:34.290 --> 31:34.850
Gut.

31:38.180 --> 31:45.060
Also soviel nochmal zu Produktenpotenzen von Relationen und reflexiv

31:45.060 --> 31:48.900
-transitive Hülle, das ist auch was, was man häufig betrachten will

31:48.900 --> 31:51.760
und wir werden auch in einem späteren Kapitel auf ein algorithmisches

31:51.760 --> 31:56.280
Problem zu sprechen kommen, wo es genau wieder darum geht.

31:56.280 --> 31:59.300
Also eine Relation können Sie sich ja vorstellen, als Sie haben so

31:59.300 --> 32:04.620
Pfeile, die Punkte verbinden und dann hat man etwas, das heißt

32:04.620 --> 32:10.000
gerichteter Graph und dann stellen Sie sich vor, dass die Punkte sind

32:10.000 --> 32:12.640
irgendwelche Stellen auf dem Stadtplan und die Pfeile sind

32:12.640 --> 32:13.480
Einbahnstraßen.

32:13.560 --> 32:15.580
Dann kann man sich fragen, komme ich von einem Punkt zum anderen,

32:15.720 --> 32:17.820
indem ich immer nur entlang der Einbahnstraßen fahre.

32:19.340 --> 32:21.000
So was werden wir uns später angucken.

32:22.400 --> 32:22.680
Gut.

32:22.680 --> 32:23.720
So.

32:25.200 --> 32:30.840
Und im letzten Teil dieses Kapitels aber jetzt nochmal ein Beispiel,

32:31.740 --> 32:34.920
wo Sie sehen sollen, also es gibt nicht nur ganz banale und ganz

32:34.920 --> 32:38.100
langweilige Beweise, es gibt auch mal ein bisschen was

32:38.100 --> 32:39.080
Komplizierteres.

32:40.720 --> 32:45.120
Der Beweis, also der wesentliche Beweisteil, den ich Ihnen zeigen

32:45.120 --> 32:49.420
werde, ist etwas, da würde man nicht erwarten, dass Sie auf sowas von

32:49.420 --> 32:51.860
selber kommen, also haben Sie jetzt nicht davor Angst, dass Sie jetzt

32:51.860 --> 32:53.860
in Zukunft solche Beweise machen.

32:56.680 --> 32:58.860
Das ist nicht der Fall, aber ich will Ihnen einfach mal so ein

32:58.860 --> 33:00.860
bisschen zeigen, es gibt halt auch noch andere Dinge.

33:02.080 --> 33:07.120
Und es gibt auch in dem Beweis dann wieder so ein, zwei elementare

33:07.120 --> 33:10.180
Vorgehensweisen, die Ihnen immer wieder über den Weg laufen werden.

33:10.320 --> 33:11.740
Immer wieder, immer wieder, immer wieder.

33:12.700 --> 33:12.980
Gut.

33:15.040 --> 33:19.300
Also, wir wollen sehen, es gibt Sprachen, die sind so in

33:19.300 --> 33:22.180
Anführungszeichen kompliziert, dass man sie nicht mit einer

33:22.180 --> 33:23.760
kontextfreien Grammatik erzeugen kann.

33:25.660 --> 33:26.820
Zu schwierig dafür.

33:28.700 --> 33:34.420
Hier ist die formale Sprache, also Sie werden gleich in der Übung dann

33:34.420 --> 33:35.300
auch noch eine andere sehen.

33:36.440 --> 33:38.320
Hier ist so eine formale Sprache.

33:39.560 --> 33:43.620
Die Wörter, die dazugehören, bestehen aus kleinen a's, b's und c's.

33:44.840 --> 33:48.040
Und die Wörter, die in der Sprache drin sind, haben alle die Bauart,

33:48.340 --> 33:51.640
in dem Wort kommt genau ein c vor, genau eins.

33:52.840 --> 33:53.900
Nicht mehr und nicht weniger.

33:53.900 --> 33:58.840
Vor dem c steht irgendein Wort aus a's und b's, nennen wir das Wort

33:58.840 --> 33:59.520
kleine v.

34:00.440 --> 34:05.080
Und das Wort, das vor dem c steht, genau das gleiche Wort muss eins zu

34:05.080 --> 34:06.820
eins hinter dem c auch nochmal stehen.

34:08.440 --> 34:11.920
Das sind die Wörter, die dazugehören und alles andere, was nicht von

34:11.920 --> 34:14.280
der Bauart ist, gehört nicht zu der formalen Sprache.

34:15.600 --> 34:19.220
Also durch ein c klar getrennt zweimal das gleiche Wort aus a's und

34:19.220 --> 34:19.540
b's.

34:20.740 --> 34:24.200
Also alle Wörter der Form v, c, v und v ist aus a, b, s.

34:25.460 --> 34:28.460
Also die Wörter, die dazugehören, enthalten alle mindestens einen

34:28.460 --> 34:29.580
Buchstaben, nämlich das c.

34:32.520 --> 34:38.680
Also Beispiele a, a, b, a vor dem c und a, a, b, a hinter dem c oder

34:38.680 --> 34:43.080
a, c, a oder b hoch 3, c, b hoch 3, das gehört alles dazu.

34:43.640 --> 34:46.160
Und einfach nur c meinetwegen gehört auch dazu.

34:46.380 --> 34:48.080
Leeres Wort davor, leeres Wort dahinter.

34:50.720 --> 34:54.820
Und nicht zu der formalen Sprache gehört alles, was anders gebaut ist.

34:54.960 --> 35:00.520
Also vor dem c ein Wort a, a, b, a und hinter dem c aber ein anderes

35:00.520 --> 35:02.220
a, a, b, b.

35:02.580 --> 35:05.300
Das dahinter hört mit b auf, das davor hört mit a auf.

35:05.660 --> 35:06.140
Verboten.

35:07.160 --> 35:10.620
Unterschiedlich viele Buchstaben vor und hinter dem c ist sicherlich

35:10.620 --> 35:11.380
auch falsch.

35:11.760 --> 35:15.160
Das sind dann auch verschiedene Wörter, weil die Längen verschieden

35:15.160 --> 35:15.340
sind.

35:15.340 --> 35:19.340
Wenn Sie mehrere cs in dem Wort haben, ist auch verkehrt.

35:20.660 --> 35:24.460
Egal, ob davor und hinter den cs das gleiche steht oder nicht, es darf

35:24.460 --> 35:25.720
nur ein c da stehen.

35:27.420 --> 35:30.520
Und wenn gar kein c da steht, ist es auch verkehrt.

35:31.260 --> 35:34.460
Es muss genau ein c sein, genau eins.

35:34.780 --> 35:41.440
Also sowas wie a, a, b, a, a, b ist syntaktisch falsch, weil das c

35:41.440 --> 35:41.820
fehlt.

35:43.120 --> 35:46.860
Auch wenn Sie da vielleicht naheliegend eins einfügen könnten, aber es

35:46.860 --> 35:47.540
steht da halt nicht.

35:49.120 --> 35:51.040
Also das ist die formale Sprache.

35:51.140 --> 35:52.600
Um die Wörter geht es uns, die da oben.

35:53.580 --> 35:56.920
Und Behauptung, wenn Sie irgendeine kontextfreie Grammatik

35:56.920 --> 36:02.480
hinschreiben, da können Sie sich Mühe geben, so viel Sie wollen.

36:03.900 --> 36:08.060
Egal, welche Grammatik Sie sich ausdenken, Sie werden nie genau, genau

36:08.060 --> 36:11.720
die Wörter erzeugen, die zu der formalen Sprache gehören.

36:12.900 --> 36:13.920
Nie genau die.

36:17.320 --> 36:19.460
Sie wird zu wenig erzeugen oder zu viel.

36:19.940 --> 36:22.940
Also wird manche Wörter nicht erzeugen, obwohl sie dazugehören.

36:23.260 --> 36:25.620
Wird Wörter erzeugen, die nicht dazugehören oder vielleicht sogar

36:25.620 --> 36:26.040
beides.

36:29.300 --> 36:31.020
Irgendetwas wird verkehrt sein, immer.

36:32.140 --> 36:33.460
Das wollen wir jetzt beweisen.

36:35.260 --> 36:38.820
Da müssen wir also argumentieren über alle kontextfreien Grammatiken,

36:38.920 --> 36:39.920
davon gibt es unendlich viele.

36:40.700 --> 36:43.940
Wir müssen für diese allen beweisen, es klappt nicht.

36:46.360 --> 36:49.540
Das ist schwieriger als für irgendeine zu beweisen, es gibt eine, die

36:49.540 --> 36:49.900
es tut.

36:50.000 --> 36:52.040
Da müssen Sie nur die richtige nehmen, für eine was arbeiten.

36:52.360 --> 36:53.740
Hier müssen wir für alle was tun.

36:53.940 --> 36:54.280
Also gut.

36:56.040 --> 37:00.820
Ein Hilfsmittel, das klingt für Sie hoffentlich plausibel, das ist

37:00.820 --> 37:01.180
auch so.

37:01.420 --> 37:04.080
Das werden wir einfach benutzen, ohne dass ich jetzt hier groß rum

37:04.080 --> 37:05.440
beweise, warum das so ist.

37:07.740 --> 37:11.960
Stellen Sie sich vor, Sie haben eine Grammatik, die erzeugt

37:11.960 --> 37:13.840
irgendwelche Wörter, aber nicht das leere Wort.

37:15.300 --> 37:18.460
Zum Beispiel unsere formale Sprache erzeugt nicht das leere Wort, weil

37:18.460 --> 37:20.580
im leeren Wort nicht genau ein C vorkommt.

37:22.040 --> 37:25.520
Und wenn Sie das leere Wort bei den erzeugten Wörtern nicht brauchen,

37:25.820 --> 37:29.280
mit Teilung, dann brauchen Sie es auch in den Produktionen nicht als

37:29.280 --> 37:29.900
rechte Seite.

37:31.100 --> 37:31.960
Das ist so.

37:33.240 --> 37:36.440
Also wenn Sie eine Grammatik haben, wo das leere Wort vielleicht noch

37:36.440 --> 37:39.060
auf der rechten Seite irgendwo vorkommt, aber Sie müssen das leere

37:39.060 --> 37:41.960
Wort gar nicht erzeugen können mit der Grammatik, dann können Sie die

37:41.960 --> 37:44.640
Produktionen ersetzen durch andere, wo das leere Wort weg ist.

37:46.020 --> 37:50.100
Und so eine Grammatik, wo das leere Wort nirgends mehr vorkommt, so

37:50.100 --> 37:51.560
eine Grammatik heißt epsilonfrei.

37:51.560 --> 37:56.960
Und weil uns eine Sprache interessiert, die das leere Wort nicht

37:56.960 --> 38:01.420
enthält, können wir uns auch einfach darauf beschränken, nur für

38:01.420 --> 38:05.060
solche kontextfreien Grammatiken, die epsilonfrei sind, zu beweisen,

38:05.400 --> 38:06.440
die machen es nicht.

38:08.240 --> 38:11.840
Oder anders gesagt, jede epsilonfreie, kontextfreie Grammatik und nur

38:11.840 --> 38:14.460
die müssen wir anschauen, erzeugt etwas Verkehrtes, erzeugt eine

38:14.460 --> 38:17.320
formale Sprache, ungleich diesem LVV.

38:18.200 --> 38:20.680
Haben wir also schon mal die Menge der Gebilde, die wir angucken

38:20.680 --> 38:22.300
müssen, so ein bisschen eingeschränkt.

38:22.820 --> 38:25.160
Die Grammatiken, wo das leere Wort irgendwo vorkommt, müssen wir gar

38:25.160 --> 38:25.700
nicht anschauen.

38:27.180 --> 38:30.080
Es reicht, sich die anzugucken und zu sehen, da geht es nicht.

38:32.280 --> 38:39.360
Und jetzt kommt eine Aussage, die ist etwas länger, aber inhaltlich

38:39.360 --> 38:41.580
auch jetzt nicht so verblüffend.

38:43.520 --> 38:47.520
Also jetzt, wir beschränken uns auf epsilonfreie, kontextfreie

38:47.520 --> 38:47.900
Grammatik.

38:48.000 --> 38:50.100
Das leere Wort taucht in keiner Produktion auf.

38:51.700 --> 38:55.900
Das heißt, die rechten Seiten haben alle mindestens Länge 1, da steht

38:55.900 --> 38:59.840
mindestens ein Symbol oder zwei oder drei und es gibt endlich viele

38:59.840 --> 39:00.340
Produktionen.

39:00.420 --> 39:04.020
Es gibt eine maximale Länge, also rechte Seiten sind alle höchstens 5

39:04.020 --> 39:05.860
lang oder 7 oder wie viel auch immer.

39:06.520 --> 39:09.840
Also nennen wir diese maximale Länge von irgendwelchen rechten Seiten

39:09.840 --> 39:11.520
bei den Produktionen mal kleine L.

39:14.120 --> 39:18.060
Behauptung, jetzt wenn Sie hier mal in die Mitte gucken, wenn Sie aus

39:18.060 --> 39:22.560
einem Nicht-Terminalsymbol X ein Wort ableiten können, in beliebig

39:22.560 --> 39:28.860
vielen Schritten, der Form U, W, U', alles Terminalsymbole.

39:31.020 --> 39:36.220
U und U' interessieren uns nicht, aber wenn Sie da so ein Teilwort W

39:36.220 --> 39:42.140
haben, das mindestens die Länge, das länger ist als dieses L hoch K,

39:42.360 --> 39:48.000
für irgendeine Zahl K, dann, wenn Sie sich den Ableitungsbaum hinmalen

39:48.000 --> 39:53.920
und von der Wurzel, also des Ableitungsbaums, der hier mit dem X

39:53.920 --> 39:59.000
startet, angucken, die Pfade zu den einzelnen Terminalsymbolen in

39:59.000 --> 40:00.840
diesem langen Teilwort W.

40:02.020 --> 40:09.760
Dann auf diesen Pfaden, da gibt es mindestens einen Pfad, auf dem Sie

40:09.760 --> 40:19.160
bei K plus 1 Nicht-Terminalsymbolen vorbeikommen, wo mindestens zwei

40:19.160 --> 40:20.000
Kanten weggehen.

40:23.270 --> 40:24.950
Stellen Sie sich vor, das wäre nicht so.

40:25.110 --> 40:30.830
Also bei jedem Nicht-Terminalsymbol, es würden höchstens K-Kanten

40:30.830 --> 40:31.310
weggehen.

40:31.670 --> 40:35.270
Also auf dem ersten Niveau, es könnten höchstens K-Symbole entstehen.

40:35.270 --> 40:38.330
Auf dem nächsten Niveau, aus jedem von dem K wieder K, dann wären Sie

40:38.330 --> 40:39.270
bei K-Quadrat.

40:39.730 --> 40:42.230
Auf dem nächsten Niveau dann bei K hoch 3.

40:45.370 --> 40:51.290
Und wenn Sie da nur... Entschuldigung, L.

40:51.770 --> 40:53.350
Falsch, jetzt habe ich alles falsch gesagt.

40:53.450 --> 40:57.030
Also nochmal, beim ersten Verzweigen höchstens L-Symbole, dann auch

40:57.030 --> 41:00.870
von jedem von diesem L, jeweils L, sind Sie bei L-Quadrat, L hoch 3, L

41:00.870 --> 41:01.210
hoch 4.

41:01.210 --> 41:05.590
Wenn Sie das nur K mal machen können, kommen Sie höchstens auf L hoch

41:05.590 --> 41:05.910
K.

41:06.790 --> 41:09.550
Und wenn das Wort, das Sie ableiten wollen, aber länger ist als L hoch

41:09.550 --> 41:14.250
K, dann brauchen Sie mindestens einmal K plus 1 Nicht-Terminalsymbole.

41:19.400 --> 41:24.540
Mindestens K plus 1 mal ein Nicht-Terminalsymbol, wo mindestens zwei

41:24.540 --> 41:25.280
Kanten weggehen.

41:25.380 --> 41:29.020
Es kann auch so Produktionen geben, wo Sie einfach X durch Y ersetzen,

41:29.100 --> 41:30.400
das ist alles völlig uninteressant.

41:34.740 --> 41:39.720
Jetzt nehmen wir diesen Ableitungs... Achso, das wollen wir jetzt

41:39.720 --> 41:40.900
vielleicht doch ein bisschen beweisen.

41:42.520 --> 41:45.220
Stellen Sie sich vor, Sie haben den ganzen Ableitungsbaum, da steht

41:45.220 --> 41:50.120
also irgendwo in der Mitte dieses lange Wort W, Länge größer L hoch K

41:50.120 --> 41:51.880
und vielleicht links noch was, rechts noch was.

41:52.660 --> 41:54.000
Das links und rechts machen Sie weg.

41:54.780 --> 41:57.380
Das interessiert Sie gar nicht, die Äste dahin schneiden Sie alle ab.

41:57.700 --> 42:00.020
Das ist dann kein Ableitungsbaum mehr, aber immer noch ein Baum.

42:01.400 --> 42:05.920
Dann, wenn Sie so Ersetzungen haben, X durch Y, Y durch Z, ein Nicht

42:05.920 --> 42:10.280
-Terminalsymbol durchs andere, das radieren Sie alles auch weg, malen

42:10.280 --> 42:12.100
einfach eine Kante hin in den Baum.

42:13.560 --> 42:16.380
Dann bleiben nur noch die Stellen, wo Sie ein Nicht-Terminalsymbol

42:16.380 --> 42:19.920
haben, wo mindestens zwei Kanten weggehen oder drei oder vier oder L.

42:21.020 --> 42:24.120
Und unten an den Blättern stehen die Symbole von dem Wort W.

42:24.540 --> 42:29.680
Und jetzt die Argumentation von eben, nach K-Niveaus können Sie

42:29.680 --> 42:31.780
höchstens bei L hoch K-Symbolen sein.

42:31.940 --> 42:35.460
Und wenn Sie aber mehr als L hoch K brauchen, kommen Sie nicht mit K

42:35.460 --> 42:36.100
-Niveaus aus.

42:36.220 --> 42:39.980
Da müssen mindestens einmal irgendwo K plus 1 Symbole gewesen sein.

42:39.980 --> 42:43.160
Ja, dann höre ich, glaube ich, an dieser Stelle auf.

42:44.040 --> 42:47.760
Und das werden wir dann das nächste Mal benutzen, um zu zeigen, also

42:47.760 --> 42:51.740
LVV kann man mit solchen Grammatiken nicht erzeugen.

42:52.400 --> 42:52.800
Dankeschön.

42:52.800 --> 42:58.020
So, schönen guten Morgen zusammen, herzlich willkommen zur Übung.

43:00.580 --> 43:02.220
Ja, da gibt es noch ein bisschen Unruhe.

43:04.580 --> 43:11.920
So, heute werden wir weiter mit dem Thema der Vorlesung machen, also

43:11.920 --> 43:13.360
Kortexfreie Grammatiken.

43:14.600 --> 43:19.220
Und am Ende gibt es noch ein bisschen was zu Relationen.

43:23.560 --> 43:29.260
Was ist die Motivation dahinter, also was für Grammatiken?

43:29.740 --> 43:35.620
Also wir haben im Laufe der Vorlesung alle diese Begriffe

43:35.620 --> 43:42.560
kennengelernt, einmal Zeichen, Alphabete, Wörter, Sprachen und jetzt

43:42.560 --> 43:43.280
Grammatiken.

43:45.840 --> 43:51.660
Das war ursprünglich konzipiert, also menschliche Sprache mathematisch

43:51.660 --> 43:52.240
zu modellieren.

43:52.560 --> 43:59.240
Also ich hatte irgendwelche Wörter und zum Beispiel die Sprache

43:59.240 --> 44:01.600
Deutsch hat irgendwelche gültigen Wörter.

44:01.600 --> 44:10.900
Und mit Grammatik kann ich fast wie Subjekt, Verb, Objekt und so

44:10.900 --> 44:11.640
weiter modellieren.

44:11.920 --> 44:17.280
Also ein Satz besteht aus einem Subjekt, einem Verb und einem Objekt.

44:19.320 --> 44:25.320
Und gegebenenfalls besteht das Subjekt aus einem Namen und ein paar

44:25.320 --> 44:31.300
Adjektiven und Artikeln da vorne und vielleicht gibt es mehrere Sätze

44:31.300 --> 44:33.620
in der Mitte zum Beispiel.

44:42.440 --> 44:47.160
Und die kontextfreie Grammatik ist dann in diesem Kontext entstanden

44:47.160 --> 44:51.280
und später hat man festgestellt, das kann man doch benutzen, um

44:51.280 --> 44:53.620
Sprachen für Maschinen zu modellieren.

44:53.620 --> 44:58.200
Also dass wir Syntax zum Beispiel von Programmiersprachen durch

44:58.200 --> 45:02.960
Grammatiken beschreiben, aber nicht nur Programmiersprachen, die

45:02.960 --> 45:09.340
sagen, was der Rechner tun soll, sondern die kann man auch anwenden,

45:09.740 --> 45:16.940
um zum Beispiel sowas wie HTML zu spezifizieren, was keine

45:16.940 --> 45:19.560
Programmiersprache ist, sondern nur eine Sprache, die von einem

45:19.560 --> 45:21.620
Rechner verarbeitet wird.

45:21.620 --> 45:25.300
Deswegen Computersprachen am Megabyte und nicht nur

45:25.300 --> 45:26.120
Programmiersprachen.

45:27.480 --> 45:31.640
Ich kann die Grammatik nicht ganz kompakt, ganz einfach, die ganze

45:31.640 --> 45:34.780
Syntax von einer solchen Sprache beschreiben.

45:38.380 --> 45:42.360
Und wie gesagt, was ist diese kontextfreie Grammatik?

45:42.440 --> 45:45.620
Wir haben zwei Typen von Symbolen.

45:45.680 --> 45:50.500
Wir haben einmal die Nicht-Terminale und die Terminalsymbole und die

45:50.500 --> 45:53.220
Grammatik verarbeitet nur die Nicht-Terminale und die Terminale sollen

45:53.220 --> 45:54.620
nicht weiter verändert werden.

45:57.180 --> 46:02.880
Terminalsymbole sind zum Beispiel die Symbole des Vorortes, die ich am

46:02.880 --> 46:03.960
Ende haben will.

46:05.240 --> 46:08.760
Nicht-Terminalsymbole sind einfach Hilfsmittel, die sagen, da kann ich

46:08.760 --> 46:10.060
weiter Dinge einsetzen.

46:12.080 --> 46:16.740
Und was mir das sagt, was ich dann für Nicht-Terminale einsetzen kann,

46:16.800 --> 46:17.920
sind diese Produktionen.

46:18.460 --> 46:22.820
Das ist eine ähnliche Menge von gewissen Regeln, die ich beachten

46:22.820 --> 46:23.120
soll.

46:25.880 --> 46:30.260
Und wir fangen nicht bei irgendwelchen Mustern von Nicht-Terminalen

46:30.260 --> 46:33.120
an, sondern wir fangen immer bei diesen Staatssymbolen.

46:33.120 --> 46:33.920
Das ist alles eindeutig.

46:34.160 --> 46:37.740
Ich nehme ein Staatssymbol und dann habe ich Produktion und dann kann

46:37.740 --> 46:43.340
ich dieses Staatssymbol weiter verarbeiten, bis ich nach einer

46:43.340 --> 46:50.220
ähnlichen Anzahl von Veränderungen zu einem Vorort komme.

46:52.460 --> 46:55.440
Das ist so ein Berechnungsmodell auch.

46:55.620 --> 47:01.120
Also ich habe ein Zeichen und dann habe ich Regeln angewählt auf

47:01.120 --> 47:04.280
dieses Zeichen und dann habe ich Symbole weiterverarbeitet, bis ich am

47:04.280 --> 47:06.100
Ende zu einem Ergebnis gekommen bin.

47:06.100 --> 47:09.440
Im Endeffekt das Wort, das produziert wird.

47:11.400 --> 47:16.560
Und diese Grammatiken heißen kontextfrei, weil die Produktion eben von

47:16.560 --> 47:20.940
dieser Form wieder abgeschrieben ist.

47:20.940 --> 47:25.180
Also dass ich links ein Nicht-Terminal habe und rechts ein Wort aus

47:25.180 --> 47:27.220
Nicht -Terminale oder auch Terminale.

47:27.940 --> 47:31.400
Aber leeres Wort ist auch erlaubt, deswegen schreibe ich.

47:35.940 --> 47:41.800
Und wie gesagt, links darf nur ein Nicht-Terminal stehen, deswegen

47:41.800 --> 47:42.740
heißt das kontextfrei.

47:43.800 --> 47:48.140
Ich werde noch später ein bisschen was dazu sagen.

47:49.840 --> 47:55.280
Vielleicht erstmal ein Beispiel, wie ich ein Wort ableite mit einer

47:55.280 --> 47:56.660
Grammatik.

47:57.120 --> 47:57.460
Also z.B.

47:57.540 --> 48:02.040
habe ich eine Grammatik D mit Nicht-Terminale S, X, Y und mein

48:02.040 --> 48:06.560
Terminalsymbol, also mein Zielalphabet ist A, B.

48:07.440 --> 48:12.260
Und dann habe ich eine gewisse Anzahl von Produktionsregeln und ich

48:12.260 --> 48:14.000
fange immer beim Startsymbol an.

48:15.000 --> 48:19.180
Und dann schaue ich mal, was in den Produktionsregeln da steht.

48:19.420 --> 48:21.860
Also da kann ich von S, X, Y ableiten.

48:22.320 --> 48:23.680
Ja, dann mache ich das.

48:25.580 --> 48:29.420
Dann habe ich zwei Nicht-Terminale da, also ich kann entweder X oder Y

48:29.420 --> 48:30.340
weiter ableiten.

48:32.160 --> 48:33.100
Ich nehme mal X.

48:33.800 --> 48:37.740
Dann kann ich von X ein A produzieren und dann habe ich das Wort AY.

48:39.180 --> 48:41.860
Jetzt kann ich mit dem Mal nichts weiter tun.

48:42.020 --> 48:45.460
Das ist ein Terminalsymbol, das muss da verändert bleiben.

48:45.620 --> 48:49.660
Dann muss ich was mit Y machen und dann kann ich z.B.

48:50.560 --> 48:59.020
die Regel für Y anwenden und das weiter noch ein paar Mal anwenden.

48:59.020 --> 49:05.140
Und am Ende muss ich irgendwann zum Ende kommen.

49:06.880 --> 49:14.020
Und dann wende ich diese letzte Regel, das Y produziert.

49:14.480 --> 49:15.720
Und dann bin ich zum Ende.

49:17.040 --> 49:23.140
Und dann habe ich keine Nicht-Terminalsymbole mehr und dann habe ich

49:23.140 --> 49:27.380
ein Wort im Alphabet T.

49:33.560 --> 49:38.320
Wenn ich alle Wörter betrachte, die ich in dieser Weise erzeugen kann,

49:38.980 --> 49:42.120
dann bildet das eine Menge von Wörtern und eine Menge von Wörtern ist

49:42.120 --> 49:42.900
einfach eine Sprache.

49:42.900 --> 49:48.640
Und diese Sprache ist dann die Sprache, die von G erzeugt wird.

49:49.160 --> 49:49.860
So nennen wir das.

49:51.060 --> 49:56.280
Und die enthält eben jedes Wort, das ich durch mehrfache Anwendung

49:56.280 --> 50:01.340
dieser Produktionsregeln dann von S aus ableiten kann.

50:03.520 --> 50:08.600
Es gibt die zwei Symbole, also dieser Doppelfeier, einzelne und

50:08.600 --> 50:14.060
Doppelfeierhochstern, also das sind dann zwei unterschiedliche Dinge,

50:14.420 --> 50:18.640
die in der Relation darauf kommen für später noch mal.

50:20.200 --> 50:26.320
So, dann kann ich mit meiner Grammatik Wörter ableiten, viele, viele

50:26.320 --> 50:26.660
Wörter.

50:27.540 --> 50:33.340
Aber manchmal, wenn ich so langes Wort aus Nicht-Terminalen und

50:33.340 --> 50:37.340
Terminale habe, dann habe ich vielleicht die Übersicht verloren, was

50:37.340 --> 50:39.260
alles von Wo und Schan ist.

50:39.260 --> 50:44.240
Und deswegen gibt es auch diese Schreibweise für eine Ableitung, dass

50:44.240 --> 50:47.900
man alles mit einem Baum schön darstellt.

50:48.560 --> 50:51.880
Und dann ist ganz deutlich zu erkennen, also oben habe ich dieses

50:51.880 --> 50:56.380
Startsymbol und dann habe ich eine Produktionsregel angewendet und

50:56.380 --> 51:00.540
daraus A, B und ein S in der Mitte abgeleitet und so weiter nach

51:00.540 --> 51:00.740
unten.

51:00.740 --> 51:05.080
Und dann kann ich leicht nachvollziehen, welche Regeln denn wo

51:05.080 --> 51:09.980
angefeuert wurden, um das Wort zu erzeugen.

51:12.260 --> 51:17.160
Vorteil daran, ich kann diese Struktur dann einfacher mit einem

51:17.160 --> 51:20.760
Augenblick auf einmal nachvollziehen.

51:21.420 --> 51:25.240
Nachteil, ich kann das Wort, das am Ende herauskommt, nicht so ganz

51:25.240 --> 51:26.100
deutlich lesen.

51:26.100 --> 51:30.780
Dann muss ich irgendwo links anfangen, dann steht ein A, dann muss ich

51:30.780 --> 51:33.500
weiter schreiben, dann ist es weiter ein A.

51:36.220 --> 51:41.520
Wobei, wenn man nur das Produktionsregel nacheinander aufschreibt,

51:41.720 --> 51:43.380
dann steht am Ende das Wort da.

51:45.200 --> 51:50.380
Das Ergebnis ist leichter zu lesen, aber der Rechnungsweg ist dafür

51:50.380 --> 51:52.900
schwer zu verstehen.

51:54.980 --> 52:02.780
So, dann ist immer schön, sich die Beispiele anzuschauen.

52:04.080 --> 52:11.440
Wie kann ich zum Beispiel überhaupt die Sprachen A, Stern und die

52:11.440 --> 52:13.720
leere Menge erzeugen mit der Grammatik?

52:13.800 --> 52:14.520
Ja, das geht.

52:15.660 --> 52:16.620
Wie geht das?

52:21.300 --> 52:27.200
Nehmen wir zuerst A hoch Stern, dann muss ich alle Wörter erzeugen und

52:27.200 --> 52:29.820
dann muss ich beim Startsymbol anfangen.

52:29.820 --> 52:37.560
Das erste Symbol kann ein A oder ein B sein oder ich kann das leere

52:37.560 --> 52:38.340
Wort produzieren.

52:39.140 --> 52:44.360
Und wenn ich ein A oder ein B produziert habe, dann kann das nächste

52:44.360 --> 52:47.760
Symbol wieder ein A, B oder das leere Wort.

52:49.260 --> 52:55.740
Das leere Wort kann danach kommen und so kann man das aufschreiben.

52:56.500 --> 53:01.700
Also, ich kann entweder gar kein Symbol da haben, ein A oder ein B und

53:01.700 --> 53:03.940
dann war ich weiter rechts.

53:05.620 --> 53:07.020
So geht das.

53:08.960 --> 53:16.500
Umgekehrt, wenn ich die leere Menge haben will, dann fange ich beim

53:16.500 --> 53:21.900
Startsymbol an und da kann ich keine Wörter produzieren.

53:22.720 --> 53:27.060
Wenn ich ein Wort produzieren würde, auch wenn das das leere Wort sein

53:27.060 --> 53:32.800
würde, dann würde das in der Sprache gestrich sein und das will ich

53:32.800 --> 53:33.000
nicht.

53:33.000 --> 53:38.760
Dann muss ich dafür sorgen, dass wenn ich Produktionsregeln auf das

53:38.760 --> 53:40.280
Startsymbol usw.

53:40.520 --> 53:44.240
anwende, dass ich nie ein Wort aus dem Terminal erzeuge.

53:47.180 --> 53:48.180
Wie macht man das?

53:49.380 --> 53:51.720
Zum Beispiel, man macht aus dem S wieder ein S.

53:52.080 --> 53:56.400
Dann habe ich ein S zu einem S gemacht und weiter und weiter und

53:56.400 --> 53:58.020
weiter und dann komme ich nie zum Ende.

53:58.160 --> 53:59.600
Das ist wie eine Enddurchschreife.

54:01.820 --> 54:05.920
Diese Enddurchschreife, da kann ich keine Wörter aus dem

54:05.920 --> 54:07.760
Terminalsymbol produzieren.

54:09.280 --> 54:13.240
Und die Alternative könnte man auch, wenn man für die

54:13.240 --> 54:16.660
Produktionsregeln die leere Menge nimmt, dann kann ich auch erst gar

54:16.660 --> 54:17.440
nichts produzieren.

54:18.200 --> 54:21.120
Dann kann ich persönlich kein Wort produzieren.

54:22.820 --> 54:27.880
Beide Alternativen erfüllen den Zweck, die leere Menge zu erzeugen.

54:28.260 --> 54:32.660
Dann kommen wir mal zurück zu dem Begriff kontextfrei.

54:34.580 --> 54:38.060
Wir haben kontextfreie Grammatik definiert.

54:38.220 --> 54:42.200
Man hat auch Grammatiken, die nicht kontextfrei sind.

54:42.920 --> 54:47.040
Da gibt es eine spezielle Eigenschaft, die diese Grammatiken haben.

54:47.040 --> 54:51.840
Und das ist eben diese Form der Produktionsregeln.

54:52.040 --> 54:55.420
Ich habe links ein Nicht-Terminal stehen und nur das.

54:58.100 --> 55:02.100
Und dieses einzige Nicht-Terminal, da gibt es keinen Kontext

55:02.100 --> 55:03.080
drumherum.

55:03.240 --> 55:04.740
Deswegen heißt es kontextfrei.

55:05.940 --> 55:08.960
Ich nehme einfach ein Nicht-Terminal und ersetze das.

55:09.980 --> 55:14.080
Ich kann nicht sehen, ob vor dem Nicht-Terminal ein A oder ein B

55:14.080 --> 55:15.260
stehen würde zum Beispiel.

55:16.640 --> 55:18.380
Um anderes zu erzeugen.

55:19.160 --> 55:22.220
Aber es gibt auch Grammatiken, die nicht kontextfrei sind.

55:22.380 --> 55:24.820
Es gibt z.B.

55:24.980 --> 55:26.740
die kontextsensitive Grammatik.

55:26.800 --> 55:29.220
Da kann ich z.B.

55:29.320 --> 55:33.560
schauen, ob vor dem X ein A oder ein B steht und dann anderes tun.

55:33.860 --> 55:34.620
In den zwei Fällen.

55:35.080 --> 55:43.980
Dann habe ich etwas viel mehr komplexer durch diesen Kontext

55:43.980 --> 55:44.500
einbezogen.

55:45.480 --> 55:52.040
Und man kann auch zeigen, dass es mehr Sprachen erzeugt als

55:52.040 --> 55:53.420
kontextfreie Grammatiken.

55:53.840 --> 55:59.840
Dass es kontextsensitive Grammatiken gibt, die von kontextsensitive

55:59.840 --> 56:03.040
Grammatiken erzeugt werden, die aber nicht von einer kontextfreien

56:03.040 --> 56:04.400
Grammatik erzeugt werden können.

56:05.360 --> 56:14.280
Und diese Überlegungen, da gibt es, da können Sie mehr lernen in der

56:14.280 --> 56:17.200
Vorlesung, theoretische Grundlagen der Informatik, z.B.

56:17.320 --> 56:19.840
im dritten Semester Bachelor Informatik.

56:22.980 --> 56:26.840
Aber für die meisten Zwecke erfüllen die die kontextfreien Grammatiken

56:26.840 --> 56:30.880
was geleistet werden, sondern z.B.

56:31.460 --> 56:42.420
die ganzen Grammiersprachen, die Sie vernünftig schreiben werden.

56:42.860 --> 56:50.340
Und die Sprachen wie HTML, XML, CSS, was auch immer Sie mit dem

56:50.340 --> 56:53.800
Rechner verarbeiten, die können alle mit kontextfreien Grammatiken

56:53.800 --> 56:57.280
definiert oder erzeugt werden.

56:58.320 --> 57:03.100
Machen Sie sich keine Gedanken darüber, ich sollte vielleicht eine

57:03.100 --> 57:05.000
mächtigere Grammatik definieren.

57:05.140 --> 57:05.800
Das ist nicht so.

57:05.880 --> 57:08.560
Es ist auch gut, dass die Grammatik nicht komplex ist.

57:08.900 --> 57:19.760
Also dann kann ich Algorithmen, also kann ich was auf diese

57:19.760 --> 57:25.560
Grammatiken anwenden, was viel effizienter ist, als wenn ich, oder

57:25.560 --> 57:28.720
überhaupt unmöglich wäre, wenn ich nur eine kontextsensitive Grammatik

57:28.720 --> 57:29.260
da hatte.

57:29.980 --> 57:33.380
Die kontextfreie Grammatik ist ganz simpel, dann kann ich die auch

57:33.380 --> 57:35.580
simpler verarbeiten, wenn ich z.B.

57:35.920 --> 57:39.900
schauen will, ob ein gewisses Wort von dieser Grammatik erzeugt wird

57:39.900 --> 57:40.420
oder nicht.

57:41.300 --> 57:44.080
Wenn das kontextsensitiv wäre, dann müsste ich viel, viel mehr

57:44.080 --> 57:46.520
einbeziehen, das wäre ganz komplexer.

57:47.340 --> 57:50.120
Deswegen ist das auch ein Vorteil, dass es nicht kompliziert ist.

57:52.420 --> 57:55.820
So, dann jetzt zum Wort kompliziert.

57:55.980 --> 57:59.940
Dann schauen wir uns doch mal ein bisschen mehr komplizierte Beispiele

57:59.940 --> 58:05.500
für kontextfreie Grammatiken und die davon erzeugten Sprachen.

58:06.980 --> 58:10.560
Also, ich glaube, es war in der ersten oder zweiten Übung, da habe ich

58:10.560 --> 58:19.360
fast eine umgekehrte Reihenfolge des Zeichens erzählt.

58:22.240 --> 58:24.780
Und hier haben wir den Begriff Palindrom.

58:24.860 --> 58:25.580
Was ist ein Palindrom?

58:25.640 --> 58:30.480
Das ist einfach ein Wort, das von links nach rechts gelesen wird.

58:31.220 --> 58:34.140
Das Gleiche gibt es von rechts nach links gelesen.

58:34.780 --> 58:37.080
Zum Beispiel Anauto und Rallye-Fahrer.

58:38.960 --> 58:43.420
Und die Definition ist ein bisschen komplizierter.

58:43.640 --> 58:46.560
Da muss ich mir die Indexe schauen.

58:46.920 --> 58:50.400
Also, da steht zum Beispiel, setzen wir mal für i 0.

58:50.520 --> 58:51.340
Dann habe ich an der 0.

58:51.480 --> 58:57.520
Stelle, was an der Stelle Länge des Wortes minus 1 steht, das ist das

58:57.520 --> 58:58.200
letzte Zeichen.

58:58.200 --> 59:03.100
Und dann, wenn ich hier erhöhe, dann mache ich weiter zu der Mitte.

59:03.340 --> 59:04.700
Dann bin ich vielleicht in der Mitte gekommen.

59:05.820 --> 59:08.400
Dann müssen sich alle Is vergleichen.

59:10.520 --> 59:12.460
Deswegen diese Definition mit dem Is.

59:12.860 --> 59:17.080
Aber das ist, was Sie erfahren, der Palindrom.

59:20.580 --> 59:23.380
Und Wörter mit dieser Eigenschaft, das sind Wörter.

59:23.560 --> 59:25.720
Und eine Menge von Wörtern ist eine Sprache, deswegen ist das eine

59:25.720 --> 59:26.120
Sprache.

59:28.000 --> 59:31.640
Gibt es denn eine kontextfreie Grammatik, die diese Sprache erzeugt?

59:31.700 --> 59:32.560
Ja, das gibt es.

59:33.000 --> 59:34.180
Aber wie kommt man drauf?

59:38.480 --> 59:44.660
Wir machen genau diese Überlegung mit dem i gleich 0.

59:45.860 --> 59:48.140
Und dann vergleichen wir die Zeichen.

59:48.800 --> 59:52.240
Und dann, was in der Mitte steht, da machen wir rekursiv weiter.

59:53.520 --> 59:54.060
Wie ist das?

59:54.060 --> 59:56.560
Also in der Mitte kann das Wort leer sein.

59:56.760 --> 59:59.620
Das ist per Definition ein Palindrom.

01:00:00.320 --> 01:00:02.360
Das könnte man natürlich anders definiert haben.

01:00:03.660 --> 01:00:06.240
Aber ich finde, das soll ein Palindrom sein.

01:00:06.780 --> 01:00:10.920
Also von links nach rechts gelesen, da wird kein Zeichen gelesen.

01:00:11.040 --> 01:00:12.040
Das muss das gleich sein.

01:00:15.200 --> 01:00:17.600
Dann gibt es noch den anderen Randfall.

01:00:17.740 --> 01:00:23.420
Ich habe nur ein Symbol da, das ist von links nach rechts gelesen.

01:00:23.420 --> 01:00:24.880
Das gleiche Wort.

01:00:26.260 --> 01:00:28.640
Und wenn ich mehrere Zeichen habe, dann mache ich diesen Vergleich.

01:00:28.920 --> 01:00:31.400
Also ich nehme das erste Symbol und das letzte Symbol.

01:00:31.760 --> 01:00:32.720
Die sollen gleich sein.

01:00:33.020 --> 01:00:35.060
Und was in der Mitte steht, soll wieder ein Palindrom sein.

01:00:35.300 --> 01:00:38.800
Also du musst weiter die Zeichen alle übereinstimmen.

01:00:39.540 --> 01:00:43.040
Wenn ich immer linkshäußere und rechtshäußere Zeichen nehme.

01:00:44.840 --> 01:00:48.840
Und mit dieser Idee kann man eine Grammatik bauen.

01:00:50.480 --> 01:00:50.960
Wie?

01:00:50.960 --> 01:00:56.240
Also ich erzeuge einfach an den Rändern gleiche Zeichen.

01:00:56.900 --> 01:00:59.420
Und in der Mitte mache ich weiter mit dem erzeugenden Palindrom.

01:00:59.940 --> 01:01:04.260
Dann komme ich zum Beispiel zu dem, was da unten steht.

01:01:04.800 --> 01:01:12.240
Also da habe ich die zwei Randfälle, leeres Wort und einziges Symbol

01:01:12.240 --> 01:01:13.940
in Betracht gezogen.

01:01:14.160 --> 01:01:17.440
Die einzelnen dann behandeln.

01:01:17.440 --> 01:01:28.580
Und dann habe ich für die zwei rechten Regeln diese Symbole links und

01:01:28.580 --> 01:01:29.620
rechts müssen gleich sein.

01:01:29.720 --> 01:01:31.640
Und in der Mitte soll wieder ein Palindrom entstehen.

01:01:32.240 --> 01:01:33.620
Dann komme ich zu sowas.

01:01:37.160 --> 01:01:39.800
Aber es gibt auch Wörter, die nicht Palindrome sind.

01:01:40.880 --> 01:01:45.100
Und das kann auch von einer kontrastfreien Grammatik erzeugt werden.

01:01:45.220 --> 01:01:45.900
Wie geht das denn?

01:01:45.900 --> 01:01:51.580
Also wir machen uns wieder die Überlegung, wann das nicht ein Nicht

01:01:51.580 --> 01:01:52.360
-Palindrom ist.

01:01:53.080 --> 01:02:00.440
Ja, also da führt der Epsilon, das Wort, das einzigen Symbol A oder B.

01:02:00.620 --> 01:02:05.600
Die drei Wörter sind Palindrome und die können in dieser Sprache nicht

01:02:05.600 --> 01:02:05.880
sein.

01:02:06.120 --> 01:02:09.960
Da muss ich die zuerst mal weglassen.

01:02:10.100 --> 01:02:12.400
Deswegen muss ich zumindest Linke 2 haben.

01:02:12.400 --> 01:02:17.940
Da gibt es nur diese drei Wörter, die Länge echt kleiner als 2 haben.

01:02:20.900 --> 01:02:29.280
Und dann mache ich wieder diese Geschichte, links und rechts zu

01:02:29.280 --> 01:02:29.740
vergleichen.

01:02:29.900 --> 01:02:33.600
Also entweder sind sie ungleich, dann habe ich keinen Palindrom da.

01:02:34.960 --> 01:02:36.680
Automatisch, weil die ungleich sind.

01:02:37.120 --> 01:02:41.000
Oder die können vielleicht gleich sein, aber was in der Mitte steht,

01:02:41.000 --> 01:02:43.240
dann soll bitte kein Palindrom sein.

01:02:46.020 --> 01:02:47.440
Es gibt zwei Fälle.

01:02:48.400 --> 01:02:53.240
Und dann kommen wir zu einer Grammatik.

01:02:53.360 --> 01:02:56.480
Wir erzeugen einfach links und rechts verschiedene Symbole.

01:02:56.800 --> 01:02:58.700
Und wir sorgen dafür, dass wir...

01:03:01.540 --> 01:03:05.800
Wir erzeugen links und rechts unterschiedliche Symbole.

01:03:05.800 --> 01:03:09.340
Dann soll in der Mitte etwas Beliebiges stehen, aus A, B.

01:03:10.220 --> 01:03:11.060
Also aus Stern.

01:03:11.300 --> 01:03:12.800
Dafür haben wir schon eine Grammatik.

01:03:12.940 --> 01:03:18.600
Wir können einfach nehmen, was das macht.

01:03:18.720 --> 01:03:20.120
Das ist dieser U-Teil unten.

01:03:20.600 --> 01:03:21.960
Das erzeugt das A-Stern.

01:03:22.420 --> 01:03:24.000
Das hatten wir schon vorgesehen.

01:03:26.260 --> 01:03:30.220
Und dann sorge ich dafür, dass dieses S dann links und rechts

01:03:30.220 --> 01:03:31.320
verschiedene Symbole erzeugt.

01:03:31.420 --> 01:03:32.620
Und in der Mitte passt das A auf Stern.

01:03:32.620 --> 01:03:38.940
Oder es kann ein Symbol links und rechts gleiche Symbole erzeugen,

01:03:39.500 --> 01:03:42.520
aber in der Mitte soll wieder ein Nicht-Palindrom stehen.

01:03:42.720 --> 01:03:49.200
Dann muss ich wieder zu S zurückkehren, was dann die Geschichte von

01:03:49.200 --> 01:03:50.320
vornherein weitermacht.

01:03:52.080 --> 01:03:58.420
Und hier habe ich dafür gesorgt, dass keine Wörter der Linke echt

01:03:58.420 --> 01:04:03.020
kleiner als zwei erzeugt werden, weil rechts von dem S stehen nur

01:04:03.020 --> 01:04:06.140
Produktionsregeln, die zumindest zwei Terminalsymbole haben.

01:04:06.600 --> 01:04:10.920
Dann kann ich überhaupt keine Wörter erzeugen, die die Linke echt

01:04:10.920 --> 01:04:11.700
kleiner als zwei haben.

01:04:15.650 --> 01:04:20.450
Dann habe ich viel über Sprachen geredet, die von kontextfreien

01:04:20.450 --> 01:04:21.570
Grammatiken erzeugt werden.

01:04:21.670 --> 01:04:23.710
Die nennt man auch kontextfrei.

01:04:24.150 --> 01:04:25.030
Also etwas anderes.

01:04:25.590 --> 01:04:26.310
Was denn sonst?

01:04:31.470 --> 01:04:36.050
Es kann sein, dass eine Sprache eben nicht von einer kontextfreien

01:04:36.050 --> 01:04:37.070
Grammatik erzeugt wird.

01:04:37.230 --> 01:04:39.070
Nicht jede Sprache ist kontextfrei.

01:04:39.230 --> 01:04:40.510
Das habe ich schon angedeutet.

01:04:41.550 --> 01:04:45.770
Und zum Beispiel, in der Vorlesung haben Sie gesehen, Herr Walsch hat

01:04:45.770 --> 01:04:49.530
sogar einen Beweis, oder war in der Mitte von einem Beweis, ich weiß

01:04:49.530 --> 01:04:55.070
nicht, ob er zum Ende gekommen ist, für eine Sprache, die nicht

01:04:55.070 --> 01:04:57.690
kontextfrei ist, das ist diese LVV.

01:04:57.950 --> 01:05:03.150
Also ich habe ein Wort, V, und am Ende wieder das Wort zwei Mal.

01:05:04.590 --> 01:05:07.410
Die kann man nicht mit kontextfreien Grammatiken erzeugen.

01:05:07.830 --> 01:05:10.750
Und hier bringe ich ein anderes Beispiel, aber leider kein Beweis, das

01:05:10.750 --> 01:05:12.330
ist ein bisschen zu kompliziert jetzt.

01:05:13.130 --> 01:05:16.910
Und ich würde nicht viel an der Stelle bringen.

01:05:18.710 --> 01:05:23.470
Also das ist eine Sprache, die As, Bs und Cs hat.

01:05:23.850 --> 01:05:28.890
Und die Anzahl der As, Bs und Cs ist gleich.

01:05:32.290 --> 01:05:34.210
Oder auch das leere Wort ist da.

01:05:35.990 --> 01:05:36.750
Leeres Wort.

01:05:37.250 --> 01:05:40.570
A, B, C oder zwei Mal das A, zwei Mal das B, zwei Mal das C und so

01:05:40.570 --> 01:05:40.790
weiter.

01:05:41.730 --> 01:05:50.690
Ja, wieder die Anmerkung, Beweis gibt es vermutlich in der Vorlesung.

01:05:52.830 --> 01:05:57.950
Hier an der Stelle zu kompliziert, würde ich sagen.

01:05:59.890 --> 01:06:03.050
Aber wir können damit schon einiges machen.

01:06:03.050 --> 01:06:12.810
Zum Beispiel habe ich, wenn ich zwei kontextfreie Grammatiken habe,

01:06:13.570 --> 01:06:18.070
kann ich mir überlegen, ob die Vereinigung davon dann auch kontextfrei

01:06:18.070 --> 01:06:18.350
ist.

01:06:19.370 --> 01:06:20.150
Und das ist sie.

01:06:24.590 --> 01:06:25.550
Warum?

01:06:25.550 --> 01:06:31.070
Ich habe Grammatiken für L1 und L2, und dann soll ich eine Grammatik

01:06:31.070 --> 01:06:34.350
für die Vereinigung konstruieren.

01:06:36.330 --> 01:06:42.350
Ja, also habe ich G1 und G2, die erzeugen jeweils L1 und L2.

01:06:43.590 --> 01:06:49.150
Und wir nehmen einfach an, dass diese Nicht-Terminalsymbole der

01:06:49.150 --> 01:06:52.070
jeweiligen Grammatiken gleich sind.

01:06:52.310 --> 01:06:57.450
Also ich kann lieber, also zum Beispiel, dass das gleiche S für G1 und

01:06:57.450 --> 01:06:59.130
G2 dastehen würde.

01:07:00.110 --> 01:07:03.630
Dann wäre es ein bisschen komisch, wenn ich alle Produktionsregeln

01:07:03.630 --> 01:07:07.150
vereinige und dann selbst kann ich was in der Grammatik G1 machen oder

01:07:07.150 --> 01:07:08.290
was in der Grammatik G2.

01:07:08.410 --> 01:07:10.390
Es ist nicht eindeutig, wie das alles zusammenpasst.

01:07:11.070 --> 01:07:14.110
Dann habe ich das einfach verboten.

01:07:14.230 --> 01:07:23.130
Ich kann einfach die Symbole jeweils verändern, dass die alle gut

01:07:23.130 --> 01:07:23.790
getrennt sind.

01:07:24.190 --> 01:07:25.090
Und dann kann ich das machen.

01:07:25.650 --> 01:07:28.810
Und dann als Grammatik für die Vereinigung, dann nehme ich die

01:07:28.810 --> 01:07:33.270
Vereinigung der zwei Grammatiken.

01:07:34.470 --> 01:07:38.630
Also ich nehme die Nicht-Terminalsymbole aus G1 und G2 und auch mein

01:07:38.630 --> 01:07:39.490
Startsymbol.

01:07:40.850 --> 01:07:46.850
Das bitte ich schon nicht, dass es in den jeweiligen Grammatiken

01:07:46.850 --> 01:07:48.910
stehen sollte.

01:07:50.630 --> 01:07:53.610
Und für die Terminalsymbole muss ich die auch vereinigen.

01:07:53.610 --> 01:07:57.190
Und als Produktionsregeln nehme ich einfach alle Produktionsregeln der

01:07:57.190 --> 01:08:04.010
Grammatik G1 und G2 und auch ein Startsymbol, was entweder zu G1 oder

01:08:04.010 --> 01:08:04.790
G2 geht.

01:08:07.950 --> 01:08:13.950
Also intuitiv kann ich entweder was in L1 erzeugen, dem ich zu der

01:08:13.950 --> 01:08:17.670
Grammatik G1 gehe oder ich kann was in L2 erzeugen, dem ich zu dem

01:08:17.670 --> 01:08:19.250
Startsymbol der Grammatik G2 gehe.

01:08:22.190 --> 01:08:31.090
Aber man sollte sich auch Gedanken machen, dass das wirklich diese

01:08:31.090 --> 01:08:31.990
Sprache erzeugt.

01:08:32.430 --> 01:08:35.530
Dann machen wir doch mal einen Beweis dafür.

01:08:36.810 --> 01:08:41.450
Ich habe diese Grammatik G gegeben und ich will zeigen, dass die davon

01:08:41.450 --> 01:08:45.550
erzeugte Sprache dann gleich diese Vereinigung der zwei Sprachen L1

01:08:45.550 --> 01:08:46.350
und L2 ist.

01:08:46.350 --> 01:08:49.730
Dann habe ich wieder Gleichung von Mengen.

01:08:49.830 --> 01:08:53.710
Das habe ich schon in der ersten Übung angedeutet.

01:08:54.590 --> 01:08:56.750
Beweis dafür einfach die zwei Inklusionen.

01:08:57.650 --> 01:09:01.790
Also dann nehme ich einfach die Asynclusion und ich sage zuerst, dass

01:09:01.790 --> 01:09:05.610
alle Wörter, die von G erzeugt werden, daneben diese Vereinigung sind.

01:09:06.410 --> 01:09:10.350
Das ist der einfache Teil.

01:09:11.450 --> 01:09:15.390
Dann nehme ich einfach ein Wort, das in LGL ist.

01:09:16.810 --> 01:09:19.590
Dann zeige ich, dass das in der Vereinigung liegt.

01:09:20.310 --> 01:09:23.490
Wenn das ein Wort in LGL ist, dann wird das von S produziert.

01:09:24.230 --> 01:09:26.610
Und S hat nur zwei Produktionsregeln.

01:09:26.790 --> 01:09:28.750
Also ich kann entweder S1 oder S2 produzieren.

01:09:29.610 --> 01:09:35.230
Ich muss dann entweder durch S1 zu W gekommen sein oder durch S2.

01:09:36.210 --> 01:09:41.250
Also ich muss entweder durch die Grammatik G1 oder durch die Grammatik

01:09:41.250 --> 01:09:46.570
G2 zu W gekommen sein und dann muss W in einer der zwei Sprachen

01:09:46.570 --> 01:09:46.830
liegen.

01:09:48.790 --> 01:09:49.230
Muss sein.

01:09:51.410 --> 01:09:58.290
Umgekehrt, also wenn ich zeigen will, dass die Vereinigung in LGL ist,

01:09:58.730 --> 01:10:03.850
dann muss ich nicht unbedingt ein Wort aus der Vereinigung nehmen und

01:10:03.850 --> 01:10:06.990
dann sagen, dass es in LGL ist, sondern ich kann zeigen, dass wenn ich

01:10:06.990 --> 01:10:11.450
ein Wort aus L1 nehme, dass es in LGL ist und dass ein Wort aus L2

01:10:11.450 --> 01:10:15.890
auch in LGL ist, dann habe ich gezeigt, dass die Vereinigung in LGL

01:10:15.890 --> 01:10:16.150
ist.

01:10:16.410 --> 01:10:19.810
Also ein Wort in der Vereinigung muss in einer der zwei Sprachen

01:10:19.810 --> 01:10:20.070
liegen.

01:10:22.390 --> 01:10:23.990
Das ist einfacher zu zeigen.

01:10:25.890 --> 01:10:29.610
Und hier nehme ich das L1.

01:10:30.310 --> 01:10:36.910
Also wenn ein Wort von der Grammatik G1 erzeugt wird, dann muss das

01:10:36.910 --> 01:10:38.190
auch aus S1 erzeugt sein.

01:10:38.830 --> 01:10:43.070
Also das Stahlsymbol von der Grammatik G1 ist S1 und S1 produziert

01:10:43.070 --> 01:10:43.510
dieses W.

01:10:43.910 --> 01:10:47.910
Also damit kann ich auch aus S1 das S1 produzieren und dann das W.

01:10:49.170 --> 01:10:55.910
Dann muss das W in der Sprache der Grammatik G auch liegen.

01:10:57.250 --> 01:11:04.610
Und wenn ich dieses Stück da einfach 1 durch 2 ersetze, dann klappt

01:11:04.610 --> 01:11:05.590
das Argument genauso.

01:11:06.530 --> 01:11:10.170
Deswegen ist die andere Inklusion auch analog und dann habe ich

01:11:10.170 --> 01:11:13.690
gezeigt, dass die zwei Sprachen gleich sind.

01:11:18.870 --> 01:11:25.190
Umgekehrt, ein bisschen erstaunlich, aber wenn ich die zwei Sprachen

01:11:25.190 --> 01:11:30.830
schneide, also wenn ich mir den Schnitt davon betrachte, dann sind die

01:11:30.830 --> 01:11:32.670
nicht unbedingt mehr kontextfrei.

01:11:33.430 --> 01:11:36.570
Die Vereinigung geht, aber der Schnitt ist kompliziert.

01:11:39.090 --> 01:11:40.290
Warum ist das so?

01:11:42.470 --> 01:11:50.710
Zum Beispiel, ich kann eine Sprache L1 und L2 nehmen, die kontextfrei

01:11:50.710 --> 01:11:55.330
sind und die miteinander schneiden und ich will haben, dass der

01:11:55.330 --> 01:11:56.890
Schnitt nicht kontextfrei ist.

01:11:57.390 --> 01:12:00.810
Dann kann ich zum Beispiel nehmen, was ich schon weiß, was nicht

01:12:00.810 --> 01:12:05.590
kontextfrei ist, hier in dem Fall, das ist A hoch N, B hoch N, C hoch

01:12:05.590 --> 01:12:05.830
N.

01:12:08.090 --> 01:12:14.150
Und für L1 nehme ich die Sprache mit gleicher Anzahl von As und Bs und

01:12:14.150 --> 01:12:18.610
dann am Ende steht irgendwelche Anzahl von Cs, beliebig.

01:12:20.470 --> 01:12:26.790
Man kann das auch als A hoch N, B hoch N, C hoch K, wo in K natürliche

01:12:26.790 --> 01:12:27.850
Zahlen oder die Null sind.

01:12:28.550 --> 01:12:33.410
Oder ich kann auch das als Konkatenation von A hoch N, B hoch N und am

01:12:33.410 --> 01:12:36.710
Ende beliebig viele Cs als C hoch Stern schreiben.

01:12:37.870 --> 01:12:42.710
Für die Sprache L2 nehme ich beliebig viele As am Anfang und dann so

01:12:42.710 --> 01:12:46.290
viele Bs wie Cs am rechten Ende.

01:12:49.550 --> 01:12:53.050
Ja, dann gebe ich, warum sind die dann kontextfrei?

01:12:53.210 --> 01:12:55.490
Ich kann die miteinander kontextfreie Grammatik erzeugen.

01:12:58.790 --> 01:12:59.350
Entschuldigung.

01:13:01.570 --> 01:13:06.090
Zum Beispiel L1 kann ich dadurch erzeugen, dass ich zum Beispiel das

01:13:06.090 --> 01:13:11.090
Startsymbol in zwei Symbole aufspeitele, also X und Y und Y soll

01:13:11.090 --> 01:13:16.050
dieses C hoch Sternteil erzeugen und X erzeugt dieses A hoch N, B hoch

01:13:16.050 --> 01:13:16.590
N -Teil.

01:13:17.930 --> 01:13:23.710
Also X macht einfach links ein A und rechts ein B und so weiter, bis

01:13:23.710 --> 01:13:27.610
ich vielleicht irgendwie das leere Wort produziere.

01:13:29.990 --> 01:13:31.970
Und für L2 geht das genauso.

01:13:32.150 --> 01:13:38.670
Ich muss dann die Definition von X und Y anpassen und die zwei

01:13:38.670 --> 01:13:39.990
Sprachen sind kontextfrei.

01:13:40.330 --> 01:13:45.970
Also ich kann die mit dieser Grammatik erzeugen, aber der Schritt ist,

01:13:46.630 --> 01:13:49.170
ich weiß, dass es nicht kontextfrei ist, deswegen kann der Schritt

01:13:49.170 --> 01:13:50.170
nicht kontextfrei sein.

01:13:52.290 --> 01:13:56.450
Natürlich noch zu beweisen, dass diese Sprache nicht kontextfrei ist.

01:13:58.470 --> 01:13:59.770
Ja, das war eine andere Geschichte.

01:14:00.450 --> 01:14:04.850
Aber so ist das dann.

01:14:06.110 --> 01:14:09.210
Dann bin ich zum Schluss zum Thema kontextfreie Grammatiken.

01:14:09.710 --> 01:14:12.590
Wir machen den Übergang zu Relationen.

01:14:13.810 --> 01:14:16.890
Also warum schaue ich mir wieder Relationen an der Stelle?

01:14:16.890 --> 01:14:23.010
Wir hatten diese Doppelfall kennengelernt.

01:14:23.190 --> 01:14:24.230
Das ist so wie eine Relation.

01:14:25.090 --> 01:14:32.390
Also links steht ein Wort aus Nicht-Terminale und Terminale und rechts

01:14:32.390 --> 01:14:34.450
steht wieder ein anderes Wort da.

01:14:35.830 --> 01:14:39.510
Und die werden zusammen kombiniert mit dieser Ableitungsregel der

01:14:39.510 --> 01:14:40.010
Grammatik.

01:14:41.010 --> 01:14:49.010
Und diese Relation, damit ich vernünftig sagen kann, was von der

01:14:49.010 --> 01:14:56.010
Grammatik erzeugte Sprache ist, dann muss ich mir anschauen, wie ich

01:14:56.010 --> 01:15:03.770
ausdrücke, also die Mehrfachanwendung dieser Relation ausdrücken kann.

01:15:04.530 --> 01:15:09.630
Und das haben wir so gemacht, dass wir zuerst dieses Produkt von

01:15:09.630 --> 01:15:10.730
Mengen definiert haben.

01:15:11.250 --> 01:15:13.630
Entschuldigung, Produkt von Relationen.

01:15:14.130 --> 01:15:16.090
Also ich habe irgendwelche Relationen R und S.

01:15:17.450 --> 01:15:21.770
Und damit die zusammenpassen, dann soll auch...

01:15:27.970 --> 01:15:34.090
Hier habe ich das M2 und hier muss das M2 gleich sein.

01:15:39.440 --> 01:15:43.650
Das muss gleich sein, sonst kann ich das nicht vernünftig definieren.

01:15:45.930 --> 01:15:52.940
Dann S nach R, das sind die Paaren X, Z, wo ich ein Y in diesem M2

01:15:52.940 --> 01:15:59.480
finden kann, das sowohl in Relation mit X und Z stehen, aber die

01:15:59.480 --> 01:16:01.680
Ordnung ist auch wichtig.

01:16:02.000 --> 01:16:04.980
Also X in Relation mit Y.

01:16:05.820 --> 01:16:09.240
Man kann nicht unbedingt die vertauschen, das ist nicht unbedingt

01:16:09.240 --> 01:16:09.800
komputativ.

01:16:12.320 --> 01:16:16.160
Aber X steht in Relation mit Y und dieses Y steht in Relation mit Z.

01:16:16.300 --> 01:16:17.660
Das verbindet X und Z.

01:16:18.540 --> 01:16:24.260
Und in dem Fall, dass R und S Abbildungen sind, also Abbildungen sind

01:16:24.260 --> 01:16:29.960
auch Relationen, ist es einfach diese Komposition von Funktionen.

01:16:30.600 --> 01:16:34.820
Also einfach mehrfaches Anwenden einer Abbildung.

01:16:36.200 --> 01:16:43.180
Und zum Beispiel für die Produkte hier, kleiner gleich, mit sich

01:16:43.180 --> 01:16:48.880
selber verknüpfen, ich kann einfach für Y das X nehmen.

01:16:49.320 --> 01:16:54.300
Dann steht, X ist kleiner gleich X und X ist kleiner gleich Z.

01:16:58.990 --> 01:17:01.210
Dann habe ich wieder die kleiner gleich Relation.

01:17:01.710 --> 01:17:05.570
Wenn ich kleiner gleich und größer gleich damit verknüpfe, dann steht,

01:17:06.550 --> 01:17:10.470
X ist größer gleich Y und Y ist kleiner gleich Z.

01:17:10.850 --> 01:17:14.770
Also dafür kann ich zum Beispiel 0 wählen und dann sind alle Zahlen X,

01:17:14.850 --> 01:17:17.370
Z in dem Produkt erhalten.

01:17:20.050 --> 01:17:25.210
Also es kommt darauf an, es kann vieles rauskommen bei diesem Produkt.

01:17:27.370 --> 01:17:29.150
Aber das hat gewisse Eigenschaften.

01:17:29.150 --> 01:17:30.490
Zum Beispiel ist das so assoziativ.

01:17:31.010 --> 01:17:35.810
Es ist egal, welche Reihenfolge ich die Relationen miteinander

01:17:35.810 --> 01:17:38.470
verknüpfe, es kommt immer das gleiche Ergebnis raus.

01:17:39.830 --> 01:17:43.210
Das haben wir schon kennengelernt.

01:17:44.830 --> 01:17:48.090
Was ich noch mit diesem Produkt machen kann, sind natürlich Potenzen.

01:17:49.550 --> 01:17:53.470
Genauso wie ich Zahlenpotenzen definieren kann, also Multiplikationen.

01:17:55.970 --> 01:18:00.830
Was soll dann das Vernünftige für eine Potenz Null sein?

01:18:00.910 --> 01:18:03.090
Das ist einfach die Identität auf der Menge.

01:18:06.850 --> 01:18:14.650
Und wenn ich Potenz I plus 1 habe, dann ist das einfach rekursiv

01:18:14.650 --> 01:18:15.070
definiert.

01:18:15.330 --> 01:18:18.430
Also ich nehme einfach von vorne her auch I und dann verknüpfe ich das

01:18:18.430 --> 01:18:19.190
einmal mit.

01:18:22.130 --> 01:18:28.690
Da unten ein Beispiel für eine Relation, die etwas Interessantes durch

01:18:28.690 --> 01:18:29.870
diese Potenzen erzeugt.

01:18:29.970 --> 01:18:31.810
Ich nenne das einfach D1.

01:18:31.810 --> 01:18:36.670
Das sind die Paare von natürlichen Zahlen, auch die Null.

01:18:39.570 --> 01:18:43.490
Der Unterschied der Zahlen ist kleiner gleich 1.

01:18:44.530 --> 01:18:53.130
Da steht zum Beispiel 1 in Relation mit 0 und mit 1 und mit 2.

01:18:53.530 --> 01:18:59.330
Der Unterschied ist kleiner gleich 1, aber nicht 1 in Relation mit 3.

01:19:01.070 --> 01:19:04.710
Und wenn ich das auf 0 nehme, dann kommt die Identität raus.

01:19:05.810 --> 01:19:13.490
Wenn ich das auf 2, also Produkt, nehme, dann habe ich die Zahl Y,

01:19:16.350 --> 01:19:24.050
also den Abstand von nichts, der kleiner gleich 1 hat, und von diesem

01:19:24.050 --> 01:19:26.510
Z auch Abstand kleiner gleich Z hat.

01:19:26.510 --> 01:19:31.130
Das ist so in der Mitte von den X und Z.

01:19:31.790 --> 01:19:35.210
Und dann was rauskommt, sind einfach die Zahlen, die Abstand 2 haben.

01:19:35.510 --> 01:19:38.990
Also zum Beispiel 1 und 3, weil die 2 in der Mitte steht.

01:19:39.290 --> 01:19:43.290
Also 1 hat Abstand 1 zu 2 und 2 hat Abstand 1 zu 3.

01:19:43.650 --> 01:19:47.550
Und dann habe ich auch 1, 3 in der Relation.

01:19:47.550 --> 01:19:53.650
Und wenn ich weitermache, dann habe ich sowas wie die Zahlen, die

01:19:53.650 --> 01:20:01.510
Abstand n haben, wo eben dieses Produkt ist.

01:20:02.230 --> 01:20:05.370
Also das D-eigenes Hochkenntnis.

01:20:07.470 --> 01:20:08.270
Entschuldigung.

01:20:10.430 --> 01:20:12.370
Und das klappt auch für die 0.

01:20:12.370 --> 01:20:16.430
Also dann habe ich X minus Y ist kleiner gleich 0, also muss X wieder

01:20:16.430 --> 01:20:17.330
gleich X sein.

01:20:20.810 --> 01:20:25.390
Dann, es gibt gewisse Eigenschaften, die Relationen erfüllen können,

01:20:25.470 --> 01:20:27.290
zum Beispiel reflexiv und transitiv.

01:20:28.530 --> 01:20:31.370
Also reflexiv kann man entweder definieren, indem man sagt, die

01:20:31.370 --> 01:20:35.650
Identität ist in dieser Relation enthalten, als Teilmenge, oder man

01:20:35.650 --> 01:20:39.030
kann auch sagen, jedes X in dieser Menge soll in Relation mit sich

01:20:39.030 --> 01:20:39.650
selber stehen.

01:20:42.970 --> 01:20:44.410
Das ist äquivalent.

01:20:44.990 --> 01:20:49.250
Und für Transitivität habe ich, wenn X in Relation mit Y steht und Y

01:20:49.250 --> 01:20:53.110
in Relation mit Z, dann steht das X bereits in Relation mit Z.

01:20:53.350 --> 01:20:57.070
Dann habe ich sowas wie Fall von hier nach da und von da nach da, dann

01:20:57.070 --> 01:21:00.010
kann ich in einem Schritt von da nach da kommen.

01:21:03.930 --> 01:21:04.450
Entschuldigung.

01:21:07.310 --> 01:21:09.230
Dann unten habe ich mehrere Beispiele.

01:21:09.910 --> 01:21:14.490
Also das eine impliziert nicht das andere.

01:21:15.430 --> 01:21:18.750
Also es gibt Relationen, die reflexiv und transitiv sind, zum Beispiel

01:21:18.750 --> 01:21:20.770
gleich, kleiner gleich und größer gleich.

01:21:22.070 --> 01:21:26.310
Also X ist gleich X und wenn X ist gleich Y und Y ist gleich Z, dann

01:21:26.310 --> 01:21:29.810
muss X gleich Z sein zum Beispiel, das ist reflexiv und transitiv.

01:21:32.210 --> 01:21:35.810
Echt kleiner und echt größer sind transitiv.

01:21:36.210 --> 01:21:41.530
Also wenn X ist echt kleiner, wenn 1 ist echt kleiner als 2 und 2 ist

01:21:41.530 --> 01:21:44.170
echt kleiner als 3, dann ist 1 echt kleiner als 3 zum Beispiel.

01:21:46.350 --> 01:21:47.830
Aber die sind echt reflexiv.

01:21:47.990 --> 01:21:49.850
Eine Zahl ist nicht echt kleiner als ich selber.

01:21:52.070 --> 01:21:56.790
Dann gibt es auch die nicht gleich, das ist weder reflexiv noch

01:21:56.790 --> 01:21:57.070
transitiv.

01:21:58.770 --> 01:22:05.470
Und diese andere Relation, die 1 von vorher, das ist zwar reflexiv,

01:22:05.550 --> 01:22:06.830
aber das ist nicht transitiv.

01:22:09.510 --> 01:22:15.230
Also die Identität ist da enthalten, das haben wir gesehen.

01:22:16.990 --> 01:22:20.310
Aber das ist nicht transitiv, wenn ich zum Beispiel 3 in der Mitte von

01:22:20.310 --> 01:22:24.710
2 und 4 habe, dann steht eine Relation mit 2 und steht eine Relation

01:22:24.710 --> 01:22:27.330
mit 4, aber nicht 2 und 4 stehen in einer Relation miteinander.

01:22:29.490 --> 01:22:30.490
Das wusste ich schon.

01:22:32.970 --> 01:22:36.550
Da haben wir viele, viele Beispiele dafür.

01:22:38.210 --> 01:22:43.030
Und wenn man beides haben will, also Reflexivität und Transitivität

01:22:43.030 --> 01:22:47.190
aus einer beliebigen Relation und man nicht diese Relation irgendwie

01:22:47.190 --> 01:22:52.730
größer machen will, zu groß, ich könnte zum Beispiel einfach das

01:22:52.730 --> 01:22:53.790
kathedrische Produkt nehmen.

01:22:54.170 --> 01:22:58.950
Zum Beispiel R ist eine Relation auf M, dann kann ich einfach R zu M

01:22:58.950 --> 01:22:59.810
kreuz M machen.

01:22:59.910 --> 01:23:06.150
Das ist auch eine Relation, das ist zwingend reflexiv und transitiv,

01:23:06.230 --> 01:23:08.010
aber das will ich nicht unbedingt machen.

01:23:08.010 --> 01:23:17.490
Ich will einfach eine Relation R nehmen, und ich soll irgendwie

01:23:17.490 --> 01:23:26.270
erhalten eine Relation, die so klein wie möglich ist und R enthält und

01:23:26.270 --> 01:23:32.230
reflexiv und transitiv ist und diese Hülle erfüllt diese Bedingungen.

01:23:33.390 --> 01:23:37.530
Und das ist einfach die Vereinigung dieser Potenzen, von Null bis

01:23:37.530 --> 01:23:38.310
ähnlich.

01:23:40.650 --> 01:23:44.690
Und wenn zum Beispiel das R schon bereits reflexiv ist, dann muss ich

01:23:44.690 --> 01:23:49.730
nicht das R auf Null nehmen, das ist schon eine Identität, das ist

01:23:49.730 --> 01:23:50.630
schon in R enthalten.

01:23:50.910 --> 01:23:54.250
Dann darf ich bei i gleich 1 anfangen.

01:23:54.250 --> 01:24:02.110
Wenn das R transitiv ist, dann muss ich nicht all diese Potenzen auf 2

01:24:02.110 --> 01:24:07.610
oder 3 nehmen, weil die schon nach Definition in R enthalten sind.

01:24:08.610 --> 01:24:13.690
Also dann muss ich nur das R mit der Identität vereinigen.

01:24:14.110 --> 01:24:19.550
Und wenn ich beides habe, dann habe ich zwingend nur R auf 1.

01:24:19.550 --> 01:24:24.770
Wenn R bereits reflexiv und transitiv ist, dann ist das R hochstellen

01:24:24.770 --> 01:24:25.790
gleich das R wieder.

01:24:26.850 --> 01:24:30.170
Das ist eben die kleinste Relation, die R enthält und reflexiv und

01:24:30.170 --> 01:24:34.710
transitiv ist, weil R bereits reflexiv und transitiv ist, das muss so

01:24:34.710 --> 01:24:34.910
sein.

01:24:36.550 --> 01:24:42.470
Und wenn wir diese paar Anmerkungen verwenden, können wir zum Beispiel

01:24:42.470 --> 01:24:46.870
schauen, was die Hüllen für ein paar Relationen von vorher sind.

01:24:46.870 --> 01:24:49.710
Also zum Beispiel die kleine Gleichrelation ist reflexiv und

01:24:49.710 --> 01:24:52.790
transitiv, dann muss das Gleiche rauskommen.

01:24:55.670 --> 01:25:02.590
Der kleine Relation ist nur transitiv, dann muss ich einfach das mit

01:25:02.590 --> 01:25:08.130
der Identität vereinigen, dann habe ich das Gleiche dazu.

01:25:09.570 --> 01:25:12.410
Deswegen kommt der kleine Gleich raus.

01:25:12.410 --> 01:25:21.610
Das Nichtgleich als Hülle ist dann einfach der ganze Null kreuz Null,

01:25:22.070 --> 01:25:27.810
weil das Nichtgleich eben schon die Relation Null kreuz Null ohne die

01:25:27.810 --> 01:25:28.730
Identität ist.

01:25:28.890 --> 01:25:33.490
Also da habe ich einfach weggenommen alle Paare, wo die Zahlen gleich

01:25:33.490 --> 01:25:33.750
sind.

01:25:35.510 --> 01:25:37.550
Dann für die Hülle müsste ich einfach alles nehmen.

01:25:38.410 --> 01:25:39.210
Geht nicht anders.

01:25:39.210 --> 01:25:48.790
Und für dieses D1, da kommt auch die ganze Null kreuz Null, weil ich

01:25:48.790 --> 01:25:54.570
für D1 neben dieser Abstand N haben, dann kann ich, wenn ich

01:25:54.570 --> 01:26:02.310
weitermache, dann habe ich Zwing-Zahlen, die einen beliebigen Abstand

01:26:02.310 --> 01:26:03.070
voneinander haben.

01:26:04.750 --> 01:26:11.410
Dann noch ein paar Anmerkungen zu dieser Produktionsrelation, also zur

01:26:11.410 --> 01:26:12.950
Grammatik.

01:26:13.770 --> 01:26:21.010
Und das ist eine Relation auf die Wörter, die aus Nichtterminal- und

01:26:21.010 --> 01:26:22.410
Terminalsymbole bestehen.

01:26:23.330 --> 01:26:24.870
Ist das reflexiv?

01:26:25.050 --> 01:26:25.730
Leider nicht.

01:26:25.870 --> 01:26:30.050
Das kann nicht reflexiv sein, ich kann aus nur Terminalsymbole kein

01:26:30.050 --> 01:26:32.430
Wort produzieren.

01:26:33.510 --> 01:26:36.610
Da kann ich kein Wort produzieren, da muss ich eine Regel anwenden.

01:26:38.090 --> 01:26:44.330
Das ist transitiv in gewissen RAN-Beispielen, aber nicht im

01:26:44.330 --> 01:26:45.850
Allgemeinen.

01:26:47.450 --> 01:26:48.810
Also man kann z.B.

01:26:48.810 --> 01:26:52.390
aus S ein X produzieren oder X ein A, aber man muss nicht deswegen aus

01:26:52.390 --> 01:26:53.390
S ein A produzieren.

01:26:53.930 --> 01:26:55.290
Das kann nicht transitiv sein.

01:26:55.290 --> 01:26:56.670
Aber die Hülle fehlt uns.

01:27:00.130 --> 01:27:05.010
Deswegen haben wir diese Laborfeier auf Stern genommen, weil es diese

01:27:05.010 --> 01:27:07.110
zwei schönen Eigenschaften haben.

01:27:09.670 --> 01:27:11.150
Da bin ich zum Ende der Übung.

01:27:11.530 --> 01:27:13.970
Ich bedanke mich für die Aufmerksamkeit und wünsche euch noch ein

01:27:13.970 --> 01:27:14.730
schönes Wochenende.