WEBVTT 00:06.990 --> 00:11.520 Guten Morgen, herzlich willkommen zur vierten Vorlesung Theoretische 00:11.520 --> 00:13.020 Grundlagen der Informatik. 00:13.980 --> 00:20.260 Was haben wir bisher betrachtet, beziehungsweise am Dienstag uns 00:20.260 --> 00:22.020 überlegt und was kommt heute dran? 00:24.780 --> 00:30.000 Wir hatten uns am Dienstag Folgendes überlegt, beziehungsweise 00:30.000 --> 00:35.740 folgende Aussagen endgültig bewiesen. 00:35.740 --> 00:55.060 Erstmal, zu jedem NEA existiert ein equivalenter DEA und die 00:55.060 --> 01:04.140 Konstruktion ist die Potenzmengenkonstruktion. 01:05.140 --> 01:07.300 Und wir hatten bewiesen, 01:12.200 --> 01:39.110 die von EAs akzeptierten Sprachen sind genau die regulären Sprachen. 01:39.110 --> 01:42.550 Und das ist so eine Equivalenz-Aussage. 01:52.620 --> 01:54.820 Der Satz hat im Prinzip zwei Richtungen. 01:54.960 --> 01:56.300 Das ist der Satz von Clini. 01:56.920 --> 02:01.460 Wenn wir einen endlichen Automaten haben, dann ist die von diesem 02:01.460 --> 02:04.300 Automaten akzeptierte Sprache regulär. 02:04.760 --> 02:08.100 Und andersrum, wenn wir eine reguläre Sprache haben, so können wir zu 02:08.100 --> 02:12.960 dieser Sprache einen endlichen Automaten angeben, der sie akzeptiert. 02:14.140 --> 02:17.280 Beide Richtungen haben wir bewiesen und beide Beweise sind 02:17.280 --> 02:18.260 konstruktiv. 02:28.550 --> 02:32.850 Ich erwähne das aus folgendem Grund. 02:33.890 --> 02:38.050 Wenn Sie jetzt demnächst Übungsaufgaben bearbeiten oder schon 02:38.050 --> 02:40.910 bearbeitet haben, dann werden Sie solche Konstruktionen üben. 02:41.570 --> 02:47.370 Die Konstruktionen, Potenzmengenkonstruktionen, die Konstruktionen, um 02:47.370 --> 02:53.910 einerseits zu einer regulären Sprache einen entsprechenden endlichen 02:53.910 --> 03:00.370 Automaten zu bauen und andererseits, um zu einem endlichen Automaten 03:01.040 --> 03:05.450 den regulären Aufdruck aufzustellen für die Sprache, die von diesem 03:05.450 --> 03:07.210 endlichen Automaten akzeptiert wird. 03:08.210 --> 03:13.370 Und dann war der dritte große Punkt im Zusammenhang mit endlichen 03:13.370 --> 03:19.170 Automaten und regulären Sprachen, den wir bisher angesprochen haben, 03:19.570 --> 03:22.770 das Pumping Lemma für 03:26.920 --> 03:28.040 reguläre Sprachen. 03:34.120 --> 03:36.180 Und da will ich jetzt wieder einsteigen. 03:37.160 --> 03:41.660 Wir hatten das normale Pumping Lemma bewiesen und angefangen, uns das 03:41.660 --> 03:48.100 an Beispielen klarzumachen, aber ein großes Beispiel dazu ist noch 03:48.100 --> 03:48.840 offen geblieben. 03:49.100 --> 03:52.680 Das werden wir jetzt genauer anschauen und dann werden wir noch eine 03:52.680 --> 03:56.100 verallgemeinerte Form dieses Pumping Lemmas anschauen. 03:56.560 --> 04:01.080 Das ist das Programm für die ersten 20 Minuten und der Rest der 04:01.080 --> 04:09.480 heutigen Vorlesung wird benutzt, um sich einem Aspekt zu widmen, den 04:09.480 --> 04:12.880 wir hier an dieser Stelle schon gesehen haben. 04:13.000 --> 04:17.960 Nämlich diese Potenzmengenkonstruktion führt dazu, dass die 04:17.960 --> 04:21.140 deterministischen endlichen Automaten, die wir auf diese Weise 04:21.140 --> 04:23.740 bekommen, sehr viele Zustände haben. 04:25.180 --> 04:29.860 Und da schließt sich die Frage an, kann man da noch was machen, in dem 04:29.860 --> 04:35.180 Sinne, dass man zu so einem deterministischen endlichen Automat vielen 04:35.180 --> 04:40.380 Zuständen in den äquivalenten deterministischen endlichen Automaten 04:40.380 --> 04:45.220 baut, mit weniger Zuständen, am besten mit einer nachweisbaren 04:45.220 --> 04:47.720 minimalen Anzahl von Zuständen. 04:48.720 --> 04:52.100 Betonung ist auf deterministisch, also einen deterministischen 04:52.100 --> 04:55.840 endlichen Automaten mit minimaler Anzahl von Zuständen, denn wir 04:55.840 --> 05:01.060 wissen natürlich, an den Beispielen, die wir betrachtet haben, dass 05:01.060 --> 05:10.520 man mit einem NEA die selbe Sprache akzeptieren kann, wie der 05:10.520 --> 05:15.160 äquivalente DEA akzeptiert und der NEA typischerweise weniger Zustände 05:15.160 --> 05:15.440 hat. 05:15.440 --> 05:19.520 Es geht uns in dem Fall dann um deterministische endliche Automaten. 05:25.660 --> 05:27.320 Zurück zum Pumping Lemma. 05:29.160 --> 05:30.480 Hier steht es nochmal. 05:33.060 --> 05:38.900 Es lautet, gegeben sei eine reguläre Sprache, dann existiert eine 05:38.900 --> 05:43.800 natürliche Zahl n, sodass für jedes Wort aus der regulären Sprache, 05:44.320 --> 05:49.860 das eine Länge hat, die größer ist als n, eine Darstellung existiert 05:49.860 --> 05:58.300 der Form w gleich uvx mit Länge uv ist kleiner gleich n und v ist 05:58.300 --> 06:07.560 nicht das leere Wort, sodass für alle i aus n0 auch das Wort uv hoch 06:07.560 --> 06:11.580 ix wieder in der regulären Sprache ist. 06:13.100 --> 06:16.600 Ich habe Sie das letzte Mal schon darauf hingewiesen, dass wenn man 06:16.600 --> 06:20.980 sich dieses Lemma merken will, man ja vor allem sozusagen die richtige 06:20.980 --> 06:24.720 Abfolge der Existenz und für alle Quantoren, die in dem Lemma 06:24.720 --> 06:30.680 vorkommen, sich merken muss und dass es dabei sehr hilft, wenn man das 06:30.680 --> 06:34.560 Kernargument des Beweises sich vor Augen führt. 06:34.680 --> 06:41.740 Und das Kernargument des Beweises ist, dass n, zunächst mal weil die 06:41.740 --> 06:45.100 Sprache regulär ist, jetzt wissen wir, es gibt einen deterministischen 06:45.100 --> 06:47.520 endlichen Automaten, der diese Sprache akzeptiert. 06:48.080 --> 06:49.100 Und dieses n, 06:52.410 --> 06:55.970 das ist gerade die Anzahl der Zustände dieses deterministischen 06:55.970 --> 06:57.050 endlichen Automaten. 06:57.790 --> 07:04.650 Und wenn man dann ein solches Wort der Länge größer n betrachtet, dann 07:04.650 --> 07:10.890 weiß man, dass dessen Abarbeitung mindestens einen Zustand mehr als 07:10.890 --> 07:11.970 einmal durchläuft. 07:13.150 --> 07:16.950 Das heißt also, man hat irgendwo so eine Stelle in der Abarbeitung, in 07:16.950 --> 07:21.390 der Zustandsfolge, die durchlaufen wird, wenn man das Wort abarbeitet, 07:21.810 --> 07:26.490 man hat irgendwo so eine Stelle, wo sozusagen ein Zykel von Zuständen 07:26.490 --> 07:27.310 durchlaufen wird. 07:27.590 --> 07:31.450 Also so ein i, qi, wird mehr als einmal durchlaufen. 07:32.170 --> 07:36.930 Also man hat dieses Bild, wenn w abgearbeitet wird, kommt man 07:36.930 --> 07:41.830 irgendwann mal zu einem Zustand, von dem aus wird dann ein weiteres 07:41.830 --> 07:47.170 Teilwort abgearbeitet, dass das wieder zu demselben Zustand führt, bis 07:47.170 --> 07:49.490 es dann weitergeht zum Endzustand. 07:51.910 --> 07:56.910 Und dieses Bild, das kann man so interpretieren, das Wort w der Länge 07:56.910 --> 08:03.610 größer n, das ist wichtig, n ist die Anzahl der Zustände, sieht also 08:03.610 --> 08:11.010 so aus, man hat am Anfang ein Teilwort u und dann ein Teilwort v und 08:11.010 --> 08:15.210 dann ein Teilwort x und dieses Teilwort v ist nicht leer, denn wir 08:15.210 --> 08:19.990 haben hier wirklich diese Wiederholung des Zustands qi in der 08:19.990 --> 08:27.070 Abarbeitung von w und u, v kann auch nicht länger als n sein. 08:28.950 --> 08:32.030 Damit haben wir also auch diese Darstellung erklärt. 08:32.650 --> 08:38.350 Wenn aber bei der Abarbeitung von w so ein Zykel durchlaufen wird, das 08:38.350 --> 08:45.990 Teilwort v, dann kann man auch diesen Zykel weglassen oder mehrfach 08:45.990 --> 08:51.330 durchlaufen und landet wieder hier hinten im Endzustand. 08:51.590 --> 08:58.490 Und die Wörter, die den Zykel gar nicht durchlaufen und von s aus in 08:58.490 --> 09:02.590 den Endzustand führen über diesen selben Weg oder mehrfach 09:02.590 --> 09:07.210 durchlaufen, das sind gerade die Wörter u, v hoch i, x. 09:09.030 --> 09:12.190 Für alle i haben wir so eine Abarbeitung. 09:14.210 --> 09:15.070 Das ist alles. 09:15.190 --> 09:19.330 Es ist eigentlich nicht schwer, sich das zu merken und dann 09:19.330 --> 09:21.330 entsprechend auch das Pumping Lemma sich zu merken. 09:21.790 --> 09:28.010 Dieses Pumping Lemma kann man jetzt ausnutzen, aber dabei muss man 09:28.010 --> 09:29.830 vorsichtig sein. 09:30.650 --> 09:35.710 Zunächst mal, das Pumping Lemma sagt nichts anderes als reguläre 09:35.710 --> 09:37.710 Sprachen haben eine bestimmte Eigenschaft. 09:39.650 --> 09:41.870 Diese Eigenschaft, die hier beschrieben ist. 09:42.490 --> 09:45.110 Natürlich kann man sich eine reguläre Sprache vornehmen. 09:45.790 --> 09:49.530 Das haben wir am Dienstag gemacht. 09:50.710 --> 09:55.890 Sprache, die 1,0 nicht als Teilwort enthält, von der wissen wir, sie 09:55.890 --> 10:01.330 ist regulär und sie kann durch den regulären Ausdruck 0 Stern, 1 Stern 10:01.330 --> 10:02.070 beschrieben werden. 10:03.310 --> 10:05.430 Die muss das Pumping Lemma auch erfüllen. 10:05.730 --> 10:07.230 Das kann man sozusagen verifizieren. 10:07.330 --> 10:11.310 Das haben wir gemacht, indem wir eben so ein n angegeben haben, sodass 10:11.310 --> 10:16.430 für jede Darstellung eines Wortes aus L der Form u, v, x ... 10:20.080 --> 10:25.540 Sodass eine Darstellung der Form w gleich u, v, x existiert, die diese 10:25.540 --> 10:31.360 Eigenschaften erfüllt und derart, dass dann für alle u, v, x auch n, l 10:31.360 --> 10:31.660 ist. 10:32.300 --> 10:35.320 Das ist jetzt keine Überraschung, das ist einfach ein Verifizieren, 10:35.460 --> 10:38.520 dass tatsächlich auch diese reguläre Sprache das Lemma erfüllt. 10:39.880 --> 10:42.300 Was wir ja bewiesen haben, insofern muss das so sein. 10:44.880 --> 10:49.380 Interessanter ist, das Lemma wirklich zu benutzen, um neue Einsichten 10:49.380 --> 10:50.000 zu bekommen. 10:50.820 --> 10:53.660 Und das Lemma eine notwendige Bedingung dafür, dass eine Sprache 10:53.660 --> 11:00.360 regulär ist, beinhaltet, dann kann man es ja möglicherweise nutzen, um 11:00.360 --> 11:05.180 für nicht reguläre Sprachen zu beweisen, dass sie nicht regulär sind. 11:07.040 --> 11:11.680 Das haben wir gemacht bei diesem Beispiel der Sprache 0 hoch i, 1 hoch 11:11.680 --> 11:14.060 i, das auch funktioniert. 11:14.800 --> 11:18.220 Wir wissen, wir wussten schon vorher, 0 hoch i, 1 hoch i ist nicht 11:18.220 --> 11:18.740 regulär. 11:21.800 --> 11:26.580 Man kann jetzt nachweisen, dass diese Sprache auch nicht das Pumping 11:26.580 --> 11:30.640 -Lemma erfüllt und damit ist tatsächlich bewiesen, dass sie nicht 11:30.640 --> 11:31.480 regulär ist. 11:32.760 --> 11:34.220 Was muss man dafür machen? 11:36.240 --> 11:42.300 Wir müssen eine beliebige Zahl n uns vorgeben und dann ein Wort der 11:42.300 --> 11:48.280 Länge größer n angeben, sodass wir eine beliebige Darstellung der Form 11:49.260 --> 12:00.380 uvx mit Länge uv kleiner gleich dem n und v und gleich y wir ein i aus 12:00.380 --> 12:06.320 n0 angeben können, sodass uv hoch i x nicht in der Sprache ist. 12:06.320 --> 12:12.640 Die Negation dieser Aussage nachweisen. 12:13.580 --> 12:21.560 Und in dem Fall wählt man einfach zu dem beliebigen n als Wort 0 hoch 12:21.560 --> 12:22.420 n, 1 hoch n. 12:22.720 --> 12:28.200 Das ist ein Wort der Länge echt größer n und egal wie wir jetzt 0 hoch 12:28.200 --> 12:35.840 n, 1 hoch n darstellen als uvx mit Länge uv kleiner gleich n und v und 12:35.840 --> 12:44.180 gleich y sehen wir, dass wir, wenn wir jetzt uv hoch 0x bilden, aus 12:44.180 --> 12:45.780 der Sprache rausfallen. 12:46.540 --> 12:53.680 Wenn wir uv hoch 0x bilden, heißt das, dass dieses Anfangswort der 12:53.680 --> 12:59.340 Nullen weniger als n Nullen bekommt. 13:00.440 --> 13:07.060 Also wir bekommen auf die Art das Wort 0 hoch l, 1 hoch n l kleiner n 13:07.060 --> 13:09.780 und das entspricht nicht mehr diesem Schema. 13:11.260 --> 13:16.800 Also hier bei dieser Sprache 0 hoch i, 1 hoch i ist das Pumping Lemma 13:17.360 --> 13:20.420 prima zu gebrauchen, um zu beweisen, dass die Sprache nicht regulär 13:20.420 --> 13:20.700 ist. 13:22.140 --> 13:28.280 Ich habe Sie gewarnt, es gibt nicht reguläre Sprachen, die das Pumping 13:28.280 --> 13:29.040 Lemma erfüllen. 13:29.300 --> 13:31.520 Da hat man also mit dem Pumping Lemma nichts gewonnen. 13:32.380 --> 13:35.800 So ein Beispiel schauen wir uns jetzt an. 13:36.220 --> 13:38.080 Also wir schauen folgende Sprache an. 13:38.320 --> 13:40.720 Die Sprache der W aus Sigma Stern. 13:41.000 --> 13:42.900 Sigma ist das Alphabet 0,1. 13:43.740 --> 13:51.820 W hat entweder die Form 1 hoch k, also besteht einfach nur aus Einsen 13:51.820 --> 14:00.360 und k größer 0 oder W hat die Form 0 hoch j, 1 hoch k². 14:01.300 --> 14:07.200 Also vorne haben wir auf jeden Fall mindestens eine 0 und die Anzahl 14:07.200 --> 14:12.360 der Einsen ist also quadratisch in einem k, k größer gleich 0 und dass 14:12.360 --> 14:18.560 die quadratisch sein soll in einem k, k größer gleich 0 das lässt uns 14:18.560 --> 14:21.680 vermuten, dass die Sprache nicht regulär ist. 14:23.460 --> 14:30.420 Schauen wir mal nach, ob das Pumping Lemma hier erfüllt ist, trotzdem 14:30.420 --> 14:31.640 erfüllt ist, 14:38.390 --> 14:39.930 sei n gleich 1. 14:40.430 --> 14:43.430 Nach Pumping Lemma existiert ein n so das. 14:43.890 --> 14:48.510 Also wir nehmen mal jetzt n gleich 1 und ein beliebiges Wort aus 14:48.510 --> 14:52.430 dieser Sprache, der Länge echt größer 1. 14:54.250 --> 14:58.430 Jetzt schauen wir uns mal eine Darstellung von dem Wort als uvx mit 14:58.430 --> 15:03.470 Länge uv kleiner gleich n, v ungleich y an. 15:05.030 --> 15:12.110 Jetzt setzen wir, existiert eine Darstellung dieser Art, jetzt setzen 15:12.110 --> 15:20.650 wir u gleich leeres Wort und dann ist, weil n gleich 1 gewählt wurde 15:20.650 --> 15:28.550 und uv kleiner gleich n sein muss, v ein Symbol, hat v die Länge 1. 15:30.050 --> 15:33.830 Dann schauen wir mal an, wie das W tatsächlich aussehen kann, dass wir 15:33.830 --> 15:39.750 hier das beliebige W, dass wir das L gegriffen haben und ob 15:39.750 --> 15:45.090 tatsächlich für beliebiges i dann das Wort, das wir bekommen, wenn wir 15:45.090 --> 15:49.190 den Anteil v i-fach wiederholen, wieder in L ist. 15:49.930 --> 15:53.430 Die eine Möglichkeit ist, dass das Wort die Form hat 1 hoch k, also 15:53.430 --> 15:54.630 diesem Schema entspricht. 15:55.830 --> 16:03.090 Gut, wenn man dann ein Symbol aus dem Wort, das ist v, L-fach 16:03.090 --> 16:07.970 wiederholt, L aus N0, dann kriegt man natürlich wieder ein Wort von 16:07.970 --> 16:12.070 dem Typ gewisse Anzahl von Einsen. 16:12.070 --> 16:16.930 Also dann bekommt man ein 1 hoch L, das ist wieder in dieser Sprache 16:16.930 --> 16:17.250 drin. 16:19.650 --> 16:24.330 Die andere Möglichkeit ist, das Wort w hat die Form 0 hoch j, 1 hoch k 16:24.330 --> 16:25.710 Quadrat, also diese Form. 16:28.470 --> 16:35.430 Und wir wissen, v ist ein Symbol und u ist leer, also das ist dann 16:35.430 --> 16:40.930 dieses erste Symbol von w und da, wenn w die Form 0 hoch j, 1 hoch k 16:40.930 --> 16:47.370 Quadrat hat, dass j größer gleich 1 ist, wissen wir also, dieses v ist 16:47.370 --> 16:48.950 0, ist die führende 0. 16:51.070 --> 16:55.350 Diese führende 0 können wir aber auch weglassen oder nochmal beliebig 16:55.350 --> 17:00.930 oft wiederholen und bekommen wieder ein Wort dieser Form gewisse 17:00.930 --> 17:06.430 Anzahl von Nullen gefolgt von einer quadratischen Anzahl von Einsen 17:06.430 --> 17:11.570 oder in dem einen Sonderfall, wenn j gleich 1 ist und wir i gleich 0 17:11.570 --> 17:19.970 wählen, dann ist u v hoch 0 x gerade x, das ist dann 1 hoch k Quadrat, 17:20.530 --> 17:23.270 aber das ist ein Wort dieser Form. 17:25.210 --> 17:30.270 Also nochmal, wenn w die Form hat 0 hoch j, 1 hoch k Quadrat, j größer 17:30.270 --> 17:43.330 gleich 1, dann muss auch einerseits u v hoch 0 x in L sein, denn v 17:43.330 --> 17:47.830 hoch 0 heißt einfach nur, also v ist die führende 0 und v hoch 0 heißt 17:47.830 --> 17:52.170 einfach nur, wir lassen eine davon weg und selbst in dem Fall, dass j 17:52.170 --> 17:55.830 gleich 1 ist, führt uns das nicht aus der Sprache raus. 17:58.350 --> 18:04.950 Und wenn wir i größer gleich 1 wählen, dann ist das Wort u v hoch i x 18:04.950 --> 18:11.050 nichts anderes als 0 hoch j plus i, also i weitere Nullen kommen 18:11.050 --> 18:15.090 hinzu, gefolgt von 1 hoch k Quadrat. 18:15.490 --> 18:18.590 Und das ist wieder in der Sprache L drin. 18:20.410 --> 18:24.450 Also diese Sprache erfüllt das Pumping Lemma, sie ist aber trotzdem 18:24.450 --> 18:25.290 nicht regulär. 18:25.970 --> 18:29.290 Also das ahnen wir, bisher haben wir es nicht bewiesen, das ahnen wir. 18:29.370 --> 18:34.150 Und die Frage ist, können wir das denn irgendwie trotzdem beweisen? 18:34.850 --> 18:38.650 Es gibt noch eine kleine Chance, denn dieses Pumping Lemma in der 18:38.650 --> 18:43.350 Form, wie wir das jetzt kennengelernt haben, lässt sich noch etwas 18:43.350 --> 18:44.250 verallgemeinern. 18:46.330 --> 18:49.870 Und so diese erste verallgemeinerte Form, die schauen wir jetzt an, 18:50.530 --> 18:54.250 die reicht auch aus, um für die Sprache 18:57.550 --> 19:03.730 der Worte, die die Form haben, 1 hoch k oder 0 hoch j 1 hoch k Quadrat 19:03.730 --> 19:06.530 zu zeigen, dass sie nicht regulär ist. 19:07.370 --> 19:15.110 Aber im Kern ist das verallgemeinerte Pumping Lemma auch nicht 19:15.110 --> 19:19.370 deutlich allgemeiner als das Pumping Lemma, weil es ist wiederum nur 19:19.970 --> 19:24.570 ein Lemma, das eine notwendige Bedingung beinhaltet dafür, dass eine 19:24.570 --> 19:25.670 Sprache regulär ist. 19:26.710 --> 19:31.210 Also man kann dann wieder Sprachen konstruieren, die nicht regulär 19:31.210 --> 19:34.590 sind, aber dieses verallgemeinerte Pumping Lemma erfüllen. 19:35.610 --> 19:38.210 Und wie sieht dieses verallgemeinerte Pumping Lemma aus? 19:39.130 --> 19:40.090 Das sieht jetzt so aus. 19:40.890 --> 19:47.690 Sei l eine reguläre Sprache, dann existiert ein n aus n, sodass für 19:47.690 --> 19:50.370 jedes Wort aus l der Länge größer gleich n. 19:52.530 --> 19:56.830 Hier steht jetzt größer gleich, ansonsten ist es so weit, genauso wie 19:56.830 --> 19:57.870 beim Pumping Lemma. 19:59.010 --> 20:06.410 Und jede Darstellung von w der Form tyx mit y, also der mittlere Teil, 20:06.690 --> 20:08.910 hat Länge n gilt. 20:11.810 --> 20:20.570 Für das Teilwort y existiert eine Darstellung als uvz mit v und gleich 20:20.570 --> 20:25.710 dem leeren Wort, für die gilt, wie auch immer ich i aus n null wähle, 20:26.490 --> 20:30.150 tuvi zx ist wieder ein Wort der Sprache. 20:30.950 --> 20:35.630 Also im Kern hat das jetzt wieder das gleiche Schema wie das einfache 20:35.630 --> 20:41.810 Pumping Lemma, ein kleines bisschen allgemeiner in seiner Aussage. 20:41.810 --> 20:48.530 Der Beweis läuft genauso wie im Prinzip, genauso wie beim normalen 20:48.530 --> 20:50.310 Pumping Lemma oder einfachen Pumping Lemma. 20:51.330 --> 20:52.670 Schauen wir uns das an. 20:53.330 --> 20:58.030 Wir schauen uns wieder die reguläre Sprache L an und nutzen aus, dass 20:58.030 --> 21:01.270 es zu dieser regulären Sprache einen endlichen Automaten gibt, der die 21:01.270 --> 21:05.170 Sprache akzeptiert, deterministischen endlichen Automaten. 21:05.970 --> 21:09.310 Weil er endlich ist, hat er eine endliche Zustandsmenge. 21:09.650 --> 21:14.410 Und wie bei dem Beweis des einfachen Pumping Lemmas ist die 21:14.410 --> 21:22.310 Zustandsmenge, die Größe der Zustandsmenge, sozusagen die Zahl, die 21:22.310 --> 21:24.030 uns dieses n hier liefert. 21:24.590 --> 21:30.290 Jetzt bei dem verallgemeinerten Pumping Lemma muss n gleich 21:30.290 --> 21:34.250 Mächtigkeit der Zustandsmenge plus 1 gesetzt werden. 21:34.950 --> 21:38.910 Technisch ein kleines bisschen anders als beim einfachen Pumping 21:38.910 --> 21:39.170 Lemma. 21:40.490 --> 21:49.290 Und sei jetzt tyx Darstellung unseres Wortes w, derart das Länge von y 21:49.290 --> 21:51.430 genau n ist. 21:51.950 --> 21:58.370 Dann schauen wir jetzt wieder den Kern an, nämlich die Abarbeitung des 21:58.370 --> 22:05.330 Wortes und jetzt in dem Fall, was bei Abarbeitung von y passiert. 22:07.230 --> 22:10.950 Also genau wie beim Beweis des normalen Pumping Lemmas schauen wir die 22:10.950 --> 22:15.170 Abfolge der Zustände an, die durchlaufen wird bei Abarbeitung von y. 22:16.830 --> 22:20.890 Aus dem ganzen Wort, das wir vorgegeben haben, greifen wir jetzt in 22:20.890 --> 22:24.770 dem Fall den mittleren Teil der Länge n raus und schauen genau dahin, 22:24.830 --> 22:27.330 was passiert denn, wenn der abgearbeitet wird. 22:31.570 --> 22:35.990 Dieses n haben wir Mächtigkeit q plus 1 gewählt. 22:36.710 --> 22:42.550 Das heißt also, schon bei der Abarbeitung von y muss mindestens ein 22:42.550 --> 22:45.530 Zustand zweimal durchlaufen werden. 22:47.430 --> 22:52.450 Das Wort ist um 1 länger als die Anzahl der Zustände. 22:53.410 --> 22:57.430 Das heißt, die Abfolge der Zustände, die bei Abarbeitung dieses 22:57.430 --> 23:01.390 Teilworts durchlaufen wird, muss eine Wiederholung enthalten. 23:05.850 --> 23:11.750 Also q0 bis qn, Folge der Zustände, die bei Abarbeitung von y 23:11.750 --> 23:14.810 durchlaufen werden, enthält mindestens einen Zykel. 23:17.150 --> 23:23.210 Dann gibt es eine Zerlegung von y in uvz, sodass v gerade die 23:24.090 --> 23:28.950 Buchstabenfolge ist, die diesen Zykel, bei deren Abarbeitung dieser 23:28.950 --> 23:31.970 Zykel durchlaufen wird, genau wie beim normalen Pumpinglemma. 23:32.410 --> 23:35.990 Insbesondere kann das v nicht leer sein, wenn wir wirklich so einen 23:35.990 --> 23:36.590 Zykel haben. 23:37.530 --> 23:41.730 Und dieser Zykel kann dann natürlich wieder beliebig oft durchlaufen 23:41.730 --> 23:47.790 werden oder ignoriert werden und man bekommt wieder eine Abarbeitung 23:47.790 --> 23:51.450 eines Wortes, die in einen Endzustand führt. 23:51.710 --> 23:58.510 Das heißt, das gesamte Wort t, u, v hoch i, z, x ist für jedes 23:58.510 --> 24:02.610 beliebige i wieder ein Wort, das vom Automaten erkannt wird, also 24:02.610 --> 24:03.910 wieder ein Wort aus der Sprache. 24:04.230 --> 24:08.890 Also dieser Teil ist exakt der gleiche Teil wie beim Beweis des 24:08.890 --> 24:10.290 einfachen Pumpinglemmas. 24:15.620 --> 24:20.780 Und noch mal sozusagen das Wichtige zum Lemma auf einer Folie. 24:22.300 --> 24:27.240 Hier, wie das Lemma lautet und hier die wichtigen Punkte, die man sich 24:27.240 --> 24:30.560 merken muss, um das Lemma für sich wieder rekonstruieren zu können. 24:31.480 --> 24:36.820 Wir haben da eine Abfolge von Zuständen, die bei Abarbeitung des 24:36.820 --> 24:40.520 Wortes durchlaufen wird und zwar bei der Abarbeitung des mittleren 24:40.520 --> 24:49.100 Teils, in der mindestens ein Zykel sein muss und dementsprechend kann 24:49.100 --> 24:56.040 der mittlere Teil so dargestellt werden als uvz, dass v gerade das 24:56.040 --> 24:58.680 Teilwort ist, bei dem der Zykel durchlaufen wird. 25:00.920 --> 25:03.360 Dieses v ist insbesondere nicht leer, wenn es den Zykel gibt. 25:04.020 --> 25:09.260 Dann kann man den Zykel aber auch beliebig oft durchlaufen oder gar 25:09.260 --> 25:10.060 nicht durchlaufen. 25:11.360 --> 25:16.400 Das heißt also jedes Wort, das entsteht, wenn man v i-fach wiederholt 25:16.400 --> 25:21.200 oder weglässt, ist wieder ein Wort, das dessen Abarbeitung in einen 25:21.200 --> 25:22.160 Endzustand geht. 25:26.060 --> 25:29.540 Ich überlasse es Ihnen jetzt zu schauen, ob Sie mit dem Lemma 25:29.540 --> 25:37.000 nachweisen können, dass die Sprache der Wörter, die die Form haben, 1 25:37.000 --> 25:42.520 hoch k oder 0 hoch j, 1 hoch k Quadrat, nicht regulär ist. 25:45.160 --> 25:49.180 Jetzt kommen wir zu dem Hauptthema der heutigen Vorlesung. 25:51.320 --> 25:55.500 Zustandsminimierung von Automaten. 25:56.460 --> 26:00.880 Also nochmal die Motivation, wenn man mit der Potenzmengenkonstruktion 26:00.880 --> 26:06.320 zu einem NEA einen äquivalenten DEA baut, bekommt man eine 26:06.320 --> 26:12.200 Zustandsexplosion, weil potenziell die Anzahl der Zustände des DEA 26:12.200 --> 26:17.000 exponentiell in der Anzahl der Zustände des NEA sein kann. 26:17.000 --> 26:21.000 Das kommt auch wirklich vor, dass die Anzahl exponentiell wirkt. 26:21.580 --> 26:24.800 Da stellt sich die Frage, kann ich im Nachhinein diese Anzahl an 26:24.800 --> 26:29.380 Zuständen wieder reduzieren, am besten sogar eine Konstruktion 26:29.380 --> 26:35.940 angeben, die mir zu einem DEA einen äquivalenten DEA angebt, der 26:35.940 --> 26:37.920 minimale Anzahl von Zuständen hat. 26:40.000 --> 26:46.600 Die Konstruktion heißt Äquivalenzklassenkonstruktion oder der Automat, 26:46.680 --> 26:51.100 den wir bauen, um zur Zustandsminimierung zu gelangen oder zu einem 26:51.100 --> 26:56.960 zustandsminimalen DEA zu gelangen, heißt Äquivalenzklassenautomat. 26:57.560 --> 27:01.820 Da kann man schon so ungefähr ablesen, was wohl passiert. 27:02.780 --> 27:09.380 Man packt Zustände, die äquivalent sind oder natürlich noch erst 27:09.380 --> 27:13.260 formal definieren, was äquivalent heißen soll, zusammen in einen 27:13.260 --> 27:13.680 Zustand. 27:16.740 --> 27:20.100 Also kann man konstruktiv die Anzahl der Zustände eines 27:20.100 --> 27:25.320 deterministischen endlichen Automaten erheblich minimieren oder 27:25.320 --> 27:26.600 erheblich verringern. 27:27.620 --> 27:33.980 Die erste Beobachtung, die ist jetzt noch ziemlich simpel, kann 27:33.980 --> 27:38.440 natürlich sein, dass unser DEA Zustände hat, die vom Anfangszustand 27:38.440 --> 27:39.980 aus gar nicht erreichbar sind. 27:39.980 --> 27:42.460 Die sind im Prinzip überflüssig. 27:43.580 --> 27:47.560 Solche Zustände bekommen Sie meistens ein, wenn Sie zu einem NEA den 27:47.560 --> 27:51.900 äquivalenten DEA mittels Potenzmengenkonstruktion bauen und 27:51.900 --> 27:56.300 tatsächlich erstmal alle Zustände hinschreiben, die dieser Automat 27:56.300 --> 27:58.780 nach Definition des 28:02.720 --> 28:03.680 Potenzmengenkonstruktionen hat. 28:04.000 --> 28:06.460 Das haben wir schon beobachtet bei kleinen Beispielen, dass da 28:06.460 --> 28:12.280 irgendwelche Zustände noch erstmal im überhaupt keine Rolle spielen, 28:12.380 --> 28:13.820 weil sie gar nicht erreicht werden. 28:15.680 --> 28:19.120 Also die kann man sicher irgendwie mal versuchen loszuwerden. 28:21.100 --> 28:25.400 Solche Zustände nennt man einfach überflüssig, also Zustände eines 28:25.400 --> 28:29.000 endlichen Automaten, die vom Anfangszustand aus überhaupt nicht 28:29.000 --> 28:29.760 erreichbar sind. 28:30.080 --> 28:32.360 Es gibt kein Wort, das in diesen Zustand führt. 28:33.680 --> 28:35.400 Sie sind überflüssig, die kann man weglassen. 28:36.700 --> 28:37.860 Hier ist so ein Beispiel. 28:42.200 --> 28:46.980 Wenn Sie hier unten diese beiden Zustände anschauen, Q3 und Q4, dann 28:46.980 --> 28:49.700 stellen Sie schnell fest, dass man gar nicht von S aus in diese 28:49.700 --> 28:51.180 Zustände reingelangen kann. 28:52.840 --> 28:54.820 Man kann von S aus überhaupt nicht hier hinkommen. 28:56.080 --> 28:57.940 So, wie findet man solche Zustände? 28:58.240 --> 28:59.060 Haben Sie da eine Idee? 29:10.160 --> 29:17.500 Ja genau, Sie können den endlichen Automaten als gerichteten Graph 29:17.500 --> 29:21.100 auffassen und dann eine Breitensuche oder Tiefensuche machen. 29:21.900 --> 29:23.880 Ich schlage jetzt vor, wir machen eine Tiefensuche 29:27.300 --> 29:32.220 und alle die Zustände, die dann von einer Tiefensuche aus, von S aus 29:32.220 --> 29:35.600 überhaupt nicht besucht werden, die kann man vergessen. 29:36.800 --> 29:42.160 Das heißt also, die Menge aller überflüssigen Zustände eines endlichen 29:42.160 --> 29:49.200 Automaten können in Laufzeit, Anzahl der Zustände mal Mächtigkeit des 29:49.200 --> 29:50.620 Alphabets berechnet werden. 29:51.520 --> 29:58.780 Einen Moment noch, um sich zu vergewissern, wieso das die Laufzeit 29:58.780 --> 30:06.480 ist, die die Tiefensuche in dem gerichteten Graph zum endlichen 30:06.480 --> 30:08.180 Automaten braucht. 30:08.480 --> 30:12.080 Die Tiefensuche ist linear in der Größe des gerichteten Graph. 30:13.080 --> 30:18.000 Anzahl der Knoten unseres Automaten-Graph ist die Anzahl der Zustände. 30:19.340 --> 30:21.160 Wir können dann so Mehrfachkanten haben. 30:25.700 --> 30:29.560 Die Anzahl der Kanten, die kommt daher, wie groß das Alphabet ist. 30:29.740 --> 30:38.060 Von jedem Zustand führen so viele Kanten weiter, Zykelkanten sein 30:38.060 --> 30:43.680 können, Schleifen sein können oder Doppelkanten, die Zeichen im 30:43.680 --> 30:44.500 Alphabet sind. 30:45.260 --> 30:50.120 Das heißt, sie kriegen Anzahl von Mächtigkeit von Q mal Mächtigkeit 30:50.120 --> 30:51.640 des Alphabets viele Kanten. 30:53.660 --> 30:57.500 Damit ist tatsächlich die Laufzeit in O von Mächtigkeit Q mal 30:57.500 --> 30:58.420 Mächtigkeit Sigma. 31:02.970 --> 31:09.730 So ein endlicher deterministischer Automat, der keinen überflüssigen 31:09.730 --> 31:18.330 Zustand mehr enthält, muss aber noch immer nicht Zustandsminimal sein. 31:20.870 --> 31:23.330 Dafür schauen wir uns dieses Beispiel an. 31:24.350 --> 31:27.290 Erstmal ein Blick auf diese Folie. 31:28.050 --> 31:33.970 Wir haben hier einen großen deterministischen endlichen Automaten mit 31:33.970 --> 31:39.810 16 Zuständen und hier einen kleinen mit vier Zuständen und ich kündige 31:39.810 --> 31:43.710 Ihnen an, dass dieser Automat äquivalent ist zu diesem hier. 31:46.310 --> 31:51.590 Also der hier hat zwar keinen überflüssigen Zustand, ist aber dann 31:51.590 --> 31:54.530 offensichtlich nicht Zustandsminimal. 31:59.290 --> 32:00.670 Schauen wir einfach nur mal hier rein. 32:02.670 --> 32:07.870 Erste Frage, erstes kurzes draufschauen. 32:08.130 --> 32:13.890 Wir vergewissern uns, dass dieser Automat keine überflüssigen Zustände 32:13.890 --> 32:14.270 hat. 32:17.110 --> 32:21.870 Wenn man von dem Anfangszustand aus eine Tiefensuche machen würde, 32:21.970 --> 32:23.530 dann erreicht man alle diese Zustände. 32:23.650 --> 32:24.710 Das ist ziemlich offensichtlich. 32:26.790 --> 32:31.350 Jetzt nächste Frage, welche Sprache wird von diesem Automat 32:31.350 --> 32:33.330 akzeptiert? 32:34.450 --> 32:36.470 Die grünen sind die Endzustände. 32:36.810 --> 32:42.510 So wie wir immer Endzustände markieren, in solchen doppelten Kringeln 32:42.510 --> 32:47.510 sind eben diese Zustände hier, die gleichzeitig grün sind, die 32:47.510 --> 32:48.210 Endzustände. 32:48.690 --> 32:51.310 Welche Wörter führen in Endzustände? 32:58.180 --> 33:04.540 Naja, wir kämen zum Beispiel in einen Endzustand, den hier, wenn wir 0 33:04.540 --> 33:08.560 und nochmal 0 lesen würden oder in den hier, wenn wir 1 und nochmal 1 33:08.560 --> 33:09.240 lesen würden. 33:10.880 --> 33:15.460 Wir kämen auch wieder in einen Endzustand, wenn wir 0 und nochmal 0 33:15.460 --> 33:18.060 und nochmal 0 und nochmal 0 lesen würden. 33:19.760 --> 33:26.100 Also 2 Nullen oder 4 Nullen oder 6 Nullen führen in einen Endzustand. 33:26.220 --> 33:31.220 Und genauso hier runter 2 Einsen oder 4 Einsen oder 6 Einsen oder 8 33:31.220 --> 33:33.480 Einsen führen in einen Endzustand. 33:44.900 --> 33:52.360 Also hier ist der Vorschlag, Wörter 0 hoch 2i, 1 hoch 2i. 34:00.000 --> 34:02.420 Genau, also jetzt in Worten beschrieben war es richtig. 34:02.580 --> 34:12.160 Also Wörter der Form 0 hoch l, 1 hoch k mit l und k gerade werden hier 34:12.160 --> 34:12.840 akzeptiert. 34:12.920 --> 34:13.980 Aber das sind noch nicht alle. 34:15.120 --> 34:19.200 Hier wurde schon richtig gesagt, die Wörter, wo die Anzahl der Nullen 34:19.200 --> 34:21.000 und die Anzahl der Einsen gerade ist. 34:21.140 --> 34:24.840 Aber in welche Reihenfolge Nullen und Einsen kommen, das kann beliebig 34:24.840 --> 34:25.200 sein. 34:26.160 --> 34:27.540 Ich nehme an, das wollten Sie auch sagen. 34:29.820 --> 34:31.100 Das wollten Sie auch sagen. 34:31.960 --> 34:32.120 Genau. 34:35.000 --> 34:36.580 Und so ist es auch. 34:36.740 --> 34:41.100 Hier werden also die Wörter über 0, 1 akzeptiert, genau die Wörter 34:41.100 --> 34:45.880 über 0, 1 akzeptiert, die eine gerade Anzahl von Nullen und eine 34:45.880 --> 34:48.640 gerade Anzahl von Einsen enthält. 34:52.860 --> 34:58.440 Wenn man erst eine gerade Anzahl von Nullen liest, dann kommt man 34:59.780 --> 35:05.460 entweder in die erste oder innerhalb des Wortes eine gerade Anzahl von 35:05.460 --> 35:08.800 Nullen liest, dann kommt man in die erste oder in die dritte Spalte, 35:08.940 --> 35:11.760 also einen Zustand aus der ersten oder der dritten Spalte. 35:12.140 --> 35:15.080 Wenn man eine gerade Anzahl von Einsen liest, kommt man in einen 35:15.080 --> 35:18.580 Zustand aus der ersten oder der dritten Zeile. 35:19.580 --> 35:23.420 Wenn man eine gerade Anzahl von Nullen und eine Anzahl von Einsen 35:23.420 --> 35:27.840 liest, dann kommt man also gerade in die Zustände, die in der ersten 35:27.840 --> 35:37.420 Zeile und ersten oder dritten Spalte oder dritten Zeile und ersten 35:37.420 --> 35:38.680 oder dritten Spalte sind. 35:38.780 --> 35:41.920 Und das sind gerade diese vier grünen Zustände. 35:42.680 --> 35:45.500 Wir haben die Zustände jetzt auch entsprechend nummeriert. 35:45.780 --> 35:47.480 Ich habe Ihnen ja hier Namen gegeben. 35:47.660 --> 35:52.780 Der Startzustand heißt 0 0, der nächste hier heißt 1 0, der heißt 2 0 35:52.780 --> 35:53.280 und so weiter. 35:54.740 --> 36:01.060 Die erste Ziffer im Namen des Zustands entspricht immer der Anzahl der 36:01.060 --> 36:06.280 Nullen Modulo 4, die gelesen werden muss, um in diesen Zustand zu 36:06.280 --> 36:06.580 kommen. 36:08.140 --> 36:14.660 Also um in den Zustand aus der Spalte zu kommen, muss man null Nullen, 36:15.080 --> 36:17.320 also null Modulo 4 Nullen lesen. 36:18.800 --> 36:23.760 Und um in die Spalte zu kommen, muss man 1 Modulo 4 Nullen lesen, hier 36:23.760 --> 36:26.600 2 Modulo 4 Nullen und hier 3 Modulo 4 Nullen. 36:26.960 --> 36:32.300 Und die zweite Ziffer entspricht gerade die Anzahl der Einsen, die man 36:32.300 --> 36:37.560 lesen muss, wie der Modulo 4 betrachtet, um in die entsprechende Zeile 36:37.560 --> 36:38.080 zu kommen. 36:38.420 --> 36:43.920 Also um hier hin zu kommen, muss man 2 Nullen Modulo 4 oder 2 Modulo 4 36:43.920 --> 36:46.060 Nullen und 1 Modulo 4 Einsen lesen. 36:46.620 --> 36:48.220 So ist hier die Nummerierung zu verstehen. 37:03.750 --> 37:08.550 Jetzt habe ich den Zuständen verschiedene Farben gegeben. 37:09.610 --> 37:11.210 Die grünen, das sind die Endzustände. 37:12.390 --> 37:16.830 Das sind gerade diejenigen, wo sowohl die vordere als auch die hintere 37:16.830 --> 37:18.390 Ziffer gerade ist. 37:20.410 --> 37:24.790 Und jetzt habe ich noch so rote Zustände und blaue Zustände und weiße 37:24.790 --> 37:25.390 Zustände. 37:26.270 --> 37:29.210 Und gerade die roten haben was gemeinsam, die weißen haben was 37:29.210 --> 37:31.190 gemeinsam, die blauen haben was gemeinsam. 37:31.810 --> 37:35.210 Die roten haben gemeinsam, dass die Anzahl der Nullen, die ich lesen 37:35.210 --> 37:38.970 muss, um in den roten Zustand zu kommen, ungerade ist und die Anzahl 37:38.970 --> 37:43.310 der Einsen, die ich lese, um in den roten Zustand zu kommen, gerade 37:43.310 --> 37:43.650 ist. 37:43.810 --> 37:46.950 Das sehen Sie hier an diesen Bezeichnungen auch sehr gut. 37:47.830 --> 37:52.670 Und die blauen haben gemeinsam, dass die Anzahl der Nullen, die ich 37:52.670 --> 37:57.050 lesen muss, um in einen blauen Zustand zu kommen, gerade sein muss und 37:57.050 --> 37:58.790 die Anzahl der Einsen ungerade. 37:59.470 --> 38:02.170 Gerade umgekehrt als bei den roten. 38:02.650 --> 38:06.210 Und die weißen, das sind gerade diejenigen, wo die Anzahl der Nullen 38:06.210 --> 38:11.610 ungerade ist und die Anzahl der Einsen ungerade ist, die uns in den 38:11.610 --> 38:12.310 Zustand führen. 38:13.470 --> 38:19.290 Und jetzt ist sozusagen unsere Hypothese, dass man einen kleineren 38:19.290 --> 38:23.370 Automaten bauen kann, indem man diese grünen, diese roten, diese 38:23.370 --> 38:28.570 blauen, diese weißen jeweils zusammenfasst, weil die haben jeweils so 38:28.570 --> 38:32.010 eine gleiche Eigenschaft. 38:32.010 --> 38:40.050 Und das wollen wir jetzt mal machen, systematisch. 38:41.690 --> 38:45.410 Also der Automat, den man bekommt, wenn man das macht, was ich 38:45.410 --> 38:49.090 vorgeschlagen habe, die grünen zusammenpacken, die roten 38:49.090 --> 38:52.350 zusammenpacken, die blauen zusammenpacken, die weißen zusammenpacken, 38:52.710 --> 38:54.310 der wird dann wohl so aussehen. 38:54.410 --> 38:57.450 Die Frage ist, wie kommen wir von hier nach dort über ein 38:58.410 --> 39:02.890 systematisches Verfahren, das uns automatisch auch mitliefert, dass 39:02.890 --> 39:05.650 dieser Automat tatsächlich äquivalent ist zu diesem. 39:07.890 --> 39:12.530 Also hier steht nochmal, welches die Worte sind, die von dem Automat 39:12.530 --> 39:17.650 akzeptiert werden, beziehungsweise die Sprache zu dem Automat. 39:17.790 --> 39:21.230 Das ist die Sprache der Wörter, W aus 0,1 Stern. 39:22.270 --> 39:23.330 Länge von W, 39:27.690 --> 39:34.630 Anzahl der Nullen, die in W vorkommt, Modulo 2, ist gleich Anzahl der 39:34.630 --> 39:38.290 Einsen, die in W vorkommt, Modulo 2 genommen, gleich 0. 39:39.430 --> 39:43.070 Das ist nur nicht anders, das ist nur jetzt formal ausgedrückt, dass 39:43.070 --> 39:45.450 also die Anzahl der Nullen und die Anzahl der Einsen, die in W 39:45.450 --> 39:47.510 vorkommen, jeweils gerade sein muss. 39:51.150 --> 39:58.170 Gut, wir wollen also Zustände identifizieren, die man im Prinzip 39:58.170 --> 40:02.850 zusammenpacken kann, weil sie gleich geartet sind in ihrem Verhalten, 40:03.070 --> 40:03.510 sage ich mal. 40:05.130 --> 40:08.030 Äquivalenz von Zuständen, das ist das, was wir uns jetzt genauer 40:08.030 --> 40:11.890 überlegen müssen, was könnte das heißen, was ist eine sinnvolle 40:11.890 --> 40:15.410 Definition dafür, dass zwei Zustände äquivalent sind. 40:17.470 --> 40:20.850 Wir können sagen, zwei Zustände haben genau dasselbe 40:20.850 --> 40:27.510 Akzeptanzverhalten, wenn es für das Erreichen eines Endzustandes durch 40:27.510 --> 40:33.530 Abarbeitung eines Wortes W unerheblich ist, ob man von dem einen oder 40:33.530 --> 40:35.610 dem anderen Zustand startet. 40:39.410 --> 40:44.770 Andersrum, Abarbeitung eines Wortes W führt uns entweder von beiden 40:44.770 --> 40:50.130 Zuständen aus in einen Endzustand oder von beiden Zuständen aus in 40:50.130 --> 40:51.330 einen Nicht-Endzustand. 40:51.770 --> 40:54.190 Dann haben die das gleiche Akzeptanzverhalten. 40:55.630 --> 41:01.670 Dieselben Worte führen bei beiden Zuständen zur Akzeptanz oder 41:01.670 --> 41:03.570 beziehungsweise zur Nicht-Akzeptanz. 41:05.090 --> 41:10.710 Und die Idee ist jetzt, die Anzahl der Zustände zu reduzieren, indem 41:10.710 --> 41:16.390 man solche Zustände, die dasselbe Akzeptanzverhalten haben, 41:17.050 --> 41:17.850 zusammenlegt. 41:19.030 --> 41:23.230 Im letzten Beispiel waren das jeweils die Zustände, die die gleichen 41:23.230 --> 41:24.570 Farben haben. 41:26.110 --> 41:31.010 Das Ganze stellen wir jetzt auf mathematisch saubere Füße. 41:31.830 --> 41:39.850 Wir definieren den Begriff Äquivalenz von Zuständen. 41:40.010 --> 41:44.510 Zwei Zustände P und Q eines deterministischen endlichen Automaten 41:44.510 --> 41:49.930 nennen wir Äquivalent, wenn für alle Wörter aus Sigma Stern gilt. 41:52.330 --> 41:59.570 Das Wort führt von P aus in einen Endzustand, genau dann, wenn das 41:59.570 --> 42:02.650 Wort von Q aus in einen Endzustand führt. 42:03.710 --> 42:06.450 Das ist jetzt nochmal anders ausgedrückt. 42:07.690 --> 42:13.250 Ein Wort W führt entweder von beiden Zuständen aus in einen Endzustand 42:13.250 --> 42:16.610 oder von beiden Zuständen aus in einen Nicht-Endzustand. 42:17.950 --> 42:20.910 Vom einen aus kommen wir in den Endzustand genau dann, wenn wir von 42:20.910 --> 42:22.910 dem anderen aus in den Endzustand kommen. 42:23.530 --> 42:27.810 Dann nennen wir P und Q Äquivalent, wenn das gilt. 42:28.070 --> 42:34.810 Delta P W aus F genau dann, wenn Delta Q W aus F für alle W aus Sigma 42:34.810 --> 42:35.190 Stern. 42:35.970 --> 42:38.850 Das Zeichen dazu ist hier dieser Dreifachstrich. 42:40.610 --> 42:44.970 Und es ist offensichtlich, dass diese Relation, eine Relation zwischen 42:44.970 --> 42:48.030 Zuständen, dass das tatsächlich eine Äquivalenzrelation ist. 42:49.390 --> 42:52.150 Zustand ist natürlich zu sich selber Äquivalent. 42:52.930 --> 42:56.670 Wenn ein Zustand P zu einem Zustand Q Äquivalent ist, dann ist auch 42:56.670 --> 42:58.550 umgekehrt Q zu P Äquivalent. 42:59.470 --> 43:04.050 Wenn P zu einem Zustand Q Äquivalent ist und Q zu einem Zustand R 43:04.050 --> 43:07.410 Äquivalent ist, dann ist auch P zu R Äquivalent. 43:08.090 --> 43:11.610 Diese Relation, die wir hier definiert haben und die wir Äquivalent 43:12.150 --> 43:14.090 nennen, ist eine Äquivalenzrelation. 43:14.270 --> 43:18.570 Entsprechend kann man auch die Äquivalenzklassen bilden. 43:20.910 --> 43:26.570 Also die Zustände jeweils in Klassen packen, die entsprechend dieser 43:26.570 --> 43:28.810 Definition äquivalente Zustände sind. 43:34.460 --> 43:40.340 Mit dieser Definition können wir jetzt den Äquivalenzklassen Automat 43:40.340 --> 43:41.260 definieren. 43:42.000 --> 43:43.620 Den definieren wir folgendermaßen. 43:44.140 --> 43:50.600 Also zu einem gegebenen DA, A gleich Q Sigma Delta SF definieren wir 43:50.600 --> 43:58.500 den Äquivalenzklassen Automat A Äquivalent, Zustandsmenge Q 43:58.500 --> 44:01.760 Äquivalent, Sigma Äquivalent, das Alphabet Delta Äquivalent, die 44:01.760 --> 44:05.600 Übergangsfunktion S Äquivalent, der Anfangszustand F Äquivalent, die 44:05.600 --> 44:07.980 Endzustandsmenge, folgendermaßen. 44:10.560 --> 44:14.860 Die Zustandsmenge des Äquivalenzklassen Automat ist die Menge der 44:14.860 --> 44:19.340 Äquivalenzklassen der Zustände unseres Ausgangs Automat. 44:22.940 --> 44:24.640 Das Alphabet bleibt natürlich gleich. 44:26.360 --> 44:28.040 Sigma Äquivalent, das ist unser Sigma. 44:30.540 --> 44:33.000 Machen wir hier in der vierten Zeile weiter. 44:34.680 --> 44:39.780 Erscheint sinnvoll als Anfangszustand des Äquivalenzklassen Automat 44:39.780 --> 44:44.900 die Äquivalenzklasse des Anfangszustands unseres Ausgangs Automaten zu 44:44.900 --> 44:45.160 nehmen. 44:46.420 --> 44:49.800 Hier in der letzten Zeile, das erscheint ja eigentlich auch sinnvoll, 44:50.120 --> 44:54.420 dass wir als die Endzustände unseres Äquivalenzklassen Automaten die 44:55.120 --> 44:59.040 Äquivalenzklassen der Endzustände unseres Ausgangs Automaten nehmen. 45:00.600 --> 45:03.960 Und dann das Spannendste ist immer die Übergangsfunktion, die 45:03.960 --> 45:05.560 definieren wir folgendermaßen. 45:05.640 --> 45:10.120 Die Übergangsfunktion des Äquivalenzklassen Automat bekommt ja als 45:10.120 --> 45:14.760 Argument einen Zustand des Äquivalenzklassen Automates und ein Symbol. 45:16.600 --> 45:21.000 Das heißt, die bekommt als Argument die Äquivalenzklasse eines 45:21.000 --> 45:24.740 Zustands des Ausgangs Automates und ein Symbol. 45:25.720 --> 45:31.860 Die soll uns gerade führen in die Äquivalenzklasse des Zustands, in 45:31.860 --> 45:37.800 den uns Delta, die Übergangsfunktion des Ausgangs Automaten, von dem 45:37.800 --> 45:41.220 Zustand Q aus bei Lesen von A führen würde. 45:41.700 --> 45:43.800 Das erscheint auch sinnvoll. 45:44.500 --> 45:46.940 Die Frage ist, ob diese Definition, das ist jetzt einfach eine 45:46.940 --> 45:50.620 Definition eines Automaten, ob die wirklich funktioniert, ob die 45:50.620 --> 45:52.600 wirklich wohl definiert ist. 45:53.040 --> 45:56.880 Das müssen wir als allererstes mal abklären. 46:02.420 --> 46:06.600 Also ein Satz, kleiner Satz, der Äquivalenzklassenautomat zu einem 46:06.600 --> 46:09.680 deterministischen endlichen Automat ist wohl definiert. 46:10.400 --> 46:12.840 Also funktioniert das alles, was wir hier definiert haben. 46:20.420 --> 46:22.140 Vielleicht der eine Schritt zurück. 46:28.240 --> 46:31.420 Die Zustandsmenge so zu definieren, das können wir sicher machen. 46:31.500 --> 46:35.180 Bei Sigma ändert sich nichts, es so zu definieren, das können wir auch 46:35.180 --> 46:35.500 machen. 46:35.920 --> 46:38.940 Da, wo man aufpassen muss, also schauen muss, ob da nicht irgendwo ein 46:38.940 --> 46:42.980 Widerspruch auftreten könnte, das ist die Definition der Endzustände 46:42.980 --> 46:45.020 und die Definition der Übergangsfunktion. 46:45.440 --> 46:53.440 Wir müssen also nachweisen, dass F-Äquivalent und Delta-Äquivalent 46:53.440 --> 46:55.600 wohl definiert sind. 46:58.080 --> 47:02.040 Für F-Äquivalent müssen wir zeigen, dass wir also tatsächlich einfach 47:02.040 --> 47:09.040 die Äquivalenzklassen der Endzustände als Endzustände des 47:09.040 --> 47:11.060 Äquivalenzklassenautomat nehmen können. 47:11.920 --> 47:20.300 Das würde uns in Probleme führen, wenn dabei Klassen entstehen würden, 47:20.600 --> 47:28.160 in denen sowohl Endzustände als auch Nicht-Endzustände liegen. 47:30.420 --> 47:36.840 Denn dann hätten wir Zustände in einer Klasse, die sozusagen bezüglich 47:37.600 --> 47:41.960 Akzeptanz sich unterschiedlich verhalten im Ausgangsautomat, aber in 47:41.960 --> 47:46.200 dem Äquivalenzklassenautomat wird sozusagen Gleichverhalten zum 47:46.200 --> 47:47.060 gleichen führen. 47:51.660 --> 47:55.480 Was wir zeigen, ein Endzustand kann nur zu einem Endzustand-Äquivalent 47:55.480 --> 47:55.740 sein. 47:56.760 --> 48:05.360 Und das andere, Delta-Äquivalent, wäre nicht gut definiert, wenn 48:05.360 --> 48:14.560 äquivalente Zustände bei Lesen desselben Symbols in verschiedene 48:14.560 --> 48:15.840 Äquivalenzklassen führen würden. 48:18.800 --> 48:22.820 Gut, ein Endzustand kann nur zu einem Endzustand-Äquivalent sein, das 48:22.820 --> 48:31.000 ist aber eigentlich klar, denn wenn man Epsilon hier nimmt, dann ist 48:32.370 --> 48:41.070 Delta P Epsilon in F genau dann, wenn Delta Q Epsilon, oder dann 48:41.070 --> 48:46.530 bedeutet Delta Q Epsilon in F genau dann, wenn Delta Q Delta P Epsilon 48:46.530 --> 48:51.590 in F genau dann, wenn Delta Q Epsilon in F ist, dass P und Q beides 48:51.590 --> 48:52.990 Endzustände sein müssen. 48:58.660 --> 49:04.880 Das heißt also, wenn P und Q äquivalent sind, dann sind P und Q beide 49:04.880 --> 49:06.520 in F oder beide nicht in F. 49:07.300 --> 49:10.840 Das heißt also, F-Äquivalent ist wohl definiert. 49:16.000 --> 49:19.700 Und Delta führt äquivalente Zustände beim Lesen desselben Symbols 49:19.700 --> 49:21.480 wieder in äquivalente Zustände. 49:21.820 --> 49:24.900 Betrachten wir mal zwei äquivalente Zustände P und Q, 49:27.920 --> 49:33.020 dann gilt für alle Wörter aus Sigma-Stern, Delta Q W ist in F genau 49:33.020 --> 49:35.540 dann, wenn Delta P W in F ist. 49:37.680 --> 49:41.780 Das gilt dann natürlich auch für jedes Symbol, also wenn für jedes W 49:41.780 --> 49:45.800 diese Äquivalenz gilt, dann insbesondere auch für W ist ein Symbol aus 49:45.800 --> 49:46.060 Sigma. 49:49.790 --> 49:56.150 Das heißt also, wenn wir betrachten Delta von Delta Q A, W, was ja 49:56.150 --> 50:01.790 nichts anderes ist als Delta Q A W, dann ist das in F genau dann, wenn 50:01.790 --> 50:08.950 Delta P A W, was ja nichts anderes ist als Delta von Delta P A, W in F 50:08.950 --> 50:09.230 ist. 50:10.570 --> 50:15.930 Aber dann muss auch Delta Q A äquivalent zu Delta P A sein. 50:16.950 --> 50:21.210 Nach der Definition von zwei Zustände sind äquivalent. 50:21.950 --> 50:25.390 Das heißt also, diese Übergangsfunktion unseres 50:26.110 --> 50:27.750 Äquivalenzklassenautomaten ist wohl definiert. 50:28.170 --> 50:33.430 Okay, gut, also wenn der Äquivalenzklassenautomat wohl definiert ist, 50:33.470 --> 50:35.270 dann können wir jetzt mit dem wirklich arbeiten. 50:36.150 --> 50:41.230 Jetzt zeigen wir, dass der tatsächlich dieselbe Sprache akzeptiert wie 50:41.230 --> 50:47.990 der Automat, aus dem wir diesen Äquivalenzklassenautomat gebaut haben. 50:51.450 --> 50:57.650 Also wir geben A, der Äquivalenzklassenautomat zu A akzeptiert 50:57.650 --> 50:58.990 dieselbe Sprache wie A. 51:04.510 --> 51:08.270 Das ist eigentlich gar nicht schwer, denn wir haben ihn genau so 51:08.270 --> 51:10.070 definiert, dass das stimmt. 51:12.010 --> 51:18.810 Da nehmen wir einfach mal ein beliebiges Wort über dem Alphabet Sigma 51:18.810 --> 51:23.690 her, also ein beliebiges Wort aus Sigma Stern und schauen uns an, was 51:23.690 --> 51:27.870 passiert in A, wenn dieses Wort gearbeitet wird und was passiert in 51:27.870 --> 51:32.610 dem Äquivalenzklassenautomat zu A, wenn dieses Wort abgearbeitet wird. 51:34.110 --> 51:40.270 In A durchläuft dieses Wort eine bestimmte Folge von Zuständen, Q0 bis 51:40.270 --> 51:40.770 Qn. 51:42.670 --> 51:48.070 Q0 ist gerade der Anfangszustand und wenn dem so ist, dann durchläuft 51:48.070 --> 51:51.850 natürlich der Äquivalenzklassenautomat zu A bei Abarbeitung von W 51:51.850 --> 51:55.690 gerade die Zustände, die den Äquivalenzklassen dieser Zustände 51:55.690 --> 51:56.270 entsprechen. 51:58.250 --> 52:02.150 Und A akzeptiert dieses Wort genau dann, wenn dieser letzte Zustand 52:02.150 --> 52:04.150 ein Endzustand ist von A. 52:05.350 --> 52:09.850 Andererseits akzeptiert der Äquivalenzklassenautomat dieses Wort, wenn 52:09.850 --> 52:14.650 hier dieser letzte Zustand ein Endzustand des 52:14.650 --> 52:16.290 Äquivalenzklassenautomates ist. 52:16.490 --> 52:20.210 Dieser letzte Zustand ist aber nichts anderes als die Äquivalenzklasse 52:20.210 --> 52:27.910 zu diesem letzten Zustand der bei Abarbeitung von W in A besucht wird. 52:29.130 --> 52:35.470 Nach Definition ist dieser Zustand in F genau dann, wenn die 52:36.210 --> 52:40.570 Äquivalenzklasse zu diesem Zustand in der Endzustandsmenge des 52:40.570 --> 52:41.830 Äquivalenzklassenautomates ist. 52:42.690 --> 52:45.810 Also das ist per Konstruktion gilt dieser Satz. 52:49.380 --> 52:59.480 Jetzt ist die große Frage, kann ich diesen Äquivalenzklassenautomat 53:02.280 --> 53:05.060 konstruieren über ein konstruktives Verfahren. 53:11.550 --> 53:14.970 Hier steht die Definition, jetzt könnte man sagen, ja sicher, ich 53:14.970 --> 53:19.330 mache einfach das, was hier die Definition uns vorgibt. 53:23.160 --> 53:29.700 Da muss ich hier schon bei der Aufstellung der Zustandsmenge was tun. 53:30.080 --> 53:36.100 Ich muss die Äquivalenzklassen zu den Zuständen meines DEA finden. 53:37.240 --> 53:38.880 Wie finde ich diese Systematik? 53:40.280 --> 53:49.370 Nach Definition sind zwei Zustände äquivalent, wenn für alle Wörter 53:49.370 --> 53:58.090 über dem Eingangs, über dem Alphabet gilt, das Wort führt von P aus, 53:58.450 --> 54:03.390 von dem einen Zustand aus in die Endzustandsmenge, genau dann, wenn 54:03.390 --> 54:07.930 das Wort von dem anderen Zustand aus in die Endzustandsmenge führt. 54:08.610 --> 54:16.450 Das ist irgendwie eine Definition, die sozusagen unmittelbar zu 54:16.450 --> 54:21.810 überprüfen aufwendig erscheint. 54:23.750 --> 54:26.150 Also hier nochmal die Frage, wie konstruiert man den 54:26.150 --> 54:28.850 Äquivalenzklassenautomat zu einem Automat A? 54:29.770 --> 54:34.490 Das heißt, wie berechnen wir alle Äquivalenzklassen zu jedem einzelnen 54:34.490 --> 54:35.430 Zustand von A? 54:37.130 --> 54:39.410 Für den Beweis der Äquivalenz zweier Zustände 54:42.590 --> 54:48.810 müssen wir für alle Wörter überprüfen, ob beide Zustände in den 54:48.810 --> 54:52.450 Endzustand oder beide Zustände in einen Nicht-Endzustand führen. 54:53.910 --> 54:58.590 Für alle Wörter, die Wörter aus Sigma-Stern, die können beliebig lang 54:58.590 --> 54:58.910 werden. 55:00.610 --> 55:05.210 Sigma ist zwar endlich, aber Sigma-Stern unendlich. 55:06.170 --> 55:10.930 Für eine unendliche Anzahl von Wörtern müsste man diese Sache für 55:10.930 --> 55:14.190 jedes Paar von Zuständen überprüfen. 55:16.850 --> 55:18.670 Kein guter Plan. 55:20.430 --> 55:26.970 Natürlich ist es einfacher zu zeigen, dass zwei Zustände nicht 55:26.970 --> 55:28.390 -äquivalent sind. 55:28.470 --> 55:32.130 Denn um zu zeigen, dass zwei Zustände nicht-äquivalent sind, muss ich 55:32.130 --> 55:37.690 einfach nur ein Wort angeben, das von dem einen Zustand aus in einen 55:37.690 --> 55:40.430 Endzustand führt und von dem anderen nicht. 55:42.410 --> 55:46.570 Ich muss sozusagen ein Wort angeben, das bezeugt, die beiden sind 55:46.570 --> 55:47.450 nicht -äquivalent. 55:48.380 --> 55:55.270 Das ist vielleicht einfacher. 56:02.490 --> 56:03.630 Vorschlag. 56:04.510 --> 56:10.190 Wir testen systematisch alle Zustandspaare auf nicht-äquivalent, indem 56:10.190 --> 56:14.750 wir systematisch für alle Zustandspaare nach Zeugen für die nicht 56:14.750 --> 56:19.770 -äquivalent suchen, also nach Wörtern, die bezeugen, 56:23.570 --> 56:25.330 ein Wort, das gilt. 56:26.630 --> 56:30.370 Es führt von dem einen Zustand aus in einen Endzustand und von dem 56:30.370 --> 56:31.130 anderen nicht. 56:32.450 --> 56:35.850 Und diese Wörter, die Zeugen, die könnten wir ja auch systematisch 56:35.850 --> 56:39.810 suchen, indem wir erst mal anfangen mit dem leeren Wort und 56:39.810 --> 56:45.750 nachschauen, kann das leere Wort schon bezeugen, dass gewisse Zustände 56:45.750 --> 56:46.850 nicht -äquivalent sind. 56:47.310 --> 56:51.150 Dann weitermachen mit den Wörtern der Länge 1, dann weitermachen mit 56:51.150 --> 56:53.670 den Wörtern der Länge 2 und so weiter. 56:54.190 --> 56:58.110 Also systematisch von unten über die Länge der Wörter nach solchen 56:58.110 --> 57:00.050 Zeugen suchen für nicht-äquivalent. 57:05.740 --> 57:13.720 Wenn so ein Wort belegt, dass zwei Zustände P und Q nicht-äquivalent 57:13.720 --> 57:17.820 sind, dann trennt das Wort sozusagen P und Q. 57:18.820 --> 57:23.080 Bedeutet, dass P und Q gehören in getrennte Äquivalenzklassen. 57:23.860 --> 57:29.940 Wir suchen also systematisch nach Zeugen, die Zustandspaare trennen. 57:32.780 --> 57:36.380 Dieses Verfahren ist nicht weniger aufwendig als das Verfahren, 57:37.460 --> 57:40.060 sozusagen Äquivalenzklassen zu bilden, nach Definition der 57:40.060 --> 57:45.560 Äquivalenzklasse, wenn wir keinerlei Indiz dafür haben, wann wir 57:45.560 --> 57:46.480 aufhören können. 57:51.380 --> 57:54.640 Wenn Sie dieses Verfahren anwenden, haben Sie am Anfang alle Zustände 57:54.640 --> 58:00.620 zusammen in einer Menge und Sie wollen jetzt systematisch nach Zeugen 58:00.620 --> 58:03.300 suchen, die diese Menge auftrennt. 58:06.460 --> 58:09.540 Das sind Kandidaten, die könnten noch äquivalent sein und das sind 58:09.540 --> 58:13.820 Kandidaten, die könnten noch äquivalent sein, aber es gibt kein 58:13.820 --> 58:17.540 Zustandspaar, wo der eine Zustand in der einen, der andere Zustand in 58:17.540 --> 58:21.820 der anderen Menge ist, die noch in dieselbe Äquivalenzklasse gehören. 58:22.040 --> 58:26.140 Sie trennen sozusagen so systematisch auf, aber die Frage ist, wann 58:26.140 --> 58:27.660 bin ich fertig mit auftrennen. 58:28.460 --> 58:32.360 Wenn ich irgendwo ankäme, wo jeder einzelne Zustand in einer Menge 58:32.360 --> 58:36.980 ist, dann könnte ich sagen, das war es, jetzt muss ich aufhören. 58:37.360 --> 58:41.120 Aber normalerweise würden Sie ja bei diesem Bilden des 58:41.940 --> 58:44.220 Äquivalenzklassenautomats zu einem deterministischen endlichen 58:44.220 --> 58:49.900 Automat, zu dem einige Zustände in derselben Äquivalenzklasse sind. 58:50.140 --> 58:55.320 Die Frage ist, gibt es ein Indiz dafür, dass ich aufhören kann, nach 58:55.320 --> 58:58.800 weiteren Zeugen zu suchen oder dass ich fertig bin, dass ich jetzt 58:58.800 --> 59:03.800 alle Äquivalenzklassen gefunden habe oder alle Zustandspaare getrennt 59:03.800 --> 59:05.840 habe, die in verschiedene Äquivalenzklassen gehören. 59:07.160 --> 59:11.080 Ich gehe der Länge nach vor beim Suchen der Zeugen und das Schöne ist, 59:11.140 --> 59:14.860 ich kann tatsächlich irgendwann mal aufhören, nämlich dann, wenn ich 59:14.860 --> 59:21.260 für eine Wortlänge kein Zustandspaar finde, das durch ein Wort dieser 59:21.260 --> 59:25.780 Länge getrennt wird, dann weiß ich, dann kann es auch kein längeres 59:25.780 --> 59:29.700 Wort mehr geben, das noch mal zwei Zustände trennt, von denen ich 59:29.700 --> 59:33.160 bisher noch nicht gesehen habe, dass sie in verschiedene 59:33.160 --> 59:34.360 Äquivalenzklassen gehören. 59:35.960 --> 59:38.120 Das müssen wir uns jetzt natürlich klar machen, dass das stimmt, was 59:38.120 --> 59:39.340 ich da gerade gesagt habe. 59:40.120 --> 59:44.500 Also, das Verfahren läuft so, wir betrachten Wörter aus Sigma Stern, 59:45.100 --> 59:50.240 der Länge nach und zwar in aufsteigender Reihenfolge und überprüfen 59:50.240 --> 59:54.460 für jedes Wort, ob es Zeuge für Nichtäquivalenz von zwei Zuständen 59:54.460 --> 59:54.760 ist. 59:55.520 --> 59:58.880 Das heißt, wir betrachten immer Zustandspaare, von denen wir bisher 59:58.880 --> 01:00:02.880 noch nicht wissen, dass sie nichtäquivalent sind und prüfen für ein 01:00:02.880 --> 01:00:07.300 konkretes Wort nach, würde dieses Wort die beiden trennen. 01:00:09.740 --> 01:00:12.920 Wann kann dieses Verfahren abgebrochen werden? 01:00:13.240 --> 01:00:19.760 Nun gut, betrachten wir mal ein Wort W, das kürzester Zeuge für die 01:00:19.760 --> 01:00:23.180 Nichtäquivalenz zweier Zustände P und Q ist. 01:00:23.640 --> 01:00:27.660 Also zu zwei Zuständen P und Q, die nichtäquivalent sind, betrachten 01:00:27.660 --> 01:00:29.900 wir einen kürzesten Zeugen. 01:00:30.960 --> 01:00:31.500 Den nennen wir W. 01:00:32.800 --> 01:00:37.160 Dieses W, das können wir auch schreiben als Symbol A, gefolgt von dem 01:00:37.160 --> 01:00:37.980 Wort W'. 01:00:37.980 --> 01:00:45.520 Dann ist natürlich W' Zeuge für die Nichtäquivalenz der beiden 01:00:45.520 --> 01:00:49.160 Zustände P' und Q'. 01:00:49.160 --> 01:00:57.580 P' ist der Zustand, in dem wir kommen von P aus bei Lesen von A und Q' 01:00:57.740 --> 01:01:03.700 ist der Zustand, in dem wir kommen von Q aus bei Lesen von A. 01:01:05.220 --> 01:01:10.860 Nach Definition, wenn W gleich A W' kürzester Zeuge für P 01:01:10.860 --> 01:01:19.700 nichtäquivalent Q ist, dann ist W' ein Zeuge für P' gleich Delta P A 01:01:20.560 --> 01:01:23.160 nichtäquivalent Q' gleich Delta Q A. 01:01:24.540 --> 01:01:28.140 Jetzt müssen wir nur noch nachschauen, ob es hierfür einen kürzeren 01:01:28.140 --> 01:01:29.400 Zeugen geben könnte. 01:01:30.340 --> 01:01:35.540 Annahme, es gäbe einen kürzeren Zeugen für die Nichtäquivalenz von P' 01:01:35.780 --> 01:01:36.560 und Q'. 01:01:36.560 --> 01:01:38.580 Der hieße W'. 01:01:41.260 --> 01:01:47.360 Ja, wenn dem so wäre, dann wäre aber A gefolgt von W' wiederum ein 01:01:47.360 --> 01:01:53.120 Zeuge für die Nichtäquivalenz von P' und Q', weil A gefolgt von W' 01:01:53.560 --> 01:01:59.240 führt dann auch einen von den beiden P' und Q' in einen Endzustand und 01:01:59.240 --> 01:02:05.600 einen im Nichtendzustand, weil W' einen von den beiden P' und Q' in 01:02:05.600 --> 01:02:08.860 den Endzustand und den anderen in den Nichtendzustand führt. 01:02:10.040 --> 01:02:16.540 Dann hätten wir aber einen Widerspruch, weil dieses W2' kürzer wäre 01:02:16.540 --> 01:02:17.820 als AW'. 01:02:17.820 --> 01:02:22.940 Wir aber angenommen haben, dass AW' kürzester Zeuge für 01:02:22.940 --> 01:02:24.720 Nichtäquivalenz von P' und Q' ist. 01:02:26.320 --> 01:02:32.260 Das heißt also umgekehrt jetzt, wenn wir bei unserem Verfahren, wo wir 01:02:32.260 --> 01:02:35.920 der Länge nach die Wörter angucken und versuchen mit den Wörtern 01:02:35.920 --> 01:02:39.100 Zustände zu trennen, von denen wir noch nicht wissen, ob sie 01:02:39.100 --> 01:02:44.540 nichtäquivalent sind, irgendwann zu einer Wortlänge kommen, die keine 01:02:44.540 --> 01:02:49.440 Zustandspaare mehr trennt, dann sind wir fertig. 01:03:01.120 --> 01:03:05.980 Also die Vorgehensweise zur Konstruktion des Äquivalenzklassenautomats 01:03:06.840 --> 01:03:13.280 zu einem DAA ist, betrachte alle Zustandspaare und zunächst das leere 01:03:13.280 --> 01:03:18.240 Wort, dann alle Symbole, also alle Worte der Länge 1, dann alle Worte 01:03:18.240 --> 01:03:20.220 der Länge 2 und so weiter. 01:03:20.760 --> 01:03:25.020 Solange ich noch Zustandspaare finde, die getrennt werden, mache ich 01:03:25.020 --> 01:03:25.420 weiter. 01:03:25.560 --> 01:03:32.680 Wenn ich zum ersten Mal eine Wortlänge betrachte, von der ich kein 01:03:32.680 --> 01:03:36.420 Wort finde, das noch ein Zustandspaar trennt, höre ich auf. 01:03:37.920 --> 01:03:43.060 Und ich tue am Anfang so, als wären alle Zustände äquivalent. 01:03:43.940 --> 01:03:46.760 Ich nehme die als eine Menge und ich versuche, die systematisch 01:03:47.100 --> 01:03:47.740 aufzutrennen. 01:03:49.160 --> 01:03:51.640 Welche Zustände trennt das leere Wort? 01:03:54.540 --> 01:03:55.600 Welche Zustandspaare? 01:03:57.020 --> 01:04:05.520 Zwei Zustände sind äquivalent, wenn jedes Wort gilt, führt beide in 01:04:05.520 --> 01:04:09.120 einen Endzustand oder beide in einen Nicht-Endzustand. 01:04:10.140 --> 01:04:14.140 Das macht Epsilon, das führt jeden Zustand zu sich selber. 01:04:14.400 --> 01:04:15.320 Da passiert gar nichts. 01:04:15.460 --> 01:04:17.900 Wir sind in einem deterministischen endlichen Automat. 01:04:19.180 --> 01:04:23.160 Das heißt also, Epsilon trennt gerade die Endzustände von den Nicht 01:04:23.160 --> 01:04:24.020 -Endzuständen. 01:04:27.370 --> 01:04:31.630 Wenn ich in einem Endzustand bin, bleibe ich in einem Endzustand, bei 01:04:31.630 --> 01:04:32.390 Lesung von Epsilon. 01:04:32.610 --> 01:04:35.390 Wenn ich am Nicht-Endzustand bin, dann bleibe ich in dem Nicht 01:04:35.390 --> 01:04:37.390 -Endzustand, bei Lesung von Epsilon. 01:04:37.550 --> 01:04:40.990 Das heißt also, durch Epsilon werden die Zustände aus F von den 01:04:40.990 --> 01:04:43.030 Zuständen aus Q ohne F getrennt. 01:04:45.070 --> 01:04:49.330 Danach muss ich natürlich nur noch Zustandspaare, die innerhalb von F 01:04:49.330 --> 01:04:54.090 liegen und Zustandspaare, die innerhalb von Q ohne F liegen, 01:04:54.690 --> 01:04:55.290 betrachten. 01:04:55.890 --> 01:04:57.290 Die anderen sind ja schon getrennt. 01:04:57.790 --> 01:05:02.190 Ich weiß ja schon, alle in F sind nichtäquivalent zu allen aus Q ohne 01:05:02.190 --> 01:05:02.470 F. 01:05:03.690 --> 01:05:08.330 Das heißt also, im Laufe des Verfahrens brauche ich auch nur immer 01:05:08.330 --> 01:05:09.690 weniger Zustandspaare. 01:05:12.690 --> 01:05:19.910 Wenn ich dann ein Wort der Länge 1 betrachte, dann gibt es mindestens 01:05:19.910 --> 01:05:27.530 ein Wort der Länge 1, das entweder F oder Q ohne F auftrennt, also in 01:05:27.530 --> 01:05:32.170 F oder in Q ohne F ein Zustandspaar findet, das nichtäquivalent ist. 01:05:32.170 --> 01:05:36.110 Oder ich kann das Verfahren beenden. 01:05:38.730 --> 01:05:43.890 Und so mache ich iterativ weiter mit Wörtern wachsender Länge. 01:05:45.550 --> 01:05:47.890 Das gucken wir uns jetzt mal bei unserem Beispiel an. 01:05:52.230 --> 01:05:59.670 Also zu Beginn schauen wir einfach alle Zustände an als eine Menge und 01:05:59.670 --> 01:06:04.150 dann schauen wir das leere Wort an und schauen nach, welche Zustände 01:06:04.150 --> 01:06:05.330 trennt das leere Wort. 01:06:06.290 --> 01:06:10.130 Na gut, wir wissen schon, das leere Wort trennt die Endzustandsmenge 01:06:10.130 --> 01:06:13.090 oder die Menge der Endzustände von den anderen. 01:06:14.030 --> 01:06:21.810 Das leere Wort führt gerade die grünen Zustände in Endzustände, weil 01:06:21.810 --> 01:06:25.290 die grünen sind die Endzustände, und alle anderen in Nicht 01:06:25.290 --> 01:06:28.950 -Endzustände, weil alle anderen nicht Endzustände sind. 01:06:29.630 --> 01:06:36.670 Das heißt also, vor Überprüfung, welche Zustände werden durch Epsilon 01:06:36.670 --> 01:06:39.230 getrennt, sind alle Zustände in einer Menge. 01:06:39.890 --> 01:06:46.530 Nachdem wir nachgeschaut haben, für jedes Zustandspaar wird es durch 01:06:46.530 --> 01:06:49.970 Epsilon getrennt oder nicht, haben wir einerseits die Menge der 01:06:49.970 --> 01:06:52.830 Endzustände und andererseits die Restmenge. 01:06:53.850 --> 01:06:58.310 Einerseits die grünen und andererseits die roten, blauen und weißen in 01:06:58.310 --> 01:06:58.750 einer Menge. 01:06:59.210 --> 01:07:04.170 So als nächstes betrachten wir alle Wörter der Länge 1. 01:07:04.990 --> 01:07:05.950 Wörter der Länge 1. 01:07:06.070 --> 01:07:10.210 Unser Alphabet ist 0 1, also einerseits 0, andererseits 1. 01:07:15.550 --> 01:07:19.130 Innerhalb der grünen schauen wir erst mal, wohin führt uns 0. 01:07:20.670 --> 01:07:24.990 Von den grünen aus führt uns Lesen einer 0 immer in einen roten 01:07:24.990 --> 01:07:25.590 Zustand. 01:07:26.390 --> 01:07:32.130 Also von den Endzuständen aus führt uns Lesen der 0 in allen Fällen in 01:07:32.130 --> 01:07:34.210 einen Nicht-Endzustand. 01:07:35.390 --> 01:07:38.590 Das heißt also, die grüne Menge wird nicht weiter getrennt. 01:07:39.490 --> 01:07:43.410 Und wenn man jetzt hier weiterschaut in dieser zweiten Menge, wohin 01:07:43.410 --> 01:07:56.490 führt uns 0, dann sehen wir, genau von den roten Zuständen aus führt 01:07:56.490 --> 01:07:58.610 das Lesen einer 0 in einen Endzustand. 01:07:59.750 --> 01:08:05.890 Das Lesen einer 0 führt von 1 0 nach 2 0, führt von 3 0 nach 0 0 und 01:08:05.890 --> 01:08:06.290 so weiter. 01:08:06.430 --> 01:08:11.910 Also genau von den roten aus werden bei Lesen einer 0 ein Endzustand 01:08:11.910 --> 01:08:18.190 erreicht, während von den weißen und blauen aus durch Lesen einer 0 01:08:18.190 --> 01:08:20.570 wieder ein Nicht-Endzustand erreicht wird. 01:08:20.650 --> 01:08:23.950 Von den blauen kommen wir immer in einen weißen Zustand durch Lesen 01:08:23.950 --> 01:08:27.190 einer 0 und von den weißen kommen wir immer in einen blauen Zustand 01:08:27.190 --> 01:08:28.250 durch Lesen einer 0. 01:08:28.870 --> 01:08:34.750 Das heißt also, 0 trennt die Menge der roten Zustände von der Menge 01:08:34.750 --> 01:08:36.390 der weißen und blauen Zustände. 01:08:39.680 --> 01:08:41.980 Im nächsten Schritt betrachten wir die 1. 01:08:42.360 --> 01:08:46.520 Die brauchen wir jetzt auch nur betrachten, wie alle Zustandspaare 01:08:46.520 --> 01:08:50.760 jeweils aus einer dieser Mengen, wo beide aus einer dieser Mengen 01:08:50.760 --> 01:08:50.960 sind. 01:08:51.680 --> 01:08:57.180 Die 1, die führt alle Endzustände zu einem blauen Zustand, da wird 01:08:57.180 --> 01:08:58.120 also nichts getrennt. 01:08:58.120 --> 01:09:05.020 Die 1 führt alle roten Zustände zu einem weißen Zustand, also Nicht 01:09:05.020 --> 01:09:06.940 -Endzustand, da wird also auch nichts getrennt. 01:09:07.620 --> 01:09:14.240 Die 1 führt alle blauen Zustände zu einem grünen, also in einen 01:09:14.240 --> 01:09:19.580 Endzustand und alle weißen Zustände zu einem roten, also in einen 01:09:19.580 --> 01:09:20.800 Nicht -Endzustand. 01:09:21.580 --> 01:09:25.700 Das heißt, die 1 trennt die blauen von den weißen. 01:09:27.240 --> 01:09:30.460 Das heißt also, nachdem wir die 1 überprüft haben, haben wir diese 01:09:30.460 --> 01:09:32.320 vier Mengen von Zuständen. 01:09:33.480 --> 01:09:37.780 Die Frage ist, gibt es jeweils innerhalb dieser Mengen noch weitere 01:09:37.780 --> 01:09:40.640 Zustandspaare, die nicht äquivalent sind? 01:09:41.620 --> 01:09:49.280 Dafür müssen wir jetzt alle Wörter der Länge 2 überprüfen und wenn wir 01:09:49.280 --> 01:09:53.180 das machen, merken wir, es wird keine Menge mehr aufgetrennt. 01:09:55.320 --> 01:09:59.160 Wörter der Länge 2, das ist 00, 01, 10, 11. 01:10:01.460 --> 01:10:10.980 00 führt von den grünen aus wieder in grüne, 01 führt von den grünen 01:10:10.980 --> 01:10:17.740 aus in weiße, 10 führt von den grünen aus in weiße und 11 führt von 01:10:17.740 --> 01:10:20.440 den grünen aus in grüne. 01:10:21.200 --> 01:10:26.560 Das heißt also, jedes dieser Wörter führt entweder die grünen wieder 01:10:26.560 --> 01:10:31.080 in die grünen, also wieder in Endzustände oder die grünen in die roten 01:10:31.080 --> 01:10:36.060 oder die weißen oder die blauen, also nicht Endzustände. 01:10:36.500 --> 01:10:40.640 Also die grünen werden schon mal nicht aufgetrennt durch irgendeines 01:10:40.640 --> 01:10:41.280 dieser Wörter. 01:10:41.660 --> 01:10:47.020 Und genauso kann man es für die anderen auch sehen, dass keines dieser 01:10:47.020 --> 01:10:50.440 Wörter der Länge 2 noch eine der Klassen trennt. 01:10:50.760 --> 01:10:53.020 Also schauen wir jetzt einfach mal die weißen an. 01:10:53.440 --> 01:10:58.900 Die weißen, die werden durch Lesen von 00 wieder zu Weißen geführt, 01:10:59.880 --> 01:11:02.720 also in allen Fällen zu Nicht-Endzuständen. 01:11:03.120 --> 01:11:08.400 Und durch Lesen von 01 in Grüne geführt, also für alle Weißen in 01:11:08.400 --> 01:11:15.780 Endzustand oder durch Lesen von 10 in Grün geführt, also für alle 01:11:15.780 --> 01:11:21.540 Weißen in einen Endzustand und durch Lesen von 11 wieder in den Weißen 01:11:21.540 --> 01:11:24.860 geführt, also für alle Weißen wieder in Nicht-Endzustand. 01:11:25.000 --> 01:11:28.260 Das heißt, die Weißen werden auch durch keines dieser Wörter getrennt. 01:11:28.380 --> 01:11:30.000 Und das hier ist ja alles sehr regelmäßig. 01:11:30.500 --> 01:11:33.060 Das heißt, wir müssen jetzt für die Blauen und die Roten es nicht auch 01:11:33.060 --> 01:11:33.920 noch mal überprüfen. 01:11:35.480 --> 01:11:39.800 Wir haben sozusagen gesehen, die Wörter der Länge 2 enthalten keine 01:11:39.800 --> 01:11:41.900 Zeugen mehr für Nicht-Äquivalenz. 01:11:42.460 --> 01:11:45.440 Nach dem, was wir uns vorher klar gemacht haben, können wir also jetzt 01:11:45.440 --> 01:11:46.680 mit dem Verfahren enden. 01:11:46.760 --> 01:11:52.500 Wir wissen, wir haben die Äquivalenzklassen Zustände dieses Automats 01:11:52.500 --> 01:11:53.100 gefunden. 01:11:53.940 --> 01:11:56.760 Das sind vier, das sind die Grünen, das sind die Roten, das sind die 01:11:56.760 --> 01:11:57.940 Weißen und das sind die Blauen. 01:12:02.920 --> 01:12:06.260 Das heißt also, der Äquivalenzklassenautomat hat vier Zustände. 01:12:07.260 --> 01:12:12.380 Der erste Zustand ist die Äquivalenzklasse des Zustands 0,0. 01:12:14.280 --> 01:12:19.340 Und weil 0,0 der Startzustand ist, ist das auch gleichzeitig der 01:12:19.340 --> 01:12:21.720 Startzustand unseres Äquivalenzklassenautomats. 01:12:22.840 --> 01:12:29.520 Der hat als zweiten Zustand die Äquivalenzklasse des Zustands 0,1. 01:12:30.420 --> 01:12:31.840 Das sind also diese Blauen. 01:12:34.860 --> 01:12:40.720 Als dritten Zustand die Äquivalenzklasse des Zustands 1,0. 01:12:41.360 --> 01:12:43.300 Das nennen wir Q2, das sind die Roten. 01:12:43.960 --> 01:12:49.080 Und als vierten Zustand die Äquivalenzklasse des Zustands 1,1. 01:12:49.800 --> 01:12:52.880 Nennen wir Q3 und das sind die Weißen. 01:12:55.320 --> 01:13:00.280 Und die Äquivalenzklasse von 0,0 ist gleichzeitig auch Endzustand, 01:13:00.960 --> 01:13:04.760 weil das ist eine Äquivalenzklasse, die nur Endzustände enthält. 01:13:04.880 --> 01:13:07.220 Und es ist auch die einzige, die Endzustände enthält. 01:13:08.380 --> 01:13:11.340 Und wie dann die Übergangsfunktion aussieht, das kann man dann direkt 01:13:11.340 --> 01:13:11.960 ablesen. 01:13:12.120 --> 01:13:16.240 Das entspricht genau diesem Schema hier, wie komme ich von Grün nach 01:13:16.240 --> 01:13:24.100 Grün, wie komme ich von erster Zeile, erster Spalte in einen roten 01:13:24.100 --> 01:13:29.520 Zustand oder in einen blauen Zustand oder in einen weißen Zustand.