WEBVTT

00:07.330 --> 00:09.330
Ja, hallo, guten Tag zusammen.

00:10.550 --> 00:14.070
Herzlich willkommen zur Vorlesung Theoretische Grundlagen der

00:14.070 --> 00:14.950
Informatik.

00:15.490 --> 00:18.230
Wie Sie sehen, fange ich pünktlich an.

00:19.190 --> 00:22.150
Sie sollten also auch in Zukunft pünktlich kommen, dann können wir

00:22.150 --> 00:27.850
auch pünktlich die Vorlesung beenden um 13 Uhr, damit Sie noch in die

00:27.850 --> 00:28.510
Mensa kommen.

00:30.630 --> 00:40.890
Also, die Semestervorlesung Theoretische Grundlagen der Informatik,

00:41.890 --> 00:46.770
Pflichtvorlesung im Informatik-Bachelorstudiengang, drittes Semester

00:46.770 --> 00:50.070
und ich weiß, es sind noch Informationswörter, vielleicht auch

00:50.070 --> 00:51.390
Mathematiker unter Ihnen.

00:51.970 --> 00:55.410
Ich werde jetzt am Anfang erstmal ein paar organisatorische Dinge

00:55.410 --> 00:55.910
sagen.

01:00.430 --> 01:06.030
Also, wer wir sind, wer ich bin, wer die Mitarbeiter sind, die die

01:06.030 --> 01:13.150
Übungen halten, wie das mit den Übungen oder Tutorien ist, wo Sie die

01:13.150 --> 01:18.710
Materialien zur Vorlesung finden, wie es mit Übungsabgabe geht,

01:18.950 --> 01:20.250
Klausur und so weiter.

01:21.690 --> 01:23.950
So, und jetzt zu den organisatorischen Dingen.

01:23.950 --> 01:29.430
Mein Name ist Dorothea Wagner, bin Professorin am Institut für

01:29.430 --> 01:33.830
Theoretische Informatik, insofern an dem Institut, das prädestiniert

01:33.830 --> 01:35.010
ist für diese Vorlesung.

01:35.530 --> 01:37.590
Und ich habe die Vorlesung schon sehr oft gehalten.

01:38.610 --> 01:42.930
Ich glaube, in Karlsruhe ist es das siebte Mal, dass ich die Vorlesung

01:42.930 --> 01:43.270
halte.

01:43.730 --> 01:47.290
Jetzt brauchen Sie nicht glauben, dass ich deshalb gelangweilt bin.

01:47.670 --> 01:50.750
Ganz im Gegenteil, das ist eine meiner Lieblingsvorlesungen.

01:50.750 --> 01:53.990
Also unter den Pflichtvorlesungen ist es meine Lieblingsvorlesung.

01:54.630 --> 01:57.830
Und obwohl ich die jetzt wirklich schon sehr, sehr oft gehalten habe,

01:57.930 --> 02:01.070
also auch nicht nur in Karlsruhe, vorher schon an der Uni Konstanz

02:01.070 --> 02:03.530
mehrfach, mache ich das immer wieder gern.

02:03.670 --> 02:05.950
Das ist in meinen Augen wirklich sehr schöner Stoff.

02:06.090 --> 02:12.350
Ich weiß, dass nicht alle die Vorlesung lieben, aber ich finde sie

02:12.350 --> 02:12.790
sehr schön.

02:13.170 --> 02:16.510
Und ich hoffe, dass zumindest ein Großteil von Ihnen Gefallen daran

02:16.510 --> 02:17.190
finden wird.

02:18.150 --> 02:19.370
Also das bin ich.

02:19.950 --> 02:25.550
Die Übungen werden von zwei Mitgliedern meines Lehrstuhls gehalten,

02:25.810 --> 02:30.250
einem Doktoranden und einer Doktorandin, Benjamin Niedermann und

02:30.250 --> 02:31.470
Franziska Wegner.

02:31.630 --> 02:33.010
Die beiden sitzen auch hier vorne.

02:33.190 --> 02:36.650
Ich zeige jetzt nicht mit dem Laserpointer auf die in der ersten

02:36.650 --> 02:37.090
Reihe.

02:40.960 --> 02:45.540
Dass bei den beiden die E-Mail-Adresse dabei steht, bei mir nicht, hat

02:45.540 --> 02:46.800
durchaus einen Hintergrund.

02:46.800 --> 02:50.720
Meine E-Mail-Adresse ist auch die kanonische E-Mail-Adresse dorothea

02:50.720 --> 02:55.920
.wagner.edu und wenn mir Studierende eine E-Mail schreiben mit einer

02:55.920 --> 02:58.900
sinnvollen Frage, dann versuche ich die auch immer schnell zu

02:58.900 --> 02:59.560
beantworten.

02:59.640 --> 03:04.200
Aber bei einer Vorlesung dieser Größe würden E-Mails, wo es sich

03:04.200 --> 03:09.020
irgendwie um Organisatorisches handelt oder Stoff der Übung oder der

03:09.020 --> 03:12.680
Vorlesung, mich möglicherweise ein bisschen überfordern, weil ich auch

03:12.680 --> 03:13.660
anderes zu tun habe.

03:13.800 --> 03:18.200
Deshalb rate ich Ihnen, dass Sie, wenn Sie der Meinung sind, Sie

03:18.200 --> 03:21.400
bekommen die Informationen, die Sie brauchen, nicht sowieso über die

03:21.400 --> 03:22.520
Webseite und so weiter.

03:22.600 --> 03:25.940
Also wenn Sie wirklich eine Frage haben, dass Sie eher an Benjamin

03:25.940 --> 03:29.320
Niedermann oder Franziska Wegner oder gleich an die beiden schreiben.

03:29.820 --> 03:31.160
Aber Sie können mir auch schreiben.

03:31.260 --> 03:34.240
Wenn Sie glauben, eine Frage zu haben, die nur ich beantworten kann

03:34.240 --> 03:36.760
und nicht meine Mitarbeiter, können Sie mir durchaus eine E-Mail

03:36.760 --> 03:37.020
schreiben.

03:37.140 --> 03:41.940
Ich versuche es wirklich auch zeitnah zu beantworten.

03:42.780 --> 03:45.640
Es gibt natürlich zur Vorlesung auch Tutorien.

03:46.500 --> 03:49.040
Hier sind die Namen der Tutorinnen und Tutoren

03:55.810 --> 03:59.630
und die Vorlesungen und Übungen werden aufgezeichnet.

03:59.730 --> 04:01.550
Das mache ich jetzt zum ersten Mal.

04:01.550 --> 04:04.810
Bisher war mir das irgendwie nicht ganz geheuer.

04:05.530 --> 04:09.390
Aber Sie bekommen also jede Menge Informationen zur Vorlesung.

04:09.890 --> 04:14.750
Da gibt es die Aufzeichnung von Vorlesungen und Übungen.

04:14.870 --> 04:18.790
Sie wissen wahrscheinlich besser als ich, wo Sie die finden im Netz.

04:19.630 --> 04:23.110
Natürlich über die Vorlesungs-Homepage bekommen Sie auch den Link zu

04:23.110 --> 04:24.030
den Aufzeichnungen.

04:24.550 --> 04:29.050
Die Aufzeichnungen werden immer möglichst zeitnah online gestellt.

04:29.050 --> 04:31.310
Natürlich eine gewisse Verzögerung gibt es manchmal.

04:31.930 --> 04:36.650
Es wird vielleicht noch ein bisschen was daran zu bearbeiten sein.

04:36.950 --> 04:39.870
Dann kann es also nicht unbedingt nach der Vorlesung schon online

04:39.870 --> 04:40.190
stehen.

04:42.210 --> 04:46.710
Hier ist die Homepage zur Veranstaltung.

04:46.910 --> 04:48.710
Das brauchen Sie nicht unbedingt abschreiben.

04:49.250 --> 04:52.130
Ich denke, Sie finden die über die verschiedensten Wege, über die

04:52.130 --> 04:56.450
Fakultätsseiten oder wenn Sie über meine Seite gehen und dann unter

04:56.450 --> 05:00.130
Lehre auf das aktuelle Wintersemester kommen Sie auch zu der Homepage.

05:00.490 --> 05:03.250
Und da finden Sie eigentlich alle Informationen, die Sie brauchen.

05:05.250 --> 05:10.610
Die Links zur Aufzeichnung, natürlich die Folien zur Vorlesung.

05:11.510 --> 05:16.290
Die werden wir sogar versuchen, immer vor der Vorlesung ins Netz zu

05:16.290 --> 05:20.050
stellen, sodass Sie während der Vorlesung schon die Folien auch selber

05:20.050 --> 05:20.770
vor sich haben.

05:20.770 --> 05:24.350
Das ist heute nicht gelungen, weil im letzten Moment noch was geändert

05:24.350 --> 05:24.950
werden muss.

05:26.950 --> 05:29.990
Aber das wird also ab Donnerstag immer der Fall sein.

05:32.150 --> 05:33.990
Da steht ein Skript.

05:34.590 --> 05:38.510
Das Skript deckt ungefähr 80 Prozent der Vorlesung ab.

05:39.130 --> 05:42.150
Das ist schon ein bisschen älter, aber die Teile, die...

05:42.150 --> 05:45.770
Also das soll ich vielleicht dazu sagen, die theoretischen Grundlagen

05:45.770 --> 05:48.510
der Informatik, das ist ein sehr stabiles Gebiet.

05:49.830 --> 05:53.130
Das heißt also, auch wenn das Skript schon einige Jahre alt ist, ist

05:53.130 --> 05:54.350
das nicht überholt.

05:54.550 --> 05:57.630
Die Dinge bleiben wahr, das ist so wie in der Mathematik auch.

05:58.190 --> 06:01.410
Das heißt also, das, was abgedeckt wird thematisch vom Skript, da

06:01.410 --> 06:06.850
können Sie im Skript auch wirklich, denke ich, sehr gut verwenden, um

06:06.850 --> 06:08.630
Dinge nachzulesen oder nachzuarbeiten.

06:09.170 --> 06:12.730
Es steht auch alles auf den Folien und die sind, wie gesagt, auch im

06:12.730 --> 06:13.010
Netz.

06:14.370 --> 06:16.750
Übungsblätter werden natürlich auf die Webseite gestellt.

06:16.750 --> 06:19.410
Alte Klausuren stehen da.

06:20.190 --> 06:26.570
Das Forum kennen Sie für Fragen an die Übungsleiter oder um Dinge

06:26.570 --> 06:28.030
untereinander zu diskutieren.

06:31.490 --> 06:34.930
Literaturempfehlungen und vielleicht dazu.

06:36.050 --> 06:40.190
Also neben dem Skript, das eigentlich fast alles abdeckt, gibt es vor

06:40.190 --> 06:42.430
allem zwei Bücher, die ich persönlich sehr mag.

06:42.430 --> 06:45.770
Das eine ist Theoretische Informatik von Ingo Wegener.

06:46.530 --> 06:49.170
Das Buch ist schon 20 Jahre alt.

06:49.730 --> 06:53.190
Das ist rausgekommen, kurz bevor ich die Vorlesung das erste Mal

06:53.190 --> 06:53.810
gehalten habe.

06:53.930 --> 06:57.150
Und da es mir damals sehr gut gefallen hat, habe ich damals die

06:57.150 --> 06:59.610
Vorlesung sehr stark an dem Buch orientiert.

06:59.950 --> 07:02.530
In der Zwischenzeit ist da auch einiges überarbeitet worden.

07:02.650 --> 07:06.790
Aber Sie werden wiedererkennen an vielen Themen, dass dieses Buch

07:06.790 --> 07:07.730
Grundlage ist.

07:07.730 --> 07:10.950
Und dann gibt es noch ein weiteres Buch, das ich sehr schön finde, von

07:10.950 --> 07:11.530
Uwe Schöning.

07:11.630 --> 07:16.050
Theoretische Informatik kurz gefasst und dieses kurz gefasst, das

07:16.050 --> 07:16.730
gefällt mir.

07:16.970 --> 07:20.510
Also er hat einen sehr knappen, aber klaren Schreibstil.

07:20.670 --> 07:23.610
Das ist ein kleines Büchlein und das deckt aber wahnsinnig viel ab.

07:24.110 --> 07:27.690
Also die beiden Bücher empfehle ich ganz besonders, wenn Sie sozusagen

07:27.690 --> 07:31.850
zusätzlich zu den Vorlesungsmaterialien mal in ein Buch schauen

07:31.850 --> 07:32.150
wollen.

07:32.150 --> 07:35.170
Es gibt dann noch weitere Bücher.

07:36.970 --> 07:42.630
Es gibt auch neuere Bücher zur theoretischen Informatik, die also wie

07:42.630 --> 07:46.930
die beiden Wegener und Schöning Lehrbuchcharakter haben.

07:47.490 --> 07:50.590
Aber es ist jetzt nicht so, dass die irgendwie dann was ganz Neues

07:50.590 --> 07:51.150
leisten.

07:51.950 --> 07:55.050
Also unter neuere Bücher fällt zum Beispiel dieses hier,

07:55.890 --> 07:57.810
deutschsprachiges Lehrbuch, etwas neuer.

07:57.950 --> 07:58.630
Das ist auch sehr gut.

07:58.630 --> 08:03.210
So die beiden Bücher, die ich hier hingeschrieben habe, haben

08:03.210 --> 08:04.710
vielleicht noch eine besondere Bedeutung.

08:05.070 --> 08:09.230
Sie werden merken während der Vorlesung, Bezüge zwischen dieser

08:09.230 --> 08:13.870
Vorlesung und anderen, die Sie schon gehört haben, gibt es und zwar

08:13.870 --> 08:21.430
vor allem zu Grundbegriffe der Informatik und zu Algorithmen 1.

08:22.180 --> 08:29.290
Und Algorithmen 1 ist stark auch durch das Buch thematisiert und

08:29.290 --> 08:32.690
überall da, wo die Berührungspunkte sind zu den theoretischen

08:32.690 --> 08:38.750
Grundlagen, finden Sie auch in dem Buch Wissenswertes.

08:39.650 --> 08:44.330
Und das erste, Gary and Johnson, Computers and Interactability, A

08:44.330 --> 08:50.090
Guide to the Theory of NP-Completeness, heißt in der Informatik

08:50.090 --> 08:54.310
-Community nur Gary Johnson, der Gary Johnson, und das ist eine Bibel.

08:54.490 --> 09:00.150
Das ist eine Bibel der Komplexitätstheorie, 1979 rausgegeben, immer

09:00.150 --> 09:00.890
noch aktuell.

09:01.690 --> 09:05.390
Das ist das erste Buch, das ich mir, zumindest soweit ich mich

09:05.390 --> 09:07.850
entsinne, während dem Studium gekauft habe.

09:09.690 --> 09:13.050
Und das ist bei mir mittlerweile extrem abgegriffen.

09:14.190 --> 09:17.630
Das habe ich auch dann nachfolgend immer mal wieder Doktoranden

09:17.630 --> 09:18.890
ausgeliehen und so.

09:18.970 --> 09:22.210
Das ist also intensiv benutzt worden.

09:22.670 --> 09:26.370
Und Sie werden sehen, ein Kernkapitel dieser Vorlesung ist

09:26.370 --> 09:28.630
Komplexitätstheorie.

09:28.630 --> 09:34.770
Also da geht es darum, Probleme, algorithmische Probleme, Probleme,

09:34.870 --> 09:39.210
die man durch Algorithmen lösen will, danach zu klassifizieren, wie

09:39.210 --> 09:40.870
schwierig sie zu lösen sind.

09:43.250 --> 09:46.970
Und das wird also in dem Buch abgehandelt.

09:49.790 --> 09:51.190
So, zu den Übungsblättern.

09:57.020 --> 10:00.660
So etwa alle zwei Wochen kommt ein neues Übungsblatt heraus.

10:02.800 --> 10:03.760
Typischerweise dienstags.

10:04.660 --> 10:08.220
Wir haben ein Schema über das ganze Semester, wann Vorlesung ist und

10:08.220 --> 10:09.000
wann Übung ist.

10:09.460 --> 10:10.960
Das steht auch schon auf der Webseite.

10:11.460 --> 10:14.180
Also genau die Termine, wann Vorlesung, wann Übung.

10:14.780 --> 10:17.800
Das ist jetzt kein durchgetakteter Plan.

10:18.160 --> 10:21.560
Es ist nicht so, jede vierte Veranstaltung ist eine Übung.

10:22.620 --> 10:24.620
Sondern das verschiebt sich ein bisschen.

10:24.620 --> 10:29.800
Am Anfang haben wir ein bisschen seltener Übungen und dann ab der

10:29.800 --> 10:32.460
dritten, vierten, fünften Woche etwas öfter.

10:33.180 --> 10:36.460
Und dann sind die Termine so getaktet, dass es thematisch passt und

10:36.460 --> 10:39.900
teilweise auch zu meinen Verpflichtungen außerhalb passt.

10:40.020 --> 10:43.900
Also es gibt ein paar einzelne Tage, Donnerstage oder Dienstage im

10:43.900 --> 10:46.500
Semester, wo ich dringend irgendwo anders sein muss.

10:46.500 --> 10:50.980
Wir haben das so durchgetaktet, dass ich mich nicht vertreten lassen

10:50.980 --> 10:55.100
muss oder die Vorlesung ausfallen muss, sondern dass es genau hinkommt

10:55.100 --> 10:55.840
mit den Übungen.

10:56.780 --> 11:03.820
Das heißt also, da das nicht so 100% jede zweite Woche eine Übung ist,

11:03.920 --> 11:08.580
ist das also nur etwa jeden zweiten Dienstag, dass ein neues Blatt

11:08.580 --> 11:09.440
rausgegeben wird.

11:10.520 --> 11:13.800
Und entsprechend haben Sie zur Bearbeitungszeit ein bis zwei Wochen,

11:13.800 --> 11:18.640
also manchmal ist es etwas kürzer, das Abgabedatum, also die Deadline

11:18.640 --> 11:21.580
steht aber jeweils auf dem aktuellen Übungsblatt, sollten Sie

11:21.580 --> 11:21.980
beachten.

11:23.480 --> 11:28.740
Und dann können Sie also Ihre bearbeiteten Übungen abgeben in so einem

11:28.740 --> 11:31.540
Kasten im Untergeschoss des Informatikgebäudes.

11:31.920 --> 11:35.200
Ich bin mir sicher, Sie wissen besser als ich, wo dieser Kasten steht.

11:37.700 --> 11:42.800
Die Übungen, die von Ihnen bearbeiteten Übungen, werden korrigiert von

11:42.800 --> 11:48.840
den TutorInnen und die korrigierten Blätter bekommen Sie dann in dem

11:48.840 --> 11:54.920
entsprechenden Tutorium, in dem Sie sich angemeldet haben, bekommen

11:54.920 --> 11:56.120
Sie es dann wieder zurück.

11:57.640 --> 12:01.620
Die Lösungen werden in den Plenarübungen besprochen.

12:03.120 --> 12:05.760
Und das erste Übungsblatt gibt es heute.

12:07.260 --> 12:08.320
Heute geht es schon los.

12:10.320 --> 12:12.480
So, und jetzt zur Bearbeitung der Übungen.

12:12.560 --> 12:17.540
Ich kann Ihnen nur wärmstens empfehlen, die Übungen zu bearbeiten.

12:19.240 --> 12:22.960
Das müssen Sie nicht machen, aber die Erfahrung lehrt, dass

12:22.960 --> 12:26.560
diejenigen, die das machen, insgesamt auch einen größeren Erfolg

12:26.560 --> 12:26.880
haben.

12:26.880 --> 12:30.100
Da gibt es ganz tolle Statistiken zu.

12:31.880 --> 12:37.280
Sie dürfen, und ich empfehle das sogar, zu zweit zusammenarbeiten.

12:38.160 --> 12:44.380
Sie können zwei zusammen sozusagen die Übungen bearbeiten und ein

12:44.380 --> 12:46.360
Lösungsblatt abgeben.

12:47.060 --> 12:50.380
Allerdings bitte nur, wenn beide im selben Tutorium sind.

12:51.340 --> 12:54.400
Das wird sonst einfach logistisch zu schwierig.

12:55.620 --> 13:01.160
Und bitte schreiben Sie auf Ihre Übung auch alle relevanten

13:01.160 --> 13:06.160
Informationen, wie Name, Vorname, Matrikelnummer, Tutoriumsnummer,

13:06.540 --> 13:07.520
Nummer des Tutors.

13:08.080 --> 13:12.380
Sonst ist es einfach schwierig, in der einen oder anderen Weise Ihre

13:12.380 --> 13:13.440
Übungen zuzuordnen.

13:13.880 --> 13:17.720
Und bitte keine lose Blättersammlung, sondern zusammenheften.

13:17.720 --> 13:19.760
So, jetzt ein Punkt.

13:21.160 --> 13:23.460
Ich hoffe, Sie können noch mit der Hand schreiben.

13:25.020 --> 13:29.920
Also die Übungsblätter müssen handschriftlich, also die Lösungen, Ihre

13:29.920 --> 13:32.940
Hausaufgaben, handschriftlich abgegeben werden.

13:33.480 --> 13:39.900
Das machen wir einfach, um duplizieren von Lösungen, sozusagen

13:39.900 --> 13:43.840
abschreiben, um das in einer gewissen Weise zu unterbinden.

13:43.840 --> 13:47.960
Ich weiß, man kann auch mit der Hand abschreiben, aber das ist halt

13:47.960 --> 13:53.720
eher eine heuristische Art und Weise, um sozusagen Kopieren zu

13:53.720 --> 13:55.080
unterbinden.

13:55.820 --> 14:00.440
Das heißt also, eine Kopie von irgendwas oder was Ausgedrucktes bitte

14:00.440 --> 14:01.060
nicht abgeben.

14:02.460 --> 14:07.640
Und wenn Sie abschreiben, nicht Ihre eigenen Lösungen abgeben, sondern

14:07.640 --> 14:11.300
von anderen Kopierte, dann gibt es halt keine Punkte.

14:13.920 --> 14:15.900
So, wozu das Ganze?

14:16.580 --> 14:19.260
Ja, natürlich, damit Sie den Stoff besser lernen.

14:19.780 --> 14:24.860
Also ein intrinsisches Interesse sollten Sie haben, diese Übungen zu

14:24.860 --> 14:25.140
machen.

14:26.060 --> 14:30.100
Sie kriegen aber auch einen kleinen Bonus, wenn Sie mindestens 50

14:30.100 --> 14:37.940
Prozent der Punkte, die Sie über die Übungen bekommen könnten, auch

14:37.940 --> 14:38.360
bekommen.

14:38.360 --> 14:41.080
Dann kriegen Sie einen kleinen Klausurbonus.

14:41.740 --> 14:44.760
Der zählt allerdings nur, wenn Sie die Klausur, so wie sie gestellt

14:44.760 --> 14:46.620
ist, mindestens bestehen.

14:46.820 --> 14:49.500
Also Sie können Ihre Note sozusagen ein kleines bisschen aufbessern

14:49.500 --> 14:50.560
darüber.

14:52.140 --> 14:57.060
Das sage ich, oder das machen wir so, weil wir aus Erfahrung wissen,

14:57.280 --> 15:02.080
dass der Mensch manchmal zusätzliche Motivation braucht, um was zu

15:02.080 --> 15:04.520
machen, was eigentlich für sich genommen schon sinnvoll ist.

15:07.800 --> 15:12.160
Okay, zu den Tutorien, also da werden die Übungsblätter zurückgegeben

15:12.160 --> 15:17.280
und da wird eben zusätzlicher Stoff behandelt, also nicht zusätzlicher

15:17.280 --> 15:19.580
Stoff, das ist jetzt falsch ausgedrückt, da werden sozusagen

15:19.580 --> 15:25.040
zusätzlich geübt, also zusätzliche Aufgaben und Beispiele zur

15:25.040 --> 15:26.280
Vorlesung behandelt.

15:27.760 --> 15:34.120
Los geht's ab nächster Woche und Sie müssen sich natürlich eintragen

15:34.120 --> 15:34.960
in Tutorien.

15:35.100 --> 15:39.660
Das geht über Webinscribe, über diese Seite.

15:39.800 --> 15:43.600
Ich vermute, dass Sie das auch schon kennen, der Benjamin und

15:43.600 --> 15:47.400
Franziska geben jetzt aber auch noch Zettel, verteilen Zettel, auf

15:47.400 --> 15:54.420
denen alles zu diesem Thema Anmelden in die Tutorien steht.

15:57.080 --> 16:02.900
Da ist alles verlinkt, was Sie brauchen für die Tutorien und ab heute

16:02.900 --> 16:08.880
Abend 18 Uhr können Sie sich anmelden und bis Donnerstag 18 Uhr sollte

16:08.880 --> 16:10.200
dies auch geschehen sein.

16:13.520 --> 16:17.200
Und denken Sie bitte daran, wenn Sie zusammen, zu zweit

16:17.200 --> 16:21.960
zusammenarbeiten wollen, dass Sie sich dann auch beide in dasselbe

16:21.960 --> 16:24.300
Tutorium eintragen.

16:34.710 --> 16:39.830
Um die Vorlesung, die Veranstaltung sozusagen erfolgreich

16:39.830 --> 16:47.930
abzuschließen, müssen Sie eine Klausur mitschreiben und bestehen.

16:49.490 --> 16:53.130
Und die erste Klausur findet am 20.

16:53.490 --> 16:55.150
Februar um 8 Uhr statt.

16:56.470 --> 17:01.810
Ich persönlich hätte Ihnen zu lieben auch gerne eine andere Uhrzeit

17:01.810 --> 17:06.950
gehabt, aber diese Klausurtermine, die werden zentral von der Fakultät

17:06.950 --> 17:11.990
geplant, so geplant, dass sich da keine Kollisionen ergeben oder

17:11.990 --> 17:16.090
Klausuren, die dasselbe Semester betreffen, nicht zu nah beieinander

17:16.090 --> 17:16.530
sind.

17:16.910 --> 17:19.850
Und dann brauchen wir eine gewisse Anzahl von Hörsälen und so weiter

17:19.850 --> 17:21.370
und da ist halt das rausgekommen.

17:21.370 --> 17:23.810
Da kann ich leider jetzt auch nichts dran ändern.

17:24.530 --> 17:25.170
Also 20.

17:25.430 --> 17:26.310
Februar, 8 Uhr.

17:27.450 --> 17:31.110
Es gibt dann noch eine zweite Klausur, ein halbes Jahr später, so Pi

17:31.110 --> 17:33.850
mal Daumen, der Termin steht aber noch nicht fest.

17:36.550 --> 17:42.970
Ich empfehle Ihnen wirklich auch zu planen, dass Sie diese Klausur

17:42.970 --> 17:43.630
mitschreiben.

17:45.250 --> 17:46.130
Und der 20.

17:46.330 --> 17:50.330
Februar, das ist relativ knapp nach Ende der Vorlesungszeit.

17:51.330 --> 17:53.730
Es kann sogar sein, dass gerade mal ein, zwei Tage nach Ende der

17:53.730 --> 17:56.050
Vorlesungszeit ist, das habe ich jetzt nicht genau im Kopf.

17:56.510 --> 17:59.110
Also Sie müssen natürlich, um bei der Klausur erfolgreich zu sein,

17:59.230 --> 18:02.170
jetzt dann schon auch das Semester gut am Ball bleiben.

18:03.650 --> 18:05.490
Die Klausur dauert zwei Stunden.

18:05.890 --> 18:11.570
Das ist so, seit wir diese Veranstaltung im Bachelorstudiengang

18:11.570 --> 18:15.650
anbieten, seit es den Bachelorstudiengang hier in Karlsruhe gibt, ist

18:15.650 --> 18:19.310
das so, dass diese Klausur über theoretische Grundlagen der Informatik

18:19.310 --> 18:20.870
eine Dauer von zwei Stunden hat.

18:21.630 --> 18:26.110
Es gab natürlich eine Vorgängerveranstaltung, die hieß Informatik 3,

18:26.290 --> 18:29.870
war genauso im dritten Semester, damals im Diplomstudiengang.

18:31.170 --> 18:34.310
Die dauerte aber aus irgendwelchen Gründen, die ich nie verstanden

18:34.310 --> 18:35.630
habe, nur eine Stunde.

18:36.450 --> 18:39.710
Das ist deshalb relevant, weil es alte Klausuren gibt und die alten

18:39.710 --> 18:42.450
Klausuren, die also noch aus der Zeit sind, die können Sie natürlich

18:42.450 --> 18:46.170
auch als Übungsmaterial verwenden, aber da sollten Sie beachten, dass

18:46.170 --> 18:49.870
die damals für eine Stunde konzipiert waren, während jetzt die neueren

18:49.870 --> 18:54.250
Klausuren, seit es den Bachelorstudiengang gibt, eben für zwei Stunden

18:54.250 --> 18:55.190
konzipiert sind.

18:55.970 --> 19:00.410
Also Sie können sich auf den alten Klausuren auf der Homepage an denen

19:00.410 --> 19:03.110
austoben, auch wenn Sie sich auf die Klausur vorbereiten.

19:03.510 --> 19:05.450
Im Stil bleiben die gleich.

19:06.010 --> 19:14.130
Und da meine ich jetzt vor allem die Klausuren zur Vorlesung TGI in

19:14.130 --> 19:17.450
den Semestern, in denen ich die Veranstaltung gehalten habe.

19:17.850 --> 19:20.730
Das heißt nicht, dass die anderen, also in der Zwischenzeit hat zum

19:20.730 --> 19:25.170
Beispiel Müller-Quade die Vorlesung gehalten, das heißt nicht, dass

19:25.170 --> 19:27.270
die jetzt irrelevant sind, aber er hat einfach ein bisschen einen

19:27.270 --> 19:29.830
anderen Stil, also die Klausuren sehen einfach ein bisschen anders

19:29.830 --> 19:30.110
aus.

19:30.110 --> 19:36.450
Aber das, was es da gibt aus dem Wintersemester 10.11 und 11.12 ist

19:36.450 --> 19:38.330
hochrelevant für Sie und brauchbar.

19:38.730 --> 19:43.110
Und dann gibt es, wie gesagt, diese Informatik-3-Klausuren aus

19:43.110 --> 19:46.910
vorherigen Zeiten, aber die sind für eine Stunde konzipiert gewesen.

19:49.090 --> 19:55.630
Nochmal, Sie können also, wenn Sie die Hausaufgaben machen und 50% der

19:55.630 --> 20:00.730
erreichbaren Punkte erreichen, einen kleinen Klausurbonus erzielen,

20:00.890 --> 20:03.250
der auf bestandene Klausuren angerechnet wird.

20:04.070 --> 20:08.130
So, und das, was hier steht, habe ich schon gesagt, die zweite Klausur

20:08.130 --> 20:11.230
ist irgendwann, ich weiß nicht, September, August, September, Oktober,

20:11.370 --> 20:14.570
in der Größenordnung, der Termin steht aber noch nicht fest.

20:15.550 --> 20:19.470
Da habe ich jetzt auch keinen Einfluss drauf, wann der festgelegt

20:19.470 --> 20:19.670
wird.

20:19.850 --> 20:22.870
Ich denke aber, noch während der Vorlesungszeit wird der festgelegt.

20:23.710 --> 20:28.070
Aber Sie sollten planen, im Februar mitzuschreiben, dann hätten Sie im

20:28.070 --> 20:30.730
Falle, dass Sie nicht erfolgreich sind, auch die Möglichkeit, ein

20:30.730 --> 20:35.610
halbes Jahr später diese Klausur, die zweite als Nachholklausur oder

20:35.610 --> 20:37.310
Wiederholungsklausur mitzuschreiben.

20:37.790 --> 20:40.230
Aber letztendlich ist es Ihnen natürlich überlassen.

20:40.350 --> 20:46.210
Sie können auch einfach den ersten Termin passieren lassen und nur bei

20:46.210 --> 20:47.510
dem zweiten Termin mitschreiben.

20:49.370 --> 20:50.810
Gibt es dazu Fragen?

20:51.550 --> 20:53.470
Da hinten ist so Gemurmel.

20:55.590 --> 20:56.690
Gibt es Fragen dazu?

20:58.570 --> 20:59.690
Zum Organisatorischen?

21:01.350 --> 21:03.150
Denn ich glaube, das ist es.

21:03.910 --> 21:06.210
Also gibt es zum Organisatorischen Fragen?

21:09.330 --> 21:11.950
Gut, dann fangen wir jetzt mit dem Vorlesungsstoff an.

21:13.070 --> 21:18.370
Gut, die ersten beiden Folien heute sagen nur so allgemein, was

21:18.370 --> 21:22.250
eigentlich Ziel dieser Vorlesung ist oder worum es geht bei den

21:22.250 --> 21:24.170
theoretischen Grundlagen der Informatik.

21:28.000 --> 21:32.370
Wir wollen sozusagen die theoretischen Grundlagen zum Algorithmen- und

21:32.370 --> 21:34.270
Programmentwurf legen.

21:35.730 --> 21:40.170
Und das sollen Grundlagen sein, die möglichst allgemeingültig sind.

21:40.590 --> 21:45.830
Deshalb werden wir versuchen, uns von konkreten Rechnern und von

21:45.830 --> 21:48.310
Programmiersprachen zu lösen.

21:48.550 --> 21:54.370
Wir wollen Aussagen treffen, die für alle Varianten von Computern und

21:54.370 --> 21:56.810
für alle Programmiersprachen gelten.

21:57.650 --> 22:02.650
Das heißt, es bezieht sich mehr darauf, welche Probleme kann man

22:02.650 --> 22:06.850
überhaupt lösen oder wie effizient kann man die lösen.

22:09.150 --> 22:15.030
Umgekehrt gefragt, gibt es Probleme, die von einem Computer nicht

22:15.030 --> 22:16.230
gelöst werden können.

22:17.070 --> 22:18.670
Das ist das ganze Thema Berechenbarkeit.

22:19.510 --> 22:22.550
Sie wissen wahrscheinlich, ja, es gibt Probleme, die nicht berechenbar

22:22.550 --> 22:22.930
sind.

22:23.670 --> 22:27.850
Ein kleines bisschen dran gekratzt haben Sie schon in Grundbegriffe

22:27.850 --> 22:28.890
der Informatik.

22:29.370 --> 22:34.330
Hier werden wir dieses ganze Thema systematisch behandeln mit

22:34.330 --> 22:35.710
entsprechenden Beweisen.

22:36.070 --> 22:40.390
Beweise, dass bestimmte Probleme nicht berechenbar sind.

22:40.390 --> 22:46.290
Und auch mit einer Formalisierung, die sozusagen auch dann keinen

22:46.290 --> 22:49.830
Freiraum zu Spekulationen gibt.

22:50.150 --> 22:53.170
Man muss sich dann erst mal festlegen, was man eigentlich unter

22:53.170 --> 22:56.690
berechenbar versteht, was ein Problem ist.

22:56.790 --> 23:00.770
Sie werden sehen, wir werden bei der Berechenbarkeit und auch bei der

23:00.770 --> 23:04.870
Komplexitätstheorie und im Zweiten bei der Komplexitätstheorie ist das

23:04.870 --> 23:10.570
vielleicht sogar noch merkwürdiger, uns immer, wenn wir so formale

23:10.570 --> 23:15.950
Beweise führen, auf eine Sprachenebene begeben.

23:16.810 --> 23:20.670
Selbst wenn wir im Kopf haben, wir wollen wissen, ob ein bestimmtes

23:20.670 --> 23:26.670
Problem berechenbar ist oder effizient gelöst werden kann oder eben zu

23:26.670 --> 23:31.910
den schweren Problemen gehört, was auch immer schwer heißt, werden wir

23:31.910 --> 23:34.830
das nicht auf Problemebene, sondern auf Sprachebene machen.

23:34.830 --> 23:36.910
Also das Akzeptieren einer Sprache.

23:37.110 --> 23:42.510
Gibt es ein Computer, ein Rechenmodell, das eine bestimmte Sprache

23:42.510 --> 23:43.570
akzeptieren kann?

23:44.770 --> 23:48.390
Das ist, wie gesagt, ein bisschen merkwürdig, vor allem, wenn man

23:48.390 --> 23:53.070
eigentlich bei der Komplexitätstheorie das Lösen von Problemen im Kopf

23:53.070 --> 23:53.310
hat.

23:53.470 --> 23:58.690
Und vor allem eben, was hat das für Konsequenzen für die Existenz von

23:58.690 --> 24:00.950
Algorithmen einer bestimmten Art?

24:00.950 --> 24:07.370
Aber wir führen das sozusagen auf diese Sprachebene zurück, weil man

24:07.370 --> 24:15.350
dann eine wirklich durchgehende Kette hat von fundierten Argumenten,

24:15.770 --> 24:17.770
so wie bei einem mathematischen Beweis.

24:19.530 --> 24:23.210
Und dazu braucht man dann natürlich auch ein Modell eines Computers.

24:24.690 --> 24:31.490
Das heißt also, ein Thema der Veranstaltung ist, einfache, abstrakte

24:31.490 --> 24:40.190
Modelle von Berechnung zu betrachten und danach zu beurteilen, wie

24:40.190 --> 24:42.310
mächtig dieses Modell ist.

24:43.190 --> 24:47.490
Das klingt sehr abstrakt und sieht auch teilweise so sehr theoretisch

24:47.490 --> 24:51.830
und abgefahren aus, also im Sinne von, hat nichts mit der Realität zu

24:51.830 --> 24:52.090
tun.

24:52.410 --> 24:56.150
Das hat aber deutlich mehr mit der Realität zu tun, als man vielleicht

24:56.150 --> 24:58.150
im ersten Moment denken mag.

24:58.270 --> 25:04.230
Denn man kann das, was ein real existierender Computer kann oder nicht

25:04.230 --> 25:09.850
kann, tatsächlich auf eine abstrakte Ebene heben, wo die Abstraktion

25:09.850 --> 25:13.650
sehr einfach aussieht, sehr einfach zu beschreiben ist.

25:13.810 --> 25:15.330
Und das werden wir hier in der Vorlesung machen.

25:16.890 --> 25:18.470
Und damit eng verknüpft ist,

25:24.980 --> 25:27.880
wie ausdrucksfähig sind bestimmte Sprachen.

25:29.080 --> 25:34.780
Welches Rechnermodell kann welche Sprachen erkennen, akzeptieren, das

25:34.780 --> 25:35.840
habe ich eben schon gesagt.

25:36.180 --> 25:40.580
Sprachen akzeptieren ist das, worüber wir reden, wenn wir immer

25:40.580 --> 25:45.040
wirklich fundierte Beweise führen, selbst wenn wir eigentlich an

25:45.040 --> 25:47.840
Lösbarkeit von Problemen interessiert sind.

25:48.300 --> 25:51.480
Und dann muss man natürlich auch ein Augenmerk haben auf der Sprache,

25:51.760 --> 25:55.280
die man benutzt, um irgendwas auszudrücken, um es zu formulieren.

25:56.720 --> 26:00.280
Das sind also so grundlegende Fragen, die in der Vorlesung behandelt

26:00.280 --> 26:00.640
werden.

26:03.320 --> 26:06.480
Das heißt also, Ziel der Vorlesung ist, einen vertieften Einblick in

26:06.480 --> 26:08.980
die Grundlagen der theoretischen Informatik zu geben.

26:11.720 --> 26:15.880
Und was Sie also dann am Schluss mitnehmen sollten, ist natürlich

26:15.880 --> 26:20.880
dieses Wissen über Berechenbarkeit und Nichtberechenbarkeit, das

26:20.880 --> 26:29.980
Wissen über gewisse Komplexitätsklassen, das Wissen über einfache

26:29.980 --> 26:33.860
Berechnungsmodelle, die dazugehören, und deren Mächtigkeit.

26:34.160 --> 26:37.980
Da gibt es Modelle, die sind weniger mächtig, mächtigere Modelle,

26:39.560 --> 26:43.640
kennen auch die grundlegenden endliche Automaten einerseits,

26:45.040 --> 26:52.550
Touringmaschine, und natürlich ein Verständnis für die Grenzen dessen,

26:52.650 --> 26:53.610
was möglich ist.

26:54.310 --> 27:01.410
Ein Großteil der Ergebnisse, die wir hier beweisen werden, sind also

27:01.410 --> 27:05.270
Ergebnisse, die sozusagen die Grenzen aufzeichnen, das, was nicht mehr

27:05.270 --> 27:10.310
geht, was nicht berechenbar ist, was zu komplex ist, um in einer

27:10.310 --> 27:12.850
bestimmten Art und Weise gelöst werden können.

27:12.850 --> 27:20.150
Sie brauchen dafür ein bestimmtes Abstraktionsvermögen, solche

27:20.150 --> 27:28.210
grundlegenden Aspekte, wie Modelle für Berechnungen oder Konzepte von

27:28.210 --> 27:29.690
Programmiersprachen zu verstehen.

27:30.930 --> 27:33.850
Und Sie sollten auch gewisse Techniken lernen.

27:35.630 --> 27:39.710
Spätestens bei der Evaluation der Vorlesung höre ich oft von

27:39.710 --> 27:43.950
denjenigen, die die Vorlesung nicht mögen, das gibt es, da sind zu

27:43.950 --> 27:44.950
viele Beweise drin.

27:46.730 --> 27:50.010
TGI finde ich nicht gut, da sind zu viele Beweise drin.

27:50.470 --> 27:57.710
Das ist eine essentielle Eigenschaft dieses Themas und dieser

27:57.710 --> 28:00.250
Vorlesung, dass Beweise geführt werden.

28:01.430 --> 28:04.890
Dieses Wissen, ein bestimmtes Problem ist nicht berechenbar oder ein

28:04.890 --> 28:08.750
bestimmtes Problem ist NP-vollständig und damit sehr komplex.

28:09.670 --> 28:12.370
Dieses Wissen, das ist wenig wert.

28:13.890 --> 28:19.190
Sie müssen die Konzepte, die dahinterstehen, verstehen und Sie sollten

28:19.190 --> 28:23.170
auch die ganz grundlegenden Techniken, die man braucht, um solche

28:23.170 --> 28:26.470
Aussagen zu treffen, wie ein bestimmtes Problem ist nicht berechenbar,

28:26.930 --> 28:30.870
ein bestimmtes Problem ist NP-vollständig, diese Techniken sollten Sie

28:30.870 --> 28:32.610
auch kennen.

28:34.310 --> 28:39.050
Was sind so Techniken, wenn man eben weiß, ein bestimmtes Problem ist

28:39.050 --> 28:42.170
nicht berechenbar und jetzt ein anderes betrachtet, von dem man das

28:42.170 --> 28:47.750
Gefühl hat, das ist genauso nicht berechenbar wie dieses erste, wie

28:47.750 --> 28:50.790
Sie dies auch beweisen können, mit Hilfe der Kenntnis, dass dieses

28:50.790 --> 28:52.070
erste nicht berechenbar ist.

28:52.450 --> 28:57.630
Das ist ein ganz berühmtes Konzept der theoretischen Informatik, die

28:57.630 --> 28:59.670
Reduktion auf ein anderes Problem.

29:00.310 --> 29:02.910
Bei Komplexitätsaussagen geht das genauso.

29:03.130 --> 29:05.570
Sie haben da ein Problem, von dem wissen Sie, das ist sehr schwer.

29:05.570 --> 29:11.850
Jetzt betrachten Sie ein neues Problem, sage ich mal, für Sie neu, und

29:11.850 --> 29:15.330
Sie wissen nicht, ist das jetzt leichter als das andere oder schwerer

29:15.330 --> 29:18.270
als das andere oder mindestens genauso schwer wie das andere.

29:19.910 --> 29:23.710
Um zu zeigen, dass es mindestens genauso schwer wie das andere ist,

29:23.910 --> 29:27.570
und das ist der gängige Weg, um Probleme in gewisse

29:27.570 --> 29:32.970
Komplexitätsklassen einzuteilen, brauchen Sie eine Technik, die nennt

29:32.970 --> 29:34.370
sich wiederum Reduktion.

29:34.370 --> 29:38.250
Sie reduzieren das Problem auf das vorherige, von dem Sie wissen, wie

29:38.250 --> 29:39.070
schwierig es ist.

29:40.370 --> 29:44.090
Also diese Konzepte, die müssen Sie am Schluss auch beherrschen.

29:44.830 --> 29:48.210
Und das muss dann auch in der Klausur angewendet werden.

29:52.250 --> 29:57.630
Ich habe eben schon gesagt, zu zwei anderen Veranstaltungen gibt es

29:57.630 --> 29:59.130
vor allem Querbezüge.

29:59.390 --> 30:03.990
Einerseits zu Algorithmen 1, das betrifft vor allem Komplexität von

30:03.990 --> 30:09.930
Problemen, weil man halt daran interessiert ist, effiziente

30:09.930 --> 30:12.250
Algorithmen zur Lösung von Problemen zu entwerfen.

30:12.330 --> 30:16.670
Das macht man in der Algorithmen 1 Vorlesung und in Algorithmen 2 im

30:16.670 --> 30:17.610
fünften Semester.

30:18.570 --> 30:22.830
Und eben als Grundlage für vieles, was da gemacht wird, zumindest

30:22.830 --> 30:26.910
Hintergrund, ist dann diese Veranstaltung TGI und da vor allem das

30:26.910 --> 30:29.490
Kapitel Komplexitätsklassen relevant.

30:29.490 --> 30:33.850
Und andererseits gibt es Bezüge zu Grundbegriffe der Informatik, GBI.

30:35.190 --> 30:37.490
Und heute werde ich den Rest der Vorlesung

30:40.930 --> 30:43.690
Begriffe wiederholen, die Sie dort schon gehört haben.

30:44.370 --> 30:48.550
Ich persönlich habe so ein bisschen ein gespaltenes Verhältnis dazu,

30:48.770 --> 30:53.190
wie TGI und GBI zueinander stehen.

30:53.790 --> 30:58.230
Ich weiß, dass in GBI, Grundbegriffe der Informatik, einige Themen

30:58.230 --> 31:02.730
schon angesprochen werden, die hier systematisch bearbeitet werden.

31:03.230 --> 31:06.910
Und das wird bei Ihnen vielleicht ein Gän auslösen, wenn Sie sowieso

31:06.910 --> 31:09.110
nicht interessiert sind an theoretischen Grundlagen.

31:09.530 --> 31:12.530
Oder das Gefühl, ja wieso, das haben wir doch alles schon im ersten

31:12.530 --> 31:13.490
Semester gemacht.

31:13.870 --> 31:16.370
Also deshalb habe ich dieses gespaltene Verhältnis dazu.

31:16.870 --> 31:21.130
Ich persönlich bin eigentlich ein Vertreter davon, die Dinge sozusagen

31:21.130 --> 31:23.790
systematisch, wie man es auch in der Mathematik macht, aufeinander

31:23.790 --> 31:24.670
aufzubauen.

31:25.030 --> 31:28.970
Und warum soll ich es in der Frühphase über Turing-Maschinen was sagen

31:28.970 --> 31:34.290
oder über endliche Automaten, wenn ich es da doch nicht systematisch

31:34.290 --> 31:37.190
mache, warum nicht warten bis zum dritten Semester, wo es dann

31:37.190 --> 31:38.450
systematisch gemacht wird.

31:38.710 --> 31:42.150
Gibt aber durchaus auch Kollegen und Kolleginnen, die das anders

31:42.150 --> 31:42.450
sehen.

31:42.830 --> 31:46.830
Und man kann auch, und insofern will ich das, was da in Grundbegriffe

31:46.830 --> 31:49.990
der Informatik schon behandelt wird, was eigentlich jetzt hier

31:49.990 --> 31:53.070
drankommt, auch nicht sozusagen verteufeln.

31:54.070 --> 31:57.230
Man kann auch vertreten, dass es manchmal einfach ganz gut ist, von

31:57.230 --> 32:00.210
Anfang an, wenn man sich nun mal für so ein Fach wie Informatik

32:00.210 --> 32:04.650
interessiert und das studiert, so ein paar ganz grundlegende Konzepte

32:04.650 --> 32:05.770
schon mal gesehen zu haben.

32:07.290 --> 32:10.930
Und so ist sozusagen das Verhältnis von GBI und TGI.

32:11.810 --> 32:15.590
Ein paar grundlegende Begriffe, die zu den theoretischen Grundlagen

32:15.590 --> 32:20.430
der Informatik gehören, werden in GBI schon mal so angekratzt.

32:20.490 --> 32:24.030
Sie werden aber sehr schnell merken, bei GBI wird da nur an der

32:24.030 --> 32:26.670
Oberfläche gekratzt und hier machen wir das wirklich fundiert.

32:27.450 --> 32:31.210
Hier werden Beweise geführt, hier werden Konzepte wirklich durchgängig

32:31.210 --> 32:35.150
und auch ohne Lücke in der Argumentationskette oder in den Beweisen

32:35.150 --> 32:38.250
abgehandelt.

32:39.290 --> 32:43.110
Und das allererste Thema, das wir hier behandeln werden, hier in der

32:43.110 --> 32:48.070
Vorlesung, sind endliche Automaten und reguläre Sprachen.

32:48.950 --> 32:53.650
Und bei den endlichen Automaten insbesondere der Aspekt Determinismus

32:53.650 --> 32:55.350
versus Nicht-Determinismus.

32:55.810 --> 33:01.030
Diese Worte, endliche Automaten, reguläre Sprachen, deterministisch,

33:01.390 --> 33:04.810
nicht -deterministisch, die haben Sie in GBI schon gehört, aber

33:04.810 --> 33:11.470
spätestens bei dem Abhandeln von Determinismus versus Nicht

33:11.470 --> 33:15.030
-Determinismus im Zusammenhang mit endlichen Automaten werden Sie sehr

33:15.030 --> 33:17.930
schnell sehen, dass was hier wirklich fundiert machen wird, dass in

33:17.930 --> 33:20.770
GBI nicht weiter gemacht wurde.

33:21.950 --> 33:25.510
Damit hier diese Veranstaltung jetzt aber in sich abgeschlossen ist,

33:25.630 --> 33:28.570
also jetzt erstmal ein paar Begriffe zur Wiederholung, die Sie schon

33:28.570 --> 33:31.350
kennen, aber es schadet ja auch nicht, wenn Sie sich jetzt vor Augen

33:31.350 --> 33:34.930
führen, denn ab Donnerstag wird damit dann weitergearbeitet.

33:35.070 --> 33:39.790
Die ersten Begriffe sind die Begriffe eines Wortes oder Wörter,

33:39.970 --> 33:43.010
formale Sprachen, reguläre Ausdrücke, endliche Automaten und

33:43.010 --> 33:44.310
kontextfreie Grammatiken.

33:44.810 --> 33:48.890
Also alles Themen, die in GBI mal kurz dran waren und hier als

33:48.890 --> 33:51.710
Wiederholung nochmal kommen, damit wir dann am Donnerstag darauf

33:51.710 --> 33:52.690
weiter aufbauen können.

33:54.130 --> 33:55.090
Also Wörter.

33:56.890 --> 33:59.850
Sie betrachten ein Alphabet, Sigma.

34:02.210 --> 34:05.890
Und zwar ist es definiert als eine endliche Menge von Zeichen.

34:06.470 --> 34:10.010
Beispiel Sigma besteht nur aus den Zeichen 0 und 1.

34:10.470 --> 34:13.790
Bei vielen Beispielen, die wir hier betrachten, kommen wir mit diesem

34:13.790 --> 34:17.650
kleinen Alphabet aus, aber das Alphabet könnte natürlich auch deutlich

34:17.650 --> 34:18.890
mehr Zeichen enthalten.

34:18.890 --> 34:26.010
So, und dann ist ein Wort W über einem vorgegebenen Alphabet Sigma

34:26.010 --> 34:30.350
einfach eine Folge von Zeichen aus Sigma.

34:32.150 --> 34:36.810
Diese Folge kann auch Länge 0 haben, also leer sein.

34:37.850 --> 34:47.150
Das heißt also, das leere Wort, diese Folge von Zeichen der Länge 0

34:47.150 --> 34:48.470
ist ein Wort.

34:50.150 --> 34:56.410
Einfaches Beispiel, so eine Zeichenkette 001 001 0, das ist ein Wort

34:56.410 --> 34:58.670
über dem Alphabet Sigma gleich 0 1.

34:59.410 --> 35:06.950
Das leere Wort, also Wort über Sigma der Länge 0, das symbolisieren

35:06.950 --> 35:08.610
wir oder schreiben wir als klein Sigma.

35:09.110 --> 35:10.050
Das ist das leere Wort.

35:11.930 --> 35:15.510
So, und dann kann man natürlich für ein endliches Alphabet die Menge

35:15.510 --> 35:18.530
aller Wörter über diesem Alphabet bilden.

35:18.710 --> 35:23.230
Einfach alle möglichen Folgen von Zeichenketten und Zeichen aus dem

35:23.230 --> 35:23.710
Alphabet.

35:24.050 --> 35:25.530
Da gehört das leere Wort dazu.

35:26.290 --> 35:29.950
Das ist die Zeichenkette über dem Alphabet, die die Länge 0 hat.

35:30.150 --> 35:33.870
Da gehören natürlich die Symbole aus dem Alphabet dazu, also bei Sigma

35:33.870 --> 35:38.610
gleich 0 1, das Wort 0, das Wort 1, aber eben auch längere Worte, die

35:38.610 --> 35:39.450
sie bilden können.

35:40.050 --> 35:41.830
Und das kann natürlich hier immer so weitergehen.

35:42.090 --> 35:47.470
Das heißt also, das werden dann unendlich viele Wörter plötzlich.

35:47.850 --> 35:51.690
Also das Alphabet ist endlich, aber wenn Sie die Menge aller Wörter

35:51.690 --> 35:56.050
über dem Alphabet bilden, dann bekommen Sie eine unendliche Menge und

35:56.050 --> 36:01.610
die wird zum Alphabet Sigma als Sigma-Stern bezeichnet.

36:04.620 --> 36:08.520
So, jetzt kann man natürlich auch nach der Länge sozusagen Menge aller

36:08.520 --> 36:13.100
Wörter über Sigma einer bestimmten Länge sozusagen Mengen bilden,

36:13.100 --> 36:14.520
Menge von Wörtern bilden.

36:15.640 --> 36:19.160
Also wenn man sagt, Menge aller Wörter der Länge n über dem Alphabet

36:19.160 --> 36:26.240
Sigma, dann bezeichnet man diese Menge mit Sigma hoch n.

36:27.260 --> 36:32.200
Also Sigma hoch 0, das ist genau die Menge, die nur das leere Wort

36:32.200 --> 36:32.660
enthält.

36:33.760 --> 36:37.980
Also es sind alle Wörter über Sigma der Länge 0, das leere Wort.

36:38.680 --> 36:43.020
Sigma hoch 1, alle Wörter über Sigma der Länge 1, das sind zwei

36:43.020 --> 36:46.840
Wörter, das Wort 0 und das Wort 1.

36:47.200 --> 36:50.160
Also die beiden Symbole haben wir in Sigma, entsprechend ist Sigma

36:50.160 --> 36:52.980
oben 1, die Menge 0, 1.

36:53.580 --> 36:56.920
Menge aller Wörter der Länge 2, das ist noch überschaubar, alles was

36:56.920 --> 37:01.760
Sie über 0, 1 bilden können, an Zeichen folgen, der Länge 2, das ist

37:01.760 --> 37:04.580
0, 0, 0, 1, 1, 0, 1, 1.

37:05.160 --> 37:05.940
Das sind die vier.

37:06.060 --> 37:07.900
Und das können Sie natürlich jetzt immer so weiter treiben.

37:08.340 --> 37:09.840
Sigma hoch 17 und so.

37:09.840 --> 37:12.080
Das wären natürlich sehr schnell sehr viel mehr Wörter.

37:13.320 --> 37:17.760
Was man hier macht, ist also, dass man Zeichen aneinanderhängt.

37:18.340 --> 37:21.720
Und so wie man Zeichen aneinanderhängt, kann man natürlich auch Folgen

37:21.720 --> 37:24.660
von Zeichen aneinanderhängen, also Wörter aneinanderhängen.

37:24.880 --> 37:27.580
Und das ist der Begriff der Konkatenation.

37:28.220 --> 37:31.840
Wenn Sie zwei beliebige Wörter, W1 und W2, betrachten, dann können Sie

37:31.840 --> 37:32.840
die konkatenieren.

37:33.400 --> 37:37.880
Wir schreiben dann, wenn wir W1 und W2 in der Reihenfolge

37:37.880 --> 37:42.540
konkatenieren, W1 Pünktchen W2, oder W1 mal W2.

37:42.960 --> 37:46.140
Das schreiben wir aber abgekürzt, meistens ohne dieses Symbol in der

37:46.140 --> 37:46.280
Mitte.

37:46.460 --> 37:47.300
Also W1 W2.

37:48.100 --> 37:50.840
Das ist einfach das Wort W1 und W2 drangehängt.

37:51.480 --> 38:01.780
Also wenn W1 001 ist und W2 110, dann ist W1 konkateniert W2 001 110.

38:03.600 --> 38:08.580
Also Sie können aus Wörtern weitere Wörter bilden durch Konkatenation.

38:08.980 --> 38:13.500
Sie können natürlich ein Wort W auch K-fach mit sich selbst

38:13.500 --> 38:14.500
konkatenieren.

38:17.480 --> 38:21.060
W konkateniert W, konkateniert W und so weiter.

38:21.340 --> 38:24.820
K -mal, so was nennt man dann, bezeichnet man mit W hoch K.

38:25.900 --> 38:30.640
Also wenn unser Wort 1 ans 0 ist, dann können Sie das auch 0 mal mit

38:30.640 --> 38:31.980
sich selbst konkatenieren.

38:32.560 --> 38:33.660
Das ist W hoch 0.

38:33.940 --> 38:35.480
Das ist dann natürlich wieder das leere Wort.

38:36.760 --> 38:44.180
Oder eben nur einmal hinschreiben W um 1, das ist das Wort selber.

38:44.620 --> 38:47.760
Oder eben einmal mit sich selbst konkatenieren.

38:48.440 --> 38:57.180
Also W konkateniert W, W um 2, das ist 110 110, oder 3 mal und so

38:57.180 --> 38:57.440
weiter.

39:01.080 --> 39:04.140
Das ist so das, was man mit Wörtern anstellen kann.

39:05.140 --> 39:11.360
Und jetzt kann man Mengen von Wörtern als Sprachen auffassen.

39:14.120 --> 39:20.560
Und wir sagen ganz einfach, so eine Menge L ist eine formale Sprache

39:20.560 --> 39:25.700
über einem Alphabet Sigma, wenn dieses L einfach eine Teilmenge von

39:25.700 --> 39:31.400
Sigma Stern ist, also Teilmenge der Menge aller möglichen Wörter, die

39:31.400 --> 39:33.860
man über Sigma bilden kann.

39:34.440 --> 39:38.460
Also irgendeine Teilmenge aus Sigma Stern nennen wir formale Sprache.

39:40.160 --> 39:40.780
Beispiel.

39:42.320 --> 39:45.340
Klar, man kann das jetzt irgendwie hinschreiben, eine bestimmte

39:45.340 --> 39:47.760
formale Sprache, indem man einfach die Wörter aufzählt.

39:48.680 --> 39:51.960
Sie haben sehr oft natürlich formale Sprachen, die unendlich sind.

39:52.340 --> 39:56.580
Die also einfach hinzuschreiben, indem sie Wörter aufzählen, das führt

39:56.580 --> 39:57.260
zu nichts.

39:58.200 --> 40:00.260
Sie werden die also irgendwie beschreiben wollen.

40:01.140 --> 40:04.980
Und jetzt kann man das vielleicht so entsprechend der Anschauung

40:04.980 --> 40:07.860
beschreiben, dass man sagt, naja, gut, also, ich kann hier Wörter über

40:07.860 --> 40:11.800
0,1 bilden, jetzt will ich als formale Sprache gerade die Wörter über

40:11.800 --> 40:15.340
0,1, die als vorletztes Symbol eine 0 haben.

40:19.970 --> 40:24.550
Sprache L' aller Wörter, deren vorletztes Zeichen 0 ist.

40:25.210 --> 40:28.690
Das kann man natürlich beschreiben, das sind Wörter, die sehen so aus.

40:28.950 --> 40:32.410
Erst kommt irgend so ein Wort W, kann beliebig lang sein, kann

40:32.410 --> 40:37.610
beliebig, beliebiges Wort aus Sigma Stern sein, also beliebige Folge

40:37.610 --> 40:38.630
von Nullen und Einsen.

40:39.690 --> 40:43.190
Und dann kommt das vorletzte Symbol, das soll 0 sein, und dann das

40:43.190 --> 40:44.070
letzte Symbol.

40:44.670 --> 40:46.330
Das darf 0 oder 1 sein.

40:46.930 --> 40:50.070
Das heißt also, die Sprache L' aller Wörter, deren vorletztes Zeichen

40:50.070 --> 40:53.950
0 ist, natürlich Wörter über Sigma, Sigma gleich 0,1.

40:54.690 --> 40:59.950
Das ist gerade die Menge L' aller Wörter, die so aussehen.

41:01.030 --> 41:02.730
W, 0, Z.

41:03.110 --> 41:07.170
W ist ein Wort aus Sigma Stern, Z ist ein Symbol aus Sigma.

41:10.070 --> 41:13.330
Das Produkt, jetzt kann man natürlich aus solchen Sprachen ein Produkt

41:13.330 --> 41:13.910
bilden.

41:15.830 --> 41:21.070
Das Produkt von zwei Sprachen, L'1 und L'2, das definieren wir als, na

41:21.070 --> 41:23.190
gut, das ist die Sprache, die rauskommt.

41:23.630 --> 41:28.050
Wenn man beliebiges Wort aus L'1 konkateniert mit einem beliebigen

41:28.050 --> 41:29.130
Wort aus L'2.

41:29.910 --> 41:33.330
Also L'1, Produkt L'1 mal L'2.

41:34.370 --> 41:40.250
Der Sprachen L'1 und L'2 ist definiert als die Menge der Wörter W1

41:40.250 --> 41:44.070
gefolgt von W2 oder konkateniert mit W2.

41:44.430 --> 41:46.990
W1 ist aus L'1, W2 ist aus L'2.

41:51.080 --> 41:54.940
Wenn man die Sprache hier oben betrachtet, könnte man fragen, kann man

41:54.940 --> 42:00.880
die mittels Produktbildung aus anderen Sprachen erzeugen?

42:01.900 --> 42:06.120
Also die Sprache, deren vorletztes Symbol Null ist, kann ich die

42:06.120 --> 42:08.160
irgendwie erzeugen aus anderen Sprachen?

42:09.760 --> 42:11.880
Einfach per Produktbildung?

42:12.700 --> 42:16.200
Na gut, also sieht ja schon so danach aus.

42:16.580 --> 42:21.180
Also irgendwie die Sprache aller beliebigen Wörter, also die Sigma

42:21.180 --> 42:24.140
Stern, das ist ja natürlich auch eine formale Sprache, die kann ich

42:24.140 --> 42:27.680
gebrauchen und die konkateniere ich jetzt einfach mit einer Sprache,

42:28.740 --> 42:31.200
wo die Wörter genau dieses Schema haben.

42:33.880 --> 42:34.980
Sieht so aus.

42:35.820 --> 42:40.060
Also diese Sprache hier, die ist das Produkt aus Sigma Stern und der

42:40.060 --> 42:46.180
Menge mit den zwei Wörtern 00 und 01, also mit allen möglichen

42:46.180 --> 42:49.900
Wörtern, die es gibt, die diese Form hier haben, 0z, z ist aus Sigma.

42:50.200 --> 42:53.320
Wenn Sigma 01 ist, ist das einfach nur diese Menge hier.

42:54.880 --> 42:58.460
Okay, das ist jetzt schon so ein erstes Beispiel, wie man systematisch

42:58.460 --> 43:02.800
aus Sprachen, neue Sprachen bilden kann, oder aber andersrum, wie man

43:02.800 --> 43:07.940
systematisch eine Sprache, die ich hier so mit Worten beschrieben

43:07.940 --> 43:10.840
habe, auch anders beschreiben kann.

43:11.840 --> 43:17.020
Also Menge der Wörter, deren vorletztes Zeichen 0 ist, über dem

43:17.020 --> 43:22.380
Alphabet 01, kann ich auch beschreiben als, ja, das ist die Sprache,

43:22.520 --> 43:26.180
die ich bekomme, wenn ich das Produkt bilde aus der Sprache Sigma

43:26.180 --> 43:30.360
Stern und der Sprache, die nur aus den Wörtern 00 und 01 besteht.

43:32.780 --> 43:37.600
So, jetzt kann ich natürlich eine beliebige Sprache k-mal mit sich

43:37.600 --> 43:42.600
selbst multiplizieren, ja, also das Produkt der Sprache mit sich

43:42.600 --> 43:49.400
selber bilden k-mal, das schreiben wir dann als Sprache L hoch K, etwa

43:49.400 --> 43:53.580
wenn die Sprache jetzt, die Sprache bestehend aus zwei Wörtern, dem

43:53.580 --> 43:59.780
Wort 00 und dem Wort 01 ist, die wir hier zugrunde legen, also L, dann

43:59.780 --> 44:08.780
ist L hoch 0, naja gut, also die Sprache 0-mal Produkt gebildet sind

44:08.780 --> 44:13.400
genau die Wörter der Länge 0 über der Sprache, das ist Epsilon, also

44:13.400 --> 44:16.860
über der Sprache, nicht aus der Sprache, sondern über der Sprache, das

44:16.860 --> 44:21.000
ist Epsilon, L hoch 1, das ist die Sprache selber, L hoch 2 ist alles,

44:21.460 --> 44:25.000
was ich bekomme, wenn ich die beiden Wörter, die hier drin sind,

44:26.100 --> 44:30.940
konkateniere beliebig mit wiederum den beiden Wörtern, die hier drin

44:30.940 --> 44:31.180
sind.

44:31.440 --> 44:37.320
Also die Sprache L mal der Sprache L bilde, und das ist sozusagen per

44:37.320 --> 44:41.740
Definition Konkatenation aller Wörter hier drin, mit allen Wörtern

44:41.740 --> 44:46.160
hier drin, alle Möglichkeiten, das wäre also 0,0 mal 0,0, das ist 0,0

44:46.160 --> 44:52.560
,0,0, oder 0,0,1 mal 1, das ist 0,0,1, oder 1 mal 0,0, das ist 1,0,0,

44:52.640 --> 44:55.380
oder 1 mal 1, das ist 1,1, und so weiter.

44:59.780 --> 45:05.660
Gut, wenn man über Wörter, die irgendwie strukturiert sind, sprechen

45:05.660 --> 45:09.840
will, also gerade deren Struktur, die so auseinandernehmen will, wie

45:09.840 --> 45:13.700
wir es hier etwa gemacht haben, das sind Wörter, die sehen so aus,

45:13.840 --> 45:18.100
vorne ist ein Wort, ein beliebiges, dann kommt ein Zeichen 0, und dann

45:18.100 --> 45:23.280
kommt ein weiteres Zeichen, dann spricht man auch von Präfix, Teilwort

45:23.280 --> 45:25.420
und Suffix eines Wortes.

45:26.800 --> 45:31.620
Präfixe ist das, was am Anfang steht, die Suffixe ist das, was am

45:31.620 --> 45:35.360
Schluss steht, und die Teilworte ist das, was in der Mitte steht.

45:35.560 --> 45:41.040
Also, wenn wir über das Wort Tal sprechen wollen, in dem Sinne, dass

45:41.040 --> 45:43.920
wir über das, was vorne stehen kann, oder das, was hinten stehen kann,

45:44.040 --> 45:49.420
oder das, was in der Mitte stehen kann, sprechen wir von den Präfixen.

45:49.540 --> 45:53.780
Die Präfixe hiervon, wenn wir alle Präfixe aufzählen wollen, alle

45:53.780 --> 46:00.640
vorderen Teile sind natürlich das T, natürlich TA und natürlich das

46:00.640 --> 46:03.740
ganze Wort, aber nicht vergessen, auch das leere Wort.

46:04.380 --> 46:09.960
Also, wenn wir alle Präfixe von dem Wort Tal hinschreiben wollen, dann

46:09.960 --> 46:14.540
ist das das leere Wort, das T, TA und Tal selbst.

46:15.040 --> 46:18.520
Und für die Suffixe analog, wenn wir es von hinten angucken, natürlich

46:18.520 --> 46:22.140
das leere Wort oder nur L oder AL oder Tal.

46:23.060 --> 46:27.780
Und die Teilworte, na gut, alles, was in der Mitte steht und aber

46:27.780 --> 46:33.540
überhaupt alles, was sozusagen dazwischen stehen kann, das ist

46:33.540 --> 46:37.340
natürlich die Mitte, also A, aber natürlich auch alle Präfixe und alle

46:37.340 --> 46:37.820
Suffixe.

46:44.050 --> 46:49.190
Okay, so, jetzt kann man systematisch aus formalen Sprachen weitere

46:49.190 --> 46:54.610
formale Sprachen bilden, etwa Produktbildung, haben wir schon

46:54.610 --> 46:59.270
angeguckt, also die Produktsprache aus zwei formalen Sprachen, L1 und

46:59.270 --> 47:06.170
L2, ist die Menge aller Worte W1 konkateniert W2, mit W1 ist in L1 und

47:06.170 --> 47:07.310
W2 ist in L2.

47:07.310 --> 47:12.570
Das K-fache Produkt haben wir auch schon angeguckt, L hoch K, Menge

47:12.570 --> 47:20.770
aller Wörter W1 bis WK aneinandergereiht, WI ist ein Wort aus L, für I

47:20.770 --> 47:21.750
zwischen 1 und K.

47:22.930 --> 47:27.910
Man kann auch das K-fache Produkt für K gleich 0 bilden, das ist

47:27.910 --> 47:31.090
gerade die Menge mit dem leeren Wort.

47:33.050 --> 47:36.570
Und jetzt neu, man kann auch eine Quotientensprache bilden, also ich

47:36.570 --> 47:41.890
habe zwei formale Sprachen über dem selben Alphabet, Sprache L1 und

47:41.890 --> 47:46.510
Sprache L2 und bilde jetzt sozusagen in Umkehrung von der

47:46.510 --> 47:53.490
Produktbildung die Quotientensprache L1 durch L2.

47:55.350 --> 47:58.910
Das ist natürlich das, was man sich auch sinnvollerweise hier

47:58.910 --> 48:04.370
überlegen würde, das sind alle die Wörter über dem Alphabet Sigma oder

48:04.370 --> 48:11.830
aus der Menge Sigma Stern, für die ich ein Wort aus L2 finden kann,

48:12.330 --> 48:18.530
sodass W konkateniert mit diesem Wort aus L2 gerade ein Wort aus L1

48:18.530 --> 48:18.930
ergibt.

48:19.750 --> 48:24.410
Also wenn ich hier hinten anfange, also das sind die W, für die es W

48:24.410 --> 48:30.150
mal Z aus L1 gibt, sodass ich ein Z finde, das in L2 ist.

48:30.150 --> 48:38.490
Also L1 durch L2, ich kürze hier hinten in einem langen Wort aus L1

48:38.490 --> 48:41.750
den hinteren Teil, der aus L2 ist, weg.

48:42.770 --> 48:46.510
Das, was ich dabei kriege, ist ein Wort aus L1, aus der

48:46.510 --> 48:48.290
Quotientensprache L1 durch L2.

48:49.590 --> 48:53.330
Dann der klinische Abschluss, das ist das, was wir mit Sigma schon

48:53.330 --> 48:56.210
gemacht haben, wenn wir Sigma Stern gebildet haben, gesagt haben, alle

48:56.210 --> 49:00.530
möglichen Wörter, die man über dem Alphabet Sigma bilden kann, bilden

49:00.530 --> 49:01.270
Sigma Stern.

49:01.630 --> 49:03.630
Sowas kann ich natürlich auch mit der Sprache machen.

49:04.750 --> 49:08.530
Der klinische Abschluss einer Sprache L ist alles, was ich durch

49:08.530 --> 49:11.890
Konkatenation möglicherweise über L kriegen kann.

49:13.350 --> 49:15.710
Das kann ich natürlich auch systematisch hinschreiben.

49:16.330 --> 49:20.570
Was kann ich alles aus L durch Konkatenation, beliebige Konkatenation

49:20.570 --> 49:23.610
von Worten aus L miteinander bekommen?

49:23.710 --> 49:26.850
Da kann ich L hoch 0 bekommen, L hoch 1, L hoch 2 und so weiter.

49:27.450 --> 49:31.250
Das heißt also, der klinische Abschluss der Sprache L, das schreiben

49:31.250 --> 49:35.950
wir eben auch als L Sternchen, das ist die Vereinigung I größer gleich

49:35.950 --> 49:39.130
0 L oben I.

49:40.170 --> 49:45.270
Das ist die Vereinigung von L oben 0 mit L oben 1, L oben 2 und so

49:45.270 --> 49:45.710
weiter.

49:46.350 --> 49:47.470
Beliebig lang.

49:50.210 --> 49:55.770
Da ist dann insbesondere da L oben 0 oder L hoch 0 dabei ist, auch das

49:55.770 --> 49:59.590
leere Wort drin, selbst wenn in L das leere Wort nicht drin war.

49:59.870 --> 50:01.850
Das kriege ich durch den klinischen Abschluss rein.

50:02.290 --> 50:05.270
Wenn ich das nicht drin haben will, kann ich auch den positiven

50:05.270 --> 50:06.150
Abschluss bilden.

50:06.450 --> 50:09.550
Da fange ich hier erst bei I größer gleich 1 an.

50:10.270 --> 50:11.690
Das ist also L oben Plus.

50:12.170 --> 50:16.850
Das ist L hoch 1 vereinigt L hoch 2, vereinigt L hoch 3 und so weiter.

50:18.550 --> 50:23.550
Und natürlich, da Sprachenmengen sind, kann ich auch Mengenoperationen

50:23.550 --> 50:24.150
durchführen.

50:26.250 --> 50:29.410
Vereinigungen ja sowieso, aber eben auch Komplementmenge.

50:30.050 --> 50:34.790
Also wenn ich eine Sprache habe, über dem Alphabet Sigma, dann ist die

50:34.790 --> 50:37.230
Sprache natürlich eine Teilmenge von Sigma Stern.

50:37.690 --> 50:40.010
Kann ich natürlich auch das Komplement der Sprache betrachten.

50:40.630 --> 50:43.510
Sigma Stern ohne die Sprache, das Komplement der Sprache.

50:46.610 --> 50:52.050
Jetzt haben wir also schon systematisch aus Wörtern neue Worte

50:52.050 --> 50:55.350
gebildet und aus Sprachen neue Sprachen gebildet.

50:55.950 --> 51:00.570
Und auf dieser Systematik oder einer solchen Systematik beruhen auch

51:00.570 --> 51:05.370
reguläre Sprachen, also die Definition einer regulären Sprache.

51:05.910 --> 51:10.390
Eine reguläre Sprache über einem Alphabet Sigma ist eine ganz

51:10.390 --> 51:12.130
bestimmte formale Sprache.

51:12.430 --> 51:14.550
L Teilmenge Sigma Stern.

51:15.230 --> 51:19.150
Formale Sprache L Teilmenge Sigma Stern, die ich auf eine ganz

51:19.150 --> 51:22.910
systematische Art aufbauen kann.

51:24.090 --> 51:26.790
Das ist sozusagen eine induktive Definition.

51:27.570 --> 51:32.010
Ich sage erstmal, was sind sozusagen die Anfangssprachen, die ich auf

51:32.010 --> 51:34.970
jeden Fall schon mal als regulär deklariere.

51:36.050 --> 51:39.070
Und wie kriege ich aus regulären Sprachen neue reguläre Sprachen?

51:39.330 --> 51:41.910
Also insbesondere aus diesen Anfangssprachen neue Sprachen.

51:42.290 --> 51:50.290
Die Anfangssprachen sind ja alle einelementigen Sprachen über dem

51:50.290 --> 51:51.210
Alphabet Sigma.

51:51.690 --> 51:56.790
Also für jedes Symbol aus Sigma jeweils die Sprache, die ich bekomme,

51:56.910 --> 52:00.970
wenn ich die Menge, die nur dieses eine Symbol enthält, bilde.

52:01.710 --> 52:05.950
Einerseits die eine Sorte von Anfangssprachen und andererseits die

52:05.950 --> 52:06.370
leere Menge.

52:07.390 --> 52:09.430
Die leere Menge ist eine reguläre Sprache.

52:09.930 --> 52:10.350
Warum nicht?

52:12.410 --> 52:17.430
Und dann kriege ich weitere reguläre Sprachen, indem ich aus solchen

52:17.430 --> 52:23.170
Sprachen neue Sprachen bilde über im Prinzip drei Sorten von, also

52:23.170 --> 52:27.090
eigentlich zwei, aber im Allgemeinen drei Sorten von Operationen.

52:27.450 --> 52:31.530
Wenn ich zwei reguläre Sprachen habe, dann ist deren Produkt wieder

52:31.530 --> 52:33.070
regulär, per Definition.

52:33.850 --> 52:37.290
Dann ist deren Vereinigung wieder regulär, per Definition.

52:37.590 --> 52:40.510
Und für eine reguläre Sprache ist der klinische Abschluss wieder

52:40.510 --> 52:42.410
regulär, per Definition.

52:44.690 --> 52:47.850
Also Produktbildung und Vereinigungsbildung, aber eben auch die

52:47.850 --> 52:51.270
Produktbildung, die dazu führt, dass ich den klinischen Abschluss

52:51.270 --> 52:51.810
habe.

52:52.890 --> 52:56.290
Wo also insbesondere auch dann plötzlich das leere Wort mit reinkommt,

52:56.390 --> 52:59.870
auch wenn ich es vielleicht vorher in der Sprache nicht drin hatte.

53:00.750 --> 53:02.110
Also das sind die regulären Sprachen.

53:02.590 --> 53:04.610
Haben Sie schon gesehen, da bin ich mir ziemlich sicher.

53:06.450 --> 53:09.870
So, das ist die erste Klasse von Sprachen, die uns genauer

53:09.870 --> 53:10.490
interessiert.

53:13.690 --> 53:19.010
Und wenn man also auf diese systematische Art und Weise reguläre

53:19.010 --> 53:22.590
Sprachen definieren kann, dann kann man sie auch entsprechend schön

53:22.590 --> 53:23.130
beschreiben.

53:23.910 --> 53:26.350
Und jetzt wäre so die erste Frage einfach als ein Beispiel.

53:26.470 --> 53:28.830
Die Sprache, die wir eben schon mal als Beispiel hatten.

53:29.870 --> 53:34.510
Menge aller Wörter über 0,1, deren vorletztes Symbol eine 0 ist.

53:35.150 --> 53:36.590
Ist das eine reguläre Sprache?

53:36.590 --> 53:41.170
Kann ich die systematisch aufbauen, so wie per Definition reguläre

53:41.170 --> 53:42.430
Sprachen aufgebaut sind?

53:43.810 --> 53:45.530
Die Antwort ist ja.

53:47.530 --> 53:48.290
Machen wir es mal.

53:48.410 --> 53:53.250
Ich muss dafür sorgen, dass ich an der vorletzten Stelle eine 0 habe.

53:54.330 --> 53:55.590
Wie sehen die Wörter aus?

53:55.650 --> 53:59.070
Vorne steht was Beliebiges, dann kommt eine 0 und dann kommt eine 0

53:59.070 --> 53:59.870
oder eine 1.

54:01.150 --> 54:04.270
Entsprechend dieser Überlegung sehen die so aus.

54:04.270 --> 54:06.050
Also vorne kommt was Beliebiges.

54:09.230 --> 54:10.370
Konkateniert mit einer 0.

54:10.710 --> 54:12.630
Konkateniert mit 0 oder 1.

54:14.770 --> 54:16.510
Jetzt in Sprachen ausgedrückt.

54:17.090 --> 54:20.270
Also die Sprache für das, was hinten stehen kann.

54:20.510 --> 54:22.310
Also hinten kann eine 0 stehen oder eine 1.

54:23.010 --> 54:27.110
Das ist die Sprache, die ich bekomme, indem ich die beiden regulären

54:27.110 --> 54:32.550
Anfangssprachen Menge mit dem Element 0 und Menge mit dem Element 1

54:33.530 --> 54:34.570
einfach vereinige.

54:36.450 --> 54:39.390
Nach Definition regulärer Sprachen kommt da wieder eine reguläre

54:39.390 --> 54:40.010
Sprache raus.

54:40.170 --> 54:43.210
Also nach Definition regulärer Sprachen ist das eine reguläre Sprache,

54:43.330 --> 54:45.350
das eine reguläre Sprache und die Vereinigung auch.

54:45.730 --> 54:48.830
Also da hinten, das habe ich schon mal wie eine reguläre Sprache

54:48.830 --> 54:49.330
beschrieben.

54:50.050 --> 54:52.450
An der vorletzten Stelle muss eine 0 stehen.

54:52.670 --> 54:54.550
Dafür habe ich auch eine entsprechende Sprache.

54:54.670 --> 54:57.330
Ich nehme wieder die Sprache, die nur 0 enthält.

54:57.510 --> 54:59.550
Und vorne darf was Beliebiges stehen.

54:59.550 --> 55:05.370
Naja gut, das ist die Menge 0, vereinigt mit der Menge 1, die

55:05.370 --> 55:09.890
entsprechende Sprache genommen und davon einen klinischen Abschluss

55:09.890 --> 55:10.470
gebildet.

55:10.930 --> 55:13.390
Dann kriege ich alles, was ich über 0,1 kriegen kann.

55:14.030 --> 55:17.630
Das heißt also, ich habe hier diese Sprache L, der Menge aller Wörter

55:17.630 --> 55:23.810
über 0,1, deren vorletztes Symbol 0 ist, aufgebaut, systematisch, so

55:23.810 --> 55:26.850
wie reguläre Sprachen aufgebaut werden bei Definition.

55:26.850 --> 55:28.950
Das heißt also, das ist eine reguläre Sprache.

55:29.090 --> 55:30.190
Ich kann sie so hinschreiben.

55:31.690 --> 55:35.570
Natürlich habe ich da jetzt eine verschiedene Art von Regeln

55:35.570 --> 55:36.010
verwendet.

55:36.110 --> 55:39.770
Ich habe Anfangssprachen genommen, damit irgendwie muss ich anfangen.

55:40.770 --> 55:42.850
Das ist sozusagen die Regel 1, sage ich mal.

55:43.290 --> 55:47.150
Ich habe zum Beispiel Vereinigung gebildet, das war die Regel 4.

55:48.610 --> 55:49.450
Produktionsform 4.

55:50.310 --> 55:53.430
Ich habe den klinischen Abschluss gebildet, Produktionsform 5.

55:53.950 --> 55:57.090
Ich habe Konkatenationen gebildet, hier und hier.

55:57.650 --> 55:59.430
Das ist die Produktionsform 3.

56:01.310 --> 56:08.990
Nach der Nummerierung einfach hier 1, 2, 3, 4, 5, durchnummerieren.

56:16.250 --> 56:18.970
Das, was wir hier gemacht haben, ist, wir haben jetzt nicht nur

56:18.970 --> 56:23.190
nachgewiesen, dass diese Sprache regulär ist, sondern wir haben sie

56:23.190 --> 56:24.470
auch schon gleich schön beschrieben.

56:24.990 --> 56:28.850
Und diese Beschreibungsart, die kennen Sie auch unter dem Term

56:29.390 --> 56:30.330
regulärer Ausdruck.

56:31.070 --> 56:34.150
Wir werden hier reguläre Ausdrücke ein bisschen anders schreiben, also

56:34.150 --> 56:38.390
eine vereinfachte Schreibweise verwenden für reguläre Ausdrücke.

56:41.510 --> 56:45.550
Und dann eben auch genauso sagen, wenn wir eine reguläre Sprache über

56:45.550 --> 56:48.550
einem Alphabet Sigma haben, dann können wir sie beschreiben durch

56:49.290 --> 56:51.650
einen regulären Ausdruck.

56:51.650 --> 56:56.390
Und reguläre Ausdrücke jetzt hier sind folgendes.

56:56.830 --> 57:00.890
Also das hier, das ist das Symbol für leere Menge, aber ich sag mal

57:00.890 --> 57:03.970
einfach ein bisschen dicker hingezeichnet oder ein bisschen runder.

57:04.890 --> 57:10.150
Das bezeichnet den regulären Ausdruck, der gerade die leere Menge

57:10.150 --> 57:10.890
beschreibt.

57:11.270 --> 57:15.690
Also den regulären Ausdruck, der die Sprache, die gleich leere Menge

57:15.690 --> 57:16.790
ist, beschreibt.

57:18.130 --> 57:25.350
Genauso schreiben wir als dick, kleinen Epsilon, den regulären

57:25.350 --> 57:30.710
Ausdruck, der die Menge, die das leere Wort enthält, beschreibt.

57:31.250 --> 57:37.610
Und dick A als den regulären Ausdruck, der die Menge, die nur das

57:37.610 --> 57:39.770
Symbol A enthält, beschreibt.

57:40.310 --> 57:42.210
So schreiben wir reguläre Ausdrücke.

57:43.030 --> 57:46.730
Also erst mal die Anfangsausdrücke und dann, wenn wir zwei reguläre

57:46.730 --> 57:47.750
Ausdrücke haben...

57:47.750 --> 57:47.750
Ja,

57:59.360 --> 58:00.720
aber wir benutzen trotzdem eins.

58:04.760 --> 58:07.860
Das ist richtig, was Sie gesagt haben, wir benutzen trotzdem eins.

58:08.220 --> 58:12.140
Und wenn wir zwei reguläre Ausdrücke haben, Alpha und Beta, die

58:12.140 --> 58:15.400
Sprachen L von Alpha, also die Sprache, die durch den regulären

58:15.400 --> 58:20.800
Ausdruck Alpha beschrieben wird, und L von Beta beschreiben, so

58:20.800 --> 58:26.700
schreiben wir erst mal in einfacher Form Alpha in Klammern vereinigt

58:26.700 --> 58:32.360
Beta in Klammern als den regulären Ausdruck, der die Sprache L von

58:32.360 --> 58:34.480
Alpha vereinigt L von Beta beschreibt.

58:35.080 --> 58:42.380
Und genauso Alpha in Klammern mal Beta in Klammern beschreibt den

58:42.380 --> 58:46.860
regulären Ausdruck oder bezeichnet den regulären Ausdruck, der die

58:46.860 --> 58:52.580
Sprache L von Alpha mal L von Beta, also Produktsprache von L von

58:52.580 --> 58:53.960
Alpha und L von Beta beschreibt.

58:54.720 --> 59:00.640
Und genauso Alpha in Klammern mit obenem Plus als regulärer Ausdruck,

59:00.760 --> 59:06.260
der die Sprache L von Alpha oben Plus, also positiver Abschluss der

59:06.260 --> 59:10.660
Sprache L von Alpha beschreibt und Alpha in Klammern Stern als den

59:10.660 --> 59:16.580
regulären Ausdruck, der die Sprache klinischer Abschluss von L von

59:16.580 --> 59:17.740
Alpha beschreibt.

59:18.100 --> 59:21.440
Das wären jetzt mal so die grundlegenden Schreibweisen und hier so ein

59:21.440 --> 59:24.260
paar vereinfachtende Notationen.

59:24.460 --> 59:34.040
Also anstatt L von Alpha und an Wort W ist Wort aus der Sprache L von

59:34.040 --> 59:38.460
Alpha, schreiben wir einfach oft nur Alpha, den entsprechenden

59:38.460 --> 59:41.640
regulären Ausdruck hin und W-Element Alpha.

59:42.280 --> 59:44.820
Das sind sozusagen vereinfachte Schreibweisen.

59:46.240 --> 59:48.560
Und dann lassen wir oft auch Klammern weg.

59:48.560 --> 59:54.920
So wie bei arithmetischen Ausdrücken Produkt oder Multiplikation mehr

59:54.920 --> 01:00:01.320
bindet als Addition, bindet hier Konkatenation stärker als Vereinigung

01:00:01.320 --> 01:00:08.540
und klinischer Abschluss bilden bindet stärker als Konkatenation und

01:00:08.540 --> 01:00:12.060
Vereinigung und entsprechend wenn man diese Regeln sozusagen im

01:00:12.060 --> 01:00:15.100
Hinterkopf haben und die sind intuitiv, dann kann man an vielen

01:00:15.100 --> 01:00:16.600
Stellen die Klammern weglassen.

01:00:16.600 --> 01:00:25.540
Etwa, wenn wir das hier eigentlich meinen, was streng genommen so

01:00:25.540 --> 01:00:33.940
aussieht, der reguläre Ausdruck, den man bekommt, wenn man B Produkt C

01:00:33.940 --> 01:00:39.060
schreibt und dann vorne vereinigt mit A da kann man auch hier die

01:00:39.060 --> 01:00:44.020
Klammern weglassen, weil diese Produktbildung stärker bindet.

01:00:44.020 --> 01:00:49.200
Das heißt also, wir lassen ganz oft Klammern weg, wenn klar ist, was

01:00:49.780 --> 01:00:53.440
gemeint ist von der Reihenfolge der Operationen, die angewendet

01:00:53.440 --> 01:00:53.620
werden.

01:00:55.580 --> 01:00:56.980
Ein paar Beispiele.

01:01:00.660 --> 01:01:03.720
Das Beispiel hier hatten wir schon betrachtet.

01:01:04.600 --> 01:01:09.480
Wir haben identifiziert, dass die Sprache aller Wörter über 0,1, deren

01:01:09.820 --> 01:01:13.420
vorletzter Symbol 0 ist, eine reguläre Sprache ist, weil wir sie

01:01:13.420 --> 01:01:18.000
entsprechende Definitionen regulärer Sprachen bilden können.

01:01:19.520 --> 01:01:22.560
Und die Art und Weise, wie wir die Sprache bilden können, die können

01:01:22.560 --> 01:01:25.940
wir durch den entsprechenden regulären Ausdruck beschreiben.

01:01:27.820 --> 01:01:33.480
Und das wäre jetzt in dieser vereinfachten Schreibweise einfach 0

01:01:33.480 --> 01:01:35.640
vereinigt 1 in Klammern.

01:01:36.840 --> 01:01:42.220
Also der klinische Abschluss von 0 vereinigt 1 konkateniert mit 0,

01:01:42.460 --> 01:01:45.500
konkateniert mit 0 vereinigt 1 in Klammern.

01:01:49.460 --> 01:01:52.560
Und hier sieht man, wenn man den regulären Ausdruck so schön schlank

01:01:52.560 --> 01:01:55.780
hingeschrieben hat, sieht man auch, also daran kann man schon

01:01:55.780 --> 01:02:01.860
argumentieren, das ist ein Ausdruck, der genau die Sprache aller

01:02:01.860 --> 01:02:05.740
Wörter über 0,1, wo das vorletzte Symbol 0 ist, beschreibt.

01:02:06.180 --> 01:02:12.880
Vorne kann was Beliebiges stehen über 0,1, hinten ein Symbol, das 0

01:02:12.880 --> 01:02:17.100
oder 1 ist und unmittelbar davor muss eine 0 stehen.

01:02:18.560 --> 01:02:23.120
Es gibt natürlich auch andere Sprachen, die man erstmal so beschreiben

01:02:23.120 --> 01:02:29.060
kann über, wie das Wort aufgebaut ist oder was für Teilworte die

01:02:29.060 --> 01:02:32.920
Wörter unbedingt enthalten müssen oder auch auf keinen Fall enthalten

01:02:32.920 --> 01:02:33.480
dürfen.

01:02:34.160 --> 01:02:39.340
Also ein anderes Beispiel wäre die Menge aller Wörter über 0,1, die 1

01:02:39.340 --> 01:02:41.260
,0 als Teilwort enthalten.

01:02:42.020 --> 01:02:45.240
Also egal, wie das Wort aussieht, irgendwo muss 1,0 vorkommen.

01:02:46.880 --> 01:02:54.300
Also Menge aller W aus 0,1 Sternchen, W enthält 1,0 als Teilwort, kann

01:02:54.300 --> 01:02:57.140
man tatsächlich über so einen regulären Ausdruck beschreiben.

01:02:58.260 --> 01:03:01.840
Irgendwo muss 1,0 stehen, davor was Beliebiges, dahinter was

01:03:01.840 --> 01:03:02.480
Beliebiges.

01:03:03.440 --> 01:03:07.640
Nachdem wir das verstanden haben, wie wir hier diese Sprache über

01:03:07.640 --> 01:03:10.060
einen regulären Ausdruck beschreiben, ist auch klar, wie wir eben

01:03:10.060 --> 01:03:14.460
diese Sprache aller Wörter über 0,1, die 1,0 als Teilwort enthalten

01:03:14.460 --> 01:03:15.500
beschreiben können.

01:03:15.600 --> 01:03:18.780
Also vorne was Beliebiges, hinten was Beliebiges, in der Mitte 1,0.

01:03:20.140 --> 01:03:22.300
Vorne was Beliebiges, hinten was Beliebiges.

01:03:22.460 --> 01:03:26.960
Das was Beliebige ist immer 0 vereinigt 1 in Klammern Sternchen.

01:03:28.300 --> 01:03:32.460
Also ist die Sprache nichts anderes als die, die durch diesen

01:03:32.460 --> 01:03:34.180
regulären Ausdruck beschrieben wird.

01:03:34.620 --> 01:03:38.920
0 vereinigt 1 in Klammern Sternchen, 0,1, 0 vereinigt 1 in Klammern

01:03:38.920 --> 01:03:39.420
Sternchen.

01:03:41.440 --> 01:03:46.980
Oder analog, Menge aller Wörter aus 0,1 Stern.

01:03:47.660 --> 01:03:51.720
W enthält 1,0,1 als Teilwort, also völlig analog.

01:03:51.880 --> 01:03:55.160
In der Mitte 1,0,1, vorne was Beliebiges, hinten was Beliebiges.

01:03:58.380 --> 01:04:04.400
So, jetzt ein bisschen schwieriger ist es vielleicht dann Wörter oder

01:04:04.400 --> 01:04:09.440
Sprachen mit regulären Ausdrücken zu beschreiben, sofern das überhaupt

01:04:09.440 --> 01:04:14.360
geht, in Klammern, die aus Worten bestehen, die ein bestimmtes

01:04:14.360 --> 01:04:16.080
Teilwort nicht enthalten.

01:04:16.960 --> 01:04:18.480
Machen wir das mal zur Übung.

01:04:19.160 --> 01:04:26.340
Also, wir wollen die Sprache aller Wörter über 0,1 die 1,0 nicht als

01:04:26.340 --> 01:04:27.640
Teilwort enthalten.

01:04:28.600 --> 01:04:33.520
Da darf alles Mögliche vorkommen, nur wenn irgendwo eine 1 vorkommt,

01:04:34.420 --> 01:04:38.480
darf unmittelbar dahinter keine 0 vorkommen.

01:04:39.840 --> 01:04:44.440
Und ich behaupte jetzt einfach mal, diese Sprache lässt sich durch

01:04:44.440 --> 01:04:49.740
diesen regulären Ausdruck beschreiben, regulärer Ausdruck, 0

01:04:49.740 --> 01:04:51.380
Sternchen, 1 Sternchen.

01:04:54.770 --> 01:04:59.070
Also, klinischer Abschluss der Sprache, die aus 0 entsteht,

01:04:59.650 --> 01:05:03.650
konkateniert mit klinischer Abschluss der Sprache, die aus 1 besteht.

01:05:04.070 --> 01:05:05.490
Das ist das, was hier steht.

01:05:06.450 --> 01:05:07.390
Ist das so?

01:05:07.790 --> 01:05:13.090
Ich habe ja gesagt, diese Wörter, bei denen darf alles vorkommen, nur

01:05:13.090 --> 01:05:16.670
nicht eine 1, auf die unmittelbare 0 folgt.

01:05:16.970 --> 01:05:21.050
Das heißt, wenn irgendwann eine 1 vorkommt, dürfen danach nur noch

01:05:21.050 --> 01:05:23.890
Einsen kommen, wenn überhaupt irgendwas kommt.

01:05:25.190 --> 01:05:29.230
Das heißt also, dass ein Wort, das hier drin ist, das dadurch

01:05:29.230 --> 01:05:32.750
beschrieben ist, in der Sprache ist, ist irgendwie klar.

01:05:33.290 --> 01:05:36.670
Also ein Wort, das hier drin ist, das sieht so aus, beliebige Folgen

01:05:36.670 --> 01:05:40.630
von 0, gefolgt von einer beliebigen Folge von Einsen und sonst gar

01:05:40.630 --> 01:05:42.350
nichts, möglicherweise sogar leeres Wort.

01:05:42.630 --> 01:05:46.670
Es ist klar, dass das ein Wort ist, das 1,0 nicht als Teilwort

01:05:46.670 --> 01:05:47.110
enthält.

01:05:47.590 --> 01:05:51.050
Die Umkehrung, also für diese Gleichheit muss man auch umgekehrt

01:05:51.050 --> 01:05:56.270
zeigen, alle Wörter, die hier drin sind, sind Wörter, die 1,0 nicht

01:05:56.270 --> 01:05:56.850
enthalten.

01:05:57.890 --> 01:05:59.530
Gut, sei also...

01:05:59.530 --> 01:06:00.710
Nee, umgekehrt.

01:06:01.050 --> 01:06:04.410
Alle Wörter, die hier drin sind, sind dadurch beschrieben.

01:06:05.410 --> 01:06:10.170
Sei also W ein Wort aus der Sprache, also ein Wort, das 1,0 nicht als

01:06:10.170 --> 01:06:11.150
Teilwort enthält.

01:06:12.790 --> 01:06:16.290
Das heißt, nach der ersten Eins kommen, wenn überhaupt, nur Nullen.

01:06:17.350 --> 01:06:19.890
Das heißt, das Wort sieht so aus.

01:06:20.570 --> 01:06:25.950
Ich schreibe alles hin, kompakt, als W, bis zur ersten Eins.

01:06:28.230 --> 01:06:32.330
Das W ist W' und dann die erste Eins.

01:06:32.830 --> 01:06:35.750
Und weil danach nur noch Einsen kommen können, kann danach, wenn ich

01:06:35.750 --> 01:06:38.930
das ausschreibe, nur noch 1,1,1,1,1 kommen.

01:06:39.370 --> 01:06:43.050
Wobei W' eben der Anfang ist, wo noch keine Eins vorkommt.

01:06:43.550 --> 01:06:46.930
Also W aus dieser Sprache ist auf jeden Fall ein Wort.

01:06:48.810 --> 01:06:52.410
Da ist ein Anfangsteil, in dem kommt keine Eins vor und dann kommt ein

01:06:52.410 --> 01:06:55.810
zweiter Teil, der Teil ab der ersten Eins.

01:06:55.910 --> 01:07:01.030
Und der Teil ab der ersten Eins besteht nur aus Einsen, kann also so

01:07:01.030 --> 01:07:01.850
beschrieben werden.

01:07:02.230 --> 01:07:05.470
Das heißt also, das Wort insgesamt, wenn hier keine Eins vorkommen

01:07:05.470 --> 01:07:08.210
kann, ist tatsächlich eines, was so beschrieben werden kann.

01:07:09.030 --> 01:07:12.170
Das war jetzt natürlich keine schwierige Argumentation.

01:07:12.410 --> 01:07:15.650
Ich wollte damit nur klar machen, man muss schon aufpassen, wenn man

01:07:15.650 --> 01:07:18.190
so Gleichheit beweisen will.

01:07:18.190 --> 01:07:23.850
Eine Sprache, die auf eine bestimmte Art beschrieben wird, ist gleich

01:07:23.850 --> 01:07:27.150
der Sprache, die durch diesen regulären Ausdruck beschrieben wird,

01:07:27.410 --> 01:07:28.870
dass man dann auch zwei Richtungen hat.

01:07:29.410 --> 01:07:32.870
Alles, was hier drin ist, ist hier drin und alles, was hier drin ist,

01:07:32.950 --> 01:07:33.490
ist hier drin.

01:07:38.000 --> 01:07:42.760
Endliche Automaten, ein weiteres Konzept, was Sie schon in

01:07:45.060 --> 01:07:48.500
Grundbegriffe der Informatik hatten, da wurden insbesondere auch Mealy

01:07:48.500 --> 01:07:50.080
und Moore Automaten behandelt.

01:07:51.140 --> 01:07:53.320
Hier betrachten wir die gar nicht weiter.

01:07:53.520 --> 01:07:56.300
Diese Mealy und Moore Automaten, das sind ja auch Automaten, wo eine

01:07:56.300 --> 01:07:57.700
Ausgabe gebildet wird.

01:07:58.960 --> 01:08:01.280
Die benutzen wir hier nicht, weil wir sie nicht brauchen.

01:08:01.560 --> 01:08:05.380
Wir benutzen hier eigentlich nur endliche Automaten, die was

01:08:05.380 --> 01:08:08.740
akzeptieren können, die bestimmte Worte akzeptieren.

01:08:09.180 --> 01:08:10.500
Also endliche Akzeptoren.

01:08:12.380 --> 01:08:16.280
Ein endlicher Automat sieht, das wissen Sie, folgendermaßen aus.

01:08:16.640 --> 01:08:19.140
Ich fange jetzt erstmal an mit einem deterministischen endlichen

01:08:19.140 --> 01:08:19.720
Automat.

01:08:19.820 --> 01:08:22.220
Wir werden jetzt erstmal eine Weile auch gar keine nicht

01:08:22.220 --> 01:08:24.600
-deterministischen endlichen Automaten betrachten.

01:08:25.440 --> 01:08:28.440
Deshalb so in Klammern deterministischer endlicher Automat.

01:08:28.820 --> 01:08:30.820
Er wird durch so ein Fünftuppel beschrieben.

01:08:31.740 --> 01:08:34.980
Q Sigma Delta klein s groß f.

01:08:35.320 --> 01:08:37.860
Q ist eine endliche Menge von Zuständen.

01:08:38.400 --> 01:08:42.220
Sigma eine endliche Menge von Eingabesymbolen oder andersrum ein

01:08:42.220 --> 01:08:43.660
Alphabet, ein endliches.

01:08:43.660 --> 01:08:45.660
Delta eine Übergangsfunktion.

01:08:46.960 --> 01:08:53.840
Da wird ein Zustand genommen, ein Symbol und dieses Paar überführt in

01:08:53.840 --> 01:08:55.300
einen neuen Zustand.

01:08:56.020 --> 01:08:57.800
Also Übergangsfunktion.

01:08:59.300 --> 01:09:03.600
Ein ausgezeichneter Zustand S, das ist der Startzustand.

01:09:03.960 --> 01:09:07.100
Eine ausgezeichnete Menge von Zuständen F.

01:09:07.560 --> 01:09:09.400
F wie Final.

01:09:10.120 --> 01:09:11.900
Also das sind die Endzustände.

01:09:11.900 --> 01:09:15.500
So wird ein endlicher deterministischer Automat beschrieben.

01:09:17.360 --> 01:09:24.440
Endlich, weil die Zustandsmenge endlich ist und damit auch der

01:09:24.440 --> 01:09:31.960
Speicher oder das Gedächtnis und deterministisch, weil das hier eine

01:09:31.960 --> 01:09:36.740
Funktion ist, die für jedes Paar bestehend aus einem Zustand und einem

01:09:36.740 --> 01:09:44.720
Symbol ganz eindeutig festlegt, was der Zustand ist, dem dieses Paar

01:09:44.720 --> 01:09:46.040
zugeordnet wird.

01:09:46.660 --> 01:09:50.240
Also deterministisch, da sieht man, dass es eine Funktion ist.

01:09:50.960 --> 01:09:54.080
Das heißt, in jedem Schritt ist klar, was der Automat macht.

01:09:54.940 --> 01:09:58.400
Es gibt keine Zufälligkeiten, es gibt keine Wahlmöglichkeiten.

01:09:59.540 --> 01:10:03.860
Das ist der Unterschied von Determinismus zu Nicht-Determinismus, wo

01:10:03.860 --> 01:10:06.160
es Wahlmöglichkeiten gibt, wo es Zufall gibt.

01:10:06.540 --> 01:10:08.600
Und damit werden wir ganz oft zu tun haben.

01:10:09.220 --> 01:10:11.900
Im Zusammenhang mit endlichen Automaten, aber auch mit Tonmaschinen.

01:10:13.300 --> 01:10:17.160
Dann ist die grundlegende Frage, die man sich natürlich als

01:10:17.160 --> 01:10:20.280
allererstes stellt, was kann so ein endlicher Automat?

01:10:20.460 --> 01:10:28.820
So ein ganz einfach aufgebautes Modell einer Berechnungs Maschine.

01:10:32.840 --> 01:10:36.040
Na gut, was gibt man dem Automat als Eingabe?

01:10:36.300 --> 01:10:39.680
Irgendeine Zeichenkette aus dem Alphabet.

01:10:41.100 --> 01:10:42.780
Was kann der Automat damit machen?

01:10:42.960 --> 01:10:47.560
In Abhängigkeit, wie die Zeichenkette aussieht, kann er entsprechend

01:10:47.560 --> 01:10:51.800
seiner Übergangsfunktion vom Startzustand aus weiter in weitere

01:10:51.800 --> 01:10:57.400
Zustände gehen, jeweils durchlesen ein Symbol und dann nach

01:10:57.400 --> 01:11:01.060
Abarbeitung des Wortes in irgendeinem Zustand landen.

01:11:02.540 --> 01:11:06.800
Wenn der Zustand, in dem man landet bei Abarbeitung, so eine Eingabe

01:11:06.800 --> 01:11:12.600
aus dieser Zustandsmenge F, Menge der ausgezeichneten Endzustände ist,

01:11:12.880 --> 01:11:17.480
dann sagen wir, der endliche Automat akzeptiert das Wort.

01:11:18.040 --> 01:11:22.460
Wir sagen, ein endlicher Automat erkennt oder akzeptiert eine Sprache,

01:11:23.560 --> 01:11:27.360
das heißt eine Menge von Wörtern über dem Alphabet, das der Automat

01:11:27.360 --> 01:11:28.080
kennt.

01:11:28.760 --> 01:11:33.300
Wenn er nach Abarbeitung eines jeden Wortes aus der Sprache und genau

01:11:33.300 --> 01:11:38.120
nach Abarbeitung dieser Worte in einem akzeptierenden Zustand F

01:11:38.120 --> 01:11:38.680
landet.

01:11:40.440 --> 01:11:46.700
Also wenn er genau bei Abarbeitung von Wörtern aus L in einem Zustand

01:11:46.700 --> 01:11:50.280
aus F landet, sagen wir, er akzeptiert die Sprache L.

01:11:54.120 --> 01:11:57.640
Und wir nennen dann so eine Sprache, zu der wir einen Automaten

01:11:57.640 --> 01:12:00.720
angeben können, einen endlichen Automaten, der genau diese Sprache

01:12:00.720 --> 01:12:03.940
akzeptiert, auch endliche Automatensprache.

01:12:04.380 --> 01:12:09.940
Das heißt also, diese Frage, was kann ein endlicher Automat, die

01:12:09.940 --> 01:12:15.100
könnte man auch umformulieren in, welches sind denn die formalen

01:12:15.100 --> 01:12:17.540
Sprachen, die endliche Automatensprachen sind?

01:12:17.820 --> 01:12:23.600
Sind das alle formale Sprachen oder nur eine ausgewählte Menge von

01:12:23.600 --> 01:12:24.440
formalen Sprachen?

01:12:26.100 --> 01:12:28.420
Beispiel für einen einfachen endlichen Automat.

01:12:28.820 --> 01:12:31.860
Ignorieren Sie jetzt mal, was hier in den Zuständen drin steht.

01:12:32.220 --> 01:12:35.960
Den Automaten werden wir später halt wieder treffen und da wird das

01:12:35.960 --> 01:12:37.860
eine Rolle spielen, was hier drin steht.

01:12:38.000 --> 01:12:39.460
Also der hat einfach vier Zustände.

01:12:39.880 --> 01:12:44.320
Den hier, das ist der Startzustand, dann einen weiteren Zustand, noch

01:12:44.320 --> 01:12:47.960
einen Zustand und noch einen Zustand und die beiden hier mit zwei

01:12:47.960 --> 01:12:51.940
Kringeln drum, das sollen die ausgezeichneten Endzustände sein.

01:12:51.940 --> 01:12:58.080
Also die Menge Q besteht aus den vier Zuständen und die Menge F

01:12:58.080 --> 01:13:03.520
besteht aus den beiden Zuständen und S, der Anfangszustand, oft nennen

01:13:03.520 --> 01:13:06.680
wir den auch Q0, sollte ich dazu sagen, ist der hier.

01:13:08.460 --> 01:13:12.080
Die Übergangsfunktion ist grafisch dargestellt über diese Pfeile,

01:13:12.380 --> 01:13:19.100
nämlich wenn wir in S, in dem Zustand S sind, im Anfangszustand und

01:13:19.100 --> 01:13:24.060
das Symbol 0 lesen, dann führt uns die Zustandsübergangsfunktion in

01:13:24.060 --> 01:13:24.900
diesen Zustand.

01:13:25.540 --> 01:13:29.840
Oder wenn wir in dem Anfangszustand das Symbol 1 lesen, dann führt uns

01:13:29.840 --> 01:13:34.140
die Zustandsübergangsfunktion in den Zustand selbst wieder und so

01:13:34.140 --> 01:13:34.440
weiter.

01:13:35.360 --> 01:13:37.400
Was ist das für ein Automat?

01:13:39.980 --> 01:13:41.620
Welche Sprache akzeptiert der?

01:13:45.030 --> 01:13:49.610
Naja gut, davon müsste man analysieren, welche Worte, genau welche

01:13:49.610 --> 01:13:52.190
Worte führen hierhin oder hierhin.

01:13:53.710 --> 01:13:56.290
Wenn man mal guckt zum Beispiel, wie kommt man hierhin?

01:13:56.990 --> 01:13:59.950
Da kommt man hin, wenn man eine 0 liest und dann eine 0.

01:14:00.970 --> 01:14:06.270
Oder ein paar Einsen liest, dann eine 0 und dann eine 0 liest.

01:14:06.550 --> 01:14:10.030
Oder ein paar Einsen, eine 0 liest, eine 0 liest und nochmal ein paar

01:14:10.030 --> 01:14:10.750
Nullen liest.

01:14:12.370 --> 01:14:16.590
Und wie kommt man hierhin, indem man eine 0 liest und dann eine 1

01:14:16.590 --> 01:14:17.050
liest?

01:14:17.970 --> 01:14:21.990
Oder ein paar Einsen liest, dann eine 0 und dann eine 1 liest.

01:14:22.790 --> 01:14:28.350
Oder ein paar Einsen liest, eine 0, eine 1, eine 0 und wieder eine 1.

01:14:30.290 --> 01:14:33.990
Oder aber indem man eine 0 liest, eine 0 und dann eine 1.

01:14:35.370 --> 01:14:38.870
Also wenn man sich das alles so anguckt, dann vermutet man, das ist

01:14:38.870 --> 01:14:43.110
der endliche Automat, der genau die Sprache aller Wörter, deren

01:14:43.110 --> 01:14:47.570
vorletzter Symbol eine 0 ist, akzeptiert.

01:14:48.910 --> 01:14:53.470
Gut, das war jetzt so durch Händewedeln der Beweis, dass das

01:14:53.470 --> 01:15:00.290
tatsächlich dieser Automat ist und systematisch aufbauen will,

01:15:00.410 --> 01:15:03.730
sozusagen, wie die Sprache aussieht, die von diesem Automaten

01:15:03.730 --> 01:15:06.790
akzeptiert wird, dann braucht man da irgendwie ein Werkzeug für.

01:15:07.490 --> 01:15:11.270
Und das werden wir auch kennenlernen, also sozusagen eine

01:15:11.270 --> 01:15:16.930
systematische Art für so einen endlichen Automat, die entsprechende

01:15:16.930 --> 01:15:20.590
Sprache hinzuschreiben, die von dem Automaten akzeptiert wird.

01:15:21.610 --> 01:15:25.170
Also hier ist es wie gesagt die Sprache aller Wörter, deren vorletzter

01:15:25.170 --> 01:15:29.050
Symbol 0 ist, also diese hier, die wir auch schon als reguläre Sprache

01:15:29.050 --> 01:15:30.870
identifiziert haben.

01:15:32.790 --> 01:15:37.450
Zum Abschluss heute noch Wiederholungen, was kontextfreie Grammatiken

01:15:37.450 --> 01:15:37.850
sind.

01:15:40.910 --> 01:15:48.270
So eine Grammatik, die besteht aus einem endlichen Alphabet Sigma, die

01:15:48.270 --> 01:15:53.050
nennen wir auch diese Menge Terminalalphabet.

01:15:54.030 --> 01:16:01.330
Es gibt nämlich noch eine weitere Menge von Symbolen, V, Symbole der

01:16:01.330 --> 01:16:02.150
Nicht -Terminale.

01:16:05.550 --> 01:16:11.110
Diese Menge hat einen leeren Schnitt mit der Menge der

01:16:12.790 --> 01:16:13.210
Terminalsymbole.

01:16:15.010 --> 01:16:18.730
Dann gibt es ein Start-Symbol und dann gibt es eine Menge von Regeln.

01:16:19.130 --> 01:16:22.750
Das Start-Symbol ist so Nicht-Terminal oder auch Variable genannt.

01:16:24.530 --> 01:16:26.610
Und die Frage ist jetzt, was ist das da hinten?

01:16:27.470 --> 01:16:30.690
So wie wir beim endlichen Automaten so eine Übergangsfunktion haben,

01:16:30.750 --> 01:16:32.190
haben wir hier eine Menge von Regeln.

01:16:32.770 --> 01:16:34.110
Und die Frage ist, wie sehen die aus?

01:16:34.110 --> 01:16:37.370
Also so eine Ableitungsregel, die kann man beschreiben durch so ein

01:16:37.370 --> 01:16:45.930
Truppel links, rechts oder L, R, wobei das L eine Variable ist und das

01:16:45.930 --> 01:16:51.570
R irgendein Wort sein kann, gemischtes Wort aus Terminal- und Nicht

01:16:51.570 --> 01:16:52.110
-Terminalsymbolen.

01:16:53.050 --> 01:16:56.490
Also ein Wort aus der Sprache, die man bekommt, wenn man Sigma

01:16:56.490 --> 01:17:01.030
vereinigt, Menge der Variablen hernimmt und einen klinischen Abschluss

01:17:01.030 --> 01:17:01.570
bildet.

01:17:04.150 --> 01:17:07.310
Also das hier ist das Spannende, diese Ableitungsregeln, die schreiben

01:17:07.310 --> 01:17:11.750
wir auch in der Form, also dieses Truppel L, R, schreiben wir auch in

01:17:11.750 --> 01:17:13.710
der Form L-Pfeil-R.

01:17:14.750 --> 01:17:17.370
Und das sind also Produktionsregeln und die gucken wir uns jetzt mal

01:17:17.370 --> 01:17:18.010
genauer an.

01:17:20.550 --> 01:17:24.850
Da kann man aus Worten neue Worte mit bilden.

01:17:25.350 --> 01:17:30.050
Wenn man ein Wort hat, wo irgendwo L vorkommt, also so ein W, dass

01:17:30.050 --> 01:17:35.110
irgendwo das Zeichen L, die Variable L enthält, dann kann man an der

01:17:35.110 --> 01:17:39.430
Stelle L ersetzen durch R, das Wort R.

01:17:39.670 --> 01:17:44.910
Wenn ich die Produktionsregel L, R habe und kriege dann ein neues

01:17:44.910 --> 01:17:45.330
Wort.

01:17:45.870 --> 01:17:53.110
Dann schreibt man auch, wenn man das macht, durch Ersetzen von L in

01:17:53.110 --> 01:17:57.550
dem Wort W durch R kriege ich ein neues Wort Z, dann schreibt man auch

01:17:58.630 --> 01:18:01.310
W habe ich abgeleitet zu Z.

01:18:02.230 --> 01:18:08.110
Und wenn ich über Anwendung von mehreren Produktionsregeln aus W, Z

01:18:08.110 --> 01:18:12.790
bekommen kann, dann schreibe ich auch W-Pfeil-Z mit so einem Sternchen

01:18:12.790 --> 01:18:13.130
drüber.

01:18:15.930 --> 01:18:18.230
Jetzt, wofür ist so eine Grammatik gut?

01:18:18.430 --> 01:18:23.670
Die ist gut, um wieder Sprachen zu beschreiben oder eine Sprache zu

01:18:23.670 --> 01:18:28.970
beschreiben, nämlich die Sprache, die all die Wörter enthält, die ich

01:18:28.970 --> 01:18:35.910
durch beliebiges Anwenden von Ableitungsregeln der Grammatik aus dem

01:18:35.910 --> 01:18:37.910
Startsymbol generieren kann.

01:18:38.570 --> 01:18:41.850
Also wenn ich so eine Grammatik G habe, bestehend aus Sigma,

01:18:42.030 --> 01:18:47.270
Variablenmenge V, Startsymbol S und R, Menge von Ableitungsregeln,

01:18:47.830 --> 01:18:52.310
dann ist L von G, also die Sprache zu dieser Grammatik, gerade die

01:18:52.310 --> 01:18:57.770
Menge all der Wörter Z über dem Alphabet Sigma, also aus Sigma Stern,

01:18:58.430 --> 01:19:02.850
die ich bekomme, wenn ich auf S, angefangen bei S, eine beliebige

01:19:02.850 --> 01:19:06.630
Folge von Ableitungsregeln aus R anwende.

01:19:07.890 --> 01:19:09.870
Und das gucken wir uns mal am Beispiel an.

01:19:11.230 --> 01:19:13.150
Also meinetwegen, wir hätten folgende Grammatik.

01:19:13.970 --> 01:19:19.590
Das Alphabet ist 0,1, wie wir es jetzt schon die ganze Zeit angeguckt

01:19:19.590 --> 01:19:19.950
haben.

01:19:20.970 --> 01:19:26.130
Das Startsymbol ist S und die Variablenmenge enthält auch nichts

01:19:26.130 --> 01:19:31.750
weiter als das Startsymbol, also V, Variablenmenge, nicht

01:19:31.750 --> 01:19:34.670
Terminalalphabet, ist Menge mit S.

01:19:35.130 --> 01:19:37.710
Und die Ableitungsregeln sind folgendermaßen aus.

01:19:38.330 --> 01:19:43.830
Ich kann das Startsymbol ersetzen durch 0,1 oder ich kann das

01:19:43.830 --> 01:19:49.910
Startsymbol ersetzen durch 0, Startsymbol 1.

01:19:49.910 --> 01:19:54.430
Also ich habe nur zwei mögliche Regeln und bei beiden Regeln steht

01:19:54.430 --> 01:19:58.190
links das Startsymbol, das ist ja auch die einzige Variable, die ich

01:19:58.190 --> 01:20:05.050
zur Verfügung habe, und rechts jeweils ein Wort aus Sigma vereinigt V

01:20:05.050 --> 01:20:06.270
in Klammernsternchen.

01:20:06.630 --> 01:20:09.690
Und es gibt dann nur zwei Möglichkeiten, nämlich dass rechts einfach

01:20:09.690 --> 01:20:14.210
das Wort 0,1 steht oder rechts 0,S1 steht.

01:20:15.530 --> 01:20:19.390
Das hier, also diese Menge von Regeln, die schreibe ich auch oft

01:20:19.390 --> 01:20:23.890
verkürzt einfach als, also wenn da links dasselbe Symbol steht, ich

01:20:23.890 --> 01:20:29.830
kann dieses Symbol ableiten entweder zu 0,1 oder zu 0,S1, also indem

01:20:29.830 --> 01:20:32.430
ich einfach hier rechts das Kompakte schreibe.

01:20:33.090 --> 01:20:36.710
So, welche Wörter kann man auf die Art und Weise bekommen, ist die

01:20:36.710 --> 01:20:37.010
Frage.

01:20:38.370 --> 01:20:39.290
Was kann ich machen?

01:20:39.710 --> 01:20:44.390
Ich kann S ersetzen durch 0,1 oder durch 0,S1.

01:20:44.910 --> 01:20:48.470
Was kann ich durch weitere Anwendungen von Produktionsregeln bekommen?

01:20:50.290 --> 01:20:55.410
Entweder ich mache hier gar nichts mehr, Ende damit, oder ich ersetze

01:20:55.410 --> 01:20:58.270
hier dieses S und da gibt es wieder zwei Möglichkeiten.

01:20:58.550 --> 01:21:03.410
Ich ersetze entweder S durch 0,1, dann bekomme ich 0,0,1,1 oder ich

01:21:03.410 --> 01:21:08.210
ersetze S durch 0,S1, dann bekomme ich 0,0,S1,1.

01:21:08.670 --> 01:21:13.670
Wenn ich da weitere Regeln anwende, behalte ich erstmal die Worte, die

01:21:13.670 --> 01:21:18.490
ich schon habe und aus dem Hinteren bekomme ich entweder 0,0,0,1,1,1

01:21:18.490 --> 01:21:23.330
oder 0,0,0, S1,1,1 und so weiter.

01:21:24.050 --> 01:21:25.950
Das Schema ist ziemlich schnell klar.

01:21:26.490 --> 01:21:31.510
Das Ganze endet jeweils bei Wörtern, wie hier auch schon, die nur noch

01:21:31.510 --> 01:21:33.030
Symbole aus Sigma enthalten.

01:21:33.770 --> 01:21:36.870
Diese Wörter sehen natürlich so aus, das ist eine Folge von Nullen,

01:21:37.190 --> 01:21:39.790
gefolgt von einer Folge von Einsen und es sind immer genauso viele

01:21:39.790 --> 01:21:40.630
Einsen wie Nullen.

01:21:41.230 --> 01:21:47.570
Das heißt also, diese Grammatik erzeugt gerade die Sprache 0 hoch N, 1

01:21:47.570 --> 01:21:50.050
hoch N, eine natürliche Zahl.

01:21:54.700 --> 01:21:59.280
Und jetzt die Sprache, die wir jetzt schon mehrmals hatten, die

01:21:59.280 --> 01:22:03.120
Sprache der Wörter, deren vorletztes Symbol 0 ist und die Wörter

01:22:03.120 --> 01:22:05.300
sollen auch außer Nullen und Einsen nichts enthalten.

01:22:05.680 --> 01:22:07.980
Kann ich die über eine Grammatik beschreiben?

01:22:13.510 --> 01:22:17.630
Okay, dann schlage ich mal folgende vor, also Sigma ist 0,1.

01:22:18.350 --> 01:22:23.550
Als Variablenmenge nehme ich die Menge, die S, also Startsymbol, eine

01:22:23.550 --> 01:22:27.690
weitere Variable A und eine weitere Variable B enthält und folgende

01:22:27.690 --> 01:22:29.030
Regeln schlage ich Ihnen vor.

01:22:29.430 --> 01:22:33.730
Aus S kann ich ableiten A0 oder A1.

01:22:34.550 --> 01:22:39.550
Aus A kann ich ableiten B0 und aus B kann ich ableiten das leere Wort

01:22:39.550 --> 01:22:41.110
oder B0 oder B1.

01:22:42.850 --> 01:22:48.270
Gucken Sie sich das mal an und die Zuständigkeit dieser Regeln, wofür

01:22:48.270 --> 01:22:49.550
sind die Regeln zuständig?

01:22:51.690 --> 01:22:56.850
Die erste Regel, die ersten beiden sind dafür zuständig, das hintere

01:22:56.850 --> 01:22:59.130
Symbol zu generieren.

01:22:59.490 --> 01:23:03.810
Also bei einem Wort, das als vorletztes Symbol 0 enthält, habe ich

01:23:03.810 --> 01:23:06.190
hinten eine 0 oder eine 1.

01:23:06.770 --> 01:23:09.090
Und davor ist eine 0 und davor ist irgendwas Beliebiges.

01:23:09.710 --> 01:23:14.590
Und die beiden Regeln S nach A0 und S nach A1, die setzen gerade

01:23:14.590 --> 01:23:15.810
dieses letzte Symbol.

01:23:16.870 --> 01:23:17.810
Da sitzt das.

01:23:18.010 --> 01:23:22.310
Und davor muss jetzt noch was produziert werden und dass das vorletzte

01:23:22.310 --> 01:23:29.130
Symbol eine 0 ist, worauf ich achten muss, dafür sind die Regeln

01:23:29.130 --> 01:23:32.870
zuständig, die aus A weiter ableiten.

01:23:33.290 --> 01:23:38.550
Nämlich aus A kann ich nur eine Sache ableiten B0.

01:23:40.650 --> 01:23:45.390
Und wofür ist jetzt, oder wie kriege ich jetzt das vor, dieser 0, dem

01:23:45.390 --> 01:23:49.890
vorletzten Symbol, was Beliebiges stehen kann, dafür sind die Regeln

01:23:49.890 --> 01:23:51.730
zuständig, die aus B ableiten.

01:23:52.150 --> 01:23:56.050
Da kann gar nichts stehen da vorne, also das Wort sieht nur so aus 0 0

01:23:56.050 --> 01:23:59.290
oder 0 1 oder irgendwas.

01:23:59.830 --> 01:24:08.530
Und das wird halt durch 0 1 und 0 1 und davor schreiben und generiert.

01:24:09.150 --> 01:24:13.610
Und dafür habe ich einfach, B kann nach B0, nach B1 abgeleitet werden,

01:24:13.710 --> 01:24:16.350
das kann ich auch in beliebiger Reihenfolge solche Regeln jetzt noch

01:24:16.350 --> 01:24:20.930
anwenden und wenn dann mal irgendwann Schluss ist, das Wort fertig

01:24:20.930 --> 01:24:23.330
generiert, dann ersetze ich B einfach durch Epsilon.

01:24:26.330 --> 01:24:30.130
Das heißt also, eine Ableitung irgendeines Wortes aus der Sprache, die

01:24:30.130 --> 01:24:33.710
hier durch generiert wird, sieht so aus.

01:24:33.830 --> 01:24:39.450
Ich fange bei S an und da gibt es nur zwei mögliche Regeln, S nach A0

01:24:39.450 --> 01:24:40.690
oder S nach A1.

01:24:41.810 --> 01:24:43.010
Und dann mache ich weiter.

01:24:43.630 --> 01:24:49.430
Weiter machen eine Regel für A wird abgeleitet.

01:24:49.990 --> 01:24:52.510
Anwenden, dafür habe ich nur eine.

01:24:53.470 --> 01:24:55.070
A wird abgeleitet nach B0.

01:24:55.230 --> 01:24:58.570
Das heißt also, im ersten Fall bekomme ich B nur 0, im zweiten Fall,

01:24:58.690 --> 01:25:03.950
also wenn ich von S aus erstmal A1 generiert habe, bekomme ich B01.

01:25:04.810 --> 01:25:10.650
Und dann alles, was ich kriegen kann, an Worten, wo keine Variablen

01:25:10.650 --> 01:25:15.710
mehr drin sind, aus B00 und B01 durch Anwenden dieser Regeln.

01:25:16.330 --> 01:25:20.970
Das ist alles, was hier vorne beliebiges noch davor schreibt.

01:25:21.710 --> 01:25:23.770
Beliebiges bestehend aus 0 und 1.

01:25:31.990 --> 01:25:37.870
Das war die Wiederholung und damit bin ich auch am Ende.

01:25:39.330 --> 01:25:42.490
Grammatiken, wie die kontextfreien Grammatiken, werden wir später in

01:25:42.490 --> 01:25:45.290
der Vorlesung betrachten und da werden wir eben auch noch mehr als

01:25:45.290 --> 01:25:47.210
diese kontextfreien Grammatiken kennenlernen.

01:25:47.590 --> 01:25:48.510
So, das wäre es für heute.