WEBVTT 00:01.300 --> 00:02.400 Ja, schönen guten Morgen. 00:02.520 --> 00:05.520 Sie merken, dass Sie viele Kommilitonen haben, die aktiv sind in den 00:05.520 --> 00:06.100 Hochschulgruppen. 00:07.000 --> 00:10.140 Fast jedes Mal war jetzt jemand da, der irgendeine schöne Aktivität 00:10.140 --> 00:10.920 vorgestellt hat. 00:11.980 --> 00:16.460 Und ja, damit sind wir jetzt beim Beginn der Vorlesung wieder 00:16.460 --> 00:17.680 Grundlagen der Informatik II. 00:19.920 --> 00:26.400 Und wir hatten uns letztes Mal angeschaut, die endlichen Automaten 00:26.400 --> 00:29.840 hatten damit begonnen, beziehungsweise hatten weitergemacht. 00:29.940 --> 00:31.760 Ich hatte Ihnen schon einige Dinge erzählt. 00:32.040 --> 00:36.740 Ich hatte Ihnen letztes Mal den Warenautomaten vorgestellt, dann habe 00:36.740 --> 00:40.260 ich noch weitere Dinge gemacht. 00:40.660 --> 00:42.680 Wir haben den dann genauer uns angeschaut. 00:42.840 --> 00:45.980 Wir haben dann bitzerielle Additionen betrachtet. 00:46.300 --> 00:50.460 Ich habe Ihnen gezeigt, dass ein einfacher PC oder jeder PC, jeder 00:50.460 --> 00:53.700 Rechner im Prinzip zunächst mal ein endlicher Automat ist. 00:53.700 --> 00:56.300 Wir hatten uns dann mit Größenordnung beschäftigt. 00:56.320 --> 01:01.420 Ich habe Ihnen den Muautomaten vorgestellt, bei dem halt die Ausgabe 01:01.420 --> 01:02.640 aus den Zuständen kommt. 01:02.960 --> 01:07.800 Dann haben wir uns die Ampelsteuerung angeschaut und kamen schließlich 01:07.800 --> 01:11.720 zu den Akzeptoren und damit wieder zurück zur Charakterisierung von 01:11.720 --> 01:12.520 Sprachen. 01:13.100 --> 01:16.960 Wir haben gesehen, wir können damit also definieren, wann ein Wort 01:16.960 --> 01:24.180 akzeptiert wird und haben damit dann, nachdem wir die Konfiguration 01:24.180 --> 01:31.080 definiert hatten, auch die Sprache eines Automaten definieren können. 01:31.260 --> 01:33.900 Hier unten steht es nochmal, die Sprache des Automaten. 01:34.280 --> 01:39.040 Die Menge aller Wörter, die wir akzeptieren können, wenn wir vom 01:39.040 --> 01:43.100 Anfangszustand starten und dann eben am Ende in einen Endzustand 01:43.100 --> 01:43.600 geraten. 01:43.700 --> 01:46.320 Das ist ein akzeptiertes Wort und damit haben wir die Sprache 01:46.320 --> 01:46.620 charakterisiert. 01:46.620 --> 01:51.820 Wir hatten dann gesehen, dass man viele Sprachen erkennen kann auf 01:51.820 --> 01:52.940 diese Art und Weise. 01:53.680 --> 01:57.900 Insbesondere habe ich Ihnen hier ein paar Fragen gestellt zu endlichen 01:57.900 --> 01:58.460 Sprachen. 01:58.780 --> 02:00.900 Das ist klar, dass die alle akzeptiert werden können. 02:01.920 --> 02:06.700 Und dann kamen wir zu der Frage bei dieser Sprache A hoch N, B hoch N, 02:07.100 --> 02:11.300 wo ich also genauso viele Bs haben möchte, wie ich vorher As gesehen 02:11.300 --> 02:11.600 habe. 02:11.700 --> 02:15.440 Das heißt, ich muss zählen können und wir sahen schon, das ist 02:15.440 --> 02:15.880 schwierig. 02:15.880 --> 02:22.380 Und wir hatten dann gesehen auf dieser Folie, dass es offensichtlich 02:22.380 --> 02:26.760 so ist, wenn wir eben bei so einem endlichen Automaten eine Folge von 02:26.760 --> 02:30.380 Zuständen haben, die länger ist als die Anzahl der unterschiedlichen 02:30.380 --> 02:33.660 Zustände, dann muss halt mindestens ein Zustand doppelt vorkommen. 02:34.160 --> 02:36.200 Und das führte dann zu diesem Pumping Lemma. 02:37.420 --> 02:41.900 Das heißt, wenn ich ein Wort in der Sprache eines Automaten habe, das 02:41.900 --> 02:45.340 länger ist oder mindestens so lang ist wie die Anzahl der Zustände, 02:46.060 --> 02:49.780 dann muss ja in der Folge der Zustände, die ich erreiche, wenn ich das 02:49.780 --> 02:52.780 Wort eingebe, mindestens ein Zustand doppelt vorkommen. 02:52.900 --> 02:57.240 Und das heißt eben, wir haben dann genau bei einem Wort E1 bis EM ein 02:57.240 --> 03:02.520 solches Anfangsstück E1 bis EJ, das zum Zustand SJ führt, das sei also 03:02.520 --> 03:04.040 der Zustand, der doppelt auftaucht. 03:05.060 --> 03:08.820 Das zweite Vorkommen erreiche ich durch ein weiteres Teilwort Y, 03:08.820 --> 03:10.300 danach kommt ein Teilwort Z. 03:10.800 --> 03:14.020 Und was dann zwischen diesen beiden Vorkommen des gleichen Zustands 03:14.020 --> 03:18.780 passiert, das kann halt beliebig oft wiederholt werden, sodass ich 03:18.780 --> 03:22.680 dann eben diese Aussage habe, dass ich für jedes solche Wort eine 03:22.680 --> 03:27.540 Zerlegung kriege in XYZ, sodass das XY nicht zu lang ist. 03:27.620 --> 03:31.300 Ich brauche nur die ersten N-Zeichen mir anzuschauen, dann muss ich 03:31.300 --> 03:37.500 die kürzeste Folge vorne anzuschauen, bei der ich eine Wiederholung 03:37.500 --> 03:38.040 bekomme. 03:38.040 --> 03:40.900 Ich muss nicht zu weit gucken, das kann ich beschränken durch die 03:40.900 --> 03:41.720 Anzahl der Zustände. 03:42.420 --> 03:46.120 Dann brauche ich mindestens ein Zeichen, um zu dem zweiten Auftauchen 03:46.120 --> 03:47.220 des Zustands zu kommen. 03:47.780 --> 03:51.940 Und ich kann eben diese Folge von Zeichen zwischen den beiden 03:51.940 --> 03:56.280 Auftauchen eines gleichen Zustands, kann ich beliebig oft wiederholen 03:56.280 --> 04:00.040 und ich bin immer noch am Ende in einem Endzustand, akzeptiere also 04:00.040 --> 04:00.540 das Wort. 04:01.120 --> 04:04.800 Das heißt, wir haben hiermit eine Strukturaussage über die Struktur 04:04.800 --> 04:09.100 von Wörtern einer Sprache, die von endlichen Automaten akzeptiert 04:09.100 --> 04:09.680 wird. 04:10.080 --> 04:13.940 Wir haben immer ein solches Stück da drin bei den Wörtern ab einer 04:13.940 --> 04:18.480 gewissen Länge, das ich beliebig häufig wiederholen kann und alle 04:18.480 --> 04:20.100 diese Wörter sind in der Sprache. 04:20.200 --> 04:21.420 Deswegen eben Pumping Lemma. 04:21.800 --> 04:25.600 Ich kann ein solches Stück mittendrin im Wort beliebig oft 04:25.600 --> 04:26.180 wiederholen. 04:26.620 --> 04:28.340 Hochpumpen, deswegen Pumping Lemma. 04:28.340 --> 04:38.420 So, und das machen wir jetzt hier nochmal als Beweis, der hier auf der 04:38.420 --> 04:39.820 Folie auch schon vorbereitet war. 04:39.980 --> 04:45.880 Nochmal also, wir haben dieses Wort aus der Sprache, Länge M, und wir 04:45.880 --> 04:52.740 wissen, da das eine Sprache ist, dass wir von der Anfangskonfiguration 04:52.740 --> 04:57.400 in eine Endkonfiguration kommen, bei der der Zustand in der Menge der 04:57.400 --> 05:01.540 Endzustände ist, deswegen ist es ja ein Wort, das akzeptiert wird. 05:02.340 --> 05:05.460 Und das heißt, wir haben also dann eine solche Zustandsfolge, die 05:05.460 --> 05:10.220 durchlaufen wird, und in dieser Zustandsfolge, die erreichen wir halt, 05:10.320 --> 05:16.500 indem wir hier das E1 eingeben, dann das E2, dann E3 und so weiter, 05:16.640 --> 05:21.840 hier ein EJ, und dann hier, da an der Stelle ist es ein EK, da kommen 05:21.840 --> 05:26.940 wir zu wieder einem neuen Zustand, hier am Ende da ein EN und hier ein 05:26.940 --> 05:27.480 EM. 05:28.240 --> 05:31.620 Das ist also unser Wort und dazwischen sind die ganzen weiteren 05:31.620 --> 05:34.280 Zeichen unseres Wortes. 05:36.200 --> 05:39.300 Und das dient eben nur nochmal dazu, um das zu veranschaulichen, was 05:39.300 --> 05:40.740 ich gerade eben schon mal gesagt habe. 05:41.280 --> 05:44.780 Ich mache das so ausführlich, weil das so eine wichtige erste 05:44.780 --> 05:45.660 Erkenntnis ist. 05:45.660 --> 05:51.420 In dieser Folge, die wir nur betrachten müssen bis hierhin maximal, 05:52.040 --> 05:57.100 wenn wir die ersten Endzeichen eingegeben haben, dann wissen wir, da 05:57.100 --> 06:00.680 muss ein Zustand doppelt vorgekommen sein, weil wir ja N plus 1 06:00.680 --> 06:03.020 Zustände haben, Gamma 0 bis Gamma N. 06:03.900 --> 06:06.760 Das sind N plus 1 Zustände, also taucht ein Zustand doppelt auf. 06:06.920 --> 06:11.880 Das sei ein Zustand, der an den Positionen J und K gerade auftaucht, 06:11.880 --> 06:19.840 deswegen diese Einteilung in dieses erste Wort E1 bis EJ, dann EJ plus 06:19.840 --> 06:24.400 1 bis EK und EK plus 1 bis EM. 06:25.240 --> 06:30.720 Und damit haben wir also X, Y und Z. 06:31.580 --> 06:35.460 Das steht hier drunter, das ist also gerade diese Einteilung. 06:35.460 --> 06:41.760 Und wir wissen, dass wir dann eben diesen Teil Y beliebig oft dort 06:41.760 --> 06:42.780 wiederholen können. 06:42.940 --> 06:50.920 Also nochmal, wir haben hier X, danach das Y und danach ein Wort Z. 06:51.400 --> 06:56.320 Und wir wissen, wir sind am Ende garantiert in einem Zustand, der in 06:56.320 --> 06:57.580 der Endzustandsmenge liegt. 06:57.840 --> 07:01.860 Damit haben wir alle solchen Wörter, die wir damit erreichen können, 07:03.000 --> 07:03.720 akzeptiert. 07:04.720 --> 07:09.280 Also das ist die wesentliche Erkenntnis nochmal, wenn Sie ein 07:09.280 --> 07:12.700 endliches System haben und Sie wollen Eigenschaften eines endlichen 07:12.700 --> 07:17.120 Systems untersuchen, dann nutzen Sie die Eigenschaft aus, dass Sie nur 07:17.120 --> 07:19.360 endlich viele Situationen unterscheiden können. 07:19.880 --> 07:23.300 Also wenn Sie ein Verhalten über einen längeren Zeitraum betrachten, 07:23.860 --> 07:27.600 der länger ist als die Anzahl der unterschiedlichen Situationen, die 07:27.600 --> 07:31.360 Sie betrachten können, muss eine Situation doppelt aufgetreten sein. 07:31.360 --> 07:35.480 Das heißt, alles, was zwischen diesem doppelten Auftreten passiert, 07:35.820 --> 07:37.220 können Sie beliebig oft machen. 07:37.680 --> 07:40.800 Und das heißt, das weitere Verhalten ist nur bestimmt dadurch, was in 07:40.800 --> 07:43.480 diesem vorderen Teil eigentlich schon passiert ist. 07:43.560 --> 07:46.760 Das heißt, Sie können Aussagen machen, indem Sie nur eine begrenzte 07:46.760 --> 07:52.280 Länge von Wörtern untersuchen, der Rest ist damit auch abgedeckt. 07:53.860 --> 07:57.100 Also das ist eine ganz wichtige Erkenntnis und wir werden noch ein 07:57.100 --> 08:01.380 weiteres Pumping Lemma kennenlernen, wenn wir nachher zu den 08:01.380 --> 08:02.820 kontextfreien Sprachen kommen. 08:04.440 --> 08:08.360 Dort wird es eine etwas andere Situation sein, aber im Prinzip ist es 08:08.360 --> 08:09.300 genau das Gleiche. 08:09.840 --> 08:15.400 Und was Sie sich merken müssen, ist wirklich diese Schleifenbildung, 08:15.940 --> 08:20.460 dass Sie eben einen Zustand haben, der halt hier mehrfach vorkommt und 08:20.460 --> 08:23.940 deswegen können Sie eben hier diese Strukturaussage machen. 08:23.940 --> 08:28.620 Okay, hier steht es nochmal, dass Sie dann eben für eine beliebige 08:28.620 --> 08:33.240 Wiederholung dieses Stückes Y immer wieder auf den gleichen Zustand 08:33.240 --> 08:35.940 zurückkommen, sodass wir dann das Wort akzeptieren können. 08:36.560 --> 08:40.200 Das ist das, was wir hier zeigen müssen zum Beweis dieses Lemmas und 08:40.200 --> 08:42.140 damit können wir das jetzt anwenden. 08:42.940 --> 08:46.140 Wir haben verschiedene Sprachen hier betrachtet, ich komme zurück zu 08:46.140 --> 08:50.720 dem Beispiel, wo alle Wörter auf zwei Zeichen enden sollten. 08:50.720 --> 08:54.400 Wir wissen, dass es eine Sprache, die von einem endlichen Automaten 08:54.400 --> 08:55.260 akzeptiert wird. 08:55.340 --> 08:57.800 Wir hatten uns den Automaten dazu aufgemalt. 08:58.680 --> 09:01.560 Also, bei dem Automaten, der hier oben nochmal angedeutet ist, da 09:01.560 --> 09:04.780 haben wir drei Zustände. 09:05.760 --> 09:11.180 Und drei Zustände heißt, wenn wir jetzt genauso vorgehen wollen, wir 09:11.180 --> 09:17.580 schauen also mal, bis wir drei Zeichen eingegeben haben, A, B, A, dann 09:17.580 --> 09:20.320 muss ja mindestens ein Zustand doppelt aufgetaucht sein. 09:20.400 --> 09:23.400 Wir sehen, wir haben sogar einen Zustand, der dreimal auftaucht, 09:23.480 --> 09:24.140 nämlich S0. 09:25.160 --> 09:28.060 Wir haben also mehrere Möglichkeiten, solche Aufteilungen zu machen. 09:28.980 --> 09:32.940 Wir wissen, es muss hier so eine Zerlegung geben, also ein X und ein 09:32.940 --> 09:35.120 Y, das können wir hier mehrere Sachen machen. 09:35.600 --> 09:39.120 Wir können also sagen, das X könnte in diesem Fall das leere Wort 09:39.120 --> 09:43.520 sein, denn wir haben ja hier bereits der Zustand S0 taucht doppelt 09:43.520 --> 09:43.840 auf. 09:43.840 --> 09:48.680 Also wäre dieser Teil zwischen dem ersten und zweiten Auftauchen von 09:48.680 --> 09:55.660 S0, wäre der Teil Y, der Teil X muss davor sein, deswegen wäre das das 09:55.660 --> 10:00.820 Lambda, das leere Wort, das Y wäre das A und das, was dahinter kommt, 10:00.940 --> 10:04.700 ist dann Z, also B, A, A, B, B, B, der ganze Rest. 10:05.560 --> 10:09.420 Ich könnte auch anders aufteilen, ich könnte, wenn also X Lambda ist, 10:09.460 --> 10:13.040 ich könnte auch sagen, das S0 taucht ja hier auch nochmal auf. 10:13.040 --> 10:17.680 Ich könnte also auch sagen, ich nehme einfach das Wort A, B, A hier, 10:17.780 --> 10:23.040 das könnte ich hier nehmen als Y und Z wäre dann A, B, B, B. 10:24.100 --> 10:25.340 Es gibt noch eine Möglichkeit. 10:26.120 --> 10:29.460 Ich könnte sagen, ich radiere das hier mal wieder weg, was ich gerade 10:29.460 --> 10:33.060 gemacht habe, das kann ich ja so mal das hier wegnehmen. 10:33.740 --> 10:36.300 Ich könnte noch anders aufteilen, das steht hier gar nicht auf der 10:36.300 --> 10:37.880 Folie, aber kann man natürlich auch machen. 10:37.880 --> 10:42.300 Ich könnte natürlich auch sagen, naja, hier taucht das S0 doppelt auf, 10:42.780 --> 10:46.460 also könnte ich auch sagen, das könnte ich auch so aufteilen, dass das 10:46.460 --> 10:51.120 hier X ist, das Y und dann hier hinten das Z. 10:51.800 --> 10:54.800 Also es ist keineswegs so, dass diese Aufteilung eindeutig ist. 10:55.960 --> 10:58.660 Es gibt hier, wie Sie an diesem Beispiel sehen, da gibt es mehrere 10:58.660 --> 11:01.920 Möglichkeiten, eine solche Aufteilung zu machen, aber Sie brauchen 11:01.920 --> 11:10.380 nicht weiterzuschauen bis zu dem Wort, das aus drei Zeichen besteht, 11:10.460 --> 11:11.900 weil wir drei Zustände haben. 11:12.280 --> 11:15.280 Wenn Sie drei Zeichen eingelesen haben, wissen Sie, mindestens ein 11:15.280 --> 11:17.660 Zustand muss doppelt aufgetaucht sein. 11:17.860 --> 11:19.280 Genau das sehen Sie hier in diesem Beispiel. 11:19.480 --> 11:23.380 Also es gibt viele Möglichkeiten, eine solche Aufteilung zu machen und 11:23.380 --> 11:27.760 egal, wie Sie die Aufteilung machen, Sie wissen, wenn Sie das Y, in 11:27.760 --> 11:32.600 dem Fall das A, in dem Fall das ABA oder auch nur das BA, wenn Sie das 11:32.600 --> 11:35.940 beliebig oft reinschreiben, alle diese Wörter sind garantiert in der 11:35.940 --> 11:36.500 Sprache drin. 11:38.420 --> 11:42.820 Und damit haben wir also das einmal gesehen, wie das tatsächlich 11:42.820 --> 11:43.400 aussieht. 11:43.960 --> 11:46.380 Und jetzt schreibe ich Ihnen eine Folgerung auf und ich schreibe 11:46.380 --> 11:49.520 gleich zum Vergleich nochmal das Pumping Lemma unten drunter. 11:50.820 --> 11:54.120 Und ich schreibe, ich fange jetzt an, das Pumping Lemma nochmal Ihnen 11:54.120 --> 11:55.560 darzulegen. 11:56.700 --> 11:59.460 Und zwar ist es so, hier steht, ist L die Sprache eines endlichen 11:59.460 --> 12:02.180 Automaten, dann gilt irgendwas. 12:02.900 --> 12:08.900 Wir haben also eine Aussage A, Groß A, das sei mal diese Aussage, L 12:08.900 --> 12:13.120 ist die Sprache eines endlichen Automaten, das sei die Aussage A. 12:13.560 --> 12:15.660 Und dann gilt irgendwas anderes. 12:16.340 --> 12:17.980 Und das ist die Aussage B. 12:18.800 --> 12:20.640 Wir sagen, aus A folgt B. 12:22.460 --> 12:25.140 So, einfache Folgerung. 12:26.780 --> 12:27.940 Was ist die Aussage B? 12:28.480 --> 12:33.240 Es gibt ein N aus N, sodass es für jedes Wort W aus L mit Betracht von 12:33.240 --> 12:37.540 W größer gleich N eine Zerlegung W gleich XYZ gibt, für die gilt 1, 2, 12:37.600 --> 12:37.800 3. 12:39.360 --> 12:45.560 Sie wissen, jede Aussage A folgt B kann man äquivalent aufschreiben 12:45.560 --> 12:51.340 als nicht B folgt nicht A. 12:51.660 --> 12:55.460 Das ist logisch die gleiche Aussage, die äquivalente Aussage, die 12:55.460 --> 12:58.100 Kontraposition der gleichen Aussage. 12:58.200 --> 13:02.240 Wenn A folgt B gilt, dann gilt auch nicht B folgt A, einfache 13:02.240 --> 13:02.960 Kontraposition. 13:03.580 --> 13:05.420 Und genau das steht hier oben in der Folgerung. 13:06.420 --> 13:07.820 Das ist die gleiche Aussage. 13:08.640 --> 13:10.800 Was ist nicht B? 13:11.880 --> 13:14.120 Wir haben also eine beliebige Sprache gegeben. 13:15.620 --> 13:21.480 Und nicht B muss, also hier steht, es gibt ein N, sodass für jedes 13:21.480 --> 13:27.280 Wort, wenn wir das negieren, muss da also stehen, für jedes N, bei der 13:27.280 --> 13:33.080 Negation wird aus dem Existenzquantor ein Alquantor, also für jedes N, 13:33.940 --> 13:35.300 gibt es ein Wort. 13:36.080 --> 13:39.280 Hier unten stand, es gibt. 13:40.880 --> 13:46.120 Und da steht, für alle, mit irgendeiner Eigenschaft. 13:46.600 --> 13:52.320 Und hier oben steht, für alle, für jedes N, gibt es ein Wort. 13:52.700 --> 13:54.020 Das ist eine einfache Negation. 13:55.940 --> 14:00.280 Gibt es ein Wort, sodass es für jede Zerlegung, X, Y, Z, hier unten 14:00.280 --> 14:05.840 stand, es gibt eine Zerlegung, also nochmal ein Existenzquantor hier 14:05.840 --> 14:06.180 unten. 14:07.180 --> 14:09.680 Und da steht jetzt, für jede, da steht also der Alquantor. 14:11.320 --> 14:12.400 Das ist genau die Negation. 14:12.900 --> 14:17.620 Für jede Zerlegung gibt es ein I aus N. 14:18.380 --> 14:20.400 Da steht, für alle I aus N. 14:20.400 --> 14:22.840 Hier steht, es gibt ein I aus N. 14:22.900 --> 14:28.940 Für jede Zerlegung, für jede Zerlegung mit diesen Eigenschaften, X, Y 14:28.940 --> 14:33.180 kleiner gleich N und Betrag von Y größer gleich 1, gibt es ein I aus 14:33.180 --> 14:39.060 N0, sodass X, Y, Y hoch I, Z nicht aus L ist. 14:39.580 --> 14:41.560 Da stand, es ist aus L von A. 14:43.140 --> 14:45.160 Also, das ist nicht B. 14:47.900 --> 14:50.880 Dann ist L nicht Sprache eines endlichen Automaten. 14:51.120 --> 14:52.000 Das ist nicht A. 14:53.220 --> 14:56.000 Hier unten stand, ist L die Sprache eines endlichen Automaten? 14:56.440 --> 14:58.020 Hier oben steht jetzt, nicht A. 14:59.120 --> 15:01.540 L ist nicht Sprache eines endlichen Automaten. 15:02.160 --> 15:04.140 Also, was hier oben steht als Folgerung, ist eine einfache 15:04.140 --> 15:06.540 Kontraposition der Aussage des Pumping Lemmas. 15:06.940 --> 15:08.120 Und warum mache ich das? 15:08.120 --> 15:13.620 Weil wir in dieser Folgerung jetzt sehen, wie wir dieses Pumping Lemma 15:13.620 --> 15:17.560 einsetzen können, um uns zu helfen bei der Charakterisierung von 15:17.560 --> 15:18.080 Sprache. 15:18.660 --> 15:23.040 Das Problem ist nämlich, ich kann mit dem Pumping Lemma nicht sagen, 15:24.180 --> 15:27.940 wenn eine Sprache diese Eigenschaft hat, dann wird sie von einem 15:27.940 --> 15:29.300 endlichen Automaten akzeptiert. 15:29.400 --> 15:32.520 Hier steht nur, wenn sie von einem endlichen Automaten akzeptiert 15:32.520 --> 15:37.700 wird, dann hat sie diese Eigenschaft, dass ich immer so eine Zerlegung 15:37.700 --> 15:42.340 finde, bei den Wörtern, die akzeptiert werden, sodass ich eine 15:42.340 --> 15:44.740 Pumpstelle finden kann, die ich beliebig oft hochpumpen kann. 15:45.240 --> 15:47.820 Das ist nur eine notwendige Aussage. 15:48.940 --> 15:50.820 Also eine notwendige Folgerung. 15:50.940 --> 15:52.420 Das ist nicht eine hinreichende. 15:53.380 --> 15:58.400 Und das heißt, wir können das also so einsetzen, dass wir feststellen, 15:58.520 --> 16:06.400 bei bestimmten Sprachen gilt nicht B, also gilt für diese Sprachen 16:06.400 --> 16:07.060 nicht A. 16:08.460 --> 16:11.300 Das heißt, sie sind nicht akzeptiert vom endlichen Automaten. 16:12.820 --> 16:14.780 Und so werden wir das Pumping Lemma einsetzen. 16:15.300 --> 16:19.600 Für gewisse Sprachen zu zeigen, diese Sprachen können auf keinen Fall 16:19.600 --> 16:22.160 von einem endlichen Automaten akzeptiert werden. 16:22.600 --> 16:25.540 Das war ja das, was wir eigentlich herausfinden wollten, als ich Ihnen 16:25.540 --> 16:28.680 das Beispiel gezeigt habe von der Sprache A auch N, B auch N. 16:28.980 --> 16:31.860 Da war die Vermutung, irgendwie reicht die Eigenschaft der endlichen 16:31.860 --> 16:32.900 Automaten nicht aus. 16:32.960 --> 16:34.200 Wir können nicht wirklich zählen. 16:34.960 --> 16:37.940 Und wir vermuten, wir können keinen endlichen Automaten finden, der 16:37.940 --> 16:39.920 diese Sprache A auch N, B auch N akzeptiert. 16:40.780 --> 16:46.380 Wenn wir also zeigen können, dass dieses nicht B gilt für die Sprache 16:46.380 --> 16:50.620 A auch N, B auch N, dann haben wir bewiesen, dass diese Sprache nicht 16:50.620 --> 16:52.600 vom endlichen Automaten akzeptiert werden kann. 16:52.700 --> 16:53.700 So setzen wir das ein. 16:53.700 --> 16:56.040 Und genau das machen wir auf der nächsten Folie. 16:57.860 --> 17:01.880 Also, Sprache, hier noch A hoch I, B hoch I genannt jetzt, die 17:01.880 --> 17:02.760 betrachte ich jetzt. 17:03.480 --> 17:11.580 Ich nehme ein beliebiges N aus N und betrachte ein Wort, W, das in der 17:11.580 --> 17:12.460 Sprache ist. 17:13.700 --> 17:17.780 A hoch N, B hoch N ist in der Sprache, also das N ist beliebig. 17:17.780 --> 17:23.540 A hoch N, B hoch N ist ein Wort, das länger ist als dieses N. 17:24.620 --> 17:31.540 Also, es gibt ein Wort, ich suche mir ein Wort, das die ausreichend 17:31.540 --> 17:34.540 Länge hat und betrachte eine beliebige Aufteilung. 17:34.580 --> 17:38.640 Ich muss jetzt für beliebige Aufteilungen zeigen, dass ich dann eine 17:38.640 --> 17:41.740 Potenz finde von so einem Y, sodass das Wort nicht drin ist. 17:41.740 --> 17:45.940 Also, ich betrachte eine beliebige Aufteilung mit diesen beiden 17:45.940 --> 17:53.000 Eigenschaften, dass das Anfangsstück XY kürzer ist oder maximal die 17:53.000 --> 17:56.940 Länge N hat und das Stück Y nicht leer ist. 17:58.480 --> 18:02.100 Also, A hoch N, B hoch N heißt doch, ich habe hier ein solches Wort, 18:03.360 --> 18:04.340 das ist mein Wort. 18:04.340 --> 18:11.340 Hier stehen nur A's und da stehen nur B's. 18:14.100 --> 18:19.500 Na gut, jetzt sage ich, ich habe hier das XY ist kleiner gleich N. 18:20.720 --> 18:31.380 Das heißt, XY sind irgendwo kürzer, also maximal so lang, wie ich hier 18:31.380 --> 18:32.600 vorne A's stehen habe. 18:33.460 --> 18:40.700 Und das heißt doch, XY muss ein Wort sein, das nur aus A's besteht. 18:43.040 --> 18:47.980 Ich brauche ja nur ein Anfangsstück zu betrachten, das maximal die 18:47.980 --> 18:50.540 Länge N hat für dieses Wort. 18:51.220 --> 18:54.900 Irgendeine beliebige Aufteilung, aber so, dass dieses Anfangsstück XY 18:54.900 --> 18:57.060 kleiner gleich N ist in der Länge. 18:57.060 --> 18:59.020 Das heißt, da sind nur A's drin. 18:59.620 --> 19:06.400 Und wenn ich jetzt das Y mehrfach reinschreibe oder auch gar nicht 19:06.400 --> 19:13.740 reinschreibe, dann ist, also das Z ist natürlich hier der Rest, das 19:13.740 --> 19:14.200 ist Z. 19:15.880 --> 19:20.440 Dann weiß ich natürlich, wenn ich jetzt XY hoch 0Z betrachte, ich 19:20.440 --> 19:26.060 streiche einfach dieses Y raus, dann müsste es ja eigentlich drin 19:26.060 --> 19:26.320 sein. 19:26.400 --> 19:31.880 Hier in diesem Fall sehe ich, aha, das XZ enthält weniger A's als B's. 19:32.860 --> 19:37.420 Das ist A hoch N minus J gefolgt von B hoch N. 19:38.160 --> 19:40.200 Das ist nicht in L, nicht in der Sprache. 19:41.940 --> 19:49.940 Also folgt daraus nach unserer gerade gezeigten Folgerung, dass dann 19:49.940 --> 19:54.800 diese Sprache nicht von einem endlichen Automaten akzeptiert werden 19:54.800 --> 19:55.060 kann. 19:55.400 --> 20:00.980 Wir haben gezeigt, wir nehmen ein beliebiges N her, ein Wort, das 20:00.980 --> 20:05.280 mindestens diese Länge hat, konnten eine beliebige Aufteilung nehmen 20:05.280 --> 20:10.940 mit den Eigenschaften XY kleiner gleich N und Y ist nicht leer, und 20:10.940 --> 20:13.840 konnten dann zeigen, dann gibt es eine Potenz, es gibt sogar viele 20:13.840 --> 20:20.820 Potenzen, aber mindestens eine Potenz von dem Y, sodass das XY hoch IZ 20:20.820 --> 20:22.940 dann nicht in der Sprache ist. 20:23.200 --> 20:26.240 Also kann das keine Sprache sein, die von einem endlichen Automaten 20:26.240 --> 20:26.980 akzeptiert wird. 20:28.640 --> 20:34.920 Und da steht es nochmal hier fettgedruckt, so können wir das Lemma 20:34.920 --> 20:35.500 einsetzen. 20:36.740 --> 20:40.700 Das ist also eine ganz einfache Art, das werden Sie mehrfach machen 20:40.700 --> 20:43.720 für eine ganze Reihe von Sprachen in den Übungen. 20:44.700 --> 20:46.500 Das ist die Art, wie wir es einsetzen. 20:46.600 --> 20:50.500 Wir wollen für Sprachen zeigen können, dass sie nicht von einem 20:50.500 --> 20:54.380 endlichen Automaten akzeptiert werden, oder genauso können Sie es eben 20:54.380 --> 20:57.760 für andere Systeme machen, für die Sie ähnliche Strukturen zeigen, Sie 20:57.760 --> 21:01.180 können das dann so einsetzen, dass Sie zeigen können, gewisse 21:01.180 --> 21:05.560 Strukturen können nicht von dem System tatsächlich beschrieben werden. 21:07.960 --> 21:12.820 Folgerung zwei ist natürlich, es gibt mindestens eine Sprache, die ich 21:12.820 --> 21:16.340 nicht mit einem endlichen Automaten akzeptieren kann, also ist die 21:16.340 --> 21:21.240 Menge der von einem endlichen Automaten akzeptierten Sprachen eine 21:21.240 --> 21:23.380 Teilmenge der Menge aller Sprachen. 21:24.040 --> 21:28.600 Weiteres Beispiel, ich könnte also A hoch I Quadrat nehmen, 21:28.880 --> 21:32.000 irgendwelche Quadratzahlen als Potenz. 21:33.360 --> 21:36.940 Man kann sich leicht überlegen, dass wenn Sie nur Quadratzahlen als 21:36.940 --> 21:39.240 Potenzen haben, also hier eine Sprache, die sieht ja eigentlich ganz 21:39.240 --> 21:43.920 einfach aus, Sie haben nur einen Buchstaben da drin, aber dieses 21:43.920 --> 21:51.320 Pumpen hat was mit Linearität zu tun, hier haben Sie ein quadratisches 21:51.320 --> 21:53.500 Verhalten, funktioniert natürlich auch nicht. 21:53.560 --> 21:59.360 Eine andere Sprache, die haben wir im Buch übrigens mehrfach drin, das 21:59.360 --> 22:04.120 wäre die Sprache A hoch P und P Primzahl. 22:07.890 --> 22:10.490 Nur um die nochmal der Vollständigkeit halber hier aufzuschreiben. 22:10.490 --> 22:13.950 Wäre also auch so eine Sprache, von der Sie zeigen können, können Sie 22:13.950 --> 22:20.530 sich leicht überlegen, mit dem Pumping Lemma, warum eben dann auch 22:20.530 --> 22:26.550 hier diese Eigenschaft gezeigt werden kann, dass es eben keinen 22:26.550 --> 22:30.330 Automaten geben kann, der diese Sprache akzeptiert. 22:31.510 --> 22:32.710 Ist das eine Frage? 22:33.490 --> 22:38.470 Naja, es gibt einige interessante Ereignisse, die manchmal einen auch 22:38.470 --> 22:41.050 bewegen, aber heute nicht unbedingt. 22:44.870 --> 22:49.550 Also, es ist immer schon schlecht, wenn man so von Underdogs besiegt 22:49.550 --> 22:49.790 wird. 22:49.790 --> 22:57.970 Okay, das zu diesen Sprachen, also eine wichtige Erkenntnis. 22:58.650 --> 23:04.210 Und damit kommen wir, dass es nicht sprachähnlich mit Automaten ist, 23:04.410 --> 23:05.670 können Sie sich in den Übungen nochmal anschauen. 23:05.770 --> 23:07.830 Sie werden viele Sprachen in den Übungen anschauen. 23:08.370 --> 23:12.790 Das ist etwas, was auf jeden Fall auch an mehreren Stellen Ihnen 23:12.790 --> 23:17.430 nochmal begegnen wird, wenn Sie danach gefragt werden, ob Sie etwas 23:17.430 --> 23:19.190 gelernt haben in dieser Vorlesung. 23:20.010 --> 23:22.670 Ja, das ist also eine wichtige Erkenntnis. 23:23.930 --> 23:27.410 Und dann kommt das Nächste, was Ihnen auch öfter begegnen wird, was 23:27.410 --> 23:30.030 auch eine wichtige Aufgabe ist für Wirtschaftsingenieure. 23:30.450 --> 23:34.150 Ein Wirtschaftsingenieur versucht immer, Systeme möglichst 23:34.150 --> 23:35.630 kostengünstig zu bauen. 23:37.030 --> 23:40.150 Und die Frage ist, wenn ich also jetzt einen Automaten bauen soll, der 23:40.150 --> 23:44.310 eine Sprache akzeptiert, oder einen Automaten für irgendein anderes 23:44.310 --> 23:47.850 System, wie kann ich den denn möglichst kostengünstig bauen? 23:47.850 --> 23:50.630 Also alles, was ich nicht brauche, werfe ich raus. 23:50.970 --> 23:53.270 Aber woher weiß ich, was ich nicht brauche? 23:54.830 --> 23:57.110 Und das wollen wir jetzt genauer anschauen. 23:57.250 --> 23:59.990 Also die Äquivalenz und Minimierung endlicher Automaten betrachten. 24:01.450 --> 24:06.830 Also die Frage ist, gibt es einen Automaten, zu einem vorgegebenen 24:06.830 --> 24:10.850 Automaten, der dieselbe Sprache akzeptiert und mit weniger Zuständen 24:10.850 --> 24:11.270 auskommt? 24:11.350 --> 24:12.150 Warum ist das wichtig? 24:12.930 --> 24:15.010 Sie wollen ja solche Systeme bauen. 24:15.010 --> 24:18.710 Und für jede Situation, die Sie unterscheiden müssen, brauchen Sie 24:18.710 --> 24:21.650 irgendeine Möglichkeit, das im Rechner darzustellen. 24:22.170 --> 24:24.390 Wenn Sie es also mit Software machen, brauchen Sie dafür entsprechend 24:24.390 --> 24:28.930 Variablen mit einem gewissen Wertebereich. 24:29.330 --> 24:32.910 Oder wenn Sie einen Automaten in Hardware bauen, dann brauchen Sie 24:32.910 --> 24:36.250 dafür entsprechend Speicherelemente, die diese unterschiedlichen 24:36.250 --> 24:37.810 Zustände alle darstellen können. 24:38.010 --> 24:41.590 Das sind Kosten, reale Kosten in der Realisierung von Automaten. 24:42.610 --> 24:46.290 Und dann fragt man sich, kann ich sogar von gewissen Automaten zeigen, 24:46.770 --> 24:49.710 dass sie bestmöglich sind, dass es nicht besser geht. 24:50.390 --> 24:54.630 Das möchte ich natürlich am liebsten haben, dass mir nicht mein Chef 24:54.630 --> 24:59.310 sagt, hier der Automaten muss aber nochmal um die Hälfte reduziert 24:59.310 --> 24:59.730 werden. 25:00.410 --> 25:03.190 Und Sie können ihm sagen, das geht nicht, der ist bereits 25:03.190 --> 25:04.910 kleinstmöglich. 25:05.330 --> 25:06.650 Das wollen Sie nachweisen können. 25:06.950 --> 25:09.690 Und das können Sie mit gewissen Verfahren, die Sie gleich kennenlernen 25:09.690 --> 25:09.950 werden. 25:09.950 --> 25:13.250 Dann ist die Frage in diesem Fall, ist der eindeutig bestimmt? 25:14.270 --> 25:17.210 Und das ist tatsächlich der Fall. 25:17.310 --> 25:22.150 Man kann also bis auf Isomorphie, bis auf Umbenennung der Zustände, 25:22.550 --> 25:26.990 können Sie eindeutig einen sogenannten minimalen oder auch reduzierten 25:26.990 --> 25:29.370 Automaten konstruieren. 25:29.530 --> 25:31.650 Und das Verfahren dafür ist relativ einfach. 25:32.210 --> 25:34.650 Hier steht also, gibt es ein effektives, abbrechendes Verfahren. 25:34.650 --> 25:38.370 Und das hatte ich schon angedeutet, bei solchen endlichen Systemen 25:38.370 --> 25:40.950 braucht man eigentlich nur Anfangsstücke zu betrachten. 25:41.470 --> 25:44.790 Und Sie werden sehen, dass eigentlich die Eigenschaft, die man 25:44.790 --> 25:49.990 betrachtet, eine Aussage ist über alle Wörter, die ein solcher Automat 25:49.990 --> 25:50.530 akzeptiert. 25:50.590 --> 25:54.110 Sie müssen zeigen, dass alle Wörter, die ein Automat akzeptiert, auch 25:54.110 --> 25:56.450 von einem anderen Automaten akzeptiert werden können. 25:56.450 --> 25:59.990 Das ist eine Aussage über unendlich viele Wörter und trotzdem können 25:59.990 --> 26:03.090 Sie sich auf die Betrachtung endlich vieler Situationen beschränken, 26:03.430 --> 26:08.390 um tatsächlich festzustellen, welche Zustände überflüssig sind. 26:09.390 --> 26:12.430 Also zunächst mal, wann nennen wir Automaten äquivalent? 26:13.290 --> 26:14.990 Das ist naheliegend, das so zu machen. 26:15.250 --> 26:19.230 Wir haben zwei endliche Automaten mit demselben Eingabealphabet und 26:19.230 --> 26:24.450 die nennen wir äquivalent, wenn die beiden Automaten die gleiche 26:24.450 --> 26:30.170 Sprache enthalten oder die gleiche Sprache charakterisieren. 26:30.470 --> 26:34.070 L von A1 ist L von A2, dann sind sie äquivalent. 26:35.050 --> 26:36.810 Das ist naheliegend, das so zu machen. 26:37.130 --> 26:40.450 Ist eine Äquivalenzrelation, ist natürlich reflexiv, ist transitiv, 26:41.250 --> 26:47.470 symmetrisch, kann man sofort einsehen, dass das der Fall ist, dann 26:47.470 --> 26:48.970 sind Automaten äquivalent. 26:51.290 --> 26:53.330 Also ist eine Äquivalenzrelation. 26:54.210 --> 26:58.050 Und jetzt schauen wir, wie wir also unsere Automaten kleiner machen 26:58.050 --> 26:58.390 können. 26:58.730 --> 27:02.050 Das erste ist, dass wir uns überlegen, wir brauchen natürlich nur 27:02.050 --> 27:03.510 solche Zustände zu betrachten. 27:03.610 --> 27:05.170 Also schauen Sie sich mal hier einen Automaten an. 27:05.570 --> 27:06.730 Ich male hier mal einen auf. 27:06.850 --> 27:13.710 Der hat hier also irgendwelche schönen Zustände, die man erreichen 27:13.710 --> 27:14.170 kann. 27:14.730 --> 27:18.030 Und hier haben wir noch einen Zustand, von dem wir da und da 27:18.030 --> 27:18.530 hinkommen. 27:18.770 --> 27:22.970 Und das ist meinetwegen ein Endzustand und hier vielleicht noch 27:22.970 --> 27:25.230 irgendein Endzustand und sowas. 27:26.250 --> 27:31.210 Und jetzt überlegt man sich, ist das eigentlich sinnvoll, den 27:31.210 --> 27:32.630 Automaten so zu betrachten? 27:33.890 --> 27:38.490 Was war denn das Wesentliche, um festzustellen, dass ein Wort von 27:38.490 --> 27:40.290 einem Automaten akzeptiert wird? 27:40.290 --> 27:47.410 Das Wesentliche ist doch, kann ich bei Eingabe dieses Wortes in den 27:47.410 --> 27:52.170 Automaten, der sich im Anfangszustand befindet, sukzessive durch 27:52.170 --> 27:56.330 Einlesen der einzelnen Zeichen des Wortes zu einem Zustand kommen, am 27:56.330 --> 27:58.390 Ende, der ein Endzustand ist. 27:59.110 --> 28:03.230 Das heißt, ich starte immer hier, bei diesem Anfangszustand, der mit 28:03.230 --> 28:04.850 diesem Pfeil gekennzeichnet ist. 28:06.730 --> 28:09.610 Das heißt, ich brauche eigentlich nur die Zustände zu betrachten, die 28:09.610 --> 28:11.590 ich von diesem Anfangszustand aus erreiche. 28:12.250 --> 28:16.570 Also diesen Zustand hier, den kann ich getrost wegstreichen. 28:17.290 --> 28:18.930 Den kann ich ja gar nicht erreichen. 28:19.570 --> 28:23.830 Genauso diesen Zustand kann ich auch nicht erreichen, von dem 28:23.830 --> 28:25.070 Anfangszustand aus. 28:25.370 --> 28:26.490 Die brauche ich gar nicht. 28:27.030 --> 28:30.830 Wenn ich die beiden wegstreiche, ändert sich das 28:30.830 --> 28:33.630 Akzeptierungsverhalten meines Automaten nicht. 28:33.630 --> 28:35.750 Und nur das interessiert mich. 28:37.070 --> 28:39.070 Das ist ja für die Äquivalenz von Automaten relevant. 28:39.890 --> 28:43.910 Also, wenn ich einen Automaten finden möchte, der die gleiche Sprache 28:43.910 --> 28:47.170 akzeptiert, streiche ich erstmal alles raus, was ich nicht erreichen 28:47.170 --> 28:47.570 kann. 28:48.810 --> 28:52.630 Dann habe ich einen Automaten, den wir vereinfachten Automaten nennen, 28:53.210 --> 28:57.250 bei dem alles rausgestrichen ist, was nicht erreichbar ist, vom 28:57.250 --> 28:58.450 Anfangszustand aus. 28:59.170 --> 29:03.310 Und wir können natürlich auch die Endzustände rausschmeißen, die nicht 29:03.310 --> 29:04.950 vom Anfangszustand aus erreichbar sind. 29:05.010 --> 29:06.650 Das hatte ich hier dargestellt. 29:07.410 --> 29:11.970 Und damit haben wir dann einen Automaten, der vereinfacht ist und eben 29:11.970 --> 29:15.910 nur noch das enthält, was relevant ist für das Betrachten der 29:15.910 --> 29:17.270 Äquivalenz von Automaten. 29:17.630 --> 29:20.950 Nämlich nur das, was ich vom Anfangszustand aus erreichen kann und 29:20.950 --> 29:22.410 alles andere ist weg. 29:23.810 --> 29:28.950 Und der Automat selbst heißt also vereinfacht, falls er bereits gleich 29:28.950 --> 29:33.090 dem vereinfachten Automaten ist, wenn also alle Zustände erreichbar 29:33.090 --> 29:33.390 sind. 29:33.550 --> 29:34.550 Das ist der erste Schritt. 29:35.570 --> 29:38.470 Das ist noch ganz einfach, das alles rauszuwerfen. 29:38.870 --> 29:45.710 Und jetzt müssen wir betrachten, sind irgendwelche Zustände in dem 29:45.710 --> 29:56.530 Sinne unnötig, dass egal, von welchem Zustand ich starte, ich immer 29:56.530 --> 29:59.370 auf die gleiche Situation komme. 30:00.130 --> 30:01.370 Das schauen wir uns gleich an. 30:02.930 --> 30:06.610 Das ist erstmal die Betrachtung hier mit dem vereinfachten Automaten. 30:11.230 --> 30:16.290 Wenn wir den vereinfachten Automaten aus Strich betrachten, dass dann 30:16.290 --> 30:20.230 natürlich das S0 erreichbar ist und das A und A' äquivalent sind. 30:20.570 --> 30:22.530 Ich glaube, das ist eine Aussage, die brauchen wir nicht extra zu 30:22.530 --> 30:22.950 beweisen. 30:23.550 --> 30:26.430 Das ist offensichtlich, der Beweis steht ja sogar nochmal drin. 30:27.030 --> 30:28.550 Dass S0 erreichbar ist, ist klar. 30:28.630 --> 30:33.210 Die Definition war, dass es ein Wort gibt, sodass ich vom 30:33.210 --> 30:35.730 Anfangszustand aus diesen Zustand erreichen kann. 30:36.370 --> 30:39.530 Es gibt ein Wort, sodass ich vom Anfangszustand aus den Anfangszustand 30:39.530 --> 30:41.410 erreichen kann, nämlich das leere Wort. 30:42.470 --> 30:47.910 Und das andere, dass die äquivalent sind, ist eben klar, weil nicht 30:47.910 --> 30:51.990 erreichbare Zustände nicht für das Akzeptieren benötigt werden. 30:52.390 --> 30:54.190 Also sind die äquivalent. 30:54.950 --> 30:58.210 Und jetzt haben wir uns zunächst einmal mit der Äquivalenz von 30:58.210 --> 31:00.010 Automaten ganz kurz beschäftigt. 31:00.270 --> 31:03.430 Der vereinfachte und der Originalautomat sind äquivalent. 31:03.990 --> 31:07.150 Und jetzt wollen wir die Äquivalenz von Zuständen betrachten. 31:07.770 --> 31:13.170 Wir haben also zwei Zustände, betrachten zwei Zustände und betrachten 31:13.170 --> 31:21.170 ein Wort, das uns irgendwie zu, oder irgendwelche Wörter, die uns 31:21.170 --> 31:23.730 irgendwie zu einem Folgezustand führen. 31:24.570 --> 31:28.450 Hier meinetwegen im Automaten A und da im Automaten A'. 31:29.390 --> 31:32.190 Wir starten in irgendeinem Zustand. 31:33.110 --> 31:34.490 Das hier ist also S. 31:35.330 --> 31:36.750 Das hier ist S'. 31:38.130 --> 31:43.290 Und wenn jetzt für jedes Wort folgendes gilt. 31:48.170 --> 31:51.650 Hier steht jetzt nicht für jedes Wort, sondern zunächst mal für jedes 31:51.650 --> 31:53.350 Wort bis zu einer gewissen Länge K. 31:54.350 --> 31:56.650 Also wie habe maximal K Zeichen. 31:56.650 --> 32:02.630 Wenn das für jedes solche Wort der Länge maximal K zu Zuständen führt, 32:03.210 --> 32:12.170 die entweder beide Endzustände sind oder beide keine Endzustände, dann 32:12.170 --> 32:16.210 kann ich ja deren Verhalten in Bezug auf das Akzeptieren von Wörtern 32:16.210 --> 32:17.730 nicht unterscheiden. 32:17.730 --> 32:22.890 Weil egal, in welchem ich starte, für dieses Wort, das ich hier 32:22.890 --> 32:26.070 betrachte, oder in dem Fall für alle Wörter bis zur Länge kleiner 32:26.070 --> 32:31.710 gleich K, werden entweder Akzeptierungsentscheidungen getroffen, 32:31.970 --> 32:34.770 positive, oder in beiden Fällen negative. 32:35.910 --> 32:40.450 Das heißt, ich kann die beiden nicht unterscheiden bei Wörtern bis zur 32:40.450 --> 32:40.990 Länge K. 32:41.110 --> 32:43.750 Da nennen wir die Zustände K-Äquivalent. 32:43.750 --> 32:47.890 Und wenn das für beliebige Wörter gilt, beliebiger Länge, dann nennen 32:47.890 --> 32:48.890 wir sie Äquivalent. 32:49.190 --> 32:53.430 Wenn also für alle K die Zustände K-Äquivalent sind. 32:53.530 --> 33:00.250 Das heißt, für beliebige Wörter ist das Verhalten des Automaten in 33:00.250 --> 33:03.390 Bezug auf das, was mich nach außen interessiert, nämlich das 33:03.390 --> 33:06.250 Akzeptierungsverhalten, nicht unterscheidbar. 33:07.130 --> 33:08.370 Dann sind sie Äquivalent. 33:09.250 --> 33:13.430 Das heißt, ob ich den einen oder anderen nehme, interessiert mich 33:13.430 --> 33:13.710 nicht. 33:14.370 --> 33:17.650 Und jetzt betrachte ich das Ganze nicht in zwei verschiedenen 33:17.650 --> 33:22.290 Automaten, sondern innerhalb eines Automaten, schaue ich mir zwei 33:22.290 --> 33:26.130 Zustände innerhalb eines Automaten an und schaue mir an, was bei 33:26.130 --> 33:31.030 diesen Wörtern passiert, bis zur Länge K oder auch dann beliebiger 33:31.030 --> 33:31.330 Länge. 33:31.330 --> 33:37.010 Und wenn ich von denen aus immer zu einem Endzustand komme oder gerade 33:37.010 --> 33:39.950 nicht, dann sind sie Äquivalent. 33:40.130 --> 33:43.010 Und genau das müssen wir uns genauer anschauen, denn solche 33:43.010 --> 33:48.650 Äquivalenten -Zustände, die können wir eigentlich zusammenfassen zu 33:48.650 --> 33:49.010 einem. 33:49.310 --> 33:51.690 Ist ja egal, ob ich den einen oder anderen nehme, dann kann ich den 33:51.690 --> 33:52.950 einen von denen auch wegstreichen. 33:55.710 --> 33:58.770 Ich kann es also anwenden auf die Zustände eines Automaten. 33:58.770 --> 34:01.370 Und jetzt schauen wir uns ein bisschen Eigenschaften an. 34:01.950 --> 34:05.870 Die brauchen wir gleich noch, um zu einem Verfahren zu kommen, mit dem 34:05.870 --> 34:10.810 wir systematisch feststellen können, welche Zustände K-Äquivalent oder 34:10.810 --> 34:11.710 auch Äquivalent sind. 34:14.170 --> 34:20.110 Also, wir haben zwei Zustände S und S' und die sind Null-Äquivalent. 34:22.790 --> 34:24.470 Wann sind die Null-Äquivalent? 34:26.250 --> 34:30.170 Null-Äquivalent müssen die sein, das war ja K-Äquivalent, das war so, 34:30.270 --> 34:33.510 dass alle Wörter bis zur Länge K, für alle Wörter bis zur Länge K, 34:33.750 --> 34:41.690 musste gelten, dass sie beim Eingeben des Wortes W im Zustand S oder 34:41.690 --> 34:45.910 Zustand S', beide auf einen Endzustand oder beide nicht auf einen 34:45.910 --> 34:46.770 Endzustand führen. 34:47.870 --> 34:50.970 Wenn ich hier die Null-Äquivalent betrachte, kann ich ja nur das leere 34:50.970 --> 34:51.850 Wort eingeben. 34:53.090 --> 35:00.850 Und Delta von S, Lambda ist natürlich gerade gleich S, Delta Strich 35:00.850 --> 35:05.430 von S Strich, Lambda ist auch gleich S Strich, also muss dann gelten, 35:05.610 --> 35:11.490 dass entweder beide S und S Strich Endzustände sind, oder beide keine 35:11.490 --> 35:12.230 Endzustände. 35:14.230 --> 35:21.030 Nochmal zur vorigen Folie, hier stand ja, Delta SW ist aus F, genau 35:21.030 --> 35:23.790 dann, wenn Delta Strich von S Strich W aus F Strich ist. 35:25.110 --> 35:30.010 Also, genau das steht hier, beide sind Endzustände oder beide sind 35:30.010 --> 35:30.970 keine Endzustände. 35:31.050 --> 35:32.230 Das ist ja sehr einfach. 35:33.530 --> 35:35.070 Nächste Aussage, B und C. 35:36.570 --> 35:38.090 Wann sind die K-Äquivalent? 35:39.970 --> 35:44.210 Wir hatten gesehen, die sind K-Äquivalent, wenn die Zustände, die ich 35:44.210 --> 35:49.630 erreiche, also wenn Delta von SW und Delta Strich von S Strich W 35:49.630 --> 35:52.530 beides Endzustände sind, oder beides keine. 35:53.990 --> 36:01.350 Und jetzt verwende ich die Aussage A, und sage, die sind also K 36:01.350 --> 36:06.030 -Äquivalent, genau dann, wenn die Zustände, die ich erreiche, bei 36:06.030 --> 36:11.610 Eingabe von W, ausgehend von S oder S Strich, Null-Äquivalent sind. 36:12.450 --> 36:16.770 Jetzt werden Sie sagen, ist das eine umständliche Formulierung dessen, 36:16.830 --> 36:18.830 was wir gerade vorgesagt haben. 36:19.270 --> 36:23.030 Hier oben steht ja nur Null-Äquivalent, naja, S und S Strich sind 36:23.030 --> 36:25.830 jeweils Endzustände, oder beides keine Endzustände. 36:26.130 --> 36:29.610 Das ist ja nur nochmal die Aussage etwas anders formuliert, jetzt für 36:29.610 --> 36:30.770 K -Äquivalent. 36:32.130 --> 36:36.170 Und natürlich, wenn S Null-Äquivalent zu S Null Strich ist, wenn die 36:36.170 --> 36:40.350 beiden Anfangszustände der beiden Automaten A und A Strich-Äquivalent 36:40.350 --> 36:47.030 sind, dann haben wir ja gerade die Aussage, dass für jedes Wort W, 36:48.830 --> 36:53.350 Delta von S Null W ein Endzustand ist, genau dann, wenn Delta Strich 36:53.350 --> 36:56.550 von S Null Strich, W ein Endzustand ist. 36:56.550 --> 37:02.270 Das heißt, die beiden Sprachen sind gleich, die beiden Automaten sind 37:02.270 --> 37:02.830 äquivalent. 37:03.830 --> 37:07.570 Das ist also sehr einfach einzusehen und dann sind das 37:07.570 --> 37:11.970 Äquivalenzrelationen, das ist also wirklich sehr einfach einzusehen 37:11.970 --> 37:19.830 und wir betrachten im Folgen also wirklich nur noch die Äquivalenz von 37:19.830 --> 37:24.910 Zuständen innerhalb eines Automaten und werden sehen, was wir damit 37:24.910 --> 37:25.990 jetzt weitermachen können. 37:26.550 --> 37:30.850 Wir wollen gerne unsere Automaten oder die Unterzustandsmenge eines 37:30.850 --> 37:35.270 Automaten, das ist unsere Zustandsmenge eines Automaten, die wollen 37:35.270 --> 37:40.210 wir gerne unterteilen in Mengen äquivalenter Zustände. 37:43.260 --> 37:47.840 Wie können wir die jetzt einteilen in Äquivalenzklassen? 37:47.840 --> 37:52.440 Diejenigen, die meinetwegen Nulläquivalent sind, 37:55.620 --> 38:00.100 Nulläquivalent, das steht hier oben, die sind Nulläquivalent, wenn sie 38:00.100 --> 38:01.880 beide Endzustände sind. 38:02.560 --> 38:10.020 Also, wenn ich hier die Menge meiner Endzustände habe, F, dann sind 38:10.020 --> 38:15.520 die alle Nulläquivalent und die, die nicht Endzustände sind, sind auch 38:15.520 --> 38:16.400 Nulläquivalent. 38:17.840 --> 38:20.140 Das heißt, das wäre die erste Aufteilung, die wir machen können 38:20.140 --> 38:21.400 bezüglich Nulläquivalenz. 38:24.390 --> 38:27.650 Und jetzt wollen wir die aufteilen in Bezug auf 1-Äquivalenz. 38:28.390 --> 38:32.730 Dann wird das so sein, dass wir irgendwie hier eine weitere Aufteilung 38:32.730 --> 38:33.750 hinbekommen werden. 38:35.710 --> 38:38.930 Und dann vielleicht noch eine Aufteilung, wenn wir 2-Äquivalenz 38:38.930 --> 38:42.750 betrachten und 3-Äquivalenz und 4-Äquivalenz usw. 38:43.590 --> 38:49.030 Wir werden also unsere Zustandsmenge immer feiner aufteilen, bis wir 38:49.030 --> 38:53.570 am Ende wissen, wie sehen die Klassen der äquivalenten Zustände aus. 38:56.030 --> 39:01.770 Und ich möchte also für jeden Zustand die Menge aller Zustände kennen, 39:01.890 --> 39:03.370 mit denen er äquivalent ist. 39:04.170 --> 39:07.270 Und wenn wir das sukzessive machen, erst die Nulläquivalenten 39:07.270 --> 39:10.530 betrachten, dann die 1-Äquivalenten, dann die 2-Äquivalenten, dann 39:10.530 --> 39:13.370 haben wir sukzessive eine immer feinere Zerlegung unserer 39:13.370 --> 39:14.170 Zustandsmenge. 39:15.090 --> 39:21.750 Und diese nennen wir Pi für Partitionierung unserer Zustandsmenge. 39:23.130 --> 39:28.530 Und das Pi-K ist dann die Zerlegung bezüglich der K-Äquivalenz. 39:30.830 --> 39:36.150 Damit haben wir diese Aufteilung definiert und jetzt ist es natürlich 39:36.150 --> 39:46.370 klar, dass für jedes K diese Zerlegung in die Mengen äquivalenter 39:46.370 --> 39:54.270 Zustände eine feinere Zerlegung ist, als die Partitionierung 39:54.270 --> 39:56.090 prinzipiell irgendeines Ks. 39:56.910 --> 39:59.970 Wir werden das immer kleiner, immer feiner machen. 39:59.970 --> 40:05.770 Das heißt, wenn wir irgendeine K-Äquivalenz betrachten, dann sind 40:05.770 --> 40:13.870 natürlich mindestens so viele K-Äquivalent wie Äquivalent sind. 40:15.750 --> 40:21.590 Es wird aber K-Äquivalente geben, die nicht K plus 1-Äquivalent sind, 40:22.610 --> 40:27.250 deren Verhalten Sie unterscheiden können, wenn Sie längere Wörter 40:27.250 --> 40:27.850 betrachten. 40:28.530 --> 40:32.170 Nur diejenigen, die für jedes Wort dann das gleiche Verhalten zeigen, 40:32.310 --> 40:33.450 sind nachher Äquivalent. 40:36.110 --> 40:40.030 Und natürlich ist hier, wenn Sie K1 kleiner gleich K2, wenn Sie 40:40.030 --> 40:43.290 längere Wörter betrachten, dann wird die Einteilung feiner. 40:43.570 --> 40:45.550 Auch das ist sehr einfach einzusehen. 40:45.590 --> 40:47.790 Das habe ich eigentlich gerade bei diesem Bild, das ich gemacht hatte, 40:48.270 --> 40:48.910 angedeutet. 40:49.810 --> 40:53.050 Das Beweis ist hier wirklich offensichtlich, das ist sehr einfache 40:53.050 --> 40:54.210 Mathematik. 40:54.970 --> 41:00.470 Und dann haben wir hier noch einen Satz, und der ist jetzt, gehen wir 41:00.470 --> 41:07.650 an die Animation zurück, für alle Zustände S1 und S2 und für jedes K 41:07.650 --> 41:09.910 aus N0 gilt jetzt folgendes. 41:11.470 --> 41:20.790 Wenn, oder nicht wenn, S1 und S2 sind, dieser elende Strich, der hier 41:20.790 --> 41:33.710 immer entsteht, also S1 und S2 sind K plus 1 Äquivalent, wenn, genau 41:33.710 --> 41:38.810 dann wenn, die beiden Nulläquivalent sind, das müssen sie ja 41:38.810 --> 41:48.330 mindestens sein, und für jeden Folgezustand von S1 oder von S2, das 41:48.330 --> 41:57.970 heißt, wir haben hier unsere beiden Zustände, S1 und S2, und wir 41:57.970 --> 42:02.570 betrachten irgendeinen Folgezustand, den wir mit irgendeinem E 42:02.570 --> 42:10.510 erreichen können, das ist unser Delta S1 E und Delta S2 E, wir 42:10.510 --> 42:15.810 betrachten jetzt diese beiden Zustände, dann müssen die beiden K 42:15.810 --> 42:19.770 -Äquivalent sein, also die beiden Zustände S1 und S2 sind 42:19.770 --> 42:26.010 Nulläquivalent, und für alle Folgezustände wissen wir, die sind K 42:26.010 --> 42:30.690 -Äquivalent, dann sind die beiden Zustände S1 und S2 K plus 1 42:30.690 --> 42:31.410 Äquivalent. 42:32.330 --> 42:35.650 Das ist eine wichtige Erkenntnis, die wir auch beweisen müssen. 42:37.210 --> 42:43.130 Also, wenn S1 und S2 K plus 1 Äquivalent sind, dann heißt das doch, 42:44.330 --> 42:53.950 für jedes Wort der Länge maximal K plus 1 sind die beiden erreichten 42:53.950 --> 42:58.870 Folgezustände, entweder beide aus F oder beide nicht aus F, oder wir 42:58.870 --> 43:02.010 hatten das vorhin gerade gesehen, ich kann auch sagen, die erreichten 43:02.010 --> 43:07.890 Folgezustände bei Eingabe des Wortes V sind beide Nulläquivalent. 43:09.050 --> 43:11.230 Das hatten wir gerade auf der vorigen Folie gesehen. 43:11.730 --> 43:12.970 Das war diese Erkenntnis. 43:14.750 --> 43:24.220 Und das heißt, das gilt ja für alle Wörter bis zur Länge K plus 1, 43:24.300 --> 43:26.060 gilt also auch für das leere Wort. 43:27.480 --> 43:32.820 Wenn das für das leere Wort gilt, heißt das S1, also von S1 und S2 43:32.820 --> 43:39.300 erreiche ich mit dem leeren Wort gerade S1 und S2, das heißt, S1 und 43:39.300 --> 43:46.360 S2 sind Nulläquivalent, das ist die Aussage für das leere Wort. 43:47.640 --> 43:53.360 Und für alle nicht leeren Wörter, die also mindestens ein Zeichen 43:53.360 --> 44:02.980 enthalten, weiß ich, dass Delta S1 EU Nulläquivalent zu Delta... 44:03.900 --> 44:07.400 Ach, das wollte ich jetzt gar nicht. 44:07.980 --> 44:09.200 Was habe ich denn jetzt gemacht? 44:10.160 --> 44:10.900 Da wollte ich hin. 44:11.800 --> 44:20.920 Ich wollte hier oben mit dem Radierer das hier wegstreichen. 44:23.280 --> 44:24.320 So, nochmal. 44:25.460 --> 44:28.800 Die beiden Folgezustände sind dann Nulläquivalent. 44:28.860 --> 44:30.360 Das ist das, was hier oben drüber stand. 44:31.320 --> 44:34.080 Das sind die nicht leeren Wörter, die haben mindestens ein Zeichen 44:34.080 --> 44:34.480 vorne. 44:35.280 --> 44:40.500 Und wenn ich mir jetzt das anschaue, Delta S1 EU Nulläquivalent Delta 44:40.500 --> 44:45.600 S2 EU, dann kann ich natürlich, ich weiß ja, dass ich das aufteilen 44:45.600 --> 44:51.520 kann, ich kann zunächst mal den Folgezustand von S1 bei Eingabe von E 44:51.520 --> 44:55.820 betrachten und den Folgezustand von S2 bei Eingabe von E. 44:56.360 --> 44:59.880 Danach muss ich noch U eingeben, dann sind die Nulläquivalent. 45:02.180 --> 45:06.440 Aber wenn ich mir das jetzt betrachte, dann ist das doch gerade die 45:06.440 --> 45:12.740 Aussage, das was hier steht, dass die beiden Folgezustände K 45:12.740 --> 45:13.500 -Äquivalent sind. 45:14.520 --> 45:17.940 Das hatten wir gerade uns überlegt, dass diese Aussage, das gilt hier 45:17.940 --> 45:22.780 für alle Wörter U, die Wörter U sind Wörter bis zur Länge K, also sind 45:22.780 --> 45:28.400 die beiden Folgezustände Delta S1 EU und Delta S2 EU K-Äquivalent. 45:28.900 --> 45:31.460 Und damit haben wir genau die Aussage, die hier oben stand. 45:32.120 --> 45:38.260 Zwei Zustände sind S1 und S2 sind K plus 1 Äquivalent, wenn sie 45:38.260 --> 45:43.680 Nulläquivalent sind und für alle Folgezustände gilt, dass sie K 45:43.680 --> 45:44.440 -Äquivalent sind. 45:45.500 --> 45:47.640 Was haben wir davon, von dieser Aussage? 45:47.700 --> 45:48.840 Sieht sehr formal aus. 45:49.360 --> 45:52.880 Wir nähern uns jetzt dem Verfahren, das wir anwenden wollen, um 45:52.880 --> 45:55.260 festzustellen, welche Zustände Äquivalent sind. 45:56.200 --> 46:00.380 Wir können nämlich diese Aussage mal wieder umkehren. 46:01.480 --> 46:11.320 Hier oben steht A-Äquivalent B und hier unten schreibe ich hin, nicht 46:11.320 --> 46:15.540 A -Äquivalent nicht B. 46:16.380 --> 46:17.580 Was steht hier unten? 46:20.480 --> 46:22.520 Hier steht es andersrum. 46:22.520 --> 46:30.540 Damit es genau passt zueinander, muss ich das anders aufschreiben. 46:34.160 --> 46:35.280 Was steht hier unten? 46:35.840 --> 46:42.380 Hier steht jetzt erstmal nicht B-Äquivalent nicht A. 46:42.840 --> 46:47.220 A war die Aussage, S1 ist K plus 1 Äquivalent zu S2. 46:47.220 --> 46:53.800 Hier unten steht nicht A, S1 nicht K plus 1 Äquivalent S2. 46:55.020 --> 46:56.920 Und vorne steht nicht B. 46:57.840 --> 47:02.840 B war die Aussage, S1 ist Null-Äquivalent zu S2 und für jeden 47:02.840 --> 47:07.860 Folgezustand sind also die Folgezustände K-Äquivalent. 47:07.940 --> 47:16.380 Und hier steht S1 ist nicht Null-Äquivalent zu S2 oder es gibt ein 47:16.380 --> 47:22.740 Folgezustand, also es gibt ein Zeichen E, sodass die Folgezustände 47:22.740 --> 47:27.740 Delta S1 E und Delta S2 E nicht K-Äquivalent sind. 47:28.440 --> 47:30.180 Das ist die Aussage nicht B. 47:31.680 --> 47:36.480 Das heißt, genau das Korollar ergibt sich durch Kontraposition dieser 47:36.480 --> 47:37.920 Aussage des Satzes. 47:38.860 --> 47:40.440 Und warum ist das interessant? 47:41.340 --> 47:44.160 Weil ich jetzt Folgendes machen kann. 47:44.560 --> 47:52.200 Ich möchte feststellen, welche Zustände sind nicht Null-Äquivalent. 47:52.940 --> 47:54.420 Das weiß ich ja sofort. 47:55.100 --> 48:01.000 Das sind diejenigen, der eine muss Endzustand sein, der andere nicht 48:01.000 --> 48:01.680 Endzustand. 48:01.940 --> 48:03.620 Dann sind sie nicht Null-Äquivalent. 48:05.940 --> 48:08.200 Wann sind sie nicht Eins-Äquivalent? 48:09.080 --> 48:13.860 Entweder sind sie nicht Null-Äquivalent, das steht hier, oder ich 48:13.860 --> 48:17.500 betrachte die Folgezustände und die dürfen dann nicht Null-Äquivalent 48:17.500 --> 48:17.840 sein. 48:18.320 --> 48:21.700 Oder zumindest muss ich Folgezustände finden können, die nicht Null 48:21.700 --> 48:22.520 -Äquivalent sind. 48:23.680 --> 48:26.940 Dann habe ich alle diejenigen, die nicht Eins-Äquivalent sind. 48:28.100 --> 48:29.060 Jetzt gehe ich weiter. 48:29.680 --> 48:33.220 Ich suche diejenigen, die nicht Zwei-Äquivalent sind, indem ich 48:33.220 --> 48:37.280 einfach schaue, sind sie nicht Null-Äquivalent. 48:37.640 --> 48:43.560 Oder gibt es einen Folgezustand, sodass die Folgezustände nicht Eins 48:43.560 --> 48:44.340 -Äquivalent sind. 48:45.080 --> 48:49.860 Und so hangeln wir uns sukzessive hoch, indem wir immer mehr zeigen, 48:50.000 --> 48:53.120 es gibt Zustände, die sind nicht Null-Äquivalent, nicht Eins 48:53.120 --> 48:55.160 -Äquivalent, nicht Zwei-Äquivalent und so weiter. 48:55.600 --> 48:59.860 Und dann wissen wir, die sind dann entsprechend auch nicht K plus Eins 48:59.860 --> 49:00.160 -Äquivalent. 49:00.920 --> 49:02.940 Und genau das wenden wir jetzt also an. 49:03.040 --> 49:07.860 Das ist hier die Grundlage für das Verfahren, das wir einsetzen, um 49:07.860 --> 49:12.560 festzustellen, ob Zustände Äquivalent sind am Ende. 49:14.160 --> 49:18.360 Also, es gibt noch vorher einen weiteren Satz, der ist wirklich sehr 49:18.360 --> 49:18.860 einfach. 49:19.840 --> 49:26.060 Der sagt folgendes aus, für alle K aus N-Null, wenn wir irgendwann 49:26.060 --> 49:31.560 hier bei dem Übergang von K-Äquivalent zu K plus Eins-Äquivalent keine 49:31.560 --> 49:34.480 Veränderung mehr haben, dann sind wir fertig. 49:36.940 --> 49:40.880 Dann kann es nicht sein, dass es noch weitere Unterteilungen gibt für 49:40.880 --> 49:41.660 größeres K. 49:44.740 --> 49:51.640 Und wenn das S also maximal N Zustände hat, dann wissen wir auch, dass 49:51.640 --> 49:57.380 wir spätestens, wenn wir N-1-Äquivalenz betrachtet haben, fertig sind, 49:57.980 --> 50:00.000 kann man sich auch leicht überlegen. 50:00.540 --> 50:01.900 Hier gibt es aber noch eine Frage. 50:03.100 --> 50:10.400 Was bedeutet das Zeichen zwischen Pi und Pi-K? 50:13.300 --> 50:15.280 Was meinen Sie denn jetzt? 50:16.020 --> 50:18.320 Die Frage verstehe ich überhaupt nicht. 50:18.320 --> 50:21.380 Beim Lexmark? 50:22.560 --> 50:24.240 Also, die Frage verstehe ich nicht. 50:24.920 --> 50:26.480 Auf welche Folie beziehen Sie sich? 50:26.600 --> 50:30.060 Auf die Folie davor, wer hat die Frage gestellt? 50:30.460 --> 50:32.240 Also, ich verstehe Sie nicht. 50:36.480 --> 50:37.560 Sie meinten... 50:37.560 --> 50:39.280 Ich gehe nochmal kurz hier zurück. 50:41.980 --> 50:43.840 Hier habe ich... 50:46.360 --> 50:49.300 Ich weiß nicht, worauf Sie sich hier beziehen könnten. 50:49.300 --> 50:52.500 Müssen Sie Ihre Frage nochmal anders formulieren, dann kann ich darauf 50:52.500 --> 50:53.640 eingehen. 50:54.360 --> 50:58.700 Also, das ist dieser kleine Satz. 51:00.480 --> 51:05.520 Diese erste Aussage, wenn wir die beweisen wollen, wenn also zwei 51:05.520 --> 51:11.040 Zustände K-Äquivalent sind, dann wissen wir, das ist genau dann der 51:11.040 --> 51:15.060 Fall, wenn die Folgezustände dann Null-Äquivalent sind, bei Eingabe an 51:15.060 --> 51:16.440 Wörter in der Länge maximal K. 51:17.320 --> 51:24.500 Und wenn wir jetzt, also die Behauptung ist, wenn wir für K und K plus 51:24.500 --> 51:31.460 1 keinen Unterschied festgestellt haben, dann gilt für jedes größere J 51:31.460 --> 51:37.000 auch, dass PJ identisch ist zu PJ plus 1. 51:37.320 --> 51:39.500 Das heißt, danach gibt es auch keine Unterscheidungen mehr. 51:40.240 --> 51:42.080 Machen wir einfach einen Induktionsbeweis. 51:42.160 --> 51:43.760 Sie wissen, wie Induktionsbeweise gehen. 51:43.760 --> 51:47.100 Man macht eine Aussage für den Induktionsanfang. 51:47.620 --> 51:53.640 Der Induktionsanfang wäre J gleich K in dem Fall. 51:54.420 --> 51:56.260 Dafür gilt es nach Voraussetzung. 51:56.980 --> 52:01.080 Und dann betrachten wir die Aussage für J plus... 52:01.080 --> 52:02.700 Also, wir müssen von J auf J plus 1 schließen. 52:02.900 --> 52:09.260 Also, wir schauen uns an die J plus 1-Äquivalenz und müssen zeigen, 52:09.420 --> 52:14.880 dass die dann gleich der J-Äquivalenz ist, also die J plus 1 52:14.880 --> 52:19.000 -Äquivalenz ist gleich der J plus 2-Äquivalenz. 52:19.240 --> 52:22.320 Dann wissen wir, dass das für alle gilt. 52:22.900 --> 52:29.120 Also, J plus 1-Äquivalenz von zwei Zuständen gilt, wenn Sie für alle 52:29.120 --> 52:34.940 Wörter der Länge kleiner gleich J plus 1 zu Folgezuständen führen, die 52:34.940 --> 52:37.400 null -Äquivalent sind. 52:37.860 --> 52:39.380 Das können wir wieder aufspalten. 52:40.020 --> 52:45.600 Dann haben wir für jedes, wenn wir irgendein Zeichen betrachten und 52:45.600 --> 52:55.220 darauf irgendein weiteres Wort der Länge maximal J betrachten, dann 52:55.220 --> 53:03.340 folgt daraus, dass also S null-Äquivalent zu S-Strich ist und außerdem 53:03.340 --> 53:08.420 Delta von SEW null-Äquivalent zu Delta S-Strich EW. 53:08.420 --> 53:11.340 Was habe ich hier gemacht bei diesem Schritt? 53:11.840 --> 53:16.100 Ich habe nur diese Aussage, die für alle Wörter aus E-Stern formuliert 53:16.100 --> 53:22.820 war, aufgeteilt auf die Wörter, die eine nicht leere Länge haben und 53:22.820 --> 53:23.680 das leere Wort. 53:25.640 --> 53:29.820 Und das leere Wort, das ist die Aussage hier, S null-Äquivalent S 53:29.820 --> 53:35.380 -Strich und das sind die nicht leeren Wörter der Länge J plus 1, das 53:35.380 --> 53:39.480 beginne mit einem Zeichen und werden gefolgt von einem Wort der Länge 53:39.480 --> 53:39.800 J. 53:41.400 --> 53:46.520 Und wenn ich jetzt mir das rausziehe, kann ich sagen, das ist S null 53:46.520 --> 53:54.560 -Äquivalent zu S-Strich und Delta von SE ist J-Äquivalent zu Delta von 53:54.560 --> 53:55.360 S -Strich E. 53:56.520 --> 53:59.100 Das ist das, was wir hier oben stehen haben. 53:59.100 --> 54:03.920 Und wenn das der Fall ist, dann setze ich jetzt unsere 54:03.920 --> 54:07.080 Induktionsannahme ein, Induktionsvoraussetzung. 54:07.740 --> 54:11.380 Ich weiß, für J gilt die Aussage bereits, für J plus 1 soll sie jetzt 54:11.380 --> 54:12.020 auch gelten. 54:12.500 --> 54:15.460 Die Aussage war, dass PJ gleich PJ plus 1 ist. 54:16.860 --> 54:21.320 Also sind Zustände, die J-Äquivalent sind, demnach auch J plus 1 54:21.320 --> 54:22.060 -Äquivalent. 54:23.200 --> 54:30.280 Und wenn das der Fall ist, sie sind null-Äquivalent und für jedes 54:30.280 --> 54:34.880 Zeichen E sind die Folgezustände J plus 1-Äquivalent, dann sind sie 54:34.880 --> 54:37.180 natürlich insgesamt J plus 2-Äquivalent. 54:38.020 --> 54:40.820 Auch hier wieder dieser dumme senkrechte Strich, tut mir leid, den 54:40.820 --> 54:41.640 mache ich jetzt nicht weg. 54:42.400 --> 54:48.560 Also, das ist genau die einfache Aussage und damit wissen wir, dass 54:48.560 --> 54:52.480 diese Aussage A hier oben gilt, die Aussage B ist wirklich sehr 54:52.480 --> 54:52.960 einfach. 54:53.340 --> 54:58.400 Wenn ich meine Menge habe hier, die ich irgendwie aufteilen will durch 54:58.400 --> 55:03.980 die Partitionierung in klassenäquivalenter Zustände, dann kann ich das 55:03.980 --> 55:09.280 ja maximal N-1 mal machen, dass ich einen Zustand rausnehme aus einer 55:09.280 --> 55:09.540 Menge. 55:10.220 --> 55:13.780 Und danach habe ich, wenn ich jetzt N-1 mal aus einer Menge einen 55:13.780 --> 55:17.820 Zustand rausgenommen habe und ich habe insgesamt nur N Elemente, 55:17.880 --> 55:19.220 bleibt ein Zustand übrig. 55:19.220 --> 55:22.060 Das heißt, mehr kann ich nicht aufteilen. 55:23.520 --> 55:28.040 Das heißt, spätestens bei der N-1-Äquivalenz bin ich fertig. 55:28.820 --> 55:36.200 So, und jetzt ist die Frage, wie wir einen Automaten reduzieren können 55:36.200 --> 55:38.660 und bevor wir das betrachten, machen wir eine kleine Pause. 55:40.000 --> 55:42.020 Hat keiner aufgepasst, dass wir eine Pause machen müssen? 55:42.060 --> 55:42.960 Wurde nicht erinnert heute. 56:58.500 --> 56:59.560 Auch zu viel. 57:07.060 --> 57:07.880 Auch zu viel. 58:10.320 --> 58:11.520 Das geht nicht. 58:15.240 --> 58:16.280 Ich lasse es. 58:34.780 --> 58:35.860 Ah, okay. 59:27.190 --> 59:28.990 So, ich denke, die Pause ist lang genug. 59:29.090 --> 59:31.430 Ich will mal die Frage beantworten, die gerade noch da war. 59:31.430 --> 59:33.590 Das ist eine berechtigte Frage. 59:34.230 --> 59:38.550 Die Frage bezog sich darauf, was dieses Zeichen bedeutet. 59:39.450 --> 59:44.390 Das habe ich Ihnen etwas so nebenbei angedeutet. 59:45.360 --> 59:50.890 Ich habe also zwei Partitionen, Pi und PiK. 59:52.770 --> 59:59.410 Und das ist eine Relation, eine feine Relation zwischen solchen 59:59.410 --> 01:00:01.810 Relationen. 01:00:01.830 --> 01:00:03.470 Und hier steht, was es bedeuten soll. 01:00:05.670 --> 01:00:06.870 Das ist die Aussage. 01:00:07.010 --> 01:00:09.530 Ich habe das hier verkürzt hingeschrieben. 01:00:09.910 --> 01:00:12.630 Gleichwertig sind das jeweils diese beiden Aussagen. 01:00:12.630 --> 01:00:20.530 Es ist wirklich zum Verrücktwerden mit diesem Strich, der da entsteht. 01:00:22.810 --> 01:00:32.970 Also, die Eigenschaft, die durch dieses feine Symbol ausgedrückt wird, 01:00:32.970 --> 01:00:40.690 ist einfach nur, dass jede Klasse der Partition Pi eine Teilmenge ist, 01:00:41.890 --> 01:00:46.950 einer Klasse der Partition PiK. 01:00:48.910 --> 01:00:53.810 Das heißt, es ist eine Verfeinerung der Partitionierung. 01:00:53.810 --> 01:00:58.390 Wenn wir uns also die eine Partition betrachten, hier haben wir 01:00:58.390 --> 01:01:02.310 irgendwelche Einteilungen in diese 1, 2, 3, 4 Mengen. 01:01:03.210 --> 01:01:06.570 Dann ist eine Partition, die feiner ist, sieht so aus, dass wir dann 01:01:06.570 --> 01:01:11.110 hier irgendwo noch eine Menge abteilen oder irgendetwas feiner machen. 01:01:11.570 --> 01:01:16.690 Und dann ist jede Menge hier eine Teilmenge der Mengen der gröberen 01:01:16.690 --> 01:01:17.230 Partition. 01:01:17.750 --> 01:01:19.330 Das ist das, was damit gemeint war. 01:01:19.330 --> 01:01:23.890 Hatte ich hier verkürzend so hingeschrieben, hatte aber auch die 01:01:23.890 --> 01:01:25.470 Bedeutung rechts daneben geschrieben. 01:01:25.630 --> 01:01:28.190 Das ist also genau die Bedeutung dieser feineren Relation. 01:01:30.630 --> 01:01:34.610 Die Aussage, die wir beweisen, jeweils ist genau die Aussage. 01:01:34.630 --> 01:01:37.010 Sie sehen, der Strich, der kommt immer wieder. 01:01:38.490 --> 01:01:42.650 Das sind die Aussagen, die wir beweisen müssen, genau das habe ich 01:01:42.650 --> 01:01:43.810 hier unten getan. 01:01:44.770 --> 01:01:48.590 So, dann mache ich weiter, wir waren da schon durch. 01:01:49.130 --> 01:01:51.550 Und jetzt ist die Frage, wie reduziert man wirklich Automaten? 01:01:51.590 --> 01:01:54.850 Das kriegen wir heute noch gut hin, Automaten zu reduzieren. 01:01:55.590 --> 01:01:58.530 Wir müssen alle in nicht erreichbaren Zustände rauswerfen, haben dann 01:01:58.530 --> 01:01:59.710 vereinfachten Automaten. 01:02:00.330 --> 01:02:02.610 Dann bestimmen wir die Klassen-Äquivalente der Zustände. 01:02:04.190 --> 01:02:05.490 Wie wir das machen, sehen wir gleich. 01:02:05.830 --> 01:02:09.290 Hatte ich schon angedeutet, welche Eigenschaften wir ausnutzen können. 01:02:09.290 --> 01:02:14.370 Und dann müssen wir drittens die Klassen-Äquivalente der Zustände 01:02:14.370 --> 01:02:17.590 praktisch nehmen, als neue Zustände unseres Automaten. 01:02:17.910 --> 01:02:21.930 Wir nehmen im Prinzip aus jeder Klasse einen Zustand raus und werfen 01:02:21.930 --> 01:02:23.690 alle anderen Zustände weg. 01:02:26.250 --> 01:02:28.490 Und dann bekommen wir einen reduzierten Automaten. 01:02:29.050 --> 01:02:34.890 Und da heißt reduziert, genau dann, wenn A vereinfacht ist und alle 01:02:34.890 --> 01:02:38.110 Zustände paarweise nicht äquivalent zueinander sind. 01:02:39.290 --> 01:02:42.410 Dann kann ich nicht weiter vereinfachen. 01:02:43.130 --> 01:02:46.310 Und ich sagte es schon, man kann zeigen, dass der eindeutig bestimmt 01:02:46.310 --> 01:02:48.770 ist, bis auf Umbenennungen der Zustände. 01:02:50.230 --> 01:02:52.530 Das ist also ein reduzierter Automaten und den wollen wir jetzt 01:02:52.530 --> 01:02:52.910 bestimmen. 01:02:53.590 --> 01:02:57.030 Dazu brauchen wir jetzt einen Algorithmus, der die äquivalenten 01:02:57.030 --> 01:02:58.450 Zustände ermittelt. 01:02:59.410 --> 01:03:02.490 Und das macht er jetzt genauso, wie ich das gerade eben angedeutet 01:03:02.490 --> 01:03:02.910 habe. 01:03:03.490 --> 01:03:05.910 Zunächst mal wird alles vereinfacht, das ist klar, das ist der 01:03:05.910 --> 01:03:06.650 einfachste Schritt. 01:03:06.650 --> 01:03:11.970 Und dann wollen wir bestimmen, welche Zustände äquivalent sind. 01:03:12.030 --> 01:03:15.810 Wir machen das so, dass wir feststellen, welche nicht äquivalent sind. 01:03:16.890 --> 01:03:17.850 Das ist der Ansatz. 01:03:18.470 --> 01:03:23.070 Wir versuchen nicht direkt jetzt zu sagen, wenn wir zwei Zustände 01:03:23.070 --> 01:03:26.210 betrachten, sind die äquivalent, sondern wir fragen, sind die nicht 01:03:26.210 --> 01:03:26.930 äquivalent. 01:03:27.470 --> 01:03:31.050 Und wir betrachten zunächst die gröbste Unterteilung, nämlich die 01:03:31.050 --> 01:03:31.910 Nulläquivalenz. 01:03:31.910 --> 01:03:39.430 Also für K gleich Null, zunächst mal schauen wir an, für jedes Paar S 01:03:39.430 --> 01:03:46.230 und S' und von verschiedenen Zuständen schauen wir, ob sie beide N 01:03:46.230 --> 01:03:49.430 -Zustände sind oder beide keine N-Zustände. 01:03:54.410 --> 01:04:01.250 Wenn also der eine Zustand aus F ist und der andere nicht aus F, es 01:04:01.250 --> 01:04:06.990 kann also sein, S ist aus F, S' nicht aus F oder S' ist aus F und S 01:04:06.990 --> 01:04:11.290 ist nicht aus F, das sind die beiden Möglichkeiten, der eine ist in N 01:04:11.290 --> 01:04:16.190 -Zustand, der andere nicht, dann sind die beiden nicht N-Zustände. 01:04:16.190 --> 01:04:23.850 Das heißt, wir betrachten im Prinzip so eine Matrix und haben hier 01:04:23.850 --> 01:04:31.030 unsere Zustände S0 und so weiter bis S' 01:04:34.970 --> 01:04:44.890 Quatsch, hier steht S' und hier haben wir entsprechend auch S0 bis S' 01:04:45.150 --> 01:04:50.630 betrachten hier irgendein Feld und wir sagen, hier ist also unser 01:04:50.630 --> 01:04:52.610 Zustand S, da ist der Zustand S'. 01:04:52.610 --> 01:04:57.190 Wenn wir ein solches Feld betrachten, dann machen wir da ein Kreuz 01:04:57.190 --> 01:05:03.530 rein und sagen, die beiden sind nicht Nulläquivalent, damit auch 01:05:03.530 --> 01:05:04.390 nichtäquivalent. 01:05:05.430 --> 01:05:07.090 Dann wissen wir, die sind nichtäquivalent. 01:05:08.050 --> 01:05:12.130 Und dann wissen wir also alle, die nicht markiert sind, alle nicht 01:05:12.130 --> 01:05:19.050 markierten Felder, da wissen wir, die sind vielleicht einsäquivalent. 01:05:19.050 --> 01:05:25.830 Wir wissen, sie könnten einsäquivalent sein, wir wissen nur von diesem 01:05:25.830 --> 01:05:27.670 hier, könnten auch Nulläquivalent sein. 01:05:28.690 --> 01:05:33.610 Also die, die nicht Nulläquivalent sind, die haben wir schon mal 01:05:33.610 --> 01:05:34.090 markiert. 01:05:34.850 --> 01:05:40.750 Und dann machen wir halt weiter, indem wir sukzessive das K erhöhen 01:05:41.680 --> 01:05:49.410 und ein unmarkiertes Paar hernehmen, SS', also ein anderes Feld 01:05:49.410 --> 01:05:54.290 hernehmen, das noch nicht markiert war. 01:05:56.070 --> 01:06:02.590 Und schauen uns jetzt an, Folgezustände, für jeden Folgezustand 01:06:02.590 --> 01:06:09.790 schauen wir nach, gibt es ein Paar von Folgezuständen, das markiert 01:06:09.790 --> 01:06:10.230 ist. 01:06:11.990 --> 01:06:17.090 Wenn wir ein Folgezustandspaar finden von diesem unmarkierten Paar, 01:06:17.710 --> 01:06:23.290 das markiert ist, dann wissen wir, aha, in diesem Fall, die beiden 01:06:23.290 --> 01:06:28.370 Folgezustände waren Nulläquivalent, oder nicht Nulläquivalent, also da 01:06:28.370 --> 01:06:32.370 die Folgezustände nicht Nulläquivalent sind, sind die beiden bisher 01:06:32.370 --> 01:06:34.450 nicht markierten nicht Einzäquivalent. 01:06:34.890 --> 01:06:39.710 Oder, wenn ich das eben für beliebiges K hier schon mache, wenn ich 01:06:39.710 --> 01:06:44.110 ein nicht markiertes Feld habe, habe ich also bisher nicht feststellen 01:06:44.110 --> 01:06:48.850 können, dass die nicht Null, nicht Eins, nicht Zwei oder nicht K-1 01:06:48.850 --> 01:06:49.650 -äquivalent sind. 01:06:50.070 --> 01:06:55.530 Und jetzt schaue ich mir an den Fall K und stelle fest, die beiden 01:06:55.530 --> 01:07:00.150 Folgezustände für irgendeine Eingabe sind markiert, dann waren die 01:07:00.150 --> 01:07:04.630 nicht K-1-äquivalent, also sind die Zustände S und das Strich nicht K 01:07:04.630 --> 01:07:05.270 -äquivalent. 01:07:06.290 --> 01:07:07.370 Und genau das steht hier. 01:07:08.270 --> 01:07:11.710 Wenn wir ein solches Folgezustandspaar finden, das bereits markiert 01:07:11.710 --> 01:07:15.710 ist, dann muss ich das Ausgangspaar auch markieren und das mache ich 01:07:15.710 --> 01:07:19.230 so lange, bis ich keine Veränderungen mehr bekomme, bis ich kein 01:07:19.230 --> 01:07:23.970 bisher noch nicht markiertes Feld neu markieren muss, denn dann kann 01:07:23.970 --> 01:07:25.750 ich meine Partition nicht weiter verfeinern. 01:07:25.750 --> 01:07:29.770 Das war der Satz, es reicht so lange zu schauen, bis ich keine 01:07:29.770 --> 01:07:31.810 Veränderungen bekomme, dann bin ich fertig. 01:07:32.430 --> 01:07:35.450 Und das, was wir hier als Algorithmus sehen, das machen wir jetzt 01:07:35.450 --> 01:07:38.110 etwas schöner gemalt auf der nächsten Folie. 01:07:39.810 --> 01:07:42.110 Oder erstmal, ich mache das an einem Beispiel. 01:07:42.710 --> 01:07:47.410 Also es ist klar, wenn wir fertig sind mit dem Algorithmus und es 01:07:47.410 --> 01:07:51.650 bleiben Felder übrig, die nicht markiert sind, dann wissen wir, wir 01:07:51.650 --> 01:07:56.110 haben nicht zeigen können, dass sie für irgendeinen K nicht K 01:07:56.110 --> 01:07:56.950 -Äquivalent sind. 01:07:57.550 --> 01:07:59.110 Also müssen sie äquivalent sein. 01:08:00.850 --> 01:08:04.330 Ansonsten hätten wir ja zeigen können, dass es ein Paar gibt, oder 01:08:04.330 --> 01:08:09.490 dass sie für irgendeinen Folgezustand, dass die bereits markiert sind. 01:08:09.830 --> 01:08:13.490 Also die, die wir nicht markieren können, die Paare, die müssen 01:08:13.490 --> 01:08:16.730 äquivalent sein, weil sie nicht 0, nicht 1, wir konnten nicht zeigen, 01:08:16.870 --> 01:08:21.590 dass sie nicht 0, nicht 1 oder nicht 2 äquivalent sind, sondern sie 01:08:21.590 --> 01:08:22.610 müssen halt äquivalent sein. 01:08:22.990 --> 01:08:25.790 Jetzt machen wir hier ein Beispiel, an dem wir das genauer dann zeigen 01:08:25.790 --> 01:08:26.250 wollen. 01:08:27.210 --> 01:08:32.390 Und das ist hier die Struktur des Automaten und wir sehen also, der 01:08:32.390 --> 01:08:35.430 hat hier einen Anfangszustand, hat zwei Endzustände, noch ein paar 01:08:35.430 --> 01:08:39.250 weitere Zustände und wir wollen jetzt feststellen im Weiteren, welche 01:08:39.250 --> 01:08:42.110 dieser Zustände dieses Automaten sind äquivalent. 01:08:43.870 --> 01:08:48.410 Also S4 und S5 sind die beiden Endzustände und jetzt müssen wir 01:08:48.410 --> 01:08:51.910 schauen, wie können wir hier den Algorithmus anwenden. 01:08:52.010 --> 01:08:54.270 Und da sehen wir jetzt genau die Art, wie wir das machen. 01:08:54.950 --> 01:09:00.610 Wir haben hier eine solche untere Dreiecksmatrix, wir betrachten alle 01:09:00.610 --> 01:09:06.490 Paare von Zuständen, wir haben also hier S1 bis S5 in dem Fall und 01:09:06.490 --> 01:09:09.350 hier S0 bis S4, dann haben wir alle Paare genau drin. 01:09:09.790 --> 01:09:12.890 Wir brauchen die Diagonale ja nicht zu betrachten, die Hauptdiagonale, 01:09:13.470 --> 01:09:17.310 weil wir ja nicht einen Zustand mit sich selbst vergleichen, das macht 01:09:17.310 --> 01:09:17.850 ja keinen Sinn. 01:09:19.150 --> 01:09:23.870 Also hier nur S1 bis S5 und da ist S0 bis S4, die Hauptdiagonale oben 01:09:23.870 --> 01:09:24.230 ist weg. 01:09:25.290 --> 01:09:34.010 Und das ist hier unten nochmal die Automatentabelle und jetzt können 01:09:34.010 --> 01:09:34.670 wir anfangen. 01:09:34.670 --> 01:09:39.690 Erster Schritt, markiere alle Paare von Zuständen, von denen einer ein 01:09:39.690 --> 01:09:42.410 Endzustand ist und der andere nicht. 01:09:43.230 --> 01:09:45.410 Und die markieren wir mit X0. 01:09:46.090 --> 01:09:52.310 Die Endzustände sind hier unten S4 und S5, also müssen wir alle Paare 01:09:52.310 --> 01:09:58.950 von Zuständen, also wenn wir S4 betrachten, alle Paare, meinetwegen 01:09:58.950 --> 01:10:04.890 S0, S0, S5 zum Beispiel, müssen wir natürlich markieren, S1, S5 auch, 01:10:05.010 --> 01:10:07.070 genauso S0, S4, also das ist sehr einfach. 01:10:07.910 --> 01:10:15.350 Diese ganzen Paare von Zuständen hier sind nicht nulläquivalent, weil 01:10:15.350 --> 01:10:18.910 das eine Element aus F ist und das andere nicht. 01:10:19.750 --> 01:10:24.610 Da haben wir schon sehr viele Kreuze hier drin, X mit einer Null dran 01:10:24.610 --> 01:10:26.470 heißt, die sind nicht nulläquivalent. 01:10:26.470 --> 01:10:31.330 Und jetzt schauen wir im nächsten Schritt, im zweiten Schritt, Felder 01:10:31.330 --> 01:10:33.410 an, die nicht markiert sind. 01:10:33.810 --> 01:10:37.930 Zum Beispiel das Feld hier oben S1, S1, S0. 01:10:38.790 --> 01:10:43.430 Schauen wir uns S1, S0 an oder S0, S1, das ist nicht markiert. 01:10:43.510 --> 01:10:48.590 S0, S1, da gehen wir mit 0 über auf S1, S4. 01:10:49.090 --> 01:10:51.170 Schauen wir uns S1, S4 an. 01:10:52.110 --> 01:10:57.430 S1, S4 ist markiert mit X0, das heißt, dieses hier müssen wir 01:10:57.430 --> 01:10:58.830 markieren mit X1. 01:11:00.010 --> 01:11:03.770 Entsprechend machen wir das weiter und kommen auf diese Markierungen, 01:11:03.850 --> 01:11:08.070 die ich hier im grünen Schritt 2 markiert habe. 01:11:09.350 --> 01:11:12.310 Für diese bisher nicht markierten Felder haben wir jeweils 01:11:12.310 --> 01:11:16.170 Folgezustände gefunden, die bereits mit X0 markiert waren. 01:11:16.920 --> 01:11:22.670 Und jetzt, im dritten Schritt, schauen wir weiter, gibt es ausgehend 01:11:22.670 --> 01:11:28.070 von nicht markierten Feldern, Folgezustandspaare, also Folgefelder, 01:11:28.170 --> 01:11:29.370 die bereits markiert sind. 01:11:30.410 --> 01:11:33.990 Und Sie können sich das anschauen, Sie werden feststellen, Sie finden 01:11:33.990 --> 01:11:34.430 keine. 01:11:35.750 --> 01:11:40.270 Das heißt, doch, hier ein, den haben wir noch gefunden, 01:11:40.350 --> 01:11:40.670 Entschuldigung. 01:11:41.190 --> 01:11:44.730 Das Feld hier oben, die sind nicht zweiquivalent. 01:11:46.190 --> 01:11:50.530 Das eine Paar hier oben, das war S2, S0, schauen wir uns das nochmal 01:11:50.530 --> 01:11:50.830 an. 01:11:50.970 --> 01:11:58.350 S2, S0, das sind diese hier, da kommen wir mit 0 auf S1, S0 und S1, S0 01:11:58.350 --> 01:12:03.450 war bereits mit X1 markiert, deswegen muss dieses Feld S2, S0 mit X2 01:12:03.450 --> 01:12:04.190 markiert werden. 01:12:05.450 --> 01:12:09.690 Und jetzt schauen wir wieder weiter und wir werden feststellen, jetzt 01:12:09.690 --> 01:12:13.170 haben wir hier zwei Felder, die noch nicht markiert waren und die 01:12:13.170 --> 01:12:15.710 werden auch in diesem vierten Schritt nicht markiert. 01:12:16.170 --> 01:12:17.270 Und damit sind wir fertig. 01:12:18.630 --> 01:12:27.150 Wir brauchten also gar nicht alle 6, also alle Folgen bis zu K gleich 01:12:27.150 --> 01:12:30.690 6 anzuschauen, sondern wir sind jetzt schon fertig. 01:12:31.910 --> 01:12:36.270 Im vierten Schritt stellen wir keine Veränderung fest, deswegen wissen 01:12:36.270 --> 01:12:41.470 wir jetzt, welche Zustände äquivalent sind, nämlich S3 und das sind 01:12:41.470 --> 01:12:43.030 hier die äquivalenten Zustände. 01:12:43.850 --> 01:12:50.470 S3, S1 sind äquivalent und S5 und S4 sind äquivalent. 01:12:51.110 --> 01:12:55.990 Die beiden Endzustände sind äquivalent und die beiden Zustände S3 und 01:12:55.990 --> 01:12:56.870 S1. 01:12:57.790 --> 01:13:00.690 Und jetzt können wir den reduzierten Automaten konstruieren. 01:13:00.830 --> 01:13:05.470 Also das ist ein ganz systematisches Verfahren, anfangend mit 01:13:05.470 --> 01:13:09.910 denjenigen, die nicht Null-äquivalent sind, dann die, die nicht Eins 01:13:09.910 --> 01:13:11.030 -äquivalent sind usw. 01:13:11.630 --> 01:13:14.450 Dann nutzen wir diese Eigenschaft aus, die wir vorher gerade gezeigt 01:13:14.450 --> 01:13:14.690 hatten. 01:13:16.130 --> 01:13:18.590 Damit haben wir dann genau das gemacht. 01:13:19.010 --> 01:13:22.190 Das können Sie sich im X-Visit auch anschauen, da gibt es dann 01:13:22.190 --> 01:13:27.570 entsprechend Möglichkeiten, sich auch genau die Reduktion vorzunehmen. 01:13:28.530 --> 01:13:32.250 Will ich jetzt aber hier gar nicht machen, das können Sie gerne sich 01:13:32.250 --> 01:13:33.570 selbst nochmal anschauen. 01:13:34.730 --> 01:13:37.990 Und jetzt können wir also den Automaten reduzieren. 01:13:38.910 --> 01:13:43.730 Und ich hatte gesagt, wir müssen dann im Prinzip die Klassen 01:13:43.730 --> 01:13:47.310 äquivalenter Zustände nehmen und daraus den neuen Automaten bauen. 01:13:47.310 --> 01:13:52.830 Das heißt, wir haben zunächst mal den vereinfachten Automaten gegeben 01:13:52.830 --> 01:13:57.870 und dann definieren wir die neuen Automaten so, dass die neue 01:13:57.870 --> 01:14:02.790 Zustandsmenge gerade aus den Äquivalenzklassen besteht des alten 01:14:02.790 --> 01:14:03.990 Automaten. 01:14:05.190 --> 01:14:10.490 Das heißt, der neue Anfangszustand ist die Äquivalenzklasse des alten 01:14:10.490 --> 01:14:11.710 Anfangszustandes. 01:14:12.460 --> 01:14:17.910 Die neue Endzustandsmenge ist die Menge aller Äquivalenzklassen, die 01:14:17.910 --> 01:14:21.930 man bekommt, wenn man die alten Endzustände betrachtet. 01:14:22.870 --> 01:14:28.250 Und die Übergangsfunktion wird gerade so definiert, dass der Übergang 01:14:28.250 --> 01:14:33.890 von der Äquivalenzklasse des Zustands S gerade die Äquivalenzklasse 01:14:33.890 --> 01:14:39.190 ist, die ich von dem Zustand S aus, also die Äquivalenzklasse des 01:14:39.190 --> 01:14:44.250 Zustandes, den ich von S aus bei Eingabe von E erreicht habe. 01:14:45.310 --> 01:14:48.630 Das heißt, das Delta SE ist der Folgezustand von S. 01:14:49.170 --> 01:14:50.870 Und dann betrachte ich dessen Äquivalenzklasse. 01:14:52.650 --> 01:14:56.770 Hier muss man zeigen, dass das hier wohl definiert ist, dass das 01:14:56.770 --> 01:15:00.990 unabhängig ist von dem Zustand, den ich gerade rausgenommen habe. 01:15:00.990 --> 01:15:05.550 Das ist aber eine sehr einfache Überlegung, dass ich also hier 01:15:05.550 --> 01:15:09.690 irgendeinen Zustand rausnehmen kann aus einer Äquivalenzklasse und 01:15:09.690 --> 01:15:14.350 dessen Folgezustand betrachte bei Eingabe von E und dann ist das die 01:15:14.350 --> 01:15:16.430 entsprechende Folgeäquivalenzklasse. 01:15:17.190 --> 01:15:19.950 Wenn ich einen anderen Zustand aus der Äquivalenzklasse nehmen würde, 01:15:20.310 --> 01:15:25.470 würde ich die gleiche Folgeäquivalenzklasse bekommen. 01:15:26.730 --> 01:15:33.170 Mit dieser Definition haben wir einen reduzierten Automaten und das 01:15:33.170 --> 01:15:35.230 ist also dann dieses einfache Verfahren. 01:15:35.310 --> 01:15:36.730 Auch das machen wir gleich an dem Beispiel. 01:15:37.550 --> 01:15:45.110 Wir haben also hier unseren alten Automaten und das Delta war 01:15:45.110 --> 01:15:51.290 definiert wie hier und jetzt müssen wir daraus einen reduzierten 01:15:51.290 --> 01:15:52.190 Automaten machen. 01:15:52.190 --> 01:15:58.770 Wir haben unsere Paare äquivalenter Zustände gefunden, S1, S3 und S4, 01:15:58.850 --> 01:15:59.330 S5. 01:16:00.070 --> 01:16:05.510 Das heißt, unser reduzierter Automat bekommt jetzt diese neuen 01:16:05.510 --> 01:16:10.710 Zustände, nämlich die Klasse von S0, Klasse von S1, Klasse von S2, 01:16:11.270 --> 01:16:12.530 Klasse von S4. 01:16:14.190 --> 01:16:19.990 Das sind alle Äquivalenzklassen, weil ja S1 und S3 äquivalent sind und 01:16:19.990 --> 01:16:20.790 S4 und S5. 01:16:24.490 --> 01:16:30.670 Und dieser F-Strich, wir haben nur noch einen Endzustand, das ist die 01:16:30.670 --> 01:16:33.750 Klasse von S4 oder Klasse von S5, das ist egal. 01:16:35.150 --> 01:16:38.590 Und damit können wir jetzt den Automaten uns hinmalen. 01:16:38.890 --> 01:16:42.510 Das ist also dann unsere Zustandstabelle von dem neuen Automaten. 01:16:43.130 --> 01:16:49.290 Wir betrachten jeweils die Klassen S0', S1', S2', S4'. 01:16:50.550 --> 01:16:54.210 Und haben dann entsprechend die Übergänge. 01:16:54.690 --> 01:17:00.050 Das sind gerade die Folgeklassen, die wir erreichen, wenn wir von den 01:17:00.050 --> 01:17:01.450 Klassen jeweils ausgehen. 01:17:01.610 --> 01:17:07.310 Also von der Klasse S1' von S1, S3 kommen wir dann entsprechend nach 01:17:07.310 --> 01:17:09.710 S4' und so weiter. 01:17:10.270 --> 01:17:14.710 Und von dem S4' kommen wir nach S1' oder nach S4', je nachdem ob wir 0 01:17:14.710 --> 01:17:15.590 oder 1 eingehen. 01:17:16.410 --> 01:17:21.230 Das ist also einfach abgeleitet dann aus dieser Tabelle, bekommen wir 01:17:21.230 --> 01:17:25.930 dann die Tabelle, dadurch, dass wir diese Einteilung gemacht haben, 01:17:26.030 --> 01:17:29.810 entsprechend der Äquivalenz der Zustände, die wir gerade vorher 01:17:29.810 --> 01:17:30.690 festgestellt haben. 01:17:33.710 --> 01:17:38.930 Also S4 und S1 weglassen, selbstverständlich können Sie das, anstatt 01:17:38.930 --> 01:17:39.830 S3 und S5. 01:17:39.950 --> 01:17:42.210 Das ist ja völlig egal, wir haben ja nicht einen Zustand weggelassen. 01:17:43.000 --> 01:17:47.790 Wir haben die Zustände zusammengefasst zu einem neuen Zustand. 01:17:48.530 --> 01:17:51.150 Sie können sagen, das ist doch das Gleiche. 01:17:51.550 --> 01:17:55.310 Abstrakt ist es so, dass wir eben nicht einen Zustand weglassen, 01:17:55.450 --> 01:17:59.430 sondern wir fassen die Zustände zusammen zu einer Klasse von 01:17:59.430 --> 01:18:01.570 Zuständen, zu einer Menge von Zuständen. 01:18:02.250 --> 01:18:09.930 Und genau das steht hier, das sind die Klassen der Zustände. 01:18:10.730 --> 01:18:15.650 Wir lassen also keinen weg, die sind alle da, aber stecken eben in 01:18:15.650 --> 01:18:17.570 diesen neuen Bezeichnungen mit drin. 01:18:18.230 --> 01:18:20.990 Das ist ein Automat, der auf Zustandsmengen operiert, im Prinzip. 01:18:21.710 --> 01:18:24.710 Sie können auch sagen, wir werfen einfach einen Zustand weg, das ist 01:18:24.710 --> 01:18:25.570 ein bisschen Geschmackssache. 01:18:26.050 --> 01:18:31.610 Aber es ist so formal, dass wir jetzt einen Zustand definieren, durch 01:18:31.610 --> 01:18:33.710 die Äquivalenzklassen, die wir haben. 01:18:53.790 --> 01:19:03.370 Also, S1' kann man nicht weglassen, weil ja Sie kommen von S1' mit 0 01:19:03.370 --> 01:19:05.170 und mit 1 auf S4'. 01:19:05.170 --> 01:19:09.190 Aber Sie kommen zum Beispiel von S4' kommen Sie nach S1' oder nach 01:19:09.190 --> 01:19:09.750 S4'. 01:19:09.750 --> 01:19:12.730 Das heißt, Sie brauchen diesen Zustand S1, das haben wir gerade 01:19:12.730 --> 01:19:13.090 gesehen. 01:19:13.190 --> 01:19:16.230 S1 und S4 sind nicht äquivalent. 01:19:17.470 --> 01:19:20.230 Die haben wir markiert, dieses Paar, S1, S4. 01:19:20.230 --> 01:19:22.130 Warum sind die nicht äquivalent? 01:19:22.230 --> 01:19:25.610 S1 ist kein Endzustand, S4 ist ein Endzustand. 01:19:26.290 --> 01:19:28.610 Das heißt, die sind nicht nulläquivalent. 01:19:30.230 --> 01:19:34.370 Und wenn Zustände nicht äquivalent sind, dann heißt das, Sie haben ein 01:19:34.370 --> 01:19:35.590 unterschiedliches Verhalten. 01:19:36.210 --> 01:19:40.470 Wenn ich von denen aus jetzt irgendwelche Zeichen eingebe, komme ich 01:19:40.470 --> 01:19:43.850 in Situationen, wo ich halt ein unterschiedliches 01:19:43.850 --> 01:19:45.130 Akzeptierungsverhalten habe. 01:19:46.290 --> 01:19:47.850 Deswegen, die kann ich gerade nicht weglassen. 01:19:48.910 --> 01:19:49.910 Noch eine Frage? 01:19:52.890 --> 01:19:54.530 Achso, die hatte ich ja gerade beantwortet. 01:19:55.370 --> 01:19:58.110 Okay, und den Automaten malen wir jetzt auch noch auf. 01:19:58.810 --> 01:20:00.990 Das ist auf der nächsten Folie der Fall, hier nochmal. 01:20:01.670 --> 01:20:03.370 Das ist also der alte Automat. 01:20:03.590 --> 01:20:05.570 Die beiden Zustände fassen wir zusammen. 01:20:07.370 --> 01:20:11.000 Und außerdem fassen wir... 01:20:11.690 --> 01:20:16.310 Achso, das S1, S3 wird auch zusammengefasst. 01:20:17.250 --> 01:20:19.510 S4, S5 wird zusammengefasst. 01:20:21.230 --> 01:20:28.070 Also wir haben hier S1 und S3 zusammengefasst. 01:20:28.390 --> 01:20:31.750 Das sind die beiden Zustände, die sind hier blau markiert, rot 01:20:31.750 --> 01:20:33.950 markiert sind die anderen beiden, die äquivalent waren. 01:20:34.530 --> 01:20:37.430 Die sind jeweils zusammengefasst worden und dann kommt eben dabei 01:20:37.430 --> 01:20:42.170 dieser Automat raus als Zustandsdiagramm, der durch diese Tabelle 01:20:42.170 --> 01:20:43.050 beschrieben wird. 01:20:43.050 --> 01:20:47.250 Und der hat das gleiche Verhalten wie der Automat, der links daneben 01:20:47.250 --> 01:20:47.610 steht. 01:20:48.990 --> 01:20:53.710 Auf die Art und Weise wissen wir jetzt, wie wir Automaten vereinfachen 01:20:53.710 --> 01:20:55.290 können und wie wir sie reduzieren können. 01:20:56.870 --> 01:21:01.430 Jetzt können Sie also auf einfache Art und Weise mit diesem Ansatz, 01:21:01.490 --> 01:21:04.770 das ist übrigens ein Ansatz, der dem dynamischen Programmieren 01:21:04.770 --> 01:21:08.550 entspricht, denn dynamisches Programmieren geht immer so vor, dass Sie 01:21:08.550 --> 01:21:14.910 tabellarisch von einfachen Eigenschaften sukzessive schließen auf 01:21:14.910 --> 01:21:16.370 kompliziertere Eigenschaften. 01:21:16.690 --> 01:21:17.830 Genau das haben wir hier gemacht. 01:21:17.950 --> 01:21:21.350 Sie können die Tabelle sukzessive ausfüllen, indem Sie einfache 01:21:21.350 --> 01:21:26.570 Eigenschaften bereits gezeigt haben und daraus auf kompliziertere 01:21:26.570 --> 01:21:27.470 Eigenschaften schließen. 01:21:28.050 --> 01:21:32.190 Das war das, was wir hier gemacht haben. 01:21:32.510 --> 01:21:36.470 Wir hatten angefangen mit der Nicht-X0-Äquivalenz, dann Nicht-X1 01:21:36.470 --> 01:21:37.570 -Äquivalenz usw. 01:21:37.570 --> 01:21:41.810 Wir schließen sukzessive, hangeln uns so hoch, bis wir dann die 01:21:41.810 --> 01:21:45.570 komplexeste Eigenschaft am Ende ermittelt haben, nämlich, dass 01:21:45.570 --> 01:21:47.630 Zustände äquivalent sind. 01:21:49.230 --> 01:21:53.590 Wir konnten eben nicht zeigen, dass sie Nicht-1, Nicht-2, Nicht-3 oder 01:21:53.590 --> 01:21:55.830 Nicht -irgendein-K-Äquivalent sind. 01:21:56.550 --> 01:22:02.350 Okay, und dadurch habe ich Ihnen gezeigt, wie man reduzieren kann. 01:22:04.070 --> 01:22:08.690 Es gibt also zu jedem endlichen Automaten einen äquivalenten minimalen 01:22:08.690 --> 01:22:09.730 endlichen Automaten. 01:22:10.270 --> 01:22:13.270 Das ist der vereinfachte und reduzierte Automat. 01:22:14.810 --> 01:22:18.610 Und diesen nennt man auch den Äquivalenzklassenautomat, weil er halt 01:22:18.610 --> 01:22:20.950 als Zustände jetzt die Äquivalenzklassen hat. 01:22:21.810 --> 01:22:23.830 Man nennt ihn auch manchmal Faktorautomat. 01:22:23.970 --> 01:22:28.010 Also wenn ich einen Automaten A habe, dann faktorisiere ich diesen 01:22:28.010 --> 01:22:31.850 Automaten nach dieser Äquivalenzrelation oder nach der Partition Pi. 01:22:32.550 --> 01:22:33.730 So schreibt man das auch hin. 01:22:34.850 --> 01:22:36.810 Und dann ist das ein Faktorautomat. 01:22:37.290 --> 01:22:40.590 Man kann auch sehr viele Dinge überlegen bezüglich solcher 01:22:40.590 --> 01:22:41.930 Faktorisierungen von Automaten. 01:22:42.750 --> 01:22:45.610 Welche Eigenschaften, welche Struktureigenschaften solche Automaten 01:22:45.610 --> 01:22:45.950 haben. 01:22:46.330 --> 01:22:47.390 Das alles lassen wir hier weg. 01:22:47.490 --> 01:22:51.330 Da kann man also viele Doppelstunden drauf verwenden, die Struktur von 01:22:51.330 --> 01:22:55.670 Automaten zu charakterisieren, wie man die aus einfachen Bauteilen 01:22:55.670 --> 01:22:56.590 aufbauen kann. 01:22:56.590 --> 01:23:00.150 Das entspricht dann sehr stark der tatsächlichen Realisierung von 01:23:00.150 --> 01:23:01.350 Automaten in Hardware. 01:23:02.110 --> 01:23:06.910 Aber das geht über den möglichen Inhalt dieser Vorlesung hinaus. 01:23:07.670 --> 01:23:11.010 Ich belasse es dabei, dass wir jetzt wissen, wie wir Automaten 01:23:11.010 --> 01:23:11.970 reduzieren können. 01:23:12.710 --> 01:23:14.090 Und jetzt kommt ein nächster Begriff. 01:23:14.530 --> 01:23:17.590 Wenn Sie sich das Buch angeschaut haben, da wird ziemlich schnell 01:23:17.590 --> 01:23:22.210 erstmal verwiesen, da haben wir die verschiedenen Automatentypen 01:23:22.210 --> 01:23:25.590 deterministisch zunächst definiert und dann sagen wir, was Nicht 01:23:25.590 --> 01:23:26.690 -Determinismus ist. 01:23:27.470 --> 01:23:30.130 Und das werden wir jetzt machen für die endlichen Automaten. 01:23:31.250 --> 01:23:34.210 Und die Frage ist, was Nicht-Determinismus heißen soll. 01:23:34.290 --> 01:23:38.850 Nicht-Determinismus soll heißen, ich habe eine gewisse Unsicherheit 01:23:38.850 --> 01:23:41.870 bezüglich des nächsten Zustandes. 01:23:42.670 --> 01:23:46.690 Ich habe also einen Zustand und eine Eingabe und danach kommt eine 01:23:46.690 --> 01:23:48.530 Menge von Folgezuständen. 01:23:50.070 --> 01:23:52.870 Der Folgezustand ist dann nicht eindeutig. 01:23:53.970 --> 01:23:56.270 Die Menge von Folgezuständen kann auch leer sein. 01:23:57.330 --> 01:24:01.490 Und das wäre dann ein nicht-deterministischer Automat, bei dem wir für 01:24:01.490 --> 01:24:05.350 jeden Zustand und jede Eingabe eine Menge von Folgezuständen angeben. 01:24:06.350 --> 01:24:07.530 Welchen Sinn macht das? 01:24:07.590 --> 01:24:08.970 Schauen Sie sich dieses Beispiel an. 01:24:10.630 --> 01:24:16.150 Wir haben einen Automaten, der fängt an bei S0 und mit A oder B kann 01:24:16.150 --> 01:24:17.470 er in S0 bleiben. 01:24:19.050 --> 01:24:24.730 Er kann aber mit A, das taucht jetzt nochmal auf, mit A könnte er auch 01:24:24.730 --> 01:24:25.710 nach S1 gehen. 01:24:26.750 --> 01:24:31.410 Mit B könnte er auch nach S2 gehen. 01:24:33.430 --> 01:24:38.790 Und wenn er in S1 oder S2 ist, dann kann er entweder in S1 oder S2 01:24:38.790 --> 01:24:39.890 bleiben mit A und B. 01:24:39.970 --> 01:24:45.050 Er könnte aber auch mit A auf das S3 gehen oder könnte hier mit B auf 01:24:45.050 --> 01:24:45.970 das S3 gehen. 01:24:46.730 --> 01:24:51.910 Und was sehen wir an diesem Automaten sofort oder sehr, sehr schnell? 01:24:52.750 --> 01:24:56.550 Welche Wörter sind in dieser Sprache, die der Automat akzeptiert? 01:24:57.190 --> 01:25:00.930 Das ist ja kein Automat, wie wir ihn bisher beschrieben haben, weil 01:25:00.930 --> 01:25:04.690 wir hier auf einmal mehrere Möglichkeiten haben, in Folgezustände zu 01:25:04.690 --> 01:25:04.930 gehen. 01:25:05.870 --> 01:25:10.430 Bei diesem Automaten kommen wir in diesen Endzustand S3, doch nur 01:25:10.430 --> 01:25:16.590 dadurch, dass wir einmal auf ein A gegangen sein müssen und dann 01:25:16.590 --> 01:25:20.090 nochmal mit einem A zu dem S3. 01:25:20.190 --> 01:25:25.530 Das heißt, diese Wörter, die hier drin sind, die enden mit einem A, 01:25:26.090 --> 01:25:28.930 wenn vorher schon mal ein A da gewesen ist. 01:25:30.430 --> 01:25:33.490 Zwischendrin kann irgendwas gewesen sein und davor auch irgendwas 01:25:33.490 --> 01:25:33.950 anderes. 01:25:34.570 --> 01:25:39.650 Oder sie enden mit einem B, wenn davor schon mal ein B gewesen ist. 01:25:40.970 --> 01:25:42.870 Das haben wir hier ganz einfach ausgedrückt. 01:25:44.390 --> 01:25:46.770 Das heißt, wir können auf einmal mit so einem nicht deterministischen 01:25:46.770 --> 01:25:51.050 Automaten die Struktur einer Sprache ein bisschen einfacher darstellen 01:25:51.050 --> 01:25:52.850 als mit einem deterministischen Automaten. 01:25:53.330 --> 01:25:55.670 Ich werde Ihnen nächstes Mal dann auch zeigen, wie der 01:25:55.670 --> 01:25:59.830 deterministische dazu äquivalente Automat aussieht. 01:26:00.230 --> 01:26:01.510 Der wird komplizierter aussehen. 01:26:01.510 --> 01:26:03.250 Also welche Sprache ist das? 01:26:03.330 --> 01:26:07.970 Das ist die Sprache aller Wörter, die auf irgendein Zeichen X enden, 01:26:08.490 --> 01:26:10.830 das vorher schon mal aufgetaucht ist. 01:26:10.930 --> 01:26:12.510 Das ist durch den Automaten angegeben. 01:26:13.190 --> 01:26:18.170 Und wir werden dann das nächste Mal noch weiter vertiefen und kommen 01:26:18.170 --> 01:26:22.010 dann zu der Betrachtung der nicht deterministischen Automaten, den 01:26:22.010 --> 01:26:23.270 Sprachen, die wir akzeptieren. 01:26:23.410 --> 01:26:26.450 Wir werden sehen, dass das zunächst mal so aussieht, dass wenn das 01:26:26.450 --> 01:26:30.290 eine Erweiterung der Möglichkeiten ist, tatsächlich sind die 01:26:30.290 --> 01:26:31.410 äquivalent. 01:26:31.830 --> 01:26:34.250 Das heißt, wir können keine weiteren Sprachen erkennen. 01:26:34.870 --> 01:26:36.830 Das ist eine nicht triviale Erkenntnis. 01:26:37.230 --> 01:26:39.810 Ich danke Ihnen für die Aufmerksamkeit, wünsche Ihnen noch einen 01:26:39.810 --> 01:26:41.070 schönen Tag, das war es für heute.