WEBVTT 00:07.500 --> 00:11.580 Wir haben uns in den letzten Vorlesungen mit dem ersten, ich sage mal 00:11.580 --> 00:17.320 größeren Projekt hier beschäftigt, nämlich drei verschiedene oder 00:17.320 --> 00:22.100 eigentlich vier verschiedene Methoden kennengelernt, um reguläre 00:22.100 --> 00:25.720 Sprachen zu beschreiben, nämlich durch Chomsky-Dreigrammatniken, 00:26.700 --> 00:29.800 deterministische endliche Automaten, nicht-deterministische endliche 00:29.800 --> 00:31.880 Automaten und durch reguläre Ausdrücke. 00:32.880 --> 00:37.160 Und ein Problem dabei war, dass dieser Schritt von nicht 00:37.160 --> 00:40.800 -deterministischen zu deterministischen endlichen Automaten zu einer 00:40.800 --> 00:43.120 Explosion der Zustandszahl führen kann. 00:45.660 --> 00:50.820 Ich habe aber auch schon angedeutet, dass man oft auch 00:50.820 --> 00:56.480 deterministische Automaten mit wenig Zuständen finden kann, die die 00:56.480 --> 00:58.000 gewünschte Sprache beschreiben. 00:58.000 --> 01:04.400 Und jetzt beschäftigen wir uns damit, wie man denn das macht. 01:05.240 --> 01:08.040 Und da sind wir sehr ehrgeizig. 01:08.460 --> 01:12.900 Wir wollen nicht irgendwie die Anzahl Zustände verringern, sondern wir 01:12.900 --> 01:16.580 wollen die minimale mögliche Zahl Zustände finden. 01:17.260 --> 01:20.920 Und was wir sehen werden, ist ein sehr schönes Ergebnis auch aus 01:20.920 --> 01:25.460 mathematischer Sicht, dass es nämlich genau einen zustandsminimalen 01:25.460 --> 01:29.040 Automaten gibt, bis auf Umbenennung der Zustände. 01:33.080 --> 01:38.080 Und damit werden wir heute beginnen und das Ganze erstmal mathematisch 01:38.080 --> 01:41.440 beschreiben und erkennen, dass das der Fall ist. 01:41.840 --> 01:46.360 Und beim nächsten Mal lernen wir dann konkrete Algorithmen, wie man 01:46.360 --> 01:49.080 diese zustandsminimalen Automaten tatsächlich findet. 01:56.990 --> 01:59.910 So, und das Ganze wird jetzt ziemlich algebraisch. 02:02.550 --> 02:06.910 Sie werden wahrscheinlich so Sachen auch im linearen Algebra gesehen 02:06.910 --> 02:10.270 haben, aber als ich das das letzte Mal gesagt habe, gab es dann ein 02:10.270 --> 02:10.750 paar Probleme. 02:11.690 --> 02:15.290 Das ist diesmal kein Problem, ich erinnere Sie an alle algebraischen 02:15.290 --> 02:16.410 Sachen, die wir hier brauchen. 02:17.490 --> 02:22.030 Also zur Erinnerung, es gibt so Dinge wie Äquivalenzrelationen. 02:22.030 --> 02:25.470 Wer kennt den Begriff Äquivalenzrelation bereits? 02:26.870 --> 02:30.750 Den kennen scheinbar alle, das freut mich, weil damit müssen wir jetzt 02:30.750 --> 02:31.890 sehr intensiv arbeiten. 02:32.250 --> 02:36.510 Trotzdem zur Erinnerung, eine Relation ist nichts anderes als eine 02:36.510 --> 02:40.710 Menge von Paaren, also eine Teilmenge von Y kreuz Y. 02:41.770 --> 02:45.970 Und die heißt Äquivalenzrelation, wenn drei Bedingungen gelten. 02:45.970 --> 02:47.710 Sie ist reflexiv, d.h. 02:47.910 --> 02:51.310 jedes Element steht in Relation zu sich selber. 02:51.410 --> 02:55.690 Sie ist transitiv, d.h. 02:55.770 --> 03:00.490 wenn X in Relation zu Y steht und Y in Relation zu Z, dann steht X 03:00.490 --> 03:01.690 auch in Relation zu Z. 03:02.550 --> 03:03.790 Und sie ist symmetrisch, d.h. 03:03.910 --> 03:08.470 wenn X in Relation zu Y steht, steht Y auch in Relation zu X. 03:10.430 --> 03:14.250 Und das sind drei sehr einfache Eigenschaften, die man meistens auch 03:14.250 --> 03:15.510 leicht nachweisen kann. 03:16.030 --> 03:18.830 Und daraus folgen aber bereits eine ganze Menge nützliche Dinge. 03:19.970 --> 03:22.430 Und das ist so ein Beispiel, wo die Algebra einem hilft. 03:23.270 --> 03:27.210 Da müssen wir jetzt nicht mehr jedes Mal für jede Relation, die wir 03:27.210 --> 03:29.250 einführen, neu beweisen. 03:29.410 --> 03:30.350 Das ist einfach so. 03:30.970 --> 03:33.950 Es gibt zunächst mal das Konzept der Äquivalenzklasse. 03:33.950 --> 03:37.450 Die schreiben wir so, dass wir sagen, also wir nehmen mal irgendein 03:37.450 --> 03:41.330 Element, machen eckige Klammern darum und sagen, okay, das ist jetzt 03:41.330 --> 03:46.450 die Menge aller Y, die in Relation zu X stehen. 03:47.090 --> 03:49.710 Und wegen der Reflexivität ist natürlich das X mit dabei. 03:53.020 --> 03:59.480 Außerdem wissen wir aus der Algebra, dass zwei Äquivalenzklassen, z.B. 03:59.580 --> 04:03.260 ich nehme jetzt ein Element X und ein Element Y, dann gibt es zu den 04:03.260 --> 04:06.620 beiden Äquivalenzklassen und es können nur zwei Dinge sein. 04:06.800 --> 04:09.700 Entweder sind das die gleichen Mengen von Elementen, weil nämlich X in 04:09.700 --> 04:14.600 Relation zu Y steht, oder sie sind komplett disjunkt. 04:15.880 --> 04:20.620 Und außerdem ist natürlich jedes Element in einer Äquivalenzklasse und 04:20.620 --> 04:23.620 das bedeutet, dass die Äquivalenzklassen eine Partitionierung der 04:23.620 --> 04:25.300 Menge Y darstellen. 04:25.700 --> 04:30.160 Das heißt, jedes Element von Y gehört zu genau einer Äquivalenzklasse. 04:31.780 --> 04:33.720 Ich habe das jetzt hier mal so dargestellt. 04:34.440 --> 04:37.540 Das hier ist eine Menge und die wird jetzt durch diese schwarzen 04:37.540 --> 04:40.600 Linien in Teilmengen zerschnitten und das sind meine 04:40.600 --> 04:41.520 Äquivalenzklassen. 04:43.420 --> 04:45.320 Dann brauchen wir doch einen Begriff, der in der Algebra 04:45.320 --> 04:47.740 wahrscheinlich nicht so häufig verwendet wird. 04:48.140 --> 04:53.240 Der Index einer Relation oder der Index einer Äquivalenzrelation ist 04:53.240 --> 04:55.180 die Anzahl der Äquivalenzklassen. 04:55.180 --> 04:57.540 Oder in Mengennotationen können wir das schreiben. 04:58.320 --> 05:01.800 Wir betrachten uns einfach die Menge aller Äquivalenzklassen und davon 05:01.800 --> 05:02.700 der Betrag. 05:03.860 --> 05:06.120 Fragen zu diesen Definitionen? 05:08.480 --> 05:13.640 Dann brauchen wir noch einen weiteren Begriff, nämlich eine Relation 05:13.640 --> 05:19.960 einer Äquivalenzrelation R kann eine Äquivalenzrelation R' verfeinern, 05:20.460 --> 05:23.100 genau dann, wenn R Teilmenge R' ist. 05:25.860 --> 05:29.320 Diese Definition funktioniert auch für beliebige Relationen, aber wir 05:29.320 --> 05:33.200 werden die nur für Äquivalenzrelationen benutzen. 05:38.000 --> 05:41.000 Diesen Begriff der Verfeinerung kann man vielleicht hier in dem Bild 05:41.000 --> 05:41.860 auch ganz gut sehen. 05:42.260 --> 05:48.720 Wir haben hier eine Zerteilung der Menge Y in Äquivalenzklassen und 05:48.720 --> 05:52.420 jetzt können wir zusätzliche Striche einzeichnen, die blauen. 05:54.480 --> 05:56.680 Und das ist dann eine Verfeinerung. 06:08.120 --> 06:14.200 Also nochmal, R verfeinert R', wenn für alle Äquivalenzklassen von R 06:16.430 --> 06:22.910 gilt, dass sie Teilmenge einer Äquivalenzklasse von R' sind. 06:27.120 --> 06:29.180 Ach nee, das ist keine Definition, sondern das ist ein Lemma, das 06:29.180 --> 06:30.040 beweisen wir gerade. 06:30.040 --> 06:33.840 Genau, zeigen wir das mal. 06:37.270 --> 06:45.250 Es sei also, Y in der Äquivalenzklasse von X bezüglich R, unserer 06:45.250 --> 06:50.370 feineren Relation, das ist nach Definition von Äquivalenzklassen 06:50.370 --> 06:55.810 gleichbedeutend mit, dass Y X in der Relation ist. 06:58.500 --> 07:04.180 Da aber R eine Teilmenge von R' ist, folgt damit, dass Y X auch ein R' 07:04.400 --> 07:04.640 ist. 07:04.740 --> 07:08.500 Und jetzt setze ich nochmal die Definition ein, einer 07:08.500 --> 07:11.140 Äquivalenzklasse, das ist äquivalent dazu, dass Y in der 07:11.140 --> 07:13.360 Äquivalenzklasse von X ist. 07:16.720 --> 07:21.300 Und das ist eben nichts anderes als eine mathematische Formulierung 07:21.300 --> 07:22.360 dieser Eigenschaft hier. 07:22.360 --> 07:26.800 Eine Verfeinerung ist nichts anderes als eine Aufteilung von 07:26.800 --> 07:29.060 Äquivalenzklassen in Teilequivalenzklassen. 07:30.520 --> 07:35.940 Und wichtiges Korollar ist, dass wenn R R' verfeinert, dann ist deren 07:35.940 --> 07:38.260 Index größer gleich dem Index von R'. 07:39.220 --> 07:43.960 Der Gleichheitsfall tritt in dem trivialen Fall auf, wenn R gleich R'. 07:43.960 --> 07:45.520 Fragen dazu? 07:47.020 --> 07:50.980 Also wir haben jetzt eingeführt Äquivalenzrelation, Index und den 07:50.980 --> 07:53.160 Begriff der Verfeinerung einer Äquivalenzrelation. 07:55.000 --> 07:58.320 Und jetzt werden wir uns sehr intensiv mit einer bestimmten 07:58.320 --> 08:07.840 Äquivalenzrelation befassen, die sogenannte Nerode-Relation, die man 08:07.840 --> 08:14.640 zunächst mal für beliebige formale Sprachen definieren kann, die aber 08:14.640 --> 08:19.240 für reguläre Sprachen eine besonders wichtige Rolle spielt. 08:27.380 --> 08:32.460 Zwar die Nerode-Relation zu einer Sprache ist die Menge aller Paare x, 08:32.540 --> 08:38.000 y, mit der Eigenschaft, naja, die sind äquivalent in irgendeiner 08:38.000 --> 08:38.660 Beziehung. 08:39.460 --> 08:40.760 Und was ist das für eine Beziehung? 08:41.220 --> 08:46.620 Dass nämlich für alle z in Sigma-Sternen gilt, dass x z in L genau 08:46.620 --> 08:48.340 dann, wenn y z in L ist. 08:54.260 --> 08:57.740 Wo es hinterher darauf hinauslaufen wird, dass in regulären Sprachen 08:57.740 --> 09:04.120 entsprechen diese Äquivalenzklassen eigentlich Zuständen eines 09:04.120 --> 09:05.520 endlichen Automaten. 09:07.280 --> 09:11.000 Oder vielleicht anders ausgedrückt, also eine Äquivalenzklasse, 09:11.380 --> 09:17.120 sondern eine Nerode-Relation, ist halt nichts anderes als, naja, das 09:17.120 --> 09:22.920 sind Wörter, die ununterscheidbar sind bezüglich dem, was danach kommt 09:22.920 --> 09:23.540 in einem Wort. 09:26.200 --> 09:30.300 Das ist eine Art Kontextinformation, die bei endlichen Automaten nur 09:30.300 --> 09:32.380 durch den Zustand kodiert werden kann. 09:35.400 --> 09:39.360 Aber was das genau mit Zuständen zu tun haben, werden wir jetzt 09:39.360 --> 09:40.720 kennenlernen. 09:43.080 --> 09:48.000 Also die Nerode-Relation ist jetzt eine Äquivalenzrelation, die wir 09:48.000 --> 09:53.800 einfach rein formal definiert haben, gib mir irgendeine formale 09:53.800 --> 09:56.200 Sprache, ich sag dir, was die Nerode-Relation ist. 09:58.840 --> 10:01.800 Das Wort Automat ist hier überhaupt nicht aufgetaucht. 10:03.260 --> 10:05.300 Das war nur meine Interpretation eben. 10:05.800 --> 10:10.920 Auf der anderen Seite können wir von einem deterministischen endlichen 10:10.920 --> 10:15.760 Automaten ausgehen und für den eine Äquivalenzrelation definieren. 10:18.300 --> 10:21.820 Die nennen wir jetzt für einen Automaten M, nennen wir die eher M. 10:23.560 --> 10:29.220 Das ist die Menge aller XY in Sigma-Stern, Kreuz-Sigma-Stern, mit der 10:29.220 --> 10:32.960 Eigenschaft, dass Delta-Dach von Startzustand Komma X gleich Delta 10:32.960 --> 10:35.040 -Dach von Startzustand Komma Y ist. 10:36.000 --> 10:41.000 Und das ist, sehen Sie schon, so ähnlich wie das, was wir hier haben. 10:41.020 --> 10:42.840 Ich habe das auch in dem Bild mal dargestellt. 10:42.840 --> 10:49.800 Also diese Automaten-Relation, die habe ich hier auch, ist halt, ich 10:49.800 --> 10:53.260 gebe X ein und lande im gleichen Zustand, wie wenn ich Y eingebe. 10:53.740 --> 10:57.280 Und dann ist es klar, dass so wie endliche Automaten definiert sind, 10:59.100 --> 11:02.500 die äquivalent sind in dem Sinne, dass sie keinen Einfluss jetzt 11:02.500 --> 11:10.980 darauf haben, welche Nachfolgewörter, also welche zweiten Teile eines 11:10.980 --> 11:15.080 Wortes man da dranhängen kann, um ein Wort der Sprache zu generieren. 11:19.300 --> 11:20.560 Aber gucken wir uns das... 11:28.590 --> 11:31.570 Da müsste man jetzt auch erst zeigen, dass das eine Äquivalenzrelation 11:31.570 --> 11:35.050 ist, aber das überlasse ich Ihnen jetzt als Übung, das ist relativ 11:35.050 --> 11:35.610 einfach. 11:38.790 --> 11:45.810 Und die erste wichtige Beobachtung ist jetzt, dass RM die Nerode 11:45.810 --> 11:47.030 -Relation verfeinert. 11:47.450 --> 11:50.770 Und das ist bereits ein wichtiger Bezug, den wir herstellen zwischen 11:50.770 --> 11:54.870 diesen Automaten-definierten Relationen und der Nerode-Relation, die 11:54.870 --> 11:56.770 nur etwas mit der Sprache zu tun hat. 11:57.550 --> 11:59.470 Also zur Erinnerung, was heißt das? 12:06.720 --> 12:09.580 Achso genau, ich habe hier einfach nochmal die Nerode-Relation 12:09.580 --> 12:14.920 hingeschrieben, also welche XY sind nicht unterscheidbar bezüglich dem 12:14.920 --> 12:16.480 zweiten Teil in der Sprache. 12:18.760 --> 12:20.660 Beweis werde ich nur skizzieren. 12:24.120 --> 12:28.440 Also wenn wir zeigen wollen, dass RM die Nerode-Relation RL 12:28.440 --> 12:36.880 verfeinert, müssen wir für jedes Paar XY zeigen, dass wenn Delta-Dach 12:36.880 --> 12:38.800 Sx gleich Delta-Dach Sy... 12:45.280 --> 12:51.900 Also wenn die äquivalent sind bezüglich der einen Maschinen-Relation, 12:51.980 --> 12:56.240 das war ja Delta-Dach Sx gleich Delta-Dach Sy, war die Definition, 12:56.660 --> 13:00.520 dann müssen sie auch äquivalent sein bezüglich der Definition der 13:00.520 --> 13:01.460 Nerode -Relation. 13:01.460 --> 13:07.640 Und da würde verlangt, dass für alle Z gilt XZ in L genau dann, wenn 13:07.640 --> 13:08.960 YZ in L. 13:09.600 --> 13:12.520 Aber das ist ziemlich klar, wenn man sich dieses Bild wieder anschaut. 13:14.840 --> 13:18.920 Wenn Delta-Dach Sx gleich Delta-Dach Sy, haben wir diese Situation, 13:19.280 --> 13:25.560 wir landen im gleichen Zustand, die Definition von Delta-Dach und dann 13:25.560 --> 13:31.980 ist es eben so, wenn ich in dem Zustand Q bin, werden halt bestimmte 13:31.980 --> 13:36.360 Wörter ab da führen in den Endzustand und das ist völlig unabhängig 13:36.360 --> 13:38.060 davon, ob es X oder Y war. 13:40.100 --> 13:43.280 Das passt also und ich habe dann diese Teilmengen-Relation nur 13:43.280 --> 13:43.760 gezeigt. 13:44.180 --> 13:47.700 Es kann aber eben durchaus sein, dass es eine echte Verfeinerung ist. 13:47.820 --> 13:49.860 Es ist nicht das gleiche wie die Nerode-Relation. 13:55.170 --> 13:56.890 Jetzt kommt so ein Einschub. 13:58.730 --> 14:03.610 Ich habe ja gesagt, die Nerode-Relation kann ich für beliebige 14:03.610 --> 14:07.150 Sprachen definieren. 14:08.810 --> 14:11.970 Die Nerode-Relation kann insbesondere auch unendlichen Index haben, 14:12.090 --> 14:14.010 das heißt unendlich viele Äquivalenzklassen. 14:15.310 --> 14:22.850 Aber wir können jetzt ganz leicht zeigen, dass wenn RL unendlichen 14:22.850 --> 14:26.090 Index hat, dass die Sprache dann nicht regulär sein kann. 14:27.770 --> 14:29.150 Und das beweisen wir jetzt. 14:29.230 --> 14:30.750 Nehmen wir mal an, L ist regulär. 14:32.270 --> 14:33.750 Hat aber einen unendlichen Index. 14:35.690 --> 14:38.730 Aber wenn sie regulär ist, gibt es einen deterministischen endlichen 14:38.730 --> 14:42.510 Automaten M, der die Sprache akzeptiert. 14:42.610 --> 14:43.750 Also L von M gleich L. 14:43.750 --> 14:50.830 Aber wir haben auf der vorigen Seite gesehen, dass RM eine 14:50.830 --> 14:52.350 Verfeinerung von RL ist. 14:56.090 --> 15:01.170 Nun habe ich aber für jeden Zustand des Automatens genau eine 15:01.170 --> 15:03.010 Äquivalenzklasse in meinem RM. 15:06.550 --> 15:11.030 Und dann folgt also Anzahl Zustände gleich Index von RM. 15:11.570 --> 15:16.230 Das ist eine Verfeinerung von RL, also größer gleich Index von RL. 15:17.090 --> 15:20.590 Und das ist unendlich, also Anzahl Zustände ist größer gleich 15:20.590 --> 15:21.190 unendlich. 15:21.830 --> 15:24.810 Dann kann es aber kein endlicher Automat gewesen sein, das ist ein 15:24.810 --> 15:25.390 Widerspruch. 15:28.450 --> 15:31.310 Genau, also wir werden ab jetzt eigentlich immer den Fall haben, dass 15:31.310 --> 15:34.390 wir einen endlichen Index der Nerode-Relation haben. 15:34.390 --> 15:39.190 Aber das hier ist schon ein ganz wichtiger Satz auch. 15:39.870 --> 15:43.510 Wir haben beim letzten Mal das Pumping Lemma für reguläre Sprachen 15:43.510 --> 15:47.370 kennengelernt und gesehen, dass man da ganz oft leicht beweisen kann, 15:48.470 --> 15:49.870 dass Sprachen nicht regulär sind. 15:49.870 --> 15:53.250 Wir haben aber auch ein Beispiel einer formalen Sprache gesehen, wo 15:53.250 --> 15:54.670 das nicht funktioniert hat. 15:56.730 --> 16:00.130 Wo wir mithilfe des Pumping Lemmas nicht zeigen konnten, dass die 16:00.130 --> 16:01.110 nicht regulär ist. 16:04.010 --> 16:15.130 Aber das hier ist, glaube ich, eine hinreichende und notwendige 16:15.130 --> 16:16.590 Bedingung für Regularität. 16:16.590 --> 16:22.790 Eine Sprache ist genau dann regulär, wenn sie ihre Nerode-Relation 16:22.790 --> 16:24.690 endlich einen Index hat. 16:25.690 --> 16:30.290 Und das heißt insbesondere, Sie können für jede nicht reguläre Sprache 16:30.290 --> 16:34.730 zeigen, dass sie nicht regulär ist, indem Sie beweisen, dass es 16:34.730 --> 16:43.210 unendlich viele Äquivalenzklassen der Nerode-Relation gibt. 16:43.950 --> 16:49.170 Das ist ein bisschen unhandlicher als das Pumping Lemma, aber dafür 16:49.170 --> 16:50.590 geht es immer. 16:52.730 --> 16:55.850 Da haben wir, glaube ich, jetzt auch eine Aufgabe auf dem Übungsblatt 16:55.850 --> 16:57.190 oder auf dem Tutorenübungsblatt? 17:04.290 --> 17:04.830 Ah, okay. 17:05.850 --> 17:07.730 Also es gibt doch keine Aufgabe dazu. 17:07.850 --> 17:09.130 Aber wir hatten uns da eine überlegt. 17:09.510 --> 17:11.510 War wohl doch ein bisschen zu eklig, oder? 17:30.510 --> 17:34.730 So, jetzt wissen wir, die haben irgendwas miteinander zu tun. 17:35.510 --> 17:37.850 Aber jetzt gehen wir einen Schritt weiter. 17:38.990 --> 17:44.790 Wenn wir die Nerode-Relation haben und der Index endlich ist, dann 17:44.790 --> 17:46.710 können wir auch einen Automaten definieren. 17:47.470 --> 17:50.070 Das war so die Intuition, die ich am Anfang hingeschrieben habe und 17:50.070 --> 17:52.310 das mache ich jetzt mathematisch präzise. 17:52.310 --> 17:55.750 Wir bauen jetzt aus den Äquivalenzklassen und Automaten. 18:01.620 --> 18:04.000 Und der sieht... 18:04.720 --> 18:05.860 Hä, wo ist denn der? 18:15.290 --> 18:17.250 Da fehlt irgendwie die Definition. 18:17.470 --> 18:18.110 Habe ich die raus? 18:19.150 --> 18:19.790 Die ist hier. 18:21.470 --> 18:21.770 Hä? 18:22.070 --> 18:23.510 In zwei Seiten vertauscht? 18:25.290 --> 18:26.130 Naja, okay. 18:26.390 --> 18:28.170 Also Nerode-Relation haben wir definiert. 18:28.170 --> 18:31.630 Die Idee ist jetzt... 18:33.070 --> 18:38.290 Ich habe ja informell gesagt, die Äquivalenzklassen von der L 18:38.290 --> 18:42.130 korrespondieren zu Zuständen eines endlichen Automaten. 18:42.270 --> 18:44.830 Dann machen wir das doch genauso. 18:45.030 --> 18:49.770 Wir definieren uns einen endlichen Automaten, dessen Zustandsmenge 18:49.770 --> 18:52.210 gerade die Äquivalenzklassen sind. 18:53.290 --> 18:57.830 Das sind jetzt sozusagen ziemlich komische Namen für 18:57.830 --> 18:59.210 Automatenzustände. 18:59.990 --> 19:02.990 Bisher hatten wir immer irgendwie Buchstaben oder Zahlen oder sowas. 19:04.010 --> 19:08.210 Jetzt haben wir einen endlichen Automaten, der einen Namen haben kann, 19:08.330 --> 19:11.510 der irgendwie sogar unendlich viele Elemente enthält oder sowas. 19:11.630 --> 19:12.390 Aber das macht nichts. 19:12.450 --> 19:14.710 Es gibt nur endlich viele dieser Äquivalenzklassen. 19:14.710 --> 19:19.170 Und außerdem zwingt mich niemand, wenn ich so einen Automaten 19:19.170 --> 19:22.150 hinschreibe, da immer diese Menge mit ranzuschreiben. 19:22.270 --> 19:23.990 Ich kann denen ja auch wieder einfach Namen geben. 19:26.770 --> 19:28.710 Aber mathematisch ist das gar kein Problem. 19:29.710 --> 19:33.650 Wir haben einen Automaten, dessen Zustandsmenge Äquivalenzklassen 19:33.650 --> 19:33.950 sind. 19:34.210 --> 19:37.010 Und da es endlich viele sind, ist das wohl ein endlicher Automat. 19:37.930 --> 19:41.370 Und ich muss mir jetzt halt noch überlegen, was ist die 19:41.370 --> 19:42.330 Übergangsfunktion. 19:44.530 --> 19:46.150 Und die habe ich hier jetzt mal hingeschrieben. 19:46.810 --> 19:49.690 Also das ist jetzt meine Nerode-Relation, das ist wieder die 19:49.690 --> 19:51.030 Definition, die wir vorher hatten. 19:54.310 --> 19:57.930 Und mein Automat ist jetzt Zustandsmenge sind die Äquivalenzklassen, 19:58.270 --> 19:59.810 Eingabealphabet wie gehabt. 20:00.790 --> 20:02.490 Übergangsfunktion muss ich noch was zu sagen. 20:06.750 --> 20:10.370 Startzustand, kann man sich überlegen, ist gerade die 20:10.370 --> 20:12.590 Äquivalenzklasse, in der das leere Wort drin ist. 20:14.310 --> 20:16.610 Und die Endzustände muss ich auch noch was dazu sagen. 20:17.410 --> 20:21.810 Und zwar, die Endzustände definiere ich als diejenigen 20:21.810 --> 20:24.590 Äquivalenzklassen, die Wörter aus L enthalten. 20:29.210 --> 20:37.550 Und die Übergangsfunktion definiere ich als, naja, wenn ich in dem 20:37.550 --> 20:42.250 Zustand bin, der der Äquivalenzklasse von W entspricht und A eingebe, 20:42.790 --> 20:46.190 dann bin ich danach in der Äquivalenzklasse, die WA entspricht. 20:47.710 --> 20:52.530 Und jetzt muss ich aber ein paar Dinge definieren, ein paar Dinge 20:52.530 --> 20:53.130 beweisen. 20:53.130 --> 20:58.290 Als erstes mal, ist das überhaupt eine sinnvolle Definition einer 20:58.290 --> 20:59.310 Übergangsfunktion? 21:01.110 --> 21:09.210 Da muss ich zeigen, dass, also der Trick ist ja, dieses W, da kann ich 21:09.210 --> 21:11.710 ja irgendein Element in der Äquivalenzklasse nehmen. 21:16.070 --> 21:18.750 Und jetzt hänge ich ein A dran und dann kriege ich halt eine neue 21:18.750 --> 21:19.650 Äquivalenzklasse. 21:19.650 --> 21:25.610 Aber das Ganze ist nur eine Funktion, wir reden ja hier über 21:25.610 --> 21:28.470 deterministische endliche Automaten, das Ganze ist nur eine Funktion, 21:29.230 --> 21:32.670 wenn die Äquivalenzklasse, in der ich lande, indem ich an das W einen 21:32.670 --> 21:36.850 A dran hänge, unabhängig davon ist, was das W ist. 21:37.410 --> 21:42.110 Das muss für alle W in der Äquivalenzklasse von W in die gleiche 21:42.110 --> 21:43.690 andere Äquivalenzklasse führen. 21:43.690 --> 21:47.250 Das muss ich erstmal beweisen, sonst ist das hier nicht die Definition 21:47.250 --> 21:50.350 eines endlichen Automaten, sondern irgendwas Komisches. 21:50.890 --> 21:54.330 Da steht halt eine Definition, die gar keine Funktion spezifiziert und 21:54.330 --> 21:55.910 dann nützt mir das nichts. 21:57.730 --> 22:03.230 Dann brauchen wir ein Lemma, das zeigt, dass Delta-Dach von 22:03.230 --> 22:07.810 Startzustand, W, gerade die Äquivalenzklasse von W ist. 22:07.810 --> 22:11.910 Und dann muss ich natürlich zeigen, dass die Sprache, die von diesem 22:11.910 --> 22:15.750 Automaten akzeptiert wird, gerade wieder die ursprüngliche Sprache 22:15.750 --> 22:16.030 ist. 22:17.630 --> 22:22.150 Also ich bin ja ausgegangen von irgendeiner regulären Sprache, dafür 22:22.150 --> 22:24.070 definiere ich mir die Nerode-Relation. 22:24.670 --> 22:27.350 Aus der Nerode-Relation definiere ich einen deterministischen 22:27.350 --> 22:28.370 endlichen Automaten. 22:29.370 --> 22:32.530 Und dann muss ich zeigen, dass die Sprache, die er akzeptiert, wieder 22:32.530 --> 22:34.550 die gleiche Sprache ist, mit der ich angefangen habe. 22:34.550 --> 22:37.450 Also das müssen wir jetzt beweisen als nächstes. 22:39.310 --> 22:41.660 Fangen wir erstmal mit der Wohldefiniertheit an. 23:15.960 --> 23:18.760 Also was muss ich für die Wohldefiniertheit zeigen? 23:18.760 --> 23:27.080 Ich habe jetzt zwei 23:33.440 --> 23:36.540 Elemente, X und Y, die sind in der gleichen Äquivalenzklasse der 23:36.540 --> 23:37.480 Nerode -Relation. 23:39.180 --> 23:43.640 Also X und Y sind jetzt das, was hier eigentlich das W war. 23:44.340 --> 23:46.440 Ich nehme zwei verschiedene Vertreter aus der gleichen 23:46.440 --> 23:47.400 Äquivalenzklasse. 23:48.240 --> 23:55.700 Und ich muss jetzt zeigen, dass wenn ich jetzt irgendein Buchstaben A 23:55.700 --> 24:07.400 dranhänge an die beiden Dinger, dass die auch wieder in der gleichen 24:07.400 --> 24:08.660 Äquivalenzklasse sind. 24:11.660 --> 24:16.740 Also in dieser Nerode-Relation entsprechend. 24:19.480 --> 24:22.420 Also das ist, was ich zeigen muss, das nennt man eine Rechtsinvarianz, 24:22.760 --> 24:23.880 weil ich rechts was dranhänge. 24:26.020 --> 24:27.900 Na gut, was weiß ich? 24:27.980 --> 24:31.280 Ich weiß, X und Y sind in der gleichen Äquivalenzklasse. 24:32.080 --> 24:36.240 Nach Definition der Nerode-Relation bedeutet das, dass für alle Z in 24:36.240 --> 24:39.600 Sigma -Stern, XZ in L genau dann, wenn YZ in L. 24:41.900 --> 24:45.020 Und insbesondere kann ich jetzt für ZA einsetzen. 24:48.630 --> 24:52.230 Ne, insbesondere kann ich jetzt das Z anders schreiben, nämlich AZ. 24:55.270 --> 25:03.250 Das heißt, es gilt auch für alle Wörter der Form AZ, dass XAZ in L 25:03.250 --> 25:06.170 genau dann, wenn YAZ in L. 25:06.990 --> 25:11.150 Da habe ich jetzt Klammern dazu geschrieben, das ist jetzt keineswegs 25:11.150 --> 25:16.630 ein Funktionsaufruf, sondern wir reden ja hier eigentlich über diese 25:16.630 --> 25:17.430 Produktbildung. 25:17.590 --> 25:19.170 Diese Punkte habe ich immer weggelassen. 25:20.330 --> 25:25.290 Aber da steht X Produkt A Produkt, Klammer auf, A Produkt Z. 25:26.830 --> 25:30.890 Das ist die Klammerung, die ich aus der Definition hier kriege. 25:30.890 --> 25:34.670 Und was ich jetzt mache, ist, dass ich die Klammerung einfach 25:34.670 --> 25:35.150 verschiebe. 25:35.250 --> 25:38.730 Ich nutze die Assoziativität dieses Produkts und schreibe jetzt 25:38.730 --> 25:42.170 stattdessen Klammer auf, X, A, Klammer zu, Z. 25:44.150 --> 25:46.290 Das ist eine Äquivalenzumformung. 25:46.390 --> 25:48.350 Ich habe halt wirklich nur hier die Klammern verschoben. 25:51.010 --> 25:59.010 Aber das ist gerade die Definition, dass XA äquivalent ist zu YA 25:59.010 --> 26:00.850 bezüglich der Nerode-Relation RL. 26:03.390 --> 26:06.790 Also ich habe hier nichts anderes gemacht, als Definitionen 26:06.790 --> 26:07.570 eingesetzt. 26:09.530 --> 26:13.490 Für dieses alle Z hier gesagt, okay, dann nehme ich eine spezielle 26:13.490 --> 26:16.630 Form an, nehme ich die Form Buchstabe und dann irgendein Wort. 26:17.450 --> 26:22.570 Und dann habe ich Klammern verschoben, also Assoziativität des 26:22.570 --> 26:23.630 Produkts ausgenutzt. 26:25.470 --> 26:26.430 Fragen dazu? 26:28.010 --> 26:31.110 Okay, also das war jetzt vielleicht schon der wichtigste Schritt. 26:31.370 --> 26:36.070 Also wir haben eine extrem abstrakte Definition hier und haben jetzt 26:36.070 --> 26:39.530 gezeigt, aha, das ist eine wohl definierte Funktion. 26:39.770 --> 26:45.030 Ich stecke irgendwas rein aus einer Äquivalenzklasse und kriege dann 26:45.030 --> 26:45.630 eine neue Äquivalenzklasse. 26:46.630 --> 26:49.410 Und damit haben wir gezeigt, dass das tatsächlich ein endlicher 26:49.410 --> 26:50.270 Automat ist. 26:50.850 --> 26:55.350 Der vielleicht wichtige Teil ist jetzt natürlich zu zeigen, dass der 26:55.350 --> 26:56.910 die richtige Sprache akzeptiert. 26:57.910 --> 27:00.350 Dafür brauchen wir aber erstmal diesen Hilfssatz hier. 27:04.340 --> 27:11.620 Das nämlich Delta-Dach bezüglich des Delta-Dach 27:11.620 --> 27:16.160 -Äquivalenzklassenautomat, lese ich das jetzt am besten, von 27:16.160 --> 27:21.000 Äquivalenzklasse von x, y gleich die Äquivalenzklasse von x, y ist. 27:21.540 --> 27:22.800 Das müssen wir jetzt zeigen. 27:23.320 --> 27:26.520 Das machen wir durch Induktion über die Länge von y. 27:28.820 --> 27:32.940 Für das leere Wort ist nichts zu zeigen, weil nach Definition von 27:32.940 --> 27:38.960 Delta -Dach von Äquivalenzklasse von x, y bleibe ich im gleichen 27:38.960 --> 27:40.460 Zustand, weil ich nichts eingebe. 27:41.400 --> 27:44.900 Und das ist eben einfach Äquivalenzklasse von x. 27:46.560 --> 27:48.880 Und jetzt mache ich Induktionsschritt. 27:52.200 --> 27:59.360 Delta-Dach-Äquivalenzklasse von Äquivalenzklasse x, a, w ist nach 27:59.360 --> 28:06.160 Definition von Delta-Dach gleich Delta-Dach von Delta von x, a, w. 28:07.280 --> 28:10.300 Und da setze ich jetzt einfach die Definition von Delta 28:10.300 --> 28:11.700 -Äquivalenzklasse ein. 28:13.680 --> 28:17.080 Delta-Äquivalenzklasse von x, a ist nämlich die Äquivalenzklasse von 28:17.080 --> 28:17.680 x, a. 28:23.800 --> 28:27.480 Aber jetzt habe ich plötzlich, ich will was wissen über Delta 28:27.480 --> 28:30.620 -Äquivalenzklasse, da muss glaube ich ein Dach hin. 28:32.260 --> 28:36.460 Nicht mehr für a, w, sondern für w, das ist ein um eins kürzeres Wort, 28:36.600 --> 28:40.480 deshalb kann ich die Induktionsvoraussetzung anwenden und kriege die 28:40.480 --> 28:42.840 Äquivalenzklasse von x, a, w wie gewünscht. 28:43.500 --> 28:44.380 Fragen dazu? 28:47.760 --> 28:52.040 Und jetzt kommt der Abschluss dessen, was wir hier zeigen wollen, dass 28:52.040 --> 28:55.000 der Äquivalenzklassenautomat auch L akzeptiert. 28:55.760 --> 28:59.200 Also was hier immer steht, ist einfach nur zur Erinnerung, das war die 28:59.200 --> 29:03.080 Nerode -Relation, das war unser endlicher Automat, das waren die 29:03.080 --> 29:04.840 Endzustände, das war die Übergangsfunktion. 29:04.840 --> 29:10.820 Und hier kommt jetzt das eigentliche Lemma, die Sprache, die der 29:10.820 --> 29:14.540 Äquivalenzklassenautomat akzeptiert, ist das ursprüngliche L. 29:16.780 --> 29:18.400 Dafür mache ich einen Äquivalenzschluss. 29:18.400 --> 29:24.300 Also betrachten ein beliebiges Wort, w, das ist in L von 29:24.300 --> 29:32.940 Äquivalenzklassenautomat, genau dann, wenn Delta-Dach-Äquivalenzklasse 29:32.940 --> 29:37.020 von Startzustand, w ist ein Endzustand. 29:37.020 --> 29:42.900 Und da setze ich jetzt ein, die definierten Wörter, die definierten 29:42.900 --> 29:46.400 Sachen, der Startzustand war die Äquivalenzklasse von Epsilon, das 29:46.400 --> 29:47.420 habe ich hier eingesetzt. 29:50.600 --> 29:55.000 Die Endzustandsmenge war ja gerade die Menge aller Äquivalenzklassen 29:55.000 --> 29:56.640 mit einem Wort aus der Sprache drin. 29:58.300 --> 30:03.200 Ich will nur wissen, dass der Zustand, den ich hier kriege, aus dieser 30:03.200 --> 30:06.000 Menge ist, die ja gerade die Menge der Endzustände ist. 30:07.020 --> 30:10.620 Da habe ich also nur die Definition von Delta-Dach- und M 30:10.620 --> 30:12.020 -Äquivalenzklasse angewendet. 30:12.820 --> 30:17.460 Nach dem Lemma eben ist das Äquivalent dazu, 30:25.700 --> 30:43.620 dass die Äquivalenzklasse von W in der Menge der Endzustände ist. 30:46.440 --> 30:51.240 Und das ist Äquivalent dazu, dass W selber in der Sprache ist. 30:52.000 --> 30:54.760 Das müssen wir allerdings noch zeigen, also das ist jetzt ein relativ 30:54.760 --> 30:56.880 großer Schritt zwischen den beiden. 30:57.980 --> 31:04.040 Was ich hier im Endeffekt behaupte ist, die Äquivalenzklasse von W ist 31:04.040 --> 31:11.960 eine der Äquivalenzklassen, die irgendein Element von L enthält. 31:14.000 --> 31:17.740 Aber daraus folgt nur, dass W in L ist, wenn Äquivalenzklassen ganz 31:17.740 --> 31:18.960 oder gar nicht in L sind. 31:20.500 --> 31:24.600 Der umgekehrte Schritt, wenn W in L, daraus folgt das hier, der ist 31:24.600 --> 31:24.980 klar. 31:26.260 --> 31:29.220 Aber den Schritt von dem, den habe ich hier jetzt nochmal 31:29.220 --> 31:29.960 wiedergegeben. 31:30.840 --> 31:36.840 Also, wenn die Äquivalenzklasse von W in dieser Endzustandsmenge ist, 31:39.000 --> 31:45.560 dann heißt das ja, dass es ein konkretes X in L gibt, 31:48.840 --> 31:52.240 mit der Eigenschaft, dass die Äquivalenzklasse von X gleich der 31:52.240 --> 31:53.860 Äquivalenzklasse von W ist. 32:03.680 --> 32:06.760 Genau, wenn die aber die gleiche Äquivalenzklasse haben, heißt das, 32:06.820 --> 32:11.240 die stehen in der Nerode-Relation zueinander, also X ist äquivalent W. 32:12.860 --> 32:16.680 Und daraus folgt nach Definition der Nerode-Relation, dass für alle Z 32:16.680 --> 32:20.940 gilt, XZ in L genau dann, wenn WZ in L. 32:26.190 --> 32:30.990 Und dann kann ich einfach hergehen und für ZY einsetzen, dann steht da 32:30.990 --> 32:35.550 XY in L genau dann, wenn WY in L ist. 32:37.910 --> 32:39.850 Und das ist aber das, was ich hier haben will. 32:40.030 --> 32:41.810 Das Y macht ja nichts. 32:42.750 --> 32:47.590 Dann steht da einfach X in L, Element L genau dann W Element L. 32:48.830 --> 32:52.850 Weil Y ist das neutrale Element der Produktoperation. 32:53.850 --> 32:54.870 Fragen dazu? 32:58.330 --> 33:04.690 Also das ist jetzt wahrscheinlich einer der abstraktesten Teile dieser 33:04.690 --> 33:05.350 Vorlesung. 33:06.350 --> 33:12.450 Ich gehe davon aus, dass nicht alle in diesem Saal mir gerade komplett 33:12.450 --> 33:13.370 folgen können. 33:14.390 --> 33:19.030 Das ist ein guter Grund, in die Übungen und Tutorien zu gehen, da wird 33:19.030 --> 33:20.130 das vertieft. 33:25.160 --> 33:29.760 Ich wünsche mir aber, dass selbst wenn sie das nicht alles perfekt 33:29.760 --> 33:39.840 können, sie trotzdem irgendwie diese Idee mitkriegen, worum es hier 33:39.840 --> 33:40.560 überhaupt geht. 33:41.400 --> 33:47.680 Also das ist schon was mathematisch sehr Schönes und auch für die 33:47.680 --> 33:49.320 Informatik dann am Ende nützlich. 33:51.500 --> 33:53.020 Wir haben eine Sprache. 33:54.120 --> 33:57.680 Wir definieren irgend so ein abstraktes Ding, eine Nerode-Relation. 33:59.420 --> 34:05.460 Darauf aufbauen dann einen endlichen Automaten mit einer ganz 34:05.460 --> 34:07.340 merkwürdigen Zustandsmenge. 34:08.160 --> 34:11.320 Und am Ende stellt sich heraus, das ist genau der Automat, den wir 34:11.320 --> 34:13.320 gerne hätten, um so eine Sprache zu beschreiben. 34:14.200 --> 34:17.480 Nämlich einer mit minimaler Zustandsmenge. 34:18.520 --> 34:21.960 Und wir lernen aus dieser ganzen abstrakten Formulierung außerdem 34:21.960 --> 34:25.720 noch, dass es genau einen solchen Minimalautomaten gibt. 34:26.280 --> 34:31.320 Und das hilft uns später beim Entwurf von konstruktiven Algorithmen, 34:31.440 --> 34:33.680 die so einen Minimalautomaten auch wirklich herleiten. 34:34.660 --> 34:38.420 Also wir machen was extrem Abstraktes, aber am Ende gibt es einiges an 34:38.420 --> 34:39.980 Einsicht und es ist auch nützlich. 34:41.680 --> 34:44.060 Und das wünsche ich mir, dass Sie das mitnehmen. 34:44.540 --> 34:50.900 Selbst wenn Sie vielleicht nicht in der Lage sind, diese Beweise rauf 34:50.900 --> 34:53.920 und runter zu reproduzieren, zu modifizieren und so weiter. 34:57.960 --> 35:01.260 Also wir haben diesen Äquivalenzklassenautomaten definiert, gezeigt, 35:01.380 --> 35:04.980 dass er wohl definiert ist und dass er genau L akzeptiert. 35:07.520 --> 35:11.100 Und ja, vielleicht kann man auch einen Schritt zurückgehen von diesen 35:11.100 --> 35:20.800 ganzen Formalismen und sich halt sagen, okay, also was ist die Nerode 35:20.800 --> 35:21.260 -Relation? 35:21.900 --> 35:23.720 Und sich einfach dieses Bild hier merken. 35:24.580 --> 35:30.720 Ich sage, Wörter sind zueinander äquivalent, wenn sie nicht 35:30.720 --> 35:33.740 unterscheidbar sind bezüglich dem, was hinterherkommt. 35:37.000 --> 35:40.420 Und es ist klar, dass bei einem endlichen Automaten das eigentlich das 35:40.420 --> 35:41.980 gleiche Konzept ist wie ein Zustand. 35:42.820 --> 35:46.140 Ein endlicher Automat ist in einem bestimmten Zustand und es ist ihm 35:46.140 --> 35:49.920 scheinbar egal, wie er dahin gekommen ist. 35:50.640 --> 35:53.520 Nichts anderes sagt auch die Nerode-Relation. 35:55.060 --> 35:59.100 Und deshalb gibt es eine Eins-zu-Eins-Beziehung zwischen der Nerode 35:59.100 --> 36:01.040 -Relation und einem endlichen Automaten. 36:01.040 --> 36:06.260 Und das Schöne ist, das ist nicht irgendein endlicher Automat, sondern 36:06.260 --> 36:09.620 sozusagen der Bestmögliche in einer gewissen Art und Weise. 36:11.460 --> 36:13.720 Jetzt machen wir trotzdem mal ein Beispiel. 36:14.900 --> 36:22.880 Wir gucken uns die Sprache an, Folgen von Nullen und Einsen. 36:25.600 --> 36:30.720 Und die Wörter sollen eine gerade Anzahl an Einsen und eine gerade 36:30.720 --> 36:32.200 Anzahl an Nullen haben. 36:34.900 --> 36:38.440 Kann mir jemand sagen, was die Äquivalenzklassen sind? 36:39.100 --> 36:42.080 Die sind hier auch schon angedeutet, es sind vier Stück. 36:43.440 --> 36:46.960 Kann mir jemand eine Charakterisierung dieser Äquivalenzklassen 36:46.960 --> 36:49.180 verraten? 36:52.590 --> 36:58.370 Das ist eigentlich so eine typische Intelligenztestaufgabe. 37:00.450 --> 37:03.930 Was haben die Elemente in so einer Menge gemeinsam? 37:06.490 --> 37:07.410 Genau, dankeschön. 37:07.510 --> 37:08.310 Haben das alle gehört? 37:09.470 --> 37:11.250 Ich gebe es nochmal durch das Mikrofon durch. 37:11.810 --> 37:17.550 Also jeder der vier Zustände sagt, die Kombination von gerade oder 37:17.550 --> 37:22.670 ungerade Anzahl von Nullen und gerade oder ungerade Anzahl von Einsen. 37:23.410 --> 37:28.810 Und wenn es beide gerade ist, dann habe ich einen Endzustand, dann ist 37:28.810 --> 37:32.030 es in der Sprache und sonst halt nicht. 37:32.610 --> 37:37.470 Und der Trick ist, wenn ich irgendein Wort in einer dieser Mengen habe 37:37.470 --> 37:44.850 und jetzt kommt ein weiterer Buchstabe dazu, dann gehe ich halt in 37:44.850 --> 37:48.570 eine von den anderen Mengen über und das ist aber völlig egal, was ich 37:48.570 --> 37:49.170 vorher hatte. 37:50.830 --> 37:53.210 Und so kann ich eben auch einen endlichen Automaten bauen. 37:53.510 --> 37:56.730 Es gibt also die Äquivalenzklassen, habe ich jetzt auch mal hingemalt, 37:56.830 --> 38:00.770 immer das kleinste Wort, das in der Äquivalenzklasse drin ist. 38:00.770 --> 38:04.670 Das ist gerade, gerade ist die Äquivalenzklasse von Epsilon. 38:07.350 --> 38:09.510 Das ist in dem Fall sogar auch der Startzustand. 38:10.610 --> 38:14.550 Null ist halt ungerade Anzahl von Nullen, gerade Anzahl von Einsen. 38:14.910 --> 38:18.670 Eins ist gerade Anzahl Nullen, ungerade Anzahl Einsen. 38:19.290 --> 38:26.570 Und 0,1 ist eben eins der kürzesten Wörter mit ungerade Anzahl Nullen 38:26.570 --> 38:27.770 und ungerade Anzahl Einsen. 38:29.070 --> 38:31.950 Das ist die Nerode-Relation dieser Sprache. 38:33.630 --> 38:36.550 Und der Äquivalenzklassenautomat sieht halt so aus, Start- und 38:36.550 --> 38:39.890 Endzustand ist die Äquivalenzklasse von Epsilon. 38:41.210 --> 38:45.750 Wenn ich eine Eins eingebe, gehe ich in die Äquivalenzklasse von Eins. 38:45.850 --> 38:48.570 Wenn ich ein Null eingebe, in die Äquivalenzklasse von Null. 38:49.130 --> 38:52.930 Also hier ist es tatsächlich immer so, dass ich dann einfach diese 38:52.930 --> 38:55.990 Null dazu schreibe oder die Eins dazu schreibe und die neue 38:55.990 --> 38:57.090 Äquivalenzklasse kriege. 38:57.770 --> 38:59.550 Man könnte sich überlegen, dass das genau passt. 39:00.170 --> 39:03.290 Also ich gebe eine Eins ein, dann komme ich von einer ungeraden Anzahl 39:03.290 --> 39:06.290 Einsen zu einer geraden Anzahl von Einsen in beiden Fällen. 39:07.390 --> 39:12.190 Und ich gebe eine Null ein, dann komme ich von einer ungeraden Anzahl 39:12.190 --> 39:15.310 Nullen zu einer geraden Anzahl von Nullen oder umgekehrt. 39:18.690 --> 39:22.850 Man kann sich überlegen, für diese konkrete Sprache, dass es auch 39:22.850 --> 39:26.870 nicht mit weniger Zuständen ausgehen kann. 39:29.170 --> 39:30.210 Fragen dazu? 39:34.220 --> 39:38.660 So, wir haben das eben schon mehr oder weniger gesagt, aber ich fasse 39:38.660 --> 39:39.680 es jetzt nochmal zusammen. 39:40.100 --> 39:44.260 Der Satz von Nerode, auf den wir hier die ganze Zeit zugearbeitet 39:44.260 --> 39:49.240 haben, sei RL die folgende Relation, nämlich die Menge aller XY aus 39:49.240 --> 39:54.080 Sigma Stern kreuz Sigma Stern, für die gilt, für alle Z in Sigma Stern 39:54.080 --> 39:57.940 ist XZ in L genau dann, wenn YZ in L. 40:00.040 --> 40:05.260 Erster Teil des Satzes, wenn L nicht regulär ist, dann ist der Index 40:05.260 --> 40:06.420 von RL unendlich. 40:08.200 --> 40:18.000 Wenn L regulär ist, dann ist der Index von RL endlich und sei der 40:18.000 --> 40:23.380 Äquivalenzklassenautomat definiert als der deterministische endliche 40:23.380 --> 40:28.800 Automat, bei dem die Zustände gleich die Äquivalenzklassen sind, 40:29.200 --> 40:36.080 Eingabe Alphabet Sigma, Übergangsfunktion Delta Dach, Startzustand ist 40:36.080 --> 40:39.940 die Äquivalenzklasse von Epsilon, Endzustände sind die 40:39.940 --> 40:44.140 Äquivalenzklassen, die Wörter aus L enthalten. 40:44.140 --> 40:47.340 Wir haben jetzt gelernt, die enthalten ausschließlich Wörter aus L. 40:51.700 --> 40:57.220 Dann gilt, sei M ein beliebiger endlicher Automat, der L akzeptiert, 40:58.860 --> 41:02.560 dann ist das die gleiche Sprache wie L von dem 41:02.560 --> 41:12.740 Äquivalenzklassenautomaten und die Äquivalenzrelation Rm, die sich aus 41:12.740 --> 41:18.380 den Zuständen definiert, ist eine Verfeinerung von RL. 41:20.980 --> 41:25.700 Ein wichtiges Korollar daraus, alle zustandsminimalen Automaten für L 41:25.700 --> 41:29.880 sind isomorph zu dem Äquivalenzklassenautomaten. 41:30.610 --> 41:34.860 Ich kann nicht sagen gleich, weil ich kann die Zustände ja irgendwie 41:34.860 --> 41:43.080 umbenennen, aber wenn mich Umbenennungen nicht interessieren, dann 41:43.080 --> 41:44.000 sind sie gleich. 41:45.040 --> 41:45.940 Fragen dazu? 41:53.420 --> 41:57.140 Dann werden wir beim nächsten Mal mehr darüber lernen, insbesondere 41:57.140 --> 42:02.260 wie man die Dinge auch konstruktiv berechnet und machen jetzt mit der 42:02.260 --> 42:02.920 Übung weiter. 42:03.340 --> 42:03.940 Vielen Dank. 42:05.680 --> 42:07.180 Fangen wir jetzt mit der Übung an. 42:08.620 --> 42:13.560 Am Anfang wollte ich nochmal zum Pumping-Lemma kommen, denn das sieht 42:13.560 --> 42:16.360 in der Form, wie es da auf den Folien steht, ja irgendwie ein bisschen 42:16.360 --> 42:21.780 komplex aus und vielleicht nicht besonders intuitiv. 42:23.320 --> 42:26.040 Deswegen wollte ich das einfach mal an einem Beispiel durchgehen, was 42:26.040 --> 42:27.580 dieses Aufpumpen dann heißt. 42:27.580 --> 42:30.640 Aber schauen wir vielleicht erstmal nochmal das Lemma an. 42:31.900 --> 42:37.400 Also es besagt, dass wenn eine Sprache regulär ist, dann gibt es eine 42:37.400 --> 42:43.200 Minimallänge n für Wörter, sodass alle Wörter der Sprache, die länger 42:43.200 --> 42:48.800 sind als dieses n, eine Zerlegung haben in diese drei Teile u, v und 42:48.800 --> 42:52.180 x, von denen der mittlere nicht leer ist und die ersten beiden 42:52.180 --> 42:56.940 zusammen höchstens n Zeichen haben, sodass dieser mittlere Teil hier 42:56.940 --> 42:59.220 beliebig oft auf- oder abgepumpt werden kann. 43:00.000 --> 43:03.040 Also ich kann den komplett weglassen oder mehrfach einsetzen. 43:04.660 --> 43:07.740 Und wenn man sich das jetzt am Beispiel von einem Automaten mal 43:07.740 --> 43:09.620 anschaut, dann sieht das so aus. 43:09.700 --> 43:11.660 Wir haben hier einen Automaten gegeben mit einer ziemlich 43:11.660 --> 43:16.920 offensichtlichen Schleife und wollen jetzt mal das Wort a a b b b a a 43:16.920 --> 43:17.820 a abarbeiten. 43:21.580 --> 43:25.420 Also angefangen vom Startzustand lesen wir das erste a, gehen in 43:25.420 --> 43:30.320 diesen Zustand q0 über, nach q1 usw. 43:31.360 --> 43:36.220 Und kommen dann mit diesem a hier das erste Mal zu einem Zustand 43:36.220 --> 43:37.620 zurück, bei dem wir schon mal waren. 43:37.880 --> 43:41.760 Haben einmal die Schleife durchlaufen und jetzt kommen nochmal a's. 43:43.640 --> 43:45.460 Und wir sind dann in einem n-Zustand. 43:47.160 --> 43:49.320 Das heißt, das Wort ist in der Sprache. 43:50.680 --> 43:53.700 Und wir können uns jetzt hier diese Zerlegung hinschreiben, die für 43:53.700 --> 43:54.600 das Pumping-Lemma funktioniert. 43:57.320 --> 43:59.900 Denn das hier ist das Präfix u. 44:00.340 --> 44:02.980 Dann kommt hier der Pumpteil in der Mitte, das v. 44:03.200 --> 44:05.540 Und diese Schleife hier können wir beliebig oft durchlaufen. 44:06.180 --> 44:09.480 Man kann die weglassen oder einmal, zweimal usw. 44:09.700 --> 44:12.540 durchlaufen und hat dann wieder ein Suffix. 44:14.380 --> 44:18.580 So muss man sich das Pumping-Lemma vorstellen, was das Aufpumpen 44:18.580 --> 44:19.120 bedeutet. 44:20.500 --> 44:26.160 Und die Aussage ist eben, dass es für jede reguläre Sprache gehen 44:26.160 --> 44:26.460 muss. 44:28.800 --> 44:31.580 Natürlich nur für unendliche reguläre Sprachen. 44:32.300 --> 44:35.120 Also endliche Sprachen sind ja immer regulär. 44:40.870 --> 44:46.150 Und diese Minimallänge hier muss eben auch groß genug gewählt werden, 44:46.290 --> 44:49.090 damit es funktioniert. 44:51.730 --> 44:53.570 Also ein paar Beispiele. 44:54.970 --> 44:58.450 Das Wort AA, AA ist drin, indem man es nullmal pumpt. 44:59.210 --> 45:01.350 Wenn man es zweimal pumpt, dann sieht es so aus. 45:04.170 --> 45:12.390 Und im Allgemeinen eben zwei A's, dann I mal BBBBA und dann nochmal 45:12.390 --> 45:13.150 zwei A's. 45:15.710 --> 45:18.610 Aber konstruktiv kann man das Pumping-Lemma ja nicht verwenden. 45:18.870 --> 45:22.090 Also man kann damit nicht zeigen, dass eine Sprache regulär ist, nur 45:22.090 --> 45:23.290 indem man sie aufpumpt. 45:24.650 --> 45:26.490 Was uns eigentlich interessiert, ist ja die Gegenrichtung. 45:27.400 --> 45:34.090 Also wenn man jetzt einmal alle Quantoren umdreht und dann sagen will, 45:34.710 --> 45:36.310 dass eine Sprache nicht regulär ist. 45:37.090 --> 45:41.390 Das heißt, ich habe jetzt hier zwischen den beiden immer aus dem 45:41.390 --> 45:43.570 Existenzquantor einen Allquantor gemacht. 45:45.030 --> 45:49.070 Und hier noch in der Aussage das Ganze negiert. 45:49.950 --> 45:54.050 Das heißt, was wir eigentlich zeigen müssen, ist, dass es für 45:54.050 --> 46:03.070 beliebige Wortlängen Worte gibt, sodass es mindestens ein Wort gibt, 46:03.510 --> 46:10.550 für das sich jede Zerlegung dieser Form irgendwie so pumpen lässt, 46:10.710 --> 46:12.970 dass es nicht in der Sprache mehr drin ist. 46:15.450 --> 46:19.070 Also wir sagen dann gewöhnlich, das hier ist die Zahl aus dem Pumping 46:19.070 --> 46:22.550 -Lemma, die Wortlänge, die Mindestwortlänge. 46:24.870 --> 46:30.590 Und müssen dann alle möglichen Zerlegungen dieses Wortes betrachten 46:30.590 --> 46:36.910 und ein i finden, sodass das gepumpte Wort nicht mehr in der Sprache 46:36.910 --> 46:37.130 ist. 46:37.210 --> 46:41.930 Und dann können wir damit feststellen, dass die Sprache nicht regulär 46:41.930 --> 46:42.270 ist. 46:45.230 --> 46:48.330 Um das mal an einem Beispiel zu machen, ich habe hier oben nochmal 46:48.330 --> 46:50.450 hingeschrieben, was wir machen wollen. 46:51.550 --> 46:56.350 Nehme ich mal die Sprache a hoch i, b hoch j, wobei die Bedingung ist, 46:56.590 --> 46:58.390 dass i größer ist als j. 46:59.710 --> 47:01.890 Also mehr a's als b's. 47:03.510 --> 47:05.150 Aber zuerst die a's und dann die b's. 47:07.390 --> 47:12.170 Die Sprache ist ja ganz offensichtlich nicht regulär, aber um das 47:12.170 --> 47:15.190 Pumping -Lemma anzuwenden, treffen wir jetzt mal die Annahme, dass sie 47:15.190 --> 47:15.890 regulär sei. 47:18.030 --> 47:19.470 Und fangen dann an. 47:19.990 --> 47:25.090 Ich färbe das jetzt hier immer ein, in den gleichen Farben wie hier 47:25.090 --> 47:26.970 oben, um die Aussagen zuzuordnen. 47:28.330 --> 47:31.410 Also wir fangen an mit sei n die Zahl aus dem Pumping-Lemma. 47:32.670 --> 47:36.170 Und dann müssen wir jetzt hier ein Wort wählen, das wir pumpen wollen. 47:37.190 --> 47:40.870 Und da wähle ich jetzt mal a hoch n plus 1, b hoch n. 47:41.730 --> 47:46.810 Ja, n plus 1 ist größer als n, also ist das Wort in der Sprache. 47:47.710 --> 47:51.190 Und offensichtlich ist es auch länger als n, denn es ist 2n plus 1 47:51.190 --> 47:51.450 lang. 47:54.850 --> 47:57.330 Jetzt müssen wir die Zerlegungen davon betrachten. 47:58.950 --> 48:00.710 Und zwar alle möglichen Zerlegungen. 48:02.850 --> 48:08.970 Also die Bedingungen sind, dass der mittlere Teil nicht leer ist und 48:08.970 --> 48:12.730 die beiden vorderen Teile zusammen höchstens n lang sind. 48:13.490 --> 48:18.630 Da das Wort aber mit n plus 1 a anfängt, sind sowohl in u als auch in 48:18.630 --> 48:19.850 v nur a drin. 48:22.150 --> 48:29.550 Das heißt, also u sind nur a, v sind nur a und der Rest ist dann das 48:29.550 --> 48:29.830 x. 48:31.290 --> 48:34.270 Und die kann man dann so hinschreiben, formal. 48:39.210 --> 48:40.730 Die letzte Bedingung noch. 48:42.550 --> 48:49.050 Und jetzt müssen wir irgendwie dieses v so aufpumpen, damit das Wort 48:49.050 --> 48:50.330 nicht mehr in der Sprache ist. 48:52.090 --> 48:56.250 Aber wenn wir hier mehr dieses v noch öfter wiederholen, dann wird ja 48:56.250 --> 48:57.550 nur der vordere Teil länger. 48:58.290 --> 48:59.530 Das hilft uns nicht. 49:00.430 --> 49:07.250 Wir wollen ja, dass es mindestens so viele b wie a gibt. 49:08.410 --> 49:11.750 Das heißt, was wir in dem Fall machen müssen, und das ist auch die 49:11.750 --> 49:15.970 einzige Wortfamilie, für die das dann funktioniert, ist es abzupumpen. 49:16.010 --> 49:18.190 Das heißt, wir müssen jetzt hier i gleich 0 wählen. 49:20.030 --> 49:26.190 Dann ist das neue Wort a hoch n plus 1 minus l b hoch n. 49:26.790 --> 49:32.530 Und da l mindestens 1 ist, ist das hier also kleiner gleich n und 49:32.530 --> 49:34.530 dadurch ist das Wort nicht in der Sprache mehr drin. 49:36.410 --> 49:38.990 Das ist ein Widerspruch zur Annahme, also ist die Sprache nicht 49:38.990 --> 49:39.450 regulär. 49:43.440 --> 49:47.620 Also das ist so ein Beispiel, wo genau ein Wort nur funktioniert für 49:47.620 --> 49:52.500 jedes n und auch nur eine Möglichkeit, das zu pumpen, funktioniert. 49:52.700 --> 49:53.870 Da muss man manchmal ein bisschen rumsuchen. 49:57.360 --> 50:01.400 Und in dem Fall ist das eben die einzige Möglichkeit, das zu pumpen. 50:04.000 --> 50:08.620 Während Logan mir das kurz aufbaut, ich brauche den Beamer noch. 50:12.360 --> 50:12.920 Ja. 50:15.420 --> 50:18.980 Wir haben das letzte Mal in der Vorlesung, also am Dienstag, auch noch 50:18.980 --> 50:22.340 die Epsilon-Nichtdeterministischen Automaten eingeführt. 50:23.860 --> 50:27.420 Und ich wollte einfach nochmal darauf eingehen, da hat es geheißen, in 50:27.420 --> 50:30.620 der Übung besprechen wir kurz, wie man die Epsilon-Übergänge wegnimmt 50:30.620 --> 50:34.180 und wie man von einem Epsilon näher zu einem normalen 50:34.180 --> 50:35.900 Nichtdeterministischen Automaten kommt. 50:36.560 --> 50:39.740 Darauf wollte ich eingehen und dann später auch nochmal auf die Nerode 50:39.740 --> 50:41.180 -Relation, die wir heute gemacht haben. 50:42.780 --> 50:45.480 Gut, als erstes, wie wird man Epsilon-Übergänge los? 50:46.780 --> 50:51.800 Der einfachste Schritt ist als erstes einmal zu überlegen, wo komme 50:51.800 --> 50:55.900 ich mit Epsilon-Übergängen überall hin von einem gewissen Zustand. 50:57.500 --> 51:00.600 Wenn wir uns zum Beispiel S anschauen, dann kommen wir mit einem 51:00.600 --> 51:05.560 Epsilon -Übergang sowohl zu Q2, aber von Q2 dann auch wieder zu Q3. 51:06.200 --> 51:11.000 Das heißt, der Epsilon-Abschluss von S sind diese drei Zustände. 51:11.200 --> 51:14.580 Man kann natürlich bei S selber bleiben, man kann zu Q2 gehen oder man 51:14.580 --> 51:15.640 kann zu Q3 gehen. 51:16.880 --> 51:18.860 Und das überlegt man sich erstmal für jeden Zustand. 51:19.040 --> 51:23.100 Von Q1 aus gibt es keine Epsilon-Übergänge, das ist einfach, ich 51:23.100 --> 51:24.020 bleibe bei Q1. 51:24.940 --> 51:29.360 Von Q2 aus, da gibt es immer noch den einen Epsilon-Übergang, man 51:29.360 --> 51:30.900 kommt von Q2 aus zu Q3. 51:31.000 --> 51:34.820 Das heißt, wann immer wir in Q2 sein könnten, könnten wir auch in Q3 51:34.820 --> 51:35.180 sein. 51:36.880 --> 51:39.600 Nicht -deterministische Automaten waren ja grundsätzlich immer so 51:39.600 --> 51:43.400 gemacht, wir könnten nur irgendwo sein oder wir sind in einer Menge 51:43.400 --> 51:44.920 von Zuständen gleichzeitig. 51:45.520 --> 51:48.480 Also wann immer wir in Q2 sein könnten, könnten wir auch in Q3 sein. 51:49.600 --> 51:52.600 Und von Q3 aus gibt es wiederum keinen Epsilon-Übergang. 51:52.760 --> 51:55.640 Das heißt, von Q3 aus bleiben wir nur in Q3. 51:55.640 --> 52:00.040 Also es ist hier immer so, ich habe das hier so ein bisschen kodiert, 52:00.160 --> 52:02.620 dass man so eine kleine Matrix hat. 52:04.240 --> 52:09.800 Auf der Diagonalen steht immer was, über oder unter der Diagonalen ist 52:09.800 --> 52:12.660 nur optional, nur wenn Epsilon-Übergänge wirklich rausgehen. 52:14.820 --> 52:17.900 Gut, wenn wir jetzt die Epsilon-Übergänge loswerden wollen, dann 52:17.900 --> 52:20.700 müssen wir sie praktisch verschmelzen mit den echten Übergängen. 52:21.260 --> 52:25.900 Wir müssen also überlegen, wenn wir in S ein A eingeben, müssen wir 52:25.900 --> 52:29.520 nicht nur machen, was bei S ein Pfeil mit A raus hat, sondern wir 52:29.520 --> 52:32.000 müssen auch schauen, vielleicht hat man erst einen Epsilon-Übergang 52:32.000 --> 52:35.660 gemacht und dann nochmal einen und hat da dann das A eingegeben. 52:36.260 --> 52:40.680 Das heißt, wenn wir jetzt die Übergänge von S aus betrachten wollen, 52:41.160 --> 52:46.460 müssen wir erstmal schauen, naja, was sind meine Epsilon-Übergänge, wo 52:46.460 --> 52:49.160 komme ich damit hin und wo komme ich damit vielleicht dann mit einem A 52:49.160 --> 52:49.560 weiter. 52:50.780 --> 52:53.600 Das heißt, wir schauen uns eben wieder diesen Epsilon-Abschluss von S 52:53.600 --> 52:58.480 an und schauen alle Übergänge mit einem A raus, die es aus diesem 52:58.480 --> 53:01.520 Epsilon -Abschluss rausgibt. 53:01.960 --> 53:05.560 Es ist in diesem Fall relativ einfach, weil nur Q3 hat wirklich einen 53:05.560 --> 53:06.200 A -Übergang. 53:07.040 --> 53:12.720 Das heißt, von S aus komme ich mit einem A nirgendwo hin, komme aber 53:12.720 --> 53:16.240 mit einem Epsilon zu Q2, komme hier wiederum mit einem A nirgendwo 53:16.240 --> 53:20.020 hin, komme aber wieder mit einem Epsilon zu Q3 und hier komme ich dann 53:20.020 --> 53:21.240 mit dem A wirklich raus. 53:21.240 --> 53:26.060 Das heißt, wenn ich in S einen A eingebe, dann kann ich eigentlich nur 53:26.060 --> 53:31.020 in Q1 landen, alle anderen Optionen landen irgendwie in dem nicht 53:31.020 --> 53:32.300 definierten Fehlerzustand. 53:33.560 --> 53:36.500 Das heißt, mit einem A komme ich zu Q2 und das mache ich jetzt für 53:36.500 --> 53:38.140 alle anderen Zustände auch. 53:38.800 --> 53:41.780 Von Q1, da gab es gar keine Epsilon-Übergänge, da gibt es nur die 53:41.780 --> 53:43.640 Möglichkeit aus Q1 selber rauszugehen. 53:46.340 --> 53:48.600 Von hier komme ich jetzt allerdings weiter. 53:49.480 --> 53:53.440 Also ich kann jetzt natürlich mit einem A zwar zu Q2 gehen, aber ich 53:53.440 --> 53:57.020 kann auch zu Q2 gehen und dann mit einem Epsilon, das immer implizit 53:57.020 --> 53:58.460 dabei ist, zu Q3 gehen. 53:58.460 --> 54:02.580 Das heißt, ein A führt mich jetzt zu diesen zwei Zuständen, die 54:02.580 --> 54:03.800 möglich sind. 54:04.900 --> 54:10.220 Von Q2 aus ein A einzugeben, hier führt es nirgendwo raus, führt aber 54:10.220 --> 54:12.960 wieder zu Q3 und Q3 führt dann wieder zu Q1. 54:14.500 --> 54:16.000 Und so mache ich das für alles. 54:16.560 --> 54:20.380 Von Q3 aus gibt es keine Epsilon-Übergänge, aber es gibt den direkten 54:20.380 --> 54:20.740 Weg. 54:21.520 --> 54:22.920 Für Bs muss ich es genauso machen. 54:28.460 --> 54:33.140 Wir können von S mit einem B aus zu Q1, wir können genauso gut aber 54:33.140 --> 54:38.380 über die Epsilon-Übergänge zu Q3 und von da aus mit einem B zu S. 54:39.340 --> 54:42.000 Und jetzt muss ich mir wieder überlegen, von S aus gab es Epsilon 54:42.000 --> 54:45.760 -Übergänge, das heißt ich muss jetzt wieder den zweiten Hop machen mit 54:45.760 --> 54:49.460 Epsilon -Übergängen und komme damit auch zu Q2 und Q3. 54:49.460 --> 54:54.480 Das heißt, wann immer wir einen Buchstaben weit gehen, müssen wir uns 54:54.480 --> 54:58.840 zuerst überlegen, was hätte ich mit Epsilon-Übergängen bis gerade eben 54:58.840 --> 55:04.480 machen können, was macht dann dieser eine Buchstabe dazu, welche 55:04.480 --> 55:08.980 Zustände kann ich erreichen aus den Zuständen, die ich erreicht habe 55:08.980 --> 55:09.980 mit den Epsilon-Übergängen. 55:10.940 --> 55:14.920 Und dann bin ich in den Zielzuständen und muss aber wieder überlegen, 55:15.000 --> 55:17.120 wo komme ich jetzt mit Epsilon-Übergängen hin. 55:17.880 --> 55:21.560 Das heißt, es sind immer so drei Hops, die man theoretisch gehen kann 55:21.560 --> 55:22.660 im Maximalfall. 55:23.320 --> 55:26.280 Und das war jetzt eben das erste Mal, dass der Maximalfall eintritt. 55:27.460 --> 55:28.720 Gut, dann gehen wir weiter. 55:29.080 --> 55:32.600 Es war S von Q1, gibt es wiederum keinen Epsilon-Übergang. 55:33.200 --> 55:35.980 Mit einem B kommen wir zu Q3, da gibt es keinen Epsilon-Übergang, das 55:35.980 --> 55:36.660 ist uninteressant. 55:38.240 --> 55:39.360 Q2 ist interessant. 55:39.940 --> 55:43.960 Aus Q2 raus gibt es keine B-Übergänge. 55:43.960 --> 55:47.500 Also müssen wir erstmal mit einem Epsilon-Übergang zu Q3 gehen. 55:49.580 --> 55:52.640 Hier ist jetzt schon das Interessante, es gibt eine Schleife an Q3. 55:52.800 --> 55:55.480 Das heißt, wir wissen schon, mit einem B können wir in Q3 bleiben. 55:56.680 --> 56:00.180 Wir können aber auch zu S gehen. 56:01.300 --> 56:03.940 Und dann müssen wir wieder machen, was wir gerade eben schon gemacht 56:03.940 --> 56:04.200 haben. 56:04.300 --> 56:09.040 Wir müssen von S wieder alle Epsilon-Übergänge abklappern und kommen 56:09.040 --> 56:11.780 damit eben wieder zu Q2 zurück. 56:12.680 --> 56:15.220 Oder theoretisch würden wir auch noch zu Q3 gehen. 56:15.320 --> 56:18.560 Das heißt, wir haben jetzt eigentlich sogar zwei Wege gefunden, wie 56:18.560 --> 56:22.020 wir zu Q3 kommen mit einem B. 56:23.680 --> 56:25.000 Gut, und das machen wir fertig. 56:26.500 --> 56:32.840 Jetzt haben wir uns eine Zustandsübergangsrelation aufgeschrieben, 56:33.500 --> 56:36.220 weil das Ganze ist ja immer noch ein nicht deterministischer Automat. 56:36.220 --> 56:38.480 Er war vorher nicht deterministisch. 56:38.640 --> 56:41.720 Jeder Automat mit Epsilon-Übergängen ist nicht deterministisch. 56:42.760 --> 56:47.920 Also auch wenn da überhaupt keine ambiguous Übergänge wären, wäre der 56:47.920 --> 56:48.860 nicht deterministisch. 56:49.780 --> 56:52.860 Aber wenn wir natürlich die Epsilon-Übergänge raus machen, wir bauen 56:52.860 --> 56:54.920 dabei mehr Ambiguity ein. 56:56.080 --> 56:58.500 Also man sieht ja hier schon, wir haben ganze Mengen, in die wir 56:58.500 --> 56:59.160 reingehen können. 56:59.220 --> 57:01.120 Das Ganze ist nicht deterministisch. 57:02.080 --> 57:05.440 Und so sieht jetzt der nicht deterministische Automat aus. 57:06.500 --> 57:09.940 Also das wird ganz schön hässlich manchmal, aber das Verfahren selber 57:09.940 --> 57:11.060 ist relativ einfach. 57:13.960 --> 57:18.780 Was jetzt hier auch noch wichtig ist, ist dadurch, dass ich vorher von 57:18.780 --> 57:23.220 S aus mit einem Epsilon-Übergang in einen akzeptierenden Zustand 57:23.220 --> 57:27.700 gekommen bin, muss S jetzt auch in akzeptierender Zustand sein. 57:28.380 --> 57:31.880 Also ich muss jeden Zustand, der mit einem Epsilon-Übergang zu einem 57:31.880 --> 57:35.200 akzeptierenden Zustand gekommen wäre, muss ich auch selber 57:35.200 --> 57:36.340 akzeptierend machen. 57:37.440 --> 57:38.860 Das muss man sich dazu überlegen. 57:40.060 --> 57:41.520 Was ist sonst noch wichtig? 57:41.780 --> 57:46.000 Man sieht jetzt hier, der Nicht-Determinismus ist noch größer 57:46.000 --> 57:46.760 ausgeweitet. 57:51.700 --> 57:57.400 Also auch wenn man aus einem Zustand nicht mit mehreren Symbolen zu 57:57.400 --> 58:04.400 einem anderen Zustand kommt, also auch wenn man nicht die normale 58:04.400 --> 58:08.660 Nicht -Determinismus-Definition erlaubt, die wir bisher hatten, wenn 58:08.660 --> 58:13.520 man Epsilon-Übergänge erlaubt, dann handelt man sich alles davon mit 58:13.520 --> 58:13.840 ein. 58:14.520 --> 58:18.880 Also wenn man deterministische Automaten definieren würde mit Epsilon 58:18.880 --> 58:22.040 -Übergängen, wären die direkt nicht deterministisch. 58:27.540 --> 58:30.480 Das wäre es zu Epsilon-Übergängen, wie man die los wird. 58:31.480 --> 58:33.580 Man muss sie auch nicht zwangsweise loswerden. 58:34.220 --> 58:38.380 Wenn die Aufgabe ist, eine Potenzmengen-Konstruktion zu machen, dann 58:38.380 --> 58:41.720 kann man auch eigentlich die Epsilon-Übergänge mit in die Potenzmengen 58:41.720 --> 58:42.510 -Konstruktion reinbauen. 58:43.290 --> 58:47.730 Da muss man also nicht zuerst diesen Graph konstruieren und dann die 58:47.730 --> 58:51.530 Potenzmengen -Konstruktion machen, sondern man kann direkt die 58:51.530 --> 58:55.510 Potenzmengen -Konstruktion machen, wenn man ein bisschen aufpasst. 58:56.470 --> 58:58.930 Also dann muss man eben auch bei jedem Schritt, den man in der 58:58.930 --> 59:05.610 Potenzmengen -Konstruktion macht, muss man dann wieder überlegen, wo 59:05.610 --> 59:07.770 man mit Epsilon-Übergängen hinkommen kann. 59:08.890 --> 59:12.250 Dann fängt man halt auch nicht bei der Menge an, die nur das 59:12.250 --> 59:17.990 Startsymbol enthält, sondern man fängt dann bei der Menge an, die den 59:17.990 --> 59:22.690 Startzustand enthält und alle Zustände, die man aus dem Startzustand 59:22.690 --> 59:25.130 mit Epsilon-Übergängen erreichen kann. 59:25.210 --> 59:26.890 Das ist dann der neue Startzustand. 59:27.830 --> 59:31.130 Also dann ist der Startzustand nicht mehr ganz so einfach, wie er war, 59:31.250 --> 59:33.150 wenn man keine Epsilon-Übergänge erlaubt. 59:33.150 --> 59:37.030 Das klingt gerade ein bisschen kompliziert, aber das kommt im Tutorium 59:37.030 --> 59:38.470 auch nochmal nächste Woche dran. 59:42.810 --> 59:45.730 Gut, das war es zum Epsilon-Abschluss. 59:46.150 --> 59:48.910 Dann will ich jetzt nochmal auf die Nerode-Relation eingehen. 59:50.330 --> 59:54.630 Ich bezeichne hier die Gleichheit ein bisschen anders, als es in der 59:54.630 --> 59:55.290 Vorlesung war. 59:55.290 --> 59:57.690 In der Vorlesung war ja immer da dieses Relationssymbol. 59:58.330 --> 01:00:01.810 Ich sage, die zwei Wörter sind gleich bezüglich dieser Sprache. 01:00:01.810 --> 01:00:05.530 Ich sage einfach ein Äquivalenzzeichen mit einem untergestellten L für 01:00:05.530 --> 01:00:06.050 die Sprache. 01:00:07.250 --> 01:00:10.310 Gut, und ich wollte einfach mal ein paar Beispiele durchgehen von 01:00:10.310 --> 01:00:13.770 Sprachen und all ihren Nerode-Äquivalenzklassen. 01:00:15.130 --> 01:00:21.890 Ein relativ einfaches Beispiel ist mal die reguläre Sprache, die alle 01:00:21.890 --> 01:00:25.910 Wörter über dem Alphabet AB enthält, die aber kein Doppel-B enthalten. 01:00:26.610 --> 01:00:31.950 Also immer wenn ich zwei B habe, müssen dazwischen mindestens ein A 01:00:31.950 --> 01:00:32.370 stehen. 01:00:34.750 --> 01:00:39.910 Man sieht also hier die Äquivalenzklasse von Epsilon und A ist 01:00:39.910 --> 01:00:42.510 dieselbe, weil sie enthalten beide noch kein Doppel-B. 01:00:43.810 --> 01:00:48.510 Und egal was sich anhängt, solange das kein Doppel-B enthält, ist das 01:00:48.510 --> 01:00:50.310 Wort immer noch fair. 01:00:51.550 --> 01:01:02.550 Aber wir können uns überlegen, dass die Äquivalenzklasse von Epsilon 01:01:02.550 --> 01:01:07.190 nicht dieselbe Äquivalenzklasse wie die von B sein kann und dann 01:01:07.190 --> 01:01:10.050 wiederum auch nicht dieselbe Äquivalenzklasse wie von BB. 01:01:10.750 --> 01:01:15.550 Von Epsilon zu B ist vielleicht das ein bisschen Schwierigere, aber 01:01:15.550 --> 01:01:20.430 man kann sich ganz einfach überlegen, wenn ich an Epsilon BAB anhänge, 01:01:21.330 --> 01:01:22.750 dann liegt das Wort in der Sprache. 01:01:23.450 --> 01:01:29.370 Wenn ich an B BAB anhänge, dann habe ich insgesamt das Wort BBAB, das 01:01:29.370 --> 01:01:30.510 liegt nicht in der Sprache. 01:01:31.170 --> 01:01:35.650 Das heißt, es müssen zwei unterschiedliche Äquivalenzklassen sein. 01:01:38.450 --> 01:01:43.130 Und das Interessante ist eben, dass diese drei Äquivalenzklassen schon 01:01:43.130 --> 01:01:46.130 alle Nerode-Äquivalenzklassen von dieser Sprache sind. 01:01:47.310 --> 01:01:56.010 Und zwar liegen in Epsilon alle Worte drin, die noch kein Doppel-B 01:01:56.010 --> 01:01:57.990 enthalten, aber auf ein A enden. 01:01:58.870 --> 01:02:02.430 Im Endeffekt, egal was sich dranhängt, solange es kein Doppel-B 01:02:02.430 --> 01:02:04.570 enthält, liegt das Wort in der Sprache. 01:02:05.490 --> 01:02:09.950 Dann alle Wörter, die auf B enden, aber noch kein Doppel-B enthalten. 01:02:17.830 --> 01:02:21.850 Das ist ein A+, und dann ein B hintendran, konkretiniert. 01:02:22.670 --> 01:02:24.050 Ganz normale, reguläre Ausdrücke. 01:02:25.410 --> 01:02:28.170 Ja, das ist ein bisschen mittig geraten. 01:02:28.390 --> 01:02:30.890 Normalerweise packe ich das immer ein bisschen näher zu dem A. 01:02:32.770 --> 01:02:36.630 Gut, also das hier sind alle Äquivalenzklassen, haben wir uns jetzt 01:02:36.630 --> 01:02:36.950 überlegt. 01:02:37.070 --> 01:02:42.850 Weil die Äquivalenzklasse mit BB, die enthält natürlich alle Wörter, 01:02:42.990 --> 01:02:45.750 die schon mal irgendwo Doppel-B enthalten. 01:02:46.310 --> 01:02:50.390 Ist ja dann egal, ob das jetzt am Ende oder am Anfang ist, diese 01:02:50.390 --> 01:02:54.510 Wörter, egal was sich anhängt, können nie wieder in der Sprache 01:02:54.510 --> 01:02:54.970 landen. 01:02:55.290 --> 01:02:58.350 Weil wir hängen ja nur hinten an, wir können nie in der Mitte oder so 01:02:58.350 --> 01:02:58.750 anhängen. 01:03:00.810 --> 01:03:04.810 Genau, also das sind alle drei Äquivalenzklassen, weil sie decken alle 01:03:04.810 --> 01:03:08.630 Wörter ab, die entweder schon Doppel-B enthalten, die noch kein Doppel 01:03:08.630 --> 01:03:11.710 -B enthalten und die sind nochmal aufgespalten, je nachdem, auf was 01:03:11.710 --> 01:03:12.330 sie enden. 01:03:12.910 --> 01:03:15.730 Ob sie auf dem B enden oder ob sie nicht auf dem B enden. 01:03:16.430 --> 01:03:18.050 Gut, dann kommen wir zur nächsten Sprache. 01:03:20.490 --> 01:03:23.530 Ja, wenn ich am Ende noch Zeit habe, kann ich auch kurz die Automaten 01:03:23.530 --> 01:03:24.470 für alle aufzeichnen. 01:03:25.510 --> 01:03:26.970 Die nächste Sprache. 01:03:27.650 --> 01:03:30.950 Alle Wörter, deren drittletzte Stelle in A ist. 01:03:32.030 --> 01:03:35.350 Wir haben schon so ähnliche Sprachen gesehen, in der Vorlesung waren 01:03:35.350 --> 01:03:36.550 sie einmal kurz dran. 01:03:36.650 --> 01:03:43.890 Da hat man gezeigt, dass da im Vergleich zu nicht-deterministischen 01:03:43.890 --> 01:03:47.630 Automaten deterministische Automaten größer werden können. 01:03:48.370 --> 01:03:51.250 Also hierfür könnte ich relativ einfach einen nicht-deterministischen 01:03:51.250 --> 01:03:52.150 Automat bauen. 01:03:55.070 --> 01:03:57.070 Der vier Zustände braucht. 01:03:58.490 --> 01:04:00.670 Und deterministisch geht es nicht ganz so einfach. 01:04:02.590 --> 01:04:07.590 Allerdings mit der Nerode-Äquivalenzrelation haben wir gesehen, kommen 01:04:07.590 --> 01:04:09.650 immer deterministische Automaten raus. 01:04:10.530 --> 01:04:14.530 Also der Äquivalenzklassenautomat, der gerade eben in der Vorlesung 01:04:14.530 --> 01:04:17.850 vorgestellt wurde, das sind immer deterministische Automaten, die da 01:04:17.850 --> 01:04:18.350 rauskommen. 01:04:18.450 --> 01:04:22.130 Das heißt, wir können jetzt mal schauen, wie viele Zustände der haben 01:04:22.130 --> 01:04:22.490 wird. 01:04:24.470 --> 01:04:27.410 Und die Idee ist, es wurde auch schon kurz in der Vorlesung 01:04:27.410 --> 01:04:31.810 angesprochen in Zusammenhang damit, wir müssen uns die letzten drei 01:04:31.810 --> 01:04:33.470 Zeichen von jedem Wort merken. 01:04:34.430 --> 01:04:38.310 Weil je nachdem, was für Wörter wir anhängen, können die letzten drei 01:04:38.310 --> 01:04:41.190 Zeichen von dem Wort, das wir gerade betrachten, wichtig werden. 01:04:42.090 --> 01:04:44.770 Deshalb gibt es die folgenden acht Äquivalenzklassen. 01:04:47.950 --> 01:04:51.310 Diese drei Äquivalenzklassen sind die, die Wörter aus der Sprache 01:04:51.310 --> 01:04:51.750 enthalten. 01:04:53.250 --> 01:04:56.270 Und diese vier Äquivalenzklassen sind die, die Wörter aus der Sprache 01:04:56.270 --> 01:04:56.570 enthalten. 01:04:56.710 --> 01:04:59.950 Und diese vier sind die, die Wörter, die nicht in der Sprache liegen, 01:05:00.010 --> 01:05:00.390 enthalten. 01:05:01.030 --> 01:05:05.410 Wir brauchen den Unterschied aber trotzdem, weil zum Beispiel hier 01:05:05.410 --> 01:05:10.070 zwischen diesen zwei gibt es den Unterschied, wenn ich irgendein 01:05:10.070 --> 01:05:15.430 zweibuchstabiges Wort anhänge, dann ist in diesem Fall akzeptierend, 01:05:15.510 --> 01:05:17.330 in diesem Fall nicht akzeptierend. 01:05:17.330 --> 01:05:23.630 Zwischen diesen beiden hier ist es, wenn ich irgendein einbuchstabiges 01:05:23.630 --> 01:05:30.510 Wort anhänge, dann ist dieses hier nicht akzeptierend, weil hier dann 01:05:30.510 --> 01:05:36.050 eben irgendein zusätzlicher Buchstabe steht und dieses hier wäre 01:05:36.050 --> 01:05:36.630 wieder akzeptierend. 01:05:37.470 --> 01:05:41.930 Im Endeffekt kann man sich überlegen, der Unterschied zwischen diesen 01:05:41.930 --> 01:05:46.450 Äquivalenzklassen, der zeigt sich nur, wenn wir kurze Wörter anhängen. 01:05:46.450 --> 01:05:51.190 Wenn wir ein langes Wort anhängen, das über drei Buchstaben hat, ist 01:05:51.190 --> 01:05:55.050 es akut gerade komplett egal, in welcher Äquivalenzklasse das Wort 01:05:55.050 --> 01:05:55.710 davor war. 01:05:56.410 --> 01:06:01.050 Nur wenn wir kurze Wörter anhängen, kann sich irgendwas unterscheiden. 01:06:01.790 --> 01:06:04.910 Und damit lässt sich eben zeigen, dass das alle Äquivalenzklassen 01:06:04.910 --> 01:06:05.210 sind. 01:06:06.310 --> 01:06:10.250 Dann muss man noch ganz kurze Ursprungswörter betrachten. 01:06:10.250 --> 01:06:17.070 Also zum Beispiel das leere Wort sieht man hier ja jetzt noch nicht 01:06:17.070 --> 01:06:21.130 direkt auf den ersten Blick drin, wobei man kann argumentieren, dass 01:06:21.130 --> 01:06:24.950 das Epsilon hier in diese Äquivalenzklasse reingehört. 01:06:25.570 --> 01:06:31.790 Genauso wie nur das A in diese Äquivalenzklasse reingehört und nur das 01:06:31.790 --> 01:06:35.230 B hier rein und so kann man auch für kurze Wörter das überlegen. 01:06:35.230 --> 01:06:41.430 Und zwar der Grund ist, dass ein B an der drittletzten Stelle zu haben 01:06:41.430 --> 01:06:45.650 ist genauso schlimm wie gar nichts an der drittletzten Stelle zu 01:06:45.650 --> 01:06:47.590 haben, weil das Wort nur zwei Stellen lang ist. 01:06:48.490 --> 01:06:50.970 Wenn das Wort nur zwei Stellen lang ist, ist es laut dieser 01:06:50.970 --> 01:06:55.710 Sprachdefinition nicht in der Sprache drin und kann aber durch das 01:06:55.710 --> 01:07:00.090 Anhängen von einem mindestens dreibuchstabigen Teilwort in die Sprache 01:07:00.090 --> 01:07:00.710 reinkommen. 01:07:00.710 --> 01:07:07.190 Und genau das hier symbolisiert unsere Äquivalenzklasse mit drei Bs. 01:07:09.030 --> 01:07:13.430 Wir haben hier mit diesen acht Äquivalenzklassen auch die zu kurzen 01:07:13.430 --> 01:07:17.370 Wörter abgedeckt, auch wenn ich sie jetzt so benannt habe, als gäbe es 01:07:17.370 --> 01:07:19.110 zu kurze Wörter eigentlich nicht. 01:07:20.410 --> 01:07:22.390 Aber so lassen sie sich einen Tick schöner aufschreiben. 01:07:23.690 --> 01:07:28.350 Gut, das wäre mal ein Beispiel für eine relativ, ich nenne es mal 01:07:28.350 --> 01:07:31.130 komplizierte, aber noch reguläre Sprache. 01:07:31.630 --> 01:07:35.350 Und jetzt kommt noch mal ein Beispiel für eine nicht reguläre Sprache, 01:07:35.470 --> 01:07:39.150 wo man dann eben zeigen soll, dass es unendlich viele Nerode 01:07:39.150 --> 01:07:40.430 -Äquivalenzklassen gibt. 01:07:40.830 --> 01:07:44.730 Weil wir haben ja gerade in der Vorlesung gehört, das ist im Endeffekt 01:07:44.730 --> 01:07:45.670 genau dasselbe. 01:07:46.490 --> 01:07:49.990 Wenn es unendlich viele Nerode-Äquivalenzklassen gibt, ist was nicht 01:07:49.990 --> 01:07:50.530 regulär. 01:07:50.970 --> 01:07:53.770 Wenn was nicht regulär ist, gibt es unendlich viele Nerode 01:07:53.770 --> 01:07:54.710 -Äquivalenzklassen. 01:07:55.770 --> 01:07:58.230 Weil wenn es nicht unendlich viele von den Äquivalenzklassen gibt, 01:07:58.350 --> 01:08:02.090 könnte ich ein Automat bauen, nämlich den Äquivalenzklassenautomat von 01:08:02.090 --> 01:08:02.610 gerade eben. 01:08:09.370 --> 01:08:12.570 Wir schauen jetzt hier die Sprache an, die wurde, glaube ich, in der 01:08:12.570 --> 01:08:14.510 letzten Vorlesung ganz zu Ende gemacht. 01:08:14.510 --> 01:08:16.770 Ich weiß nicht genau, ob das alle mitgekriegt haben. 01:08:18.690 --> 01:08:22.450 Das ist eine Sprache, von der ich mit dem Pumping-Lemmer nicht 01:08:22.450 --> 01:08:25.070 beweisen kann, dass sie nicht regulär ist. 01:08:32.990 --> 01:08:38.590 Weil wenn ich mir ein langes Wort hernehme, dann enthält es entweder 01:08:38.590 --> 01:08:42.170 Cs am Anfang oder es enthält keine Cs am Anfang. 01:08:42.170 --> 01:08:45.730 Wenn es keine Cs am Anfang enthält, kann ich mir ein beliebiges 01:08:45.730 --> 01:08:54.370 Subwort nehmen, das entweder nur aus As besteht oder nur aus Bs 01:08:54.370 --> 01:08:54.790 besteht. 01:08:55.310 --> 01:08:57.850 Wenn ich dieses Subwort habe, kann ich das pumpen. 01:08:58.710 --> 01:09:01.750 Und so wie die Sprache konstruiert ist, gibt es das hier immer, wenn 01:09:01.750 --> 01:09:04.210 das Wort eine gewisse Länge hat. 01:09:04.730 --> 01:09:07.250 Also eine gewisse Länge ist ja immer vorausgesetzt beim Pumping 01:09:07.250 --> 01:09:07.510 -Lemmer. 01:09:08.350 --> 01:09:13.850 Und wenn das Wort vorher hier drin lag, dann hat es ja mal mindestens 01:09:13.850 --> 01:09:14.530 ein C. 01:09:16.210 --> 01:09:20.930 Wenn es dieses C hat, dann wähle ich das aus und dann kann ich das 01:09:20.930 --> 01:09:22.330 beliebig häufig wiederholen. 01:09:22.410 --> 01:09:23.670 Ich kann das also größer machen. 01:09:24.430 --> 01:09:25.430 Das verändert nichts. 01:09:26.530 --> 01:09:28.690 Dann würde das Wort immer noch in der Sprache liegen. 01:09:28.690 --> 01:09:39.610 Der schlimmste Fall ist, wenn alle Cs in diesem mittleren Teilwort 01:09:39.610 --> 01:09:43.470 liegen und ich lasse das mittlere Teilwort plötzlich weg. 01:09:44.350 --> 01:09:47.490 Weil ich kann ja immer eine Sprache abpumpen und damit das Wort kürzer 01:09:47.490 --> 01:09:47.810 machen. 01:09:48.710 --> 01:09:52.230 Dabei könnte ich alle Cs vernichten, aber was passiert dabei, wenn ich 01:09:52.230 --> 01:09:56.170 alle Cs wegmache, bin ich eigentlich nur in diesem hinteren Teil drin 01:09:56.170 --> 01:09:56.710 gelandet. 01:09:56.710 --> 01:10:01.570 Das heißt, auch in diesem Fall kann ich die Sprache beliebig pumpen 01:10:01.570 --> 01:10:05.130 und bleibe immer noch in der Sprache drin. 01:10:05.490 --> 01:10:10.330 Das heißt, für das Pumping-Lemmer sieht diese Sprache so aus, als wäre 01:10:10.330 --> 01:10:11.030 sie regulär. 01:10:12.990 --> 01:10:15.630 Ich möchte jetzt zeigen, dass sie nicht regulär ist und deswegen 01:10:15.630 --> 01:10:17.970 betrachte ich die Nerode-Äquivalenz-Klassen. 01:10:22.510 --> 01:10:31.770 Meine erste Überlegung ist, dass diese zwei Wörter C A hoch N und C A 01:10:31.770 --> 01:10:35.450 hoch M unterschiedliche Äquivalenz-Klassen sind. 01:10:35.810 --> 01:10:37.690 Zumindest wenn N ungleich M ist. 01:10:38.650 --> 01:10:44.670 Und die Idee ist nämlich, wenn ich N Bs hinten anhänge, wird dieses 01:10:44.670 --> 01:10:45.890 Wort hier akzeptiert werden. 01:10:46.010 --> 01:10:49.310 Dieses Wort liegt dann in der Sprache und dieses Wort liegt nicht in 01:10:49.310 --> 01:10:49.870 der Sprache. 01:10:50.870 --> 01:10:54.930 Das heißt, egal wie ich N und M wähle, es sind unterschiedliche 01:10:54.930 --> 01:10:57.510 Äquivalenz -Klassen, wenn N und M unterschiedlich sind. 01:11:00.410 --> 01:11:04.790 Und das hier sind dann alle Äquivalenz-Klassen, die ein Wort haben. 01:11:05.150 --> 01:11:08.390 Also alle Äquivalenz-Klassen zu dieser Sprache. 01:11:09.170 --> 01:11:11.910 Wir sehen schon, wir haben hier irgendwie zweimal eine unendliche 01:11:11.910 --> 01:11:12.190 Menge. 01:11:13.510 --> 01:11:17.310 Aber es wäre ja erstmal okay, unendlich viele Nerode-Äquivalenz 01:11:17.310 --> 01:11:18.030 -Klassen zu haben. 01:11:18.250 --> 01:11:19.030 Gehen wir einmal durch. 01:11:19.910 --> 01:11:24.730 Epsilon hat eine eigene Äquivalenz-Klasse, in der nur Epsilon drin 01:11:24.730 --> 01:11:25.070 liegt. 01:11:25.970 --> 01:11:32.630 Weil an Epsilon kann ich sowohl C A hoch N, B hoch N anhängen, als 01:11:32.630 --> 01:11:37.390 auch irgendwie A, B, irgendwas, was eben beliebig viele As und 01:11:37.390 --> 01:11:38.690 beliebig viele Bs enthält. 01:11:40.590 --> 01:11:43.910 Epsilon erlaubt mehr in dem Zusammenhang als zum Beispiel A. 01:11:44.630 --> 01:11:49.010 An A kann ich beliebig viele As anhängen und dann beliebig viele Bs 01:11:49.010 --> 01:11:52.590 und dann bleibe ich damit in dieser Teilsprache hier. 01:11:52.590 --> 01:11:57.950 Also diese zwei Mengen hier liegen schon mal definitiv in dieser 01:11:57.950 --> 01:12:02.670 Teilsprache, können gar nicht mehr in diese Teilsprache hier 01:12:02.670 --> 01:12:03.170 reinfallen. 01:12:04.230 --> 01:12:08.810 Wenn ich mit einem B anfange das Wort, dann muss hier offensichtlich A 01:12:08.810 --> 01:12:13.570 null gewesen sein, oder zumindest können da schon viele As gekommen 01:12:13.570 --> 01:12:14.970 sein und dann kommt aber ein B. 01:12:15.690 --> 01:12:19.690 In dieser Äquivalenz-Klasse ist es so, wenn noch beliebig viele Bs 01:12:19.690 --> 01:12:20.890 kommen, ist alles okay. 01:12:21.670 --> 01:12:24.490 As dürfen keine mehr kommen, weil die sind hier ja immer noch 01:12:24.490 --> 01:12:25.130 geordnet. 01:12:28.210 --> 01:12:31.010 Der Unterschied zwischen diesen beiden ist, dass hier noch As kommen 01:12:31.010 --> 01:12:34.750 dürfen und hier keine As mehr kommen dürfen. 01:12:35.210 --> 01:12:37.290 Hier dürfen Bs kommen, die dürfen hier auch kommen. 01:12:38.810 --> 01:12:42.870 Die interessanteren Äquivalenzklassen sind eigentlich diese zwei hier, 01:12:43.050 --> 01:12:48.710 also diese zwei unendlich viele Äquivalenzklassen hier. 01:12:50.530 --> 01:12:54.010 C, A hoch N, haben wir gerade uns überlegt, sind unendlich viele 01:12:54.010 --> 01:13:00.090 Äquivalenzklassen abhängig von dem N, weil es sich für N und M 01:13:00.090 --> 01:13:04.510 unterschiedlich verhält beim Anhängen von B hoch N oder B hoch M, je 01:13:04.510 --> 01:13:05.490 nachdem wie man es haben will. 01:13:07.290 --> 01:13:11.410 Hier kommt es ungefähr auf dasselbe drauf raus, wenn wir schon mal ein 01:13:11.410 --> 01:13:15.490 B hatten, dürfen jetzt keine As mehr angehängt werden. 01:13:16.430 --> 01:13:20.170 Also hier brauchen wir jetzt noch N-1 Bs. 01:13:20.690 --> 01:13:25.750 Der Unterschied zu hier ist, dass hier noch As hätten kommen können, 01:13:26.570 --> 01:13:28.810 solange dann danach mehr Bs kommen. 01:13:29.640 --> 01:13:35.550 Solange danach genau N Bs mehr kommen als As gekommen sind, kommen wir 01:13:35.550 --> 01:13:40.810 hier immer noch zu einem akzeptierenden Ding. 01:13:42.590 --> 01:13:46.950 Und jetzt würde ich einfach mal alle Automaten, die wir hier praktisch 01:13:46.950 --> 01:13:49.730 generiert haben, aufschreiben. 01:13:52.190 --> 01:13:55.930 Also die oberen einfach nur kurz zur Vervollständigung, dass man halt 01:13:55.930 --> 01:13:59.090 sieht, dass das die minimale Anzahl an Zuständen sind. 01:14:00.750 --> 01:14:05.930 Und den unteren möchte ich mal kurz skizzieren, wie ein unendlicher 01:14:05.930 --> 01:14:07.430 Automat aussehen würde. 01:14:07.930 --> 01:14:10.350 Also mit einem unendlichen Automat kann ich natürlich viel 01:14:10.350 --> 01:14:11.970 kompliziertere Sprachen erkennen. 01:14:12.790 --> 01:14:15.670 Prinzipiell kann ich mit einem unendlichen Automat jede Sprache 01:14:15.670 --> 01:14:19.930 erkennen, weil ich kann einfach einen riesigen Baum machen, der je 01:14:19.930 --> 01:14:23.230 nachdem, was für ein Wort es ist, in einem ganz anderen Zustand ist. 01:14:25.530 --> 01:14:29.790 Also dessen Ausgangsgrad pro Knoten ebenso groß ist wie das Alphabet. 01:14:30.230 --> 01:14:33.570 Dann endet jedes Wort in einem eigenen Zustand und dann muss ich nur 01:14:33.570 --> 01:14:38.710 noch die Wörter, die in der Sprache liegen, zu akzeptierenden 01:14:38.710 --> 01:14:39.530 Zuständen machen. 01:14:40.050 --> 01:14:42.810 Das heißt, unendliche Automaten sind normalerweise ziemlich 01:14:42.810 --> 01:14:45.390 uninteressant, aber ich male ihn jetzt mal zum Spaß auf. 01:14:46.130 --> 01:14:47.210 Gut. 01:14:51.950 --> 01:14:55.570 Die erste Sprache, die wir uns überlegt haben, war die Sprache mit sie 01:14:55.570 --> 01:14:56.990 enthält kein BB. 01:14:58.890 --> 01:15:03.210 Die Äquivalenzklassen sahen dabei aus wie Epsilon, 01:15:06.780 --> 01:15:09.880 B und BB. 01:15:10.640 --> 01:15:15.240 Wir erinnern uns, das war für alle Wörter, die auf A enden und noch 01:15:15.240 --> 01:15:20.140 kein BB enthalten, die auf B enden und noch kein BB enthalten oder die 01:15:20.140 --> 01:15:24.260 schon irgendwo BB enthalten und damit definitiv nicht mehr zu einem 01:15:24.260 --> 01:15:25.880 akzeptierenden Zustand führen können. 01:15:28.240 --> 01:15:29.560 Wir fangen immer an. 01:15:29.680 --> 01:15:32.260 Der Startzustand ist der, der Epsilon enthält. 01:15:32.400 --> 01:15:34.740 Das ist hier einfach, weil der mit Epsilon benannt ist. 01:15:37.940 --> 01:15:44.680 Dann haben wir einen Zustand, der mit B benannt ist und einen Zustand, 01:15:45.000 --> 01:15:46.420 der mit BB benannt ist. 01:15:50.970 --> 01:15:54.810 Akzeptierend, haben wir uns schon überlegt, sind die beiden hier, weil 01:15:54.810 --> 01:15:59.390 die nur von Wörtern angenommen werden können, die kein BB enthalten. 01:16:00.470 --> 01:16:09.170 Wenn das Wort jetzt Epsilon war und ich gebe ein B ein, dann muss ich 01:16:09.170 --> 01:16:11.410 natürlich in diesen Zustand, wo das eine B drin ist. 01:16:12.110 --> 01:16:15.430 Genauso, wenn ich hier ein A eingebe, kann ich zurück in das Epsilon, 01:16:15.990 --> 01:16:19.850 weil jetzt nicht mehr die Chance da ist, dass ich mit einem B direkt 01:16:19.850 --> 01:16:21.190 in den Fehlerzustand muss. 01:16:21.770 --> 01:16:24.990 Wenn das Wort auf B endet und ein B eingegeben wird, komme ich in den 01:16:24.990 --> 01:16:28.910 Fehlerzustand und da kann ich natürlich nicht mehr rauskommen. 01:16:29.570 --> 01:16:30.810 Gut, das war einfach. 01:16:31.470 --> 01:16:36.470 Jetzt kommt der etwas kompliziertere Automat für die Sprache, die an 01:16:36.470 --> 01:16:38.950 der drittletzten Stelle ein A haben sollte. 01:16:40.510 --> 01:16:48.270 Da waren die Zustände... Ah, sorry, stimmt, hier fehlt noch eine 01:16:48.270 --> 01:16:53.450 Schleife für wenn ich ein A eingebe in Epsilon. 01:16:54.130 --> 01:16:54.470 Danke. 01:16:56.310 --> 01:17:02.310 Gut, dann schiebe ich das mal raus und wir wollen jetzt den Automaten, 01:17:02.450 --> 01:17:05.750 der alle Wörter erkennt, die an der drittletzten Stelle ein A 01:17:05.750 --> 01:17:06.310 enthalten. 01:17:07.350 --> 01:17:15.510 Wir haben schon überlegt, dass das Epsilon in diesen Zustand hier 01:17:15.510 --> 01:17:16.110 reinfällt. 01:17:19.190 --> 01:17:24.990 Wenn ich jetzt ein A eingebe, dann komme ich in den Zustand BBA, weil 01:17:24.990 --> 01:17:29.170 die neun letzten drei Zeichen BBA sind. 01:17:30.270 --> 01:17:32.310 Hier habe ich ein Selfloop für B. 01:17:33.250 --> 01:17:40.230 Wenn ich hier jetzt wiederum ein A eingebe, komme ich in BAA. 01:17:44.210 --> 01:17:51.590 Wenn ich ein B eingebe, komme ich zu BAB. 01:17:53.770 --> 01:17:58.630 Also, ich komme immer zur Äquivalenzklasse, die das enthält. 01:18:00.390 --> 01:18:04.810 Wenn ich hier ein A eingebe, komme ich zu AAA. 01:18:08.030 --> 01:18:13.630 Wenn ich hier ein B eingebe, komme ich zu AAB. 01:18:18.510 --> 01:18:29.590 Gut, wenn ich hier ein A eingebe, komme ich zu ABA. 01:18:33.010 --> 01:18:34.110 Das wird spaßig. 01:18:35.530 --> 01:18:43.520 Wenn ich hier ein B eingebe, komme ich zu ABB. 01:18:48.950 --> 01:18:52.050 So, jetzt haben wir alle Zustände, weil es waren acht 01:18:52.050 --> 01:18:53.050 Äquivalenzklassen. 01:18:54.050 --> 01:18:56.370 Jetzt muss ich die noch irgendwie sinnvoll verbinden. 01:18:57.830 --> 01:19:01.270 Also, wir haben hier B, A, B, A, B. 01:19:01.410 --> 01:19:04.170 Das heißt, die vier sind komplett verbunden. 01:19:05.430 --> 01:19:08.970 Hier kann man sich überlegen, wenn ich ein A eingebe, bleibe ich bei 01:19:08.970 --> 01:19:10.490 dem Ding selber. 01:19:10.590 --> 01:19:12.390 Wenn ich ein B eingebe, gehe ich hier rüber. 01:19:15.090 --> 01:19:22.610 Wenn ich hier ein A eingebe, dann komme ich zu ABA. 01:19:24.210 --> 01:19:28.290 Wenn ich ein B eingebe, komme ich hier rüber. 01:19:29.490 --> 01:19:37.690 Wenn ich hier ein A eingebe, komme ich hier hin zu BAA. 01:19:38.130 --> 01:19:42.670 Wenn ich ein B eingebe, komme ich zu BAB. 01:19:45.430 --> 01:19:46.090 Gut. 01:19:49.830 --> 01:19:52.210 Achso, der letzte Zustand noch. 01:19:52.910 --> 01:19:56.790 Wenn ich ein B eingebe, komme ich ganz nach hier oben zurück. 01:19:57.410 --> 01:20:00.450 Ich habe gar kein A mehr in den letzten drei Zeichen. 01:20:01.110 --> 01:20:03.830 Wenn ich ein A eingebe, komme ich zu BBA. 01:20:11.590 --> 01:20:13.610 Das ist der Graph. 01:20:13.670 --> 01:20:17.090 Wir haben schon gesagt, das ist ein relativ komplizierter Graph für 01:20:17.090 --> 01:20:18.690 die relativ einfache Sprache. 01:20:19.390 --> 01:20:23.070 Wie gesagt, als nicht deterministischen Automat könnte man es so 01:20:23.070 --> 01:20:23.430 machen. 01:20:41.060 --> 01:20:42.720 Achso, genau. 01:20:43.320 --> 01:20:45.760 Das wäre der Automat nicht deterministisch. 01:20:46.160 --> 01:20:48.380 Natürlich fehlen überall noch Endzustände. 01:20:49.480 --> 01:20:52.460 In dem Fall sind es hier diese unteren drei. 01:20:53.300 --> 01:20:57.580 Ich markiere das nur mal einfach hier so mit Final. 01:20:59.160 --> 01:21:01.980 Weil überall Doppelklingel drum zu machen, macht es nur noch 01:21:01.980 --> 01:21:02.440 hässlicher. 01:21:03.660 --> 01:21:06.160 Und hier wäre es dieser hier. 01:21:06.760 --> 01:21:08.020 Und die müssten wir noch benennen. 01:21:09.780 --> 01:21:10.360 Genau. 01:21:12.480 --> 01:21:14.080 So sähe der Automat aus. 01:21:14.200 --> 01:21:16.020 Und jetzt kommt das vielleicht Interessantere. 01:21:16.880 --> 01:21:20.920 Der unendliche Automat für die letzte Sprache. 01:21:21.080 --> 01:21:22.560 Gibt es zu diesem Automat noch eine Frage? 01:21:24.620 --> 01:21:25.200 Nicht? 01:21:25.980 --> 01:21:29.080 Dann der letzte Automat ist vielleicht der Interessanteste. 01:21:31.820 --> 01:21:34.000 Ich schreibe noch mal kurz die Sprache an. 01:21:34.000 --> 01:21:45.850 Die Sprache war C-Stern A-N B-N 01:21:50.290 --> 01:21:58.570 zusammen mit A-Stern B-Stern. 01:21:59.770 --> 01:22:00.850 Das war ungefähr die Sprache. 01:22:00.970 --> 01:22:03.950 Das ist jetzt eine Mischung aus regulären Ausdrücken und 01:22:03.950 --> 01:22:06.170 mathematischer Schreibweise mit dem Hoch-N. 01:22:06.690 --> 01:22:08.050 Aber ich denke alle verstehen es ja. 01:22:09.910 --> 01:22:12.050 Kommt aufs Gleiche raus, weil... 01:22:13.950 --> 01:22:15.190 Wichtig für die Ambiguity? 01:22:20.910 --> 01:22:22.070 Machen wir ein Plus draus. 01:22:22.710 --> 01:22:24.210 Also auf den Folien stand es mit Plus. 01:22:24.310 --> 01:22:28.590 Ich glaube es macht keinen großen Unterschied, weil man sonst ja in 01:22:28.590 --> 01:22:29.910 der anderen Sprache drin ist. 01:22:30.110 --> 01:22:32.130 Also für die Sprache selber macht es keinen Unterschied. 01:22:33.750 --> 01:22:37.190 Vielleicht ein bisschen für die Fallunterscheidung, die man beim 01:22:37.190 --> 01:22:38.330 Beweis vorher gehabt hätte. 01:22:39.710 --> 01:22:45.830 Gut, wir haben uns überlegt, die Äquivalenzklassen dazu sind Epsilon. 01:22:46.750 --> 01:22:50.430 Ich lasse dieses Mal die Klammern ein bisschen weg, einfach weil die 01:22:50.430 --> 01:22:52.210 Zustände sowieso schon nicht so toll werden. 01:22:55.290 --> 01:22:59.690 Wenn ich ein A anfüge, komme ich in diesen neuen Zustand hier rein. 01:23:01.410 --> 01:23:04.310 Die sind alle akzeptierend erstmal. 01:23:08.530 --> 01:23:15.770 Wenn ich ein B einfüge, komme ich in diesen Zustand B rein. 01:23:21.770 --> 01:23:24.310 Hier kann ich drin bleiben mit Bs. 01:23:25.710 --> 01:23:27.790 Aber jetzt darf ich kein A mehr eingeben. 01:23:27.990 --> 01:23:31.470 Also das ist wiederum dieser hintere Sprachteil, für den ich jetzt 01:23:31.470 --> 01:23:32.930 gerade ein Automat gemacht habe. 01:23:34.190 --> 01:23:35.230 Das ist dieser Teil hier. 01:23:36.210 --> 01:23:38.230 Für ein A gehe ich in den Fehlerzustand. 01:23:49.050 --> 01:23:51.930 Gut, wenn ich jetzt hier aber ein C eingebe, 01:23:55.710 --> 01:24:00.770 dann gehe ich in diesen Zustand C. 01:24:05.670 --> 01:24:10.470 Wenn ich hier ein A eingebe, gehe ich zu C A. 01:24:13.610 --> 01:24:15.190 Mit Cs bleibe ich hier. 01:24:15.470 --> 01:24:20.110 Achso, die hier gehen alle mit Cs irgendwie auch hier rein in den 01:24:20.110 --> 01:24:20.470 Fehlerzustand. 01:24:30.420 --> 01:24:34.880 Wenn ich jetzt weitere A eingebe, gehe ich immer weiter hier nach 01:24:34.880 --> 01:24:35.220 unten. 01:24:48.000 --> 01:24:49.800 Im Endeffekt beliebig weit. 01:24:50.340 --> 01:24:52.440 Man kann sich jetzt überlegen, wenn ich ein B eingebe... 01:24:57.180 --> 01:25:02.820 Wenn ich ein B eingebe, gehe ich hier zu C A B. 01:25:05.340 --> 01:25:07.480 Das ist ein akzeptierender Zustand. 01:25:11.230 --> 01:25:17.590 Wenn ich hier ein B eingebe, gehe ich zu C A A B. 01:25:19.850 --> 01:25:21.450 Das ist nicht akzeptierend. 01:25:21.450 --> 01:25:27.110 Aber das Interessante ist, wenn ich jetzt hier ein B eingebe, gehe ich 01:25:27.110 --> 01:25:30.170 hier in den selben akzeptierenden Zustand. 01:25:30.970 --> 01:25:35.970 Also im Endeffekt zählen diese Zustände hier nur, wie viele Bs fehlen 01:25:35.970 --> 01:25:38.710 noch, damit ich hier in diesen akzeptierenden Zustand kann. 01:25:39.710 --> 01:25:48.830 Man baut also so ein bisschen so eine Leiter auf aus C und mit Bs geht 01:25:48.830 --> 01:25:49.730 man hier immer nach oben. 01:25:51.110 --> 01:25:56.950 Natürlich, wenn hier nochmal irgendwann A oder B eingegeben wird, oder 01:25:56.950 --> 01:26:09.150 C, oder wenn hier nochmal was kommt, was irgendwie außer der Reihe 01:26:09.150 --> 01:26:14.510 ist, also ein A oder ein C, kommen wir für alles zum Fehlerzustand. 01:26:15.690 --> 01:26:20.430 Aber eigentlich sieht man ganz gut die Regularität, die hier passiert. 01:26:20.430 --> 01:26:24.770 Also wir können im Endeffekt eine beliebig lange Kette von solchen 01:26:24.770 --> 01:26:28.750 Zuständen aufbauen, die dann irgendwann hier rüber gehen und nach oben 01:26:28.750 --> 01:26:30.890 wandern, für akzeptierende Wörter. 01:26:31.430 --> 01:26:36.850 Also wenn ich jetzt zum Beispiel C A hoch 5 B hoch 5 hätte, oder auch 01:26:36.850 --> 01:26:41.090 C C A hoch 5 B hoch 5, der Automat würde hier lang gehen, die ganzen 01:26:41.090 --> 01:26:46.530 Cs abzählen, dann für jedes A eins hier nach unten gehen, bis er dann 01:26:46.530 --> 01:26:49.990 später hier rüber geht und wieder nach oben gehen muss. 01:26:51.490 --> 01:26:55.270 Wir sehen also im Endeffekt ganz einfach, mit unendlich vielen 01:26:55.270 --> 01:27:01.250 Zuständen können wir zählen, wie man das mit kontextfreien Grammatiken 01:27:01.250 --> 01:27:02.710 auch gekonnt hätte. 01:27:03.830 --> 01:27:05.670 Gut, dann war das mal eine Zeit für heute.