WEBVTT 00:05.920 --> 00:09.640 Herzlich Willkommen zur Vorlesung Theoretisch-Rundlang-Informatik. 00:10.260 --> 00:13.480 Mein Name ist Thorsten Ueckert und ich vertrete heute Frau Wagner, 00:13.760 --> 00:15.220 weil sie nicht da sein kann. 00:16.040 --> 00:19.780 Ab der nächsten Vorlesung kam sie dann aber wieder zurück. 00:20.960 --> 00:22.120 Was machen wir heute? 00:22.600 --> 00:27.060 Wir gucken uns erstmal das Pumping Lemma an, was Sie in der letzten 00:27.060 --> 00:31.380 Vorlesung kennengelernt haben, und erweitern es zu dem Fallgemeinerten 00:31.380 --> 00:32.080 Pumping Lemma. 00:32.080 --> 00:35.220 Und danach schauen wir uns Minimierung von endlichen Automaten an. 00:35.340 --> 00:39.200 Das heißt, wir bleiben noch in dem ganzen Gebiet der endlichen 00:39.200 --> 00:40.720 Automaten, der regulären Sprachen. 00:41.880 --> 00:44.940 Das Pumping Lemma, das sollte Ihnen bekannt sein aus der letzten 00:44.940 --> 00:45.200 Woche. 00:45.340 --> 00:48.240 Da oben ist die komplizierte, lange Schreibweise, oder zumindest ist 00:48.240 --> 00:51.800 es für mich komplizierter, das so in dem Fließtext zu lesen. 00:52.460 --> 00:55.100 Unten ist es für mich einfacher zu verdauen in dem mathematischen 00:55.100 --> 00:56.880 Kontext, aber vielleicht ist es bei Ihnen andersrum. 00:58.080 --> 00:58.680 Gehen wir es durch. 00:58.680 --> 01:03.800 Das besagt, für jede Sprache L, die regulär ist, existiert eine 01:03.800 --> 01:08.520 natürliche Zahl n, sodass für jedes Wort w, was mindestens n lang ist, 01:08.560 --> 01:14.640 oder echt größer als n, die Länge hat, aus der Sprache, existiert eine 01:14.640 --> 01:20.560 Zerlegung dieses Wortes w in die Teile uvx, wobei der Mittelteil nicht 01:20.560 --> 01:24.300 leer ist, das ist das v, und die ersten beiden Teile uv zusammen 01:24.300 --> 01:29.340 höchstens n lang sind, sodass für jedes i aus den natürlichen Zahlen 01:29.340 --> 01:33.940 dieser Mittelteil, der nicht leer ist, gepumpt werden kann, ohne aus 01:33.940 --> 01:34.900 der Sprache zu fallen. 01:35.040 --> 01:38.700 Das heißt, wir starten in der Sprache, und wenn wir das v jetzt i-mal 01:38.700 --> 01:41.900 wiederholen, also einmal, dann wäre es das Originalwort, das ist 01:41.900 --> 01:45.420 natürlich in der Sprache, aber auch nullmal oder zweimal oder 01:45.420 --> 01:49.860 siebzehnmal oder 42-mal, egal welches i wir wählen, es bleibt in der 01:49.860 --> 01:50.300 Sprache. 01:50.740 --> 01:52.360 Das ist das Pumping Lemma. 01:52.360 --> 01:57.400 Das heißt, reguläre Sprachen können sozusagen auf den ersten, also für 01:57.400 --> 02:01.700 jede reguläre Sprache gibt es ein n, sodass auf dem ersten n-Zeichen 02:01.700 --> 02:05.520 des Wortes, jedes Wortes, ein Teil gibt, der gepumpt werden kann. 02:06.300 --> 02:06.440 Okay? 02:07.260 --> 02:08.660 Das ist die Aussage. 02:10.260 --> 02:15.500 Und Sie haben auch eine Sprache kennengelernt, die regulär ist und das 02:15.500 --> 02:16.620 Pumping Lemma erfüllt. 02:16.760 --> 02:19.400 Sie haben eine Sprache kennengelernt, die das Pumping Lemma nicht 02:19.400 --> 02:21.800 erfüllt und deswegen nicht regulär sein kann. 02:22.220 --> 02:26.860 Sie haben aber auch Sprachen kennengelernt, die nicht regulär sind, 02:27.380 --> 02:31.320 aber trotzdem das nicht gezeigt werden kann durch Widerlegen des 02:31.320 --> 02:31.980 Pumping Lemmas. 02:32.200 --> 02:32.240 Okay? 02:32.460 --> 02:35.300 Also das Pumping Lemma, wir benutzen es, um zu widerlegen, dass eine 02:35.300 --> 02:36.440 Sprache regulär ist. 02:37.600 --> 02:41.040 Sie negieren die Aussage des Pumping Lemmas, weisen diese negierte 02:41.040 --> 02:45.140 Aussage nach und zeigen damit, Ihre Sprache ist nicht regulär. 02:45.300 --> 02:45.500 Okay? 02:46.580 --> 02:51.160 Es wurde Ihnen aber auch gesagt, dass das nicht immer klappt. 02:51.880 --> 02:55.100 Sie können somit nachweisen, dass ein paar Sprachen nicht regulär 02:55.100 --> 02:59.920 sind, aber es ist nicht stark genug für alle nicht regulären Sprachen, 03:00.060 --> 03:02.060 um Ihre Nicht-Regularität nachzuweisen. 03:03.160 --> 03:06.220 Deswegen machen wir heute kurz das Fallgemeinerte Pumping Lemma. 03:06.300 --> 03:07.680 Das ist ein bisschen stärker. 03:08.380 --> 03:12.260 Es kann ein paar mehr Sprachen als nicht regulär identifizieren, aber 03:12.260 --> 03:13.180 immer noch nicht alle. 03:13.180 --> 03:14.080 Okay? 03:14.620 --> 03:14.960 Gut. 03:16.040 --> 03:18.060 Das ist das Fallgemeinerte Pumping Lemma. 03:18.120 --> 03:21.700 Ich habe nur die Änderung jetzt mal in blau hervorgehoben. 03:21.820 --> 03:28.120 Und zwar, die Idee ist, dass wir statt zu sagen, es gibt ein n, sodass 03:28.120 --> 03:32.780 jedes Wort auf den ersten n Zeichen ein pumpbares Stück hat, sagen wir 03:32.780 --> 03:37.620 jetzt einfach nur, dieses erste können eigentlich irgendwo n 03:37.620 --> 03:39.200 aufeinanderfolgende Zeichen sein. 03:39.200 --> 03:39.700 Okay? 03:39.800 --> 03:42.600 Es müssen nicht unbedingt die ersten n Zeichen sein, wo das pumpbare 03:42.600 --> 03:46.840 Stück ist, sondern egal, wo ich mein Beobachtungsfenster der Länge n 03:46.840 --> 03:50.860 hinschiebe, es gibt immer ein Stück, das pumpbar ist. 03:51.440 --> 03:51.740 Okay? 03:52.340 --> 03:53.060 Das ist die Idee. 03:54.100 --> 03:57.960 Also formal gesehen sagen wir, für jede reguläre Sprache existiert 03:57.960 --> 04:01.520 diese Zahl n, sodass Wörter, die lang genug sind, Länge mindestens n 04:01.520 --> 04:06.080 haben und egal, wo ich meine Beobachtung hinmache, das heißt für jede 04:06.080 --> 04:11.820 Darstellung des Wortes W in P, Y, S. 04:12.520 --> 04:16.340 Das heißt, Y ist mein Beobachtungsfenster der Länge n und P ist 04:16.340 --> 04:18.020 einfach was davor ist und S danach. 04:18.200 --> 04:21.520 Das interessiert mich nicht weiter, sondern das sagt mir einfach, das 04:21.520 --> 04:24.160 ist n aufeinanderfolgende Zeichen in dem Wort. 04:24.360 --> 04:28.660 Egal, welche n aufeinanderfolgenden Zeichen ich wähle, kann ich in 04:28.660 --> 04:33.060 diesem Teil jetzt ein pumpbares Mittelstück finden. 04:34.120 --> 04:36.380 Wieder, was U und X ist, ist mir egal. 04:36.520 --> 04:41.460 Es gibt dieses V da drin in dem Y, das ich aufpumpen kann, das darf 04:41.460 --> 04:42.280 nicht leer sein. 04:42.540 --> 04:45.220 Und davor ist U und dahinter ist X, eventuell sind die leer. 04:46.400 --> 04:47.580 Doch, die ist regulär. 04:47.660 --> 04:48.340 Sehr gute Frage. 04:49.800 --> 04:51.500 Und jetzt ist die Frage, warum gilt das Lemma? 04:54.540 --> 04:58.140 Das Lemma gilt, also wir müssen uns klar machen, es existiert zu 04:58.140 --> 05:06.100 dieser Sprache ein n, eine Zahl n, sodass für jedes Wort, was länger 05:06.100 --> 05:08.520 als n ist, eine ganz komplizierte Bedingung gilt. 05:09.220 --> 05:11.980 Jedes Wort, was in der Sprache ist und länger als n ist. 05:13.240 --> 05:16.580 Ich wähle für Ihre Sprache, die nur das eine Wort hat mit nur einem 05:16.580 --> 05:18.440 Symbol a, wähle ich n gleich zwei. 05:22.080 --> 05:25.200 Das n wird's tun, denn jedes Wort, was in der Sprache ist und 05:25.200 --> 05:28.920 mindestens zwei lang ist, erfüllt beliebige Bedingungen, weil es so 05:28.920 --> 05:29.680 eine Wörter nicht gibt. 05:29.680 --> 05:32.660 Also es ist so eine leere Prämisse und dann ist nichts mehr zu zeigen. 05:33.200 --> 05:36.720 Das heißt, jede endliche Sprache ist regulär, weil sie einfach n 05:36.720 --> 05:39.160 größer nehmen, als alle Wörter in der Sprache. 05:44.160 --> 05:45.120 So, wo waren wir? 05:45.340 --> 05:47.480 Also nochmal, wir haben es jetzt verallgemeinert. 05:47.540 --> 05:49.420 Wir haben gesagt, Wörter sind lang genug. 05:49.980 --> 05:52.560 Ich kann mir außerdem noch ein Beobachtungsfenster wählen. 05:52.640 --> 05:54.560 Das ist das Y, der Länge n. 05:54.680 --> 05:57.760 Und dann gibt es in dem Beobachtungsfenster diesen pumpbaren Teil, das 05:57.760 --> 06:01.420 ist das V, was dann beliebig oft gepumpt werden kann. 06:02.160 --> 06:04.880 Also hier unten ist es wieder mit Quantoren. 06:05.020 --> 06:08.880 Für alle L regulär existiert n aus natürlichen Zahlen, sodass für alle 06:08.880 --> 06:14.540 W aus der Sprache und Aufteilung von W im Mittelteil der Länge n und 06:14.540 --> 06:18.780 vorn und hinten irgendwas, existiert eine Aufteilung des Mittelteils 06:18.780 --> 06:22.520 in der Mittelteil des Mittelteils ist nicht leer und vorn und hinten 06:22.520 --> 06:28.360 ist halt der Rest, sodass für alle I die Mitte vom Mittelteil gepumpt 06:28.360 --> 06:30.540 werden kann und es bleibt in der Sprache. 06:31.900 --> 06:32.720 Okay, so. 06:33.300 --> 06:35.520 Das ist das verallgemeinerte ParmetGlamour. 06:36.780 --> 06:40.680 Und wir können das auch beweisen, ganz analog zu dem Beweis, den Sie 06:40.680 --> 06:43.960 in der letzten Vorlesung gesehen haben, wo wir einfach nur gesagt 06:43.960 --> 06:46.960 haben, auf den ersten n-Zeichen gibt es in dem endlichen Automaten ein 06:46.960 --> 06:47.360 Zykel. 06:47.800 --> 06:50.940 Jetzt sagen wir, wir müssen bloß diese Abarbeitung des Wortes nicht 06:50.940 --> 06:54.820 auf den ersten n-Zeichen machen, sondern auf die n-Zeichen, die uns 06:54.820 --> 06:56.240 unser Beobachtungsfenster gibt. 06:56.620 --> 07:00.320 Okay, aber wir machen es nochmal durch zur Wiederholung und ganz in 07:00.320 --> 07:00.880 Ruhe. 07:03.200 --> 07:06.900 Wir müssen, ich mache nochmal kurz eine Folie zurück, wir müssen diese 07:06.900 --> 07:07.920 Aussage hier zeigen. 07:08.240 --> 07:11.580 Und das ist ganz häufig so, dass wenn Sie was beweisen wollen, dass 07:11.580 --> 07:15.680 Ihre Aussagen sowas sind wie für alle existiert, für alle existiert, 07:15.740 --> 07:16.360 für alle gilt. 07:17.940 --> 07:20.580 Meistens sind die Aussagen nicht ganz so komplex, nicht mit so vielen 07:20.580 --> 07:22.660 Schachtelungen von für alle existiert. 07:22.840 --> 07:25.900 Meistens ist es ganz simpel irgendwie, für alle regulären Sprachen 07:25.900 --> 07:29.200 existiert ein endlicher Automat, so das gilt, der akzeptiert die 07:29.200 --> 07:29.600 Sprache. 07:30.520 --> 07:35.160 Aber im Allgemeinen hat man immer es mit solchen Sachen zu tun. 07:35.700 --> 07:39.180 Und wenn Sie sowas nachweisen wollen, jetzt als Beweis oder dann 07:39.180 --> 07:42.480 später, wenn wir es widerlegen, dann lege ich Ihnen ans Herz, sehen 07:42.480 --> 07:44.800 Sie das als eine Art Spiel. 07:46.280 --> 07:49.140 Es gibt den für alle Spieler und es gibt den existiert Spieler. 07:49.140 --> 07:51.440 Der für alle Spieler ist der böse Gegenspieler. 07:51.740 --> 07:54.480 Der kann wählen, was er möchte. 07:55.260 --> 07:56.880 Und der existiert Spieler, das sind Sie. 07:57.480 --> 08:00.700 Sie können wählen, sodass es gut für Sie ist. 08:01.380 --> 08:04.060 Ihr Ziel ist es, am Ende dieses gilt zu zeigen. 08:05.580 --> 08:07.940 Der für alle Spieler möchte das verhindern. 08:08.440 --> 08:09.740 Und der existiert Spieler, das sind Sie. 08:09.940 --> 08:10.980 Sie wollen das hinkriegen. 08:11.220 --> 08:12.740 Und dann sehen Sie das wirklich wie ein Spiel. 08:12.880 --> 08:16.420 Für alle Züge meines Gegenspielers gibt es einen geeigneten Zug für 08:16.420 --> 08:19.680 mich, sodass, egal für alle Züge des Gegenspielers, es einen 08:19.680 --> 08:21.120 geeigneten Zug für mich gibt. 08:22.020 --> 08:24.860 Und natürlich, Sie sehen immer den Zug des Gegenspielers und der 08:24.860 --> 08:27.000 Gegenspieler sieht Ihren Zug, was Sie gewählt haben. 08:27.840 --> 08:29.240 Behalten Sie das vielleicht im Kopf. 08:30.740 --> 08:34.040 Also, wir fangen an, es fängt an mit für alle. 08:34.800 --> 08:37.240 Der Gegenspieler wählt eine Sprache, die ist regulär. 08:37.340 --> 08:38.960 Sie haben keinen Einfluss darauf, welche. 08:39.540 --> 08:42.760 Der gültige Zug des Spielers ist reguläre Sprache. 08:42.760 --> 08:45.880 Sie können dann aber sehen, welche reguläre Sprache das ist. 08:46.660 --> 08:47.820 Und können darauf reagieren. 08:48.000 --> 08:50.220 Wir müssen jetzt das N finden. 08:50.660 --> 08:51.620 Und wie reagieren wir darauf? 08:51.720 --> 08:54.340 Wir gucken uns an den Zug des Spielers, wir gucken uns die reguläre 08:54.340 --> 08:54.980 Sprache an. 08:55.360 --> 08:58.600 Wir gucken uns an einen endlichen Automaten, der die Sprache erkennt. 08:58.720 --> 09:01.020 Wir wissen nach dem Satz von Clean, dass der existiert. 09:01.740 --> 09:04.500 Und wir gucken uns zu diesem endlichen Automaten an, wie viele 09:04.500 --> 09:05.460 Zustände der hat. 09:05.800 --> 09:06.860 Und das sei unser N. 09:07.500 --> 09:08.540 Das ist unsere Antwort. 09:10.340 --> 09:11.980 Wir haben das N gefunden. 09:12.200 --> 09:14.380 Jetzt ist wieder der Gegenspieler dran mit Nimmt für alle. 09:15.040 --> 09:16.620 Und zwar muss er uns ein Wort geben. 09:17.120 --> 09:18.400 Das muss in der Sprache sein. 09:18.760 --> 09:20.540 Das muss mindestens N lang sein. 09:20.740 --> 09:23.360 Und er gibt uns das Wort auch noch mit einem Beobachtungsfenster. 09:23.860 --> 09:25.020 Y der Länge N. 09:26.080 --> 09:28.400 Wir haben keinen Einfluss darauf, was für ein Wort er nimmt. 09:29.800 --> 09:31.320 Also, gucken wir uns das Wort an. 09:31.940 --> 09:33.460 Das ist halt irgendein langes Wort. 09:34.480 --> 09:37.200 Und wir wissen nur, das Wort liegt in der Sprache. 09:37.200 --> 09:42.420 Das heißt, wenn dieser endliche Automat dieses Wort abarbeitet, wird 09:42.420 --> 09:43.960 er in einem N-Zustand landen. 09:44.100 --> 09:45.640 In einem akzeptierenden N-Zustand. 09:46.320 --> 09:49.180 Und wir wissen auch, irgendwann in dieser Abarbeitung macht der 09:49.180 --> 09:53.220 Automat, prozessiert er diesen Mittelteil Y, der uns auch gegeben 09:53.220 --> 09:56.220 wurde von unserem Gegenspieler. 09:57.500 --> 10:05.760 Das heißt, diese N-Übergänge, die für die N-Zeichen aus Y stehen, sind 10:05.760 --> 10:09.080 immer Übergänge von der Form, sagen wir mal, der erste Übergang macht 10:09.080 --> 10:11.560 von einem Zustand Q0 auf Q1. 10:11.780 --> 10:12.660 Das ist der erste Übergang. 10:12.860 --> 10:15.120 Und der zweite Übergang ist von Q1 auf Q2. 10:15.280 --> 10:17.480 Und der dritte ist von Q2 auf Q3 und so weiter. 10:17.920 --> 10:20.600 Und der I-te ist von QI-1 auf QI. 10:21.620 --> 10:24.700 Dann haben wir also diese Zustände, 0 bis N. 10:25.520 --> 10:28.120 Das sind N plus 1 Zustände, die könnten sich wiederholen. 10:28.260 --> 10:31.260 Das ist einfach nur, was die einzelnen Schritte, was der Automat bei 10:31.260 --> 10:32.280 der Abarbeitung da tut. 10:35.360 --> 10:37.040 Jetzt muss ich umblättern. 10:37.440 --> 10:38.860 Wir sind aber hier gerade. 10:39.040 --> 10:43.380 Das sind Q0 bis QN, N plus 1 Zustände, die bei der Abarbeitung von Y 10:43.380 --> 10:45.460 von diesem Beobachtungsfenster durchlaufen werden. 10:46.820 --> 10:50.960 Jetzt erinnern wir uns, da wir N als die Anzahl der Zustände gewählt 10:50.960 --> 10:54.500 haben, unseres Automatens, und wir hier N plus 1 von diesen Zuständen 10:54.500 --> 10:58.040 haben, wissen wir, naja, okay, da muss eine Doppelung vorkommen. 10:58.040 --> 11:03.940 Das heißt, irgendwie wird gelaufen in diesem Bild des Automatens und 11:03.940 --> 11:07.040 irgendwie müssen wir da so eine Art Kreis drin finden. 11:07.760 --> 11:12.920 Also es gibt eine Teilsequenz davon, die einem Zykel entspricht. 11:13.440 --> 11:15.780 Und das ist diese Teilsequenz, wenn wir die jetzt wieder 11:15.780 --> 11:19.460 uminterpretieren als was ist denn das Teilwort, was gerade da gelesen 11:19.460 --> 11:20.520 wird, das ist dieses V. 11:23.820 --> 11:25.620 Okay, also das ist unsere Antwort. 11:25.840 --> 11:29.900 Wir waren ja auf der Suche nach der Aufteilung des Mittelteils in U, 11:29.900 --> 11:33.540 V, X, also insbesondere in dieses V und dann U ist halt alles davor 11:33.540 --> 11:34.580 und X ist alles dahinter. 11:35.460 --> 11:36.480 Und das haben wir jetzt geschafft. 11:36.600 --> 11:39.000 Wir haben uns angeguckt, wie wird das Wort im Automaten gemacht, 11:39.140 --> 11:42.120 insbesondere wie wird der Mittelteil im Automaten durchlaufen. 11:42.820 --> 11:46.620 Dadurch, dass es da zu viele gibt, also mehr als Zustände, muss es ein 11:46.620 --> 11:50.240 Zykel geben und der Zykel ist das, was uns den Mittelteil gibt, das V 11:50.240 --> 11:50.520 gibt. 11:51.320 --> 11:54.500 Gut, also wir haben insbesondere diese Aufteilung gefunden. 11:54.720 --> 11:55.620 V ist nicht leer. 11:56.580 --> 11:58.120 Und jetzt ist der Gegenspieler wieder dran. 11:59.280 --> 12:03.080 Er hat jetzt die Aufteilung gesehen und wählt jetzt ein besonders 12:03.080 --> 12:03.720 fieses I. 12:06.860 --> 12:08.480 Und wir haben keine Kontrolle darüber. 12:08.580 --> 12:09.200 Er kann irgendwas machen. 12:09.280 --> 12:12.400 Er kann I gleich 1, I gleich 0, I gleich 17, I gleich 42 wählen. 12:12.400 --> 12:19.220 Er wählt jetzt irgendein I und wir müssen jetzt zeigen, dass dann das 12:19.220 --> 12:23.420 gilt, nämlich dass dieses V I mal gepumpt immer noch in der Sprache 12:23.420 --> 12:23.660 ist. 12:24.100 --> 12:29.360 Und dann sagen wir aber, naja okay, wir laufen durch, durch den 12:29.360 --> 12:34.440 Automaten P und U, so wie in dem ursprünglichen Wort das auch gemacht 12:34.440 --> 12:34.740 wurde. 12:35.100 --> 12:38.040 Und jetzt ist der Punkt, wo das erste Mal dieser Zykel durchlaufen ist 12:38.040 --> 12:40.000 und dann durchlaufen wir den halt I mal. 12:40.640 --> 12:43.500 Egal was von I er uns gibt, wenn es 17 ist, dann durchlaufen wir den 12:43.500 --> 12:44.500 Zykel halt 17 mal. 12:45.100 --> 12:48.120 Und am Ende sind wir wieder genau dort und können mit X S 12:48.120 --> 12:48.800 weitermachen. 12:49.600 --> 12:54.440 Und da das mit dem Zykel, mit einmal dem Zykel, in einem Endzustand am 12:54.440 --> 12:57.760 Ende gelandet ist, ist es auch mit I mal dem Zykel in einem Endzustand 12:57.760 --> 12:58.760 gelandet. 12:59.220 --> 13:00.760 Das heißt, das bleibt in der Sprache. 13:03.080 --> 13:03.800 Beweis abgeschlossen. 13:06.300 --> 13:07.680 Okay, das war der Beweis. 13:09.580 --> 13:13.580 Anwenden werden wir das, wie gesagt, genau andersherum. 13:14.080 --> 13:19.200 Dass wir damit zeigen, dass eine Sprache nicht regulär sein kann, weil 13:19.200 --> 13:22.060 sie ja gar nicht das verallgemeinerte Pumping Lemma erfüllt. 13:23.460 --> 13:28.660 Das heißt, wir müssen die Aussage des Pumping Lemmas, die ist hier 13:28.660 --> 13:31.820 oben nochmal kurz dargestellt, wir müssen die Aussage widerlegen. 13:32.640 --> 13:35.820 Wir müssen die Negierung, die Negation der Aussage beweisen. 13:35.820 --> 13:38.160 Also nochmal, was ist die Aussage? 13:39.220 --> 13:44.840 Die Aussage des Pumping Lemmas für eine Sprache L sagt, es gibt ein N 13:44.840 --> 13:48.880 für diese Sprache L, sodass für alle Wörter aus der Sprache und alle 13:48.880 --> 13:52.760 Aufteilungen in Beobachtungsfenster Y der Länge N und vorn und hinten 13:52.760 --> 13:57.500 gibt es eine Aufteilung des Beobachtungsfensters im Mittelteil und 13:57.500 --> 14:00.660 davor und danach, der Mittelteil ist nicht leer, sodass für jedes I 14:00.660 --> 14:03.600 dieser Mittelteil gepumpt werden kann, sodass das ganze Wort immer 14:03.600 --> 14:05.320 noch in der Sprache ist. 14:06.040 --> 14:07.900 Und jetzt müssen wir widerlegen. 14:09.680 --> 14:14.880 Und dafür haben wir ein Beispiel hier, das ist, ich glaube, Sie haben 14:14.880 --> 14:17.420 die Sprache auch schon gesehen, letzte Vorlesung, weiß ich nicht 14:17.420 --> 14:17.700 genau. 14:18.060 --> 14:21.400 Also das Alphabet ist 0 1, wie üblich, und die Sprache ist gegeben, 14:21.480 --> 14:25.940 als alle Wörter über diesem Alphabet, die entweder nur aus Einsen 14:25.940 --> 14:32.980 bestehen oder eine Folge von Nullen haben, gefolgt von Quadratzahl 14:32.980 --> 14:35.800 vielen Einsen für eine bestimmte, für irgendeine Quadratzahl. 14:36.720 --> 14:40.380 Also irgendwie entweder nur Einsen und dann ist mir egal wie viele 14:40.380 --> 14:44.860 oder irgendwelche Nullen, egal wie viele und danach muss eine Anzahl 14:44.860 --> 14:47.420 von Einsen kommen, die wirklich, aber die muss eine Quadratzahl sein, 14:47.500 --> 14:50.040 also entweder 1, 4, 9 und so weiter. 14:53.700 --> 14:57.180 Und danach, das war es dann auch, die Wörter bestehen wirklich nur aus 14:57.180 --> 14:59.920 Einsen oder nur aus einem String Nullen und gefolgt von einem String 14:59.920 --> 15:00.820 Einsen und nichts anderes. 15:01.220 --> 15:02.000 Okay, das ist eine Sprache. 15:03.440 --> 15:07.580 Und für diese Sprache wollen wir jetzt die Aussage des Pumping Lemmas 15:07.580 --> 15:08.500 widerlegen. 15:09.420 --> 15:12.500 Das heißt, das haben Sie auch gelernt beim letzten Mal, wenn wir eine 15:12.500 --> 15:16.700 Aussage negieren, können wir die so nehmen und müssen die Quantoren 15:16.700 --> 15:17.240 umdrehen. 15:17.240 --> 15:18.960 Wir tauschen die Rollen in dem Spiel. 15:19.220 --> 15:22.340 Wir sind jetzt derjenige, der für das N zuständig ist. 15:23.140 --> 15:25.360 Wir sind nicht mehr derjenige, der für das N zuständig ist. 15:25.460 --> 15:28.900 Es ist jetzt für alle N existiert ein Wort, sodass für alle 15:28.900 --> 15:30.900 Zerlegungen existiert ein I. 15:31.440 --> 15:35.400 Also wir müssen jetzt das Wort wählen und das I wählen. 15:36.640 --> 15:39.520 Nicht wie gerade im Beweis, sondern genau die anderen Rollen. 15:40.300 --> 15:43.900 Und dann ist unser Ziel jetzt, wir sind jetzt böse Gegenspieler, wir 15:43.900 --> 15:45.920 müssen das hier hinten nicht erfüllen. 15:46.300 --> 15:47.760 Das soll nicht in der Sprache sein. 15:49.060 --> 15:50.260 Okay, also machen wir das. 15:52.040 --> 15:54.080 Wir fangen also an mit für alle N. 15:54.220 --> 15:56.160 Ich rede über die negierte Aussage. 15:56.240 --> 15:56.920 Für alle N. 15:57.220 --> 15:59.580 Das heißt, der Gegenspieler wählt das N, wir haben keine Kontrolle 15:59.580 --> 15:59.980 darüber. 16:00.700 --> 16:01.300 Irgendein N. 16:02.960 --> 16:04.380 Wir sehen das N dann aber. 16:04.820 --> 16:06.780 Jetzt sind wir dran, existiert ein Wort. 16:07.060 --> 16:10.740 Also wir sehen das N und wir wählen ein Wort, müssen uns aber an die 16:10.740 --> 16:11.640 Spielregeln halten. 16:11.640 --> 16:14.760 Nämlich das Wort muss erstmal in der Sprache sein. 16:15.300 --> 16:17.860 Es muss mindestens N lang sein. 16:17.960 --> 16:21.180 Wir müssen das Wort mit einem Mittelteil der Größe N geben. 16:22.340 --> 16:23.200 Das war's. 16:23.620 --> 16:24.440 Das sind die Regeln. 16:24.620 --> 16:28.340 Also ich sehe das N vom Gegenspieler und basierend auf diesem N wähle 16:28.340 --> 16:29.080 ich mein Wort. 16:29.220 --> 16:33.860 Und zwar wähle ich 0 hoch N, 1 hoch N². 16:35.880 --> 16:38.280 Das liegt in der Sprache. 16:38.280 --> 16:40.340 Ich muss mich an die Regeln halten. 16:40.440 --> 16:42.080 Das ist nämlich von dieser zweiten Form. 16:42.180 --> 16:44.980 Irgendeine Anzahl von Nullen gefolgt von einer Quadratzahl Anzahl von 16:44.980 --> 16:45.320 Einsen. 16:46.940 --> 16:51.680 Und ich gebe jetzt aber das Wort mit einem Mittelteil mit. 16:52.160 --> 16:55.240 Und zwar sage ich, mein Mittelteil sind die ersten N Einsen. 16:56.600 --> 16:58.100 Die ersten N Einsen. 16:58.520 --> 17:01.860 Davor ist dann also diese N Nullen und dahinter ist halt die 17:01.860 --> 17:03.380 restlichen Einsen. 17:03.680 --> 17:04.680 Das ist mein Mittelteil. 17:05.360 --> 17:10.760 Ich zeige jetzt auf diesem Mittelteil und sage, da bitte drin finde 17:10.760 --> 17:12.020 ein Stück, was du pumpen kannst. 17:14.360 --> 17:16.740 Jetzt ist unser Gegenspieler dran. 17:16.880 --> 17:21.620 Das heißt, der Gegenspieler wählt die Zerlegung des Mittelteils in 17:21.620 --> 17:22.640 UVX. 17:23.180 --> 17:24.040 V, der pumpbare Teil. 17:24.680 --> 17:26.020 Wir haben keine Kontrolle darüber. 17:26.200 --> 17:27.700 Ich weiß nur, er hält sich an die Regeln. 17:27.840 --> 17:28.980 Das heißt, das V ist nicht leer. 17:30.400 --> 17:32.160 Gut, er hat nicht so viele Möglichkeiten. 17:32.160 --> 17:34.900 Das Wort, der Mittelteil hier, unser Beobachtungsfenster ist nur 17:34.900 --> 17:35.520 Einsen. 17:35.820 --> 17:39.640 Also er macht halt irgendeine Anzahl von Einsen in das V und das U und 17:39.640 --> 17:40.000 das X. 17:40.160 --> 17:41.980 Wobei er mindestens eine in das V reintut. 17:43.700 --> 17:45.260 Und jetzt sind wir wieder dran. 17:45.780 --> 17:47.000 Wir dürfen das I wählen. 17:48.800 --> 17:52.240 Und wir könnten jetzt tatsächlich sehen, wie aufgeteilt wurden und 17:52.240 --> 17:53.780 basieren darauf das I wählen. 17:53.860 --> 17:55.900 Aber tatsächlich funktioniert hier immer I gleich 2. 17:56.220 --> 17:57.960 Egal, wie das aufgeteilt wurde davor. 17:58.680 --> 18:00.140 Also ich wähle I gleich 2. 18:00.840 --> 18:04.280 Und sage, dann gilt das hier hinten nicht mehr. 18:04.440 --> 18:06.520 Das heißt, ich bin in der Sprache gestartet. 18:06.700 --> 18:10.520 Aber mit diesem Pumpschritt bin ich aus der Sprache rausgefallen. 18:10.680 --> 18:11.660 Warum ist das so? 18:12.100 --> 18:15.340 Also ich habe hier irgendeine Anzahl von Einsen gepumpt. 18:16.160 --> 18:16.680 A. 18:17.540 --> 18:19.400 Und ich weiß, das ist mindestens Eins. 18:19.480 --> 18:23.640 Das ist nämlich das, was in den pumpbaren Teilen von Gegenspieler 18:23.640 --> 18:24.180 getan wurde. 18:24.280 --> 18:26.740 Das ist irgendwas zwischen Eins und N. 18:27.580 --> 18:29.420 Unser Beobachtungsfenster war ja nur N lang. 18:30.020 --> 18:31.720 Und er darf nicht leer machen. 18:31.960 --> 18:33.160 Also irgendwas zwischen Eins und N. 18:33.760 --> 18:37.260 Das heißt, ich lande am Ende, wenn ich das jetzt gepumpt habe, bei 18:37.260 --> 18:38.560 einem Wort, das sieht so aus. 18:38.660 --> 18:40.040 Immer noch 0 hoch N. 18:40.720 --> 18:44.500 Und dann habe ich jetzt A Einsen dazu bekommen. 18:44.600 --> 18:46.000 Weil ich genau, ich habe es verdoppelt. 18:46.320 --> 18:47.720 Diese A Einsen. 18:48.860 --> 18:53.860 Und jetzt ist aber die Sache, dass das hier hinten keine Quadratzahl 18:53.860 --> 18:57.140 mehr sein kann, wenn A zwischen Eins und N ist. 18:57.140 --> 19:01.940 Weil die nächste Quadratzahl von N Quadrat ist entfernt, weiß ich 19:01.940 --> 19:05.440 nicht, so was wie 2N-1 oder so, bis zur nächsten Quadratzahl. 19:05.600 --> 19:08.160 Also auf jeden Fall mehr, der Abstand zur nächsten Quadratzahl ist 19:08.160 --> 19:08.680 mehr als N. 19:10.940 --> 19:11.200 Okay. 19:11.960 --> 19:14.900 Deswegen habe ich es geschafft, aus der Sprache rauszufallen. 19:14.940 --> 19:17.300 Und ich habe die Aussage des Pampelingeners widerlegt. 19:17.940 --> 19:19.980 Also ist diese Sprache nicht regulär. 19:22.480 --> 19:22.880 Okay. 19:24.400 --> 19:27.860 Ganz wichtig, machen Sie sich klar, wer für welche Quantoren zuständig 19:27.860 --> 19:30.540 ist, was Ihr Gegenspieler macht und was Sie machen. 19:31.660 --> 19:35.600 Das bringt Ihnen, üblicherweise werden Sie nur noch Pampelingen Lämmer 19:35.600 --> 19:36.380 widerlegen. 19:37.360 --> 19:41.620 Das heißt, Sie werden niemals Einfluss auf die Zerlegung UVX haben. 19:41.840 --> 19:43.760 UVX macht immer der Gegenspieler. 19:44.420 --> 19:44.760 Nicht Sie. 19:49.460 --> 19:52.100 So, das war das verallgemeinerte Pampelingen Lämmer. 19:54.780 --> 19:59.840 Jetzt kommt ein Teilkapitel von endlichen Automaten. 19:59.980 --> 20:02.260 Und zwar geht es um Automaten Minimierung. 20:02.480 --> 20:05.920 Sie haben ja ein paar Automaten gesehen zu endlichen Sprachen. 20:06.000 --> 20:08.120 Die waren immer halbwegs klein. 20:08.280 --> 20:09.320 Die waren eigentlich sehr klein. 20:09.620 --> 20:12.460 Die haben immer auf die Folien hier gepasst oder auf Ihre 20:12.460 --> 20:13.280 Hausaufgabenblätter. 20:14.060 --> 20:16.220 Vielleicht, wenn Sie ein paar Hausaufgaben gemacht haben, haben Sie 20:16.220 --> 20:20.320 auch mal gemerkt, wie schnell unübersichtlich und groß die Automaten 20:20.320 --> 20:20.600 werden. 20:20.600 --> 20:26.380 Es ist an sich sinnvoll, eine Methode zu haben, Automaten zu 20:26.380 --> 20:29.220 minimieren, im Sinne von Anzahl Zustände zu minimieren. 20:30.120 --> 20:33.580 Und dazu werden wir insbesondere den Äquivalenzklassenautomaten 20:33.580 --> 20:35.560 kennenlernen, der genau das tut. 20:37.040 --> 20:39.960 Also die Frage ist, kann man die Anzahl der Zustände von einem 20:39.960 --> 20:45.140 gegebenen deterministischen endlichen Automaten irgendwie konstruktiv 20:45.140 --> 20:45.560 minimieren? 20:45.720 --> 20:48.100 Also jemand gibt Ihnen einen Automaten und sagt, er tut schon die 20:48.100 --> 20:51.500 richtige Sprache, er akzeptiert schon die richtige Sprache, aber 20:51.500 --> 20:53.460 irgendwie ist der so kompliziert, der ist so riesig. 20:53.920 --> 20:55.720 Kann ich das nicht irgendwie kleiner machen? 20:56.220 --> 21:01.160 Und da gibt es ein paar einfache Sachen, zum Beispiel überflüssige 21:01.160 --> 21:02.520 Zustände zu identifizieren. 21:03.500 --> 21:06.080 Sie könnten einen Automaten haben und das ist ein Zustand überflüssig, 21:06.540 --> 21:09.160 weil der überhaupt nicht erreichbar ist vom Startzustand. 21:09.360 --> 21:12.400 Der wird niemals durch irgendeine Abarbeitung in so einen Zustand 21:12.400 --> 21:12.680 kommen. 21:13.200 --> 21:16.960 So einen überflüssigen Zustand können Sie dann natürlich entfernen. 21:16.960 --> 21:18.120 Also hier ist ein kleines Beispiel. 21:18.800 --> 21:20.300 Hier ist der Startzustand, dieses S. 21:21.540 --> 21:25.900 Und Sie sehen relativ schnell ein, dass alles was grau ist, kann 21:25.900 --> 21:31.100 erreicht werden von S aus und hier unten dieses Zeug kann überhaupt 21:31.100 --> 21:34.540 nicht erreicht werden vom Startzustand aus. 21:34.760 --> 21:38.040 Das heißt, die beiden weißen Zustände hier unten sind überflüssig und 21:38.040 --> 21:39.760 die kann ich einfach entfernen. 21:40.480 --> 21:43.460 Und algorithmisch ist es auch nicht schwierig, wenn Ihnen jemand 21:43.460 --> 21:47.480 diesen endlichen Automaten als Eingabe gibt, diese überflüssigen 21:47.480 --> 21:48.980 Zustände zu finden. 21:49.500 --> 21:51.840 Das kann mit einer Tiefensuche gemacht werden. 21:52.320 --> 21:57.520 Also DFS, Steps First Search, in dem gerichteten Graphen, der diesem 21:57.520 --> 22:02.380 Automaten entspricht, kann alle nicht überflüssigen Zustände, also 22:02.380 --> 22:05.220 alle erreichbaren Zustände finden. 22:05.880 --> 22:08.140 Starten Sie eine Tiefensuche oder eine breite Suche, irgendeine Suche 22:08.140 --> 22:12.260 vom Start von S aus und alles was Sie finden ist nicht überflüssig und 22:12.260 --> 22:13.420 den Rest schmeißen Sie weg. 22:14.960 --> 22:21.840 Das heißt, das kann in Linearzeit gemacht werden, in der Größe der 22:21.840 --> 22:24.920 Kanten in dem Automaten. 22:26.100 --> 22:28.160 Wie viele Kanten hat so ein Automat? 22:28.240 --> 22:33.060 Sie haben Q Zustände und Sie haben eine ausgehende Kante für jedes 22:33.060 --> 22:34.500 Zeichen in Ihrem Alphabet. 22:35.100 --> 22:36.580 Also Q mal Sigma. 22:37.940 --> 22:41.460 Das ist die Laufzeit für die Tiefensuche. 22:43.820 --> 22:47.580 Das klingt ja schon mal ganz gut, so könnte man vielleicht wirklich 22:47.580 --> 22:51.480 ein paar Zustände loswerden, aber das ist eventuell immer noch nicht 22:51.480 --> 22:52.840 das Beste, was man machen kann. 22:52.900 --> 22:57.320 Man kann eventuell noch einen Automaten verkleinern, der gar keine 22:57.320 --> 22:58.500 überflüssigen Zustände hat. 22:58.600 --> 22:59.380 Und hier ist ein Beispiel. 23:00.420 --> 23:01.720 Der linke Automat. 23:06.440 --> 23:08.040 Wie der Alphabet ist 0,1. 23:08.480 --> 23:10.700 Und vielleicht gucken wir erstmal nur auf den linken Automaten und 23:10.700 --> 23:12.440 überlegen uns, was das denn so tut. 23:13.580 --> 23:21.540 Der Startzustand hier ist grün und wir können von dort aus 0 oder 1 23:21.540 --> 23:21.840 lesen. 23:21.940 --> 23:23.160 Unser Alphabet ist 0,1. 23:23.320 --> 23:25.400 Wenn ich eine 0 lese, komme ich in diesen roten Zustand. 23:25.520 --> 23:27.780 Wenn ich eine 1 lese, komme ich in diesen blauen Zustand. 23:28.640 --> 23:31.680 Und wenn ich jetzt wieder eine 0 lese, also wenn ich zwei 0 23:31.680 --> 23:34.480 hintereinander lese, dann lande ich in dem grünen Zustand hier. 23:35.900 --> 23:40.860 Oder wenn ich zwei 1 lese, dann lande ich in dem grünen Zustand hier. 23:42.280 --> 23:46.120 Wenn ich aber nach einer 0 eine 1 oder nach einer 1 eine 0 lese, dann 23:46.120 --> 23:46.660 bin ich hier. 23:47.080 --> 23:51.080 Und wenn ich auch hier zwei 0 lese, bin ich in dem blauen Zustand. 23:51.200 --> 23:54.180 Solange bis ich meine zweite 1 aufgesammelt habe, bin ich wieder grün. 23:54.180 --> 23:56.960 Also wenn Sie noch ein bisschen scharf hingucken und auch so wie er 23:56.960 --> 24:00.140 hingezeichnet ist, der Automat mit den Farben, das hilft auch ganz 24:00.140 --> 24:07.980 gut, sehen Sie, dass Sie in dem grünen Zustand landen, wenn die Anzahl 24:07.980 --> 24:14.640 der Nullen gerade ist und die Anzahl der Einsen auch gerade ist, die 24:14.640 --> 24:15.320 Sie gelesen haben. 24:16.640 --> 24:23.080 Also Sie starten mit keiner Eins, reden wir mal über Einsen. 24:23.080 --> 24:31.000 Das heißt, in der ersten Zeile hat man eine gerade Anzahl von Einsen. 24:31.740 --> 24:34.800 In der zweiten Zeile hat man eine ungerade Anzahl von Einsen. 24:35.220 --> 24:37.640 Solange Sie nur Nullen lesen, bleiben Sie hier in der ersten Zeile. 24:38.760 --> 24:41.000 Und sobald Sie die erste Eins lesen, kommen Sie runter in die zweite 24:41.000 --> 24:41.380 Zeile. 24:41.840 --> 24:43.500 Und da bleiben Sie auch, solange Sie Nullen lesen. 24:43.860 --> 24:45.560 Und wenn Sie jetzt wieder eine Eins lesen, dann kommen Sie in die 24:45.560 --> 24:46.080 dritte Zeile. 24:46.200 --> 24:48.460 Das heißt, in der dritten Zeile hatten wir wieder gerade viele Einsen 24:48.460 --> 24:49.440 und so weiter. 24:49.720 --> 24:51.740 Wenn Sie jetzt wieder eine Eins lesen, kommen Sie in die vierte und 24:51.740 --> 24:53.740 dann gibt es hier diese langen wieder nach oben in die erste. 24:54.940 --> 24:57.780 Das heißt, letztendlich erkennt Ihr einfach nur die Sprache. 24:58.280 --> 25:02.680 Dort unten, die Anzahl der Nullen in dem Wort und die Anzahl der 25:02.680 --> 25:08.580 Einsen in dem Wort ist Mod 2 gleich 0, was einfach fancy ist für 25:08.580 --> 25:09.020 gerade. 25:12.860 --> 25:17.440 Aber irgendwie ist auch schon klar, dass es relativ unnütz ist. 25:17.440 --> 25:20.920 Achso, vielleicht sollte man noch sagen, die Grünen sind natürlich 25:20.920 --> 25:24.420 die, die jetzt in den ungeraden Zeilen und ungeraden Spalten sind, 25:24.540 --> 25:28.840 also die genau gerade Einsen und gerade Nullen haben, die akzeptieren 25:28.840 --> 25:29.400 den Zustände. 25:30.220 --> 25:34.940 Und trotzdem ist der ja unnötig groß, weil der hier das gleiche tun 25:34.940 --> 25:35.220 würde. 25:37.680 --> 25:41.520 Ich brauche wirklich nur eine Spalte für gerade viele Einsen und 25:41.520 --> 25:47.400 gerade viele Nullen und ungerade viele Nullen und Zeilen für die 25:47.400 --> 25:47.980 Einsen. 25:49.340 --> 25:53.120 Jetzt ist die Frage, wie kommt man ganz algorithmisch und konstruktiv 25:53.120 --> 25:55.980 von hier nach dort, ohne jetzt nur scharfes Hinsehen zu machen. 25:56.620 --> 25:59.500 Und da gibt es zum Glück wirklich eine Methode, die immer 25:59.500 --> 26:00.040 funktioniert. 26:00.680 --> 26:03.220 Und das ist der Äquivalenzklassenautomat. 26:04.700 --> 26:07.700 Also, dafür reden wir über Äquivalenz. 26:07.700 --> 26:13.820 Wir wollen darüber reden, wann zwei Zustände eines gegebenen Automaten 26:13.820 --> 26:15.320 äquivalent sind. 26:16.100 --> 26:20.480 Und dann ist die Idee, wenn die äquivalent sind, was so etwas wie 26:20.480 --> 26:25.220 gleichwertig bedeutet, dann können wir auch einen davon sparen und die 26:25.220 --> 26:27.160 sozusagen aufeinander legen, die Zustände. 26:28.600 --> 26:30.240 Und was soll Äquivalenz heißen? 26:30.300 --> 26:35.500 Äquivalenz heißt, unabhängig von der Vorgeschichte, wenn ich in den 26:35.500 --> 26:43.100 beiden Zuständen bin, dann unterscheidet sich nicht mehr das 26:43.100 --> 26:44.720 Akzeptanzverhalten ab hier. 26:45.680 --> 26:50.020 Das heißt, egal was ich jetzt lese, es ist wurscht, ob ich von hier 26:50.020 --> 26:55.340 starte oder von hier starte, es landet in dem Endzustand hier oben, 26:55.480 --> 26:57.780 genau dann, wenn es in dem Endzustand hier unten landet. 26:58.440 --> 27:02.220 Das heißt, ich könnte sozusagen, zwei Zustände sind äquivalent, wenn 27:02.220 --> 27:05.980 ich den einen Zustand erreiche und mich beamen dürfte zum anderen 27:05.980 --> 27:07.480 Zustand und ich mache damit nichts kaputt. 27:08.300 --> 27:12.160 Weil ab dort ist es eh egal, ob ich in dem einen oder in dem anderen 27:12.160 --> 27:12.360 bin. 27:12.520 --> 27:14.040 Das ist so die grobe Idee. 27:15.640 --> 27:20.580 Als Beispiel wäre die Färbung von dem letzten Automaten auf der 27:20.580 --> 27:21.160 letzten Folie. 27:21.840 --> 27:23.420 Hier ist die formale Definition. 27:24.720 --> 27:26.820 Wir haben einen endlichen Automaten. 27:27.980 --> 27:30.000 Wir haben Zustände p und q. 27:31.160 --> 27:35.880 Und wir sagen, p ist äquivalent zu q und wir schreiben das mit so drei 27:35.880 --> 27:36.760 Gleichheitszeichen. 27:36.840 --> 27:38.960 Sie müssen jetzt ein bisschen aufpassen, wenn wir die 27:38.960 --> 27:42.260 Gleichheitsstriche zählen, weil manchmal steht der äquivalent und 27:42.260 --> 27:42.900 manchmal ist gleich. 27:44.100 --> 27:51.360 Also p ist äquivalent zu q, wenn für alle Wörter w gilt, wenn ich die 27:51.360 --> 27:57.660 Übergangsfunktion folge, von p startend das Wort w lesend, dann lande 27:57.660 --> 28:01.440 ich in f, also in einem akzeptierenden Endzustand, genau dann, wenn 28:01.440 --> 28:05.800 ich das gleiche tue, wenn ich von q starte und die Zeichen in w lese. 28:06.100 --> 28:07.260 Dann lande ich auch in f. 28:09.140 --> 28:12.580 Ich lande nicht unbedingt im gleichen Zustand, aber ich akzeptiere auf 28:12.580 --> 28:15.400 der linken Seite, wenn ich auf der rechten Seite akzeptiere und wenn 28:15.400 --> 28:18.180 ich auf der linken Seite nicht akzeptiere, dann akzeptiere ich auf der 28:18.180 --> 28:19.140 rechten Seite nicht. 28:20.820 --> 28:23.100 Gut, also es geht ja nur ums Akzeptanzverhalten. 28:26.400 --> 28:30.420 Okay, also das ist die Definition von äquivalenten Zuständen. 28:30.520 --> 28:34.960 Ab hier ist es egal, ich könnte sozusagen einfach einmal springen zu 28:34.960 --> 28:35.360 einem anderen. 28:37.340 --> 28:41.860 Das ist eine Äquivalenzrelation und dann bezeichnen wir so mit eckigen 28:41.860 --> 28:46.200 Klammern um einen Zustand die Äquivalenzklasse eines Zustands. 28:46.400 --> 28:48.080 Also was heißt das, Äquivalenzrelation? 28:48.500 --> 28:52.300 Das heißt, damit habe ich meine Zustände aufgeteilt in Gruppen. 28:53.320 --> 28:54.800 Das sind die Äquivalenzklassen. 28:55.100 --> 28:58.620 Und jeder Zustand gehört zu genau einer Gruppe. 28:59.180 --> 29:01.440 Die überlappen sich nicht, die Gruppen, und alle Gruppen zusammen 29:01.440 --> 29:02.420 ergeben alle Zustände. 29:02.800 --> 29:05.600 Es kann kleine Gruppen geben, es kann Zustände geben, die sind ihre 29:05.600 --> 29:06.700 eigene Äquivalenzklasse. 29:06.800 --> 29:09.840 Es kann große Gruppen geben, wo ganz viele Zustände drin sind, die 29:09.840 --> 29:11.800 dann alle paarweise miteinander äquivalent sind. 29:12.520 --> 29:14.780 Das ist die Äquivalenzklassen. 29:15.160 --> 29:17.440 Und wenn ich jetzt über die Gruppen sprechen möchte, dann will ich 29:17.440 --> 29:20.740 jetzt nicht neue Namen einführen, sondern ich sage einfach nur die 29:20.740 --> 29:22.400 Gruppe von diesem Zustand. 29:22.560 --> 29:24.380 Die Gruppe, in der dieser Zustand drin ist. 29:25.140 --> 29:28.860 Und das tut man so, also P ist einfach ein Zustand und mit eckigen 29:28.860 --> 29:30.900 Klammern sagt die Gruppe, in der P ist. 29:32.020 --> 29:35.180 Das ist dann das gleiche wie die Gruppe, in der auch Q ist, wenn P und 29:35.180 --> 29:36.200 Q äquivalent sein sollten. 29:37.280 --> 29:37.880 Okay. 29:39.880 --> 29:43.360 So und jetzt können wir uns anhand dieser Relation einen neuen 29:43.360 --> 29:48.880 Automaten definieren, der der Äquivalenzklassenautomat heißt. 29:49.300 --> 29:49.580 Okay. 29:50.240 --> 29:54.020 Also wenn wir schon diese Gruppierung kennen, von unserem alten 29:54.020 --> 29:58.740 Automaten, dann ist jetzt von dem neuen Automaten, die Zustände sind 29:58.740 --> 30:01.600 genau die Gruppen, genau die Äquivalenzklassen sozusagen. 30:01.760 --> 30:03.640 Ich lasse die einfach alle zusammenfallen. 30:03.640 --> 30:05.980 Jede Gruppe hat jetzt nur noch einen Zustand. 30:07.760 --> 30:12.240 Das heißt, unsere Zustandsmenge ist die Menge der Äquivalenzklassen. 30:13.340 --> 30:15.180 Des Alphabetes das gleiche. 30:16.020 --> 30:17.440 Und jetzt die Übergangsfunktion. 30:18.800 --> 30:25.940 Also ich muss jetzt sagen, wenn ich von einer Gruppe ein Zeichen lese, 30:26.000 --> 30:27.420 in welche Gruppe soll ich springen. 30:28.940 --> 30:31.220 Und da gucke ich jetzt nach an meinem ursprünglichen Automaten. 30:31.220 --> 30:34.720 Ich wähle mir einen beliebigen Repräsentanten der Gruppe, also einen 30:34.720 --> 30:39.540 Zustand in der Gruppe, lasse von dem aus das Zeichen lesen, dann lande 30:39.540 --> 30:42.680 ich in irgendeinem anderen Zustand, der ist wiederum in einer Gruppe 30:43.080 --> 30:44.680 und das ist die Gruppe, auf die ich abbilde. 30:46.160 --> 30:50.600 Also wenn ich von der Klasse von Q A lese, dann gehe ich einfach in 30:50.600 --> 30:55.060 den ursprünglichen Automaten, lese von Q aus A, lande in einem Zustand 30:55.060 --> 30:57.780 und gucke mir die Gruppe davon an. 30:58.940 --> 31:01.560 Okay, das ist die Übergangsfunktion. 31:03.140 --> 31:05.960 Startzustand ist einfach die Gruppe, die den ursprünglichen 31:05.960 --> 31:07.100 Startzustand enthält. 31:09.220 --> 31:14.060 Und akzeptierende Endzustände sind die Gruppen, die akzeptierende 31:14.060 --> 31:15.520 Endzustände enthalten haben. 31:17.440 --> 31:19.320 Okay, das ist die Definition. 31:19.480 --> 31:21.400 Wir haben nicht in meine Folien geguckt. 31:22.180 --> 31:24.160 Nein, das ist genau das, was wir jetzt machen müssen. 31:24.280 --> 31:26.960 Wir müssen uns darum kümmern, ob das wohl definiert ist. 31:27.460 --> 31:27.460 Ja, 31:30.840 --> 31:31.820 das ist ein bisschen schwierig. 31:31.940 --> 31:32.500 Ich mache nochmal zurück. 31:34.540 --> 31:38.660 Diese genau dann wenn-Aussage in der Definition von Äquivalent, das 31:38.660 --> 31:46.880 heißt, wenn ich von P ein Wort W lese und ich lande in einem 31:46.880 --> 31:50.660 akzeptierenden Endzustand, dann lande ich auch von Q aus mit dem 31:50.660 --> 31:53.360 gleichen Wort W in einem akzeptierenden Endzustand. 31:53.360 --> 31:57.600 Wenn ich von P ein Wort W lese und nicht in einem akzeptierenden 31:57.600 --> 32:02.260 Endzustand lande, dann lande ich auch von Q aus mit dem gleichen Wort 32:02.260 --> 32:03.960 in einem nicht akzeptierenden Endzustand. 32:04.300 --> 32:05.720 Ihnen fehlt irgendwie der zweite Teil. 32:06.640 --> 32:09.240 Das ist sozusagen die Rückrichtung von dem Pfeil hier. 32:11.860 --> 32:15.380 Entweder beide akzeptieren oder beide nicht akzeptieren. 32:15.480 --> 32:18.800 Es könnte sein, dass sie beide immer akzeptieren oder beide nie 32:18.800 --> 32:19.420 akzeptieren. 32:19.500 --> 32:20.040 Das ist okay. 32:20.040 --> 32:21.860 Hauptsache, sie sind sich einig. 32:24.460 --> 32:25.900 Aber absolut richtig. 32:26.600 --> 32:30.400 Die Frage ist, warum ist das überhaupt wohl definiert? 32:32.460 --> 32:37.820 Und zwar, Wohldefiniertheit war zum Beispiel mit dieser 32:37.820 --> 32:38.460 Übergangsfunktion. 32:38.580 --> 32:41.380 Ich habe gesagt, ich frage mich, wo ich von dieser Gruppe hinkomme, in 32:41.380 --> 32:42.660 welche andere Gruppe soll ich gehen. 32:42.940 --> 32:47.240 Ich wähle mir irgendeinen aus der Gruppe, lese von dem das Zeichen A 32:47.240 --> 32:49.020 und gehe dann in die Gruppe, wo das hingeht. 32:49.020 --> 32:52.040 Wenn ich jetzt einen anderen gewählt hätte aus der Gruppe, nachher 32:52.040 --> 32:53.340 hätte das woanders hingeführt. 32:55.140 --> 32:57.280 Also das wäre nicht wohldefiniert. 32:57.660 --> 33:02.080 Das ist etwas, was wir gleich überprüfen müssen. 33:02.800 --> 33:06.600 Aber ich nehme schon mal vorweg, dass dieser Äquivalenzklauselautomat 33:06.600 --> 33:08.640 wohldefiniert ist. 33:09.700 --> 33:11.940 Das ist also die Behauptung, alles ist gut. 33:12.860 --> 33:16.540 Das ist eine Konstruktion, die ist zumindest mal wohldefiniert und 33:16.540 --> 33:18.500 danach können wir uns darum kümmern, was sie überhaupt tut. 33:20.300 --> 33:21.800 Also, was müssen wir zeigen? 33:21.860 --> 33:26.240 Es ist klar, dass die Staatszustand und alles ist wohldefiniert. 33:26.300 --> 33:27.040 Da war keine Wahl. 33:27.680 --> 33:31.080 Das Einzige, was schwierig ist, ist diese Übergangsfunktion, die ich 33:31.080 --> 33:34.340 gerade schon erwähnt habe, und diese Endzustandsmenge. 33:35.640 --> 33:38.500 Ich habe geguckt, ich möchte wissen, ob eine Gruppe ein akzeptierender 33:38.500 --> 33:39.340 Endzustand ist. 33:40.020 --> 33:42.300 Ich wähle mir ein Element aus der Gruppe und gucke, ob das 33:42.300 --> 33:44.340 akzeptierend war, in dem ursprünglichen Automaten. 33:44.340 --> 33:47.020 Wenn ja, ist das Ding ein akzeptierender Endzustand. 33:47.920 --> 33:49.900 Und jetzt ist wieder die Frage, vielleicht habe ich den falschen 33:49.900 --> 33:52.380 gewählt, vielleicht gab es da drin einen, der akzeptiert, und einen, 33:52.500 --> 33:54.220 der nicht akzeptiert, und dann ist es nicht klar. 33:54.460 --> 33:58.360 Also das ist die Wohldefiniertheit von den Endzuständen. 33:58.620 --> 34:01.760 Gut, das müssen wir überprüfen. 34:02.000 --> 34:07.500 Und das heißt, dass wenn zu dem ersten, zu den Endzuständen, eine 34:07.500 --> 34:14.200 Gruppe ist Endzustand, wenn da drin alle Endzustände sind. 34:14.420 --> 34:17.500 Es kann nicht Mischungen geben, dass ich, wenn ich manchmal einen 34:17.500 --> 34:21.840 Endzustand und manchmal einen Nicht-Endzustand habe, oder anders 34:21.840 --> 34:25.840 ausgedrückt, ein Endzustand kann nur zu einem Endzustand äquivalent 34:25.840 --> 34:26.080 sein. 34:27.460 --> 34:29.960 Wenn die in der gleichen Gruppe landen, sind die entweder beide 34:29.960 --> 34:31.340 Endzustände oder keiner. 34:33.240 --> 34:34.420 Und wie machen wir das? 34:34.920 --> 34:43.100 Naja, P und Q sind Endzustände, und wenn die jetzt äquivalent sind, 34:43.300 --> 34:47.140 dann ist also egal, welches Wort ich lese, von denen aus landen die in 34:47.140 --> 34:51.240 einem Endzustand genau dann, wenn der andere in einem Endzustand 34:51.240 --> 34:51.540 landet. 34:51.640 --> 34:52.560 Also die sind sich einig. 34:52.980 --> 34:56.160 Naja, und das Wort, insbesondere gilt das für das leere Wort. 34:57.700 --> 35:02.680 Wenn ich von den beiden aus das leere Wort wähle, dann müssen die in 35:02.680 --> 35:06.920 einem Endzustand landen, wenn beide, also müssen gleichzeitig oder gar 35:06.920 --> 35:08.460 nicht, in einem Endzustand landen. 35:08.760 --> 35:12.480 Das heißt, die müssen entweder beide Endzustände sein, oder beide eben 35:12.480 --> 35:13.500 nicht Endzustände sein. 35:14.140 --> 35:16.380 Das ist die Wohldefinitivität davon. 35:18.060 --> 35:20.200 Jetzt das andere mit dem Übergang. 35:20.740 --> 35:27.860 Also, ich habe meine Übergangsfunktion so definiert, dass ich wollte 35:27.860 --> 35:32.020 von der Gruppe von Q gucken, wo das hingeht, und hab mir dann Q 35:32.020 --> 35:33.220 angeguckt, wo der hingeht. 35:33.780 --> 35:36.100 Angenommen in der Gruppe von Q ist auch noch P drin. 35:37.520 --> 35:39.140 Also P und Q sind äquivalent. 35:39.360 --> 35:40.220 Die sind in der gleichen Gruppe. 35:40.920 --> 35:44.120 Und wenn ich jetzt von Q gucke, wo A hinführt, und wenn ich von P 35:44.120 --> 35:47.600 gucke, wo A hinführt, dann soll das bitte in die gleiche Gruppe gehen. 35:48.960 --> 35:50.860 Weil sonst ist nicht klar, was passiert. 35:53.300 --> 35:57.280 Also, P und Q sind äquivalent, das ist nochmal die Definition von 35:57.280 --> 35:57.860 Äquivalenz. 35:59.060 --> 36:07.080 Jetzt wenn ich A lese, dann lande ich von Q aus in irgendeinem Zustand 36:07.080 --> 36:12.020 meines ursprünglichen Automatens und von P aus auch in einem anderen 36:12.020 --> 36:15.200 oder vielleicht den gleichen Zustand meines Automatens. 36:15.360 --> 36:19.320 Und ich frage mich, ob diese beiden Zustände hier, dieses Delta Q A 36:19.320 --> 36:21.800 und das Delta P A, ob die äquivalent sind. 36:25.060 --> 36:27.940 Das heißt, ich frage mich, wenn ich jetzt ein beliebiges Wort von 36:27.940 --> 36:33.980 denen aus ranhänge, also ich bin schon in Delta Q A und lege jetzt ein 36:33.980 --> 36:36.640 beliebiges Wort W ran und frage mich, wo führt mich das hin? 36:37.280 --> 36:41.540 Dann ist es natürlich das Gleiche, als wenn ich in Q das Wort AW 36:41.540 --> 36:42.500 rangehängt hätte. 36:44.340 --> 36:50.000 Und wenn ich von Delta P A W, das gleiche Wort W ranhänge, ist es 36:50.000 --> 36:52.500 natürlich das Gleiche, wie wenn ich gleich von P starte und das Wort 36:52.500 --> 36:53.440 AW ranhänge. 36:54.460 --> 37:00.940 Und jetzt weiß ich, Q und P sind äquivalent, das heißt, wenn ich AW 37:00.940 --> 37:04.920 von Q auslese und wenn ich AW von P rauslese, dann landet das entweder 37:04.920 --> 37:06.700 Beides in einem Endzustand oder keiner. 37:08.300 --> 37:11.220 Und dann entspricht es also auch, wenn ich von dem Zustand aus ein 37:11.220 --> 37:15.080 beliebiges Wort lese und von dem Zustand aus ein beliebiges Wort lese, 37:15.260 --> 37:17.420 dann landen die beide in einem Endzustand oder keiner. 37:17.620 --> 37:18.580 Das heißt, die sind äquivalent. 37:18.740 --> 37:19.920 Okay, das ist die Wohldefiniertheit. 37:20.020 --> 37:23.100 Ein bisschen Noten im Kopf, aber funktioniert. 37:24.760 --> 37:26.560 Okay, das heißt, das ist schon mal wohldefiniert. 37:27.420 --> 37:32.660 Ist egal, wen Sie sich angucken aus einer Gruppe, die haben sozusagen 37:32.660 --> 37:33.540 das gleiche Verhalten. 37:34.560 --> 37:40.320 So und jetzt ist der wichtige Teil, was tut denn dieser Automat, der 37:40.320 --> 37:41.200 denn wohldefiniert ist? 37:41.300 --> 37:44.700 Naja, der akzeptiert dieselbe Sprache wie unser Startautomat A. 37:46.660 --> 37:48.460 Das ist wichtig. 37:49.240 --> 37:50.760 Und wie beweisen wir das? 37:50.860 --> 37:57.340 Naja, wir nehmen uns ein beliebiges Wort W her, das von dem 37:57.340 --> 38:00.440 Ursprungsautomaten A abgearbeitet wird. 38:00.720 --> 38:03.380 Und wieder, das gibt eine Folge von Zuständen. 38:03.480 --> 38:09.060 Q0 ist der Startzustand bis zu irgendeinem Qn, je nachdem wie lang das 38:09.060 --> 38:09.360 Wort ist. 38:09.440 --> 38:10.660 Also n ist jetzt die Länge des Wortes. 38:10.720 --> 38:12.440 Das ist eine Folge von Zuständen. 38:13.600 --> 38:17.380 Und das heißt, in dem großen Bild springt er jetzt durch die Zustände 38:17.380 --> 38:18.940 immer folgend diesen Übergang. 38:19.040 --> 38:22.180 Und jetzt will ich das zurückverfolgen in das kleine Bild mit den 38:22.180 --> 38:27.120 Gruppenfolgen von Übergängen in der neuen Übergangsrelation. 38:28.240 --> 38:34.680 Also wann immer ich ein Zeichen lese von Zustand Q aus A und lande in 38:34.680 --> 38:40.020 P, dann heißt es, wenn ich in der Gruppe von Q A lese, dann lande ich 38:40.020 --> 38:45.280 in der Gruppe von P. So haben wir diese Übergangsfunktionen in dem 38:45.280 --> 38:46.820 Äquivalenzklassenautomaten definiert. 38:49.100 --> 38:54.860 Das heißt, ich weiß, wenn ich jetzt von Q0 bis Qn laufe, dann ist es 38:54.860 --> 38:58.100 im Äquivalenzklassenautomaten, laufe ich von der Gruppe von Q0 in die 38:58.100 --> 39:01.640 Gruppe von Q1, in die Gruppe von Q2 bis in die Gruppe von Qn. 39:05.920 --> 39:08.420 Es könnte jetzt sein, dass da jetzt ein paar Gruppen die gleichen 39:08.420 --> 39:08.780 sind. 39:09.460 --> 39:11.980 Schon vorher waren vielleicht ein paar Zustände die gleichen, aber 39:11.980 --> 39:14.080 diese Gruppenfolge wird durchlaufen. 39:14.800 --> 39:18.800 Jetzt ist die Frage, akzeptiert der denn oder nicht? 39:19.640 --> 39:24.160 Vorher war es so, der akzeptiert das Wort W genau dann, wenn Qn hier 39:24.160 --> 39:25.760 ein akzeptierender Endzustand ist. 39:27.280 --> 39:30.180 Und jetzt lande ich bei dem Abarbeiten des gleichen Wortes, lande ich 39:30.180 --> 39:31.780 in der Gruppe von Qn. 39:32.320 --> 39:35.080 Naja, und nach der Definition der akzeptierenden Endzustände ist die 39:35.080 --> 39:39.320 Gruppe von Qn akzeptierend genau dann, wenn Qn akzeptierend ist. 39:39.460 --> 39:42.100 Das heißt, das ist genau das gleiche behalten. 39:44.080 --> 39:44.340 Okay. 39:45.160 --> 39:46.820 So, das macht der Äquivalenzklassenautomat. 39:49.080 --> 39:50.980 Der kriegt diese Äquivalenzen hin. 39:52.280 --> 39:56.300 Wenn Sie Zustände finden, die äquivalent sind, können Sie die also 39:56.300 --> 39:59.140 zusammenlegen, in eine Gruppe machen. 39:59.260 --> 40:02.040 Dadurch reduzieren Sie die Anzahl der Zustände in Ihrem Automaten. 40:03.280 --> 40:07.420 Wenn Sie Pech haben, ist kein Zustand zu irgendeinem anderen 40:07.420 --> 40:07.780 Äquivalent. 40:07.820 --> 40:09.160 Die sind alle in ihren eigenen Gruppen. 40:09.280 --> 40:11.600 Dann tut der Äquivalenzklassenautomat einfach nichts. 40:11.600 --> 40:15.620 Also der gibt Ihnen genau das gleiche Bild wieder zurück, was Sie 40:15.620 --> 40:16.020 schon hatten. 40:16.560 --> 40:18.680 Aber wenn Sie Glück haben, reduziert er Ihr Bild. 40:19.440 --> 40:19.640 Okay? 40:20.500 --> 40:21.780 Und er ändert Ihre Sprache nicht. 40:22.560 --> 40:22.760 Okay. 40:24.460 --> 40:27.460 Jetzt ist aber die Frage, wie macht man das denn tatsächlich? 40:27.720 --> 40:29.420 Denn irgendwie habe ich ein bisschen geschummelt. 40:30.560 --> 40:32.660 Ich habe immer gesagt, naja, man guckt sich diese Gruppen an. 40:33.260 --> 40:34.600 Ja, man guckt sich die Äquivalenzen an. 40:35.500 --> 40:39.620 Aber wie überprüfe ich denn überhaupt, ob zwei Zustände äquivalent 40:39.620 --> 40:39.820 sind? 40:41.720 --> 40:45.020 Wenn ich die Definition anwende, dann heißt es, okay, für alle Wörter 40:45.020 --> 40:48.940 W aus Sigma-Stern muss ich jetzt gucken, ob die immer übereinstimmen 40:48.940 --> 40:49.920 in ihrer Abarbeitung. 40:49.980 --> 40:52.880 Ob die beide gleichzeitig in einem Endzustand oder beide gleichzeitig 40:52.880 --> 40:54.700 in einem Nicht-Endzustand landen. 40:54.760 --> 40:57.460 Es ist ein bisschen aufwendig, die ganzen unendlich vielen Wörter in 40:57.460 --> 40:58.740 Sigma -Stern da zu überprüfen. 40:59.320 --> 41:02.100 Das heißt, es ist nicht so klar, wie man überhaupt Äquivalenz 41:02.100 --> 41:05.680 nachweist, um diese Gruppen aufzustellen, um mit den Gruppen dann den 41:05.680 --> 41:07.380 Äquivalenzklassenautomaten aufzustellen. 41:08.160 --> 41:08.420 Okay? 41:13.020 --> 41:20.180 Auf der anderen Seite ist es einfacher, jemanden davon zu überzeugen, 41:20.220 --> 41:22.380 dass zwei Zustände nicht-äquivalent sind. 41:25.300 --> 41:27.880 Das ist leicht danach zu machen, weil Sie müssen nur ein Wort finden, 41:28.800 --> 41:30.780 wo die beiden sich nicht einig sind. 41:32.260 --> 41:37.480 Also, um zu zeigen, dass P und Q nicht-äquivalent sind, reicht es, ein 41:37.480 --> 41:42.080 Wort zu finden, W, so dass sie sich nicht einig sind, also entweder 41:42.080 --> 41:46.220 haben wir dieses Szenario, dass P möchte, wenn man von ihm aus W 41:46.220 --> 41:48.540 liest, akzeptieren, Q aber nicht. 41:49.380 --> 41:53.400 Oder andersherum, P möchte, wenn man von ihm aus W liest, nicht 41:53.400 --> 41:54.700 akzeptieren, aber Q schon. 41:56.600 --> 41:56.900 Okay? 41:57.600 --> 42:01.440 Dann sind die sich nicht einig, und dann ist sofort klar, die sind 42:01.440 --> 42:03.220 nicht -äquivalent, die sind in verschiedenen Gruppen. 42:04.000 --> 42:07.640 Aber so einen einfachen Zeugen für Äquivalenz gibt es nicht so leicht. 42:09.000 --> 42:10.500 Jetzt habe ich das Wort schon benutzt. 42:10.500 --> 42:12.440 Dieses Zeuge. 42:13.320 --> 42:20.140 Wir sagen, wenn W ein Wort ist, wo sich P und Q nicht einig sind bei 42:20.140 --> 42:24.060 der Abarbeitung, dann ist das ein Zeuge dafür, dass P und Q nicht 42:24.060 --> 42:27.080 -äquivalent sind, oder wir sagen auch, das Wort trennt P und Q. 42:29.340 --> 42:34.140 Und jetzt ist die Idee, zu sagen, okay, wir suchen Zeugen, bis wir 42:34.140 --> 42:37.800 alles getrennt haben, was zu trennen geht, und das, was dann noch 42:37.800 --> 42:39.560 zusammensteht, ist dann äquivalent. 42:41.080 --> 42:41.260 Okay? 42:41.440 --> 42:45.660 Das ist die Idee, und das ist nicht so ganz klar, wie man das macht, 42:45.740 --> 42:48.480 wann man fertig ist, wann man sicher sein kann, dass es keine Zeugen 42:48.480 --> 42:49.720 mehr gibt, aber das ist so die Idee. 42:49.900 --> 42:53.820 Wir gehen erstmal davon aus, alles ist wahrscheinlich äquivalent, bis 42:53.820 --> 42:56.240 wir einen Zeugen dafür finden, dass Sachen getrennt werden müssen. 43:00.620 --> 43:04.220 Wir testen jetzt systematisch auf Nicht-Äquivalenz. 43:05.120 --> 43:07.900 Und dafür testen wir, ob bestimmte Wörter Zeugen sind. 43:09.060 --> 43:09.580 Okay? 43:10.200 --> 43:12.780 Und wir fangen an mit kurzen Wörtern. 43:13.460 --> 43:17.760 Wir gucken erstmal, ob das leere Wort schon ein Zeuge ist für 43:17.760 --> 43:18.620 Trennung. 43:19.440 --> 43:23.740 Oder ob einbuchstabige Wörter Zeugen sind, und dann ob zweibuchstabige 43:23.740 --> 43:24.560 Wörter und so weiter. 43:24.820 --> 43:28.040 Also dann die Wörter in aufsteigender Länge, gehen wir durch, und 43:28.040 --> 43:32.220 gucken immer, ist das ein Zeuge für irgendwas, was bisher noch nicht 43:32.220 --> 43:32.800 getrennt war? 43:34.480 --> 43:34.680 Okay? 43:35.180 --> 43:37.500 Und dann an irgendeinem Punkt haben wir so ein Abbrauchkriterium, da 43:37.500 --> 43:40.620 sagen wir, okay, wenn jetzt nichts, jetzt sind wir fertig. 43:41.160 --> 43:41.240 Okay? 43:41.340 --> 43:43.040 Da kommt aber gleich noch dazu. 43:44.040 --> 43:44.160 Okay. 43:46.420 --> 43:50.620 Also, die Idee steht da oben nochmal, ich glaube, das war gerade auf 43:50.620 --> 43:51.340 der vorigen Folie. 43:51.760 --> 43:55.500 Die Frage ist, wann kann das abgebrochen werden? 43:56.140 --> 43:59.680 Und dafür überlegen wir uns erstmal, wann wird denn getrennt? 43:59.940 --> 44:04.180 Naja, es wird getrennt mit einem kürzesten Zeugen. 44:04.260 --> 44:06.260 Das können wir auf jeden Fall mal sicher sagen. 44:06.600 --> 44:10.560 Wir gehen ja die Wörter der aufsteigenden Länge durch und sobald wir 44:10.560 --> 44:12.120 ein Zeugen haben, trennen wir. 44:12.240 --> 44:15.800 Das heißt, wenn es Zeugen gibt, dann gibt es auch kürzeste Zeugen und 44:15.800 --> 44:17.740 wir werden einen kürzesten Zeugen immer finden. 44:19.200 --> 44:19.720 Gut. 44:20.660 --> 44:25.180 Also, angenommen, wir haben einen kürzesten Zeugen für p nicht 44:25.180 --> 44:26.000 -äquivalent zu q. 44:26.600 --> 44:29.140 Und dieser Zeuge ist w. 44:29.440 --> 44:33.740 Also wenn man von p aus w abarbeitet und wenn man von q aus w 44:33.740 --> 44:36.920 abarbeitet, sind die sich nicht einig über die Akzeptanz. 44:39.200 --> 44:45.240 Okay, jetzt fragen wir uns, diese Abarbeitung von diesem Wort w fängt 44:45.240 --> 44:47.400 an, wenn es nicht leer ist, mit irgendeinem Buchstaben. 44:47.680 --> 44:48.780 Erstes Zeichen a. 44:50.760 --> 44:56.220 Das heißt, der erste Schritt ist, von p gehe ich erstmal, lese ich a 44:56.220 --> 44:57.220 und lande in p'. 44:57.220 --> 45:00.000 Und von q lese ich a und lande in q'. 45:01.560 --> 45:01.960 Ja. 45:03.920 --> 45:07.600 Die können nicht-äquivalent sein, p' und q'. 45:09.460 --> 45:12.940 Ich habe beide, ich weiß ja, ich bin gerade in der Abarbeitung von w 45:12.940 --> 45:15.980 und die sind sich am Ende nicht einig und haben jetzt nur den ersten 45:15.980 --> 45:18.180 Schritt gemacht und die beiden können sich jetzt auch nicht einig 45:18.180 --> 45:22.540 sein, weil die müssen beide noch dieses, was ist das, w' abarbeiten. 45:23.220 --> 45:23.620 Okay. 45:24.580 --> 45:27.920 Das heißt, wenn ich einen Zeugen habe, dann sehe ich auf dem ersten 45:27.920 --> 45:31.740 Schritt, die beiden ist der Rest auch noch ein Zeuge für die. 45:33.700 --> 45:33.980 Okay. 45:35.300 --> 45:45.180 Das heißt, wenn w ein kürzester Zeuge für p nicht-äquivalent zu q ist, 45:46.180 --> 45:52.560 dann finde ich ein Zeugen für p' nicht-äquivalent zu q'. 45:52.560 --> 45:54.220 Der ist auch ziemlich kurz. 45:55.100 --> 45:59.460 Und jetzt das Wichtige ist, das ist auch ein kürzester Zeuge. 46:00.340 --> 46:00.820 Warum? 46:02.220 --> 46:10.260 Wenn die noch einen kürzeren Zeugen hätten, w' noch einen kürzeren, 46:10.340 --> 46:12.740 dann könnte ich einfach den gleichen Trick machen, ich gehe einfach, 46:12.860 --> 46:15.980 ich starte von p und q, mache einen a und dann den kürzeren Zeugen. 46:17.420 --> 46:19.960 Dann wäre das auch ein kürzerer Zeuge für p und q. 46:20.840 --> 46:23.740 Das heißt, ich finde entlang dieser Wege nicht nur immer wieder 46:23.740 --> 46:27.280 Zeugen, sondern ich finde sogar entlang eines kürzesten Zeugens nur 46:27.280 --> 46:28.200 kürzeste Zeugen. 46:30.120 --> 46:30.300 Okay? 46:31.260 --> 46:31.520 Gut. 46:32.660 --> 46:36.820 Das heißt, wenn ich schon irgendwann weiß, ich gehe ja durch, die 46:36.820 --> 46:39.760 Wörter der Länge 0, Wörter der Länge 1, gucke immer, ob da Zeugen 46:39.760 --> 46:43.660 dabei sind und so Zeugen, die kürzeste Zeugen, und wenn ich irgendwann 46:43.660 --> 46:47.640 sehe, okay, keine Ahnung, Wörter der Länge 7 haben keine kürzesten 46:47.640 --> 46:53.300 Zeugen mehr, dann kann auch kein Wort der Länge 8 ein kürzester Zeuge 46:53.300 --> 46:53.600 sein. 46:56.990 --> 46:59.830 Weil kürzeste Zeugen auf ihrem Weg immer nur kürzeste Zeugen 46:59.830 --> 47:02.910 aufsammeln, also wenn es einen kürzesten Zeugen der Länge 8 gäbe, wäre 47:02.910 --> 47:05.190 nach dem ersten Schritt ein kürzester Zeuge der Länge 7 da. 47:05.970 --> 47:08.910 Also irgendwann, wenn ich schon mal sehe, in Länge 7 gibt es keine 47:08.910 --> 47:11.210 kürzesten Zeugen, kann ich aufhören. 47:12.410 --> 47:14.390 Und das ist das Wichtige, das ist also endlich. 47:15.690 --> 47:19.590 Ich kann sehen, dass es keine kürzesten Zeugen mehr gibt, also gar 47:19.590 --> 47:20.250 keine Zeugen mehr. 47:22.330 --> 47:23.670 Machen wir das vielleicht an einem Beispiel. 47:26.650 --> 47:30.450 Hier ist nochmal aufgeschrieben, was ich schon die ganze Zeit mündlich 47:30.450 --> 47:30.790 sage. 47:32.130 --> 47:38.130 Am Anfang gehe ich davon aus, dass alle quasi erstmal vorläufig 47:38.130 --> 47:41.690 äquivalent sind, in einer Gruppe, und jetzt gehe ich der Länge nach 47:41.690 --> 47:45.290 die Wörter durch, von kürzen beginnen und versuche zu trennen. 47:45.290 --> 47:46.790 Also ich fange an mit dem leeren Wort. 47:48.510 --> 47:52.450 Und gucke, gehe auf jedes Paar T und Q, lese aus beiden das leere Wort 47:52.450 --> 47:54.990 und gucke, ob die sich jetzt einig sind über das Akzeptanzverhalten 47:54.990 --> 47:55.410 oder nicht. 47:55.550 --> 47:57.010 Und dann trennt es schon mal ein paar Paare. 47:57.430 --> 47:58.790 Dann nehme ich einbuchstäbliche Wörter. 47:59.530 --> 48:01.930 Und dann gucke ich immer, trennt es Sachen, die noch nicht getrennt 48:01.930 --> 48:02.270 waren. 48:03.090 --> 48:05.490 Und dann weiß ich, okay, das ist jetzt ein kürzester Zeuge. 48:07.530 --> 48:11.370 Und wenn ich... 48:12.250 --> 48:12.610 Genau. 48:12.610 --> 48:14.770 Immer Wörter der Länge... 48:14.770 --> 48:17.910 Also genau, ich kann schon jetzt sagen, was passiert, wenn ich dieses 48:17.910 --> 48:18.730 leere Zeichen lese. 48:19.610 --> 48:24.210 Und wenn ich das leere Zeichen lese, von P und Q und frage mich, sind 48:24.210 --> 48:26.150 die sich einig über das Akzeptanzverhalten? 48:26.270 --> 48:26.490 Naja. 48:28.210 --> 48:33.030 Die sind sich einig, wenn die beide Endzustände sind, über das Lesen 48:33.030 --> 48:33.910 des leeren Wortes. 48:34.050 --> 48:36.170 Die sind sich einig, wenn die beide nicht Endzustände sind. 48:36.590 --> 48:37.970 Aber wenn die... 48:37.970 --> 48:40.710 Einer ist ein Endzustand und der andere ist ein Nicht-Endzustand, dann 48:40.710 --> 48:42.350 werden die getrennt werden durch das leere Wort. 48:42.730 --> 48:45.650 Das heißt, in dem ersten Schritt aus der großen Masse aller Zustände 48:45.650 --> 48:48.550 wird auf jeden Fall die Zweiteilung auftauchen, Endzustände, Nicht 48:48.550 --> 48:49.030 -Endzustände. 48:49.130 --> 48:50.590 Die sind schon mal nicht äquivalent zueinander. 48:51.670 --> 48:53.650 Untereinander eventuell wird noch verfeinert. 48:54.690 --> 48:54.770 Okay. 48:56.130 --> 48:58.510 So, machen wir das mal vielleicht an dem Beispiel hier. 48:59.370 --> 49:03.230 Das ist dieser große Automat mit den 16 Zuständen. 49:08.220 --> 49:11.620 Und wir machen dieses Verfahren, versuchen jetzt, Äquivalenzklassen zu 49:11.620 --> 49:11.880 finden. 49:11.980 --> 49:15.980 Sie haben schon hier als Sneak Preview die Farben werden genau die 49:15.980 --> 49:17.140 Äquivalenzklassen werden. 49:18.020 --> 49:19.500 Aber wir wissen es erstmal noch nicht. 49:20.600 --> 49:23.600 Also, bisschen schwierig zu sehen, die sind ein bisschen 49:23.600 --> 49:26.140 durchnummeriert oder durchgelabelt, die Zustände. 49:26.520 --> 49:29.100 Und hier sind die vorläufigen Äquivalenzklassen. 49:29.400 --> 49:34.440 Also, vorher sind die einfach alle 16 in einer Äquivalenzklasse drin. 49:34.780 --> 49:39.420 Und nach dem ersten Schritt sind es zwei Äquivalenzklassen, hier unten 49:39.420 --> 49:44.460 steht es auch nochmal, nämlich, ich trenne die Endzustände in grün von 49:44.460 --> 49:46.520 den Nicht-Endzuständen alle anderen. 49:48.380 --> 49:51.880 Durch den Zeugen, durch den kürzesten Zeugen, leeres Wort. 49:54.760 --> 49:55.000 Okay. 49:55.940 --> 49:58.900 Jetzt gehe ich durch, Wörter der Länge 1. 49:59.400 --> 50:00.780 Ich nehme zuerst die 0. 50:01.480 --> 50:04.700 Ich hatte jetzt vorher nochmal, wir waren hier, wir hatten zwei 50:04.700 --> 50:08.680 vorläufige Äquivalenzklassen, die Endzustände, die vier Stück und die 50:08.680 --> 50:09.320 zwölf anderen. 50:10.180 --> 50:13.740 Und jetzt wird geguckt, was passiert denn, wenn ich eine 0 lese. 50:13.960 --> 50:19.120 Ich nehme mir ein paar von Zuständen her, lese auf beiden die 0 und 50:19.120 --> 50:23.920 gucke dann, ob die beiden sich einig sind über Endzustand oder nicht. 50:24.440 --> 50:26.120 Also machen wir ganz exemplarisch. 50:26.580 --> 50:32.520 Zum Beispiel, ich nehme mir zwei grüne her, die sind bisher noch nicht 50:32.520 --> 50:38.520 getrennt, hier 0,2 und 2,2, lese aus beiden die 0, dann lande ich halt 50:38.520 --> 50:43.140 hier in 1,2 und 3,2 und gucke jetzt, kann ich die trennen oder nicht. 50:43.320 --> 50:46.020 Also sind die sich einig oder nicht einig über die Akzeptanz. 50:46.080 --> 50:47.140 Und hier sind die sich einig. 50:47.640 --> 50:49.460 Also die 0 trennt die beiden da nicht. 50:51.500 --> 50:51.500 Okay. 50:51.940 --> 50:56.100 Aber es wird zum Beispiel getrennt, zum Beispiel wird die 1,0 getrennt 50:56.100 --> 50:57.020 von der 0,1. 50:57.200 --> 50:59.260 Warum wird die 1,0 von der 0,1 getrennt? 50:59.380 --> 51:00.540 Wo ist denn die 1,0? 51:00.540 --> 51:04.680 Die 1,0 ist der rote und die 0,1 ist dieser blaue. 51:05.340 --> 51:10.460 Jetzt lese ich aus beiden die 0, dann lande ich bei der 1,0 in der 2,0 51:11.080 --> 51:14.320 und von der 0,1 in der 1,1 und jetzt sehe ich, okay, die sind sich 51:14.320 --> 51:14.920 nicht einig. 51:16.680 --> 51:18.380 Obwohl sie beide das gleiche Wort gelesen haben. 51:18.440 --> 51:20.880 Der eine will jetzt akzeptieren, der andere will nicht akzeptieren. 51:21.300 --> 51:21.960 Die werden getrennt. 51:23.060 --> 51:23.420 Okay. 51:23.980 --> 51:29.080 Und so trenne ich gerade die roten, sind die, die wenn sie 0 lesen, 51:29.180 --> 51:30.400 landen die in einem grünen Zustand. 51:32.820 --> 51:36.100 Und die anderen, wenn sie 0 lesen, landen die nicht in einem grünen 51:36.100 --> 51:36.500 Zustand. 51:37.080 --> 51:39.600 Deswegen trenne ich jetzt hier genau die roten von dem Rest ab. 51:41.120 --> 51:41.520 Okay. 51:43.300 --> 51:44.760 Jetzt gehe ich weiter mit der 1. 51:45.100 --> 51:48.860 Da trenne ich genau die blauen ab, weil die blauen sind genau die, die 51:48.860 --> 51:51.340 wenn sie eine 1 lesen, in einem grünen Zustand landen, in einem 51:51.340 --> 51:56.060 akzeptierenden Zustand und die anderen landen mit einer 1 eben nicht 51:56.060 --> 51:57.020 in einem grünen Zustand. 51:59.240 --> 52:02.520 Und das heißt, jetzt habe ich schon diese Äquivalenzklassen. 52:03.060 --> 52:04.060 Vier Äquivalenzklassen. 52:05.060 --> 52:08.280 Die grünen, ich weiß nicht mehr, rot, blau und weiß. 52:09.420 --> 52:11.200 Jetzt weiß ich aber noch nicht, ob ich fertig bin. 52:11.360 --> 52:12.880 Das sind vorläufige Äquivalenzklassen. 52:13.020 --> 52:13.880 Ich muss noch weitermachen. 52:14.040 --> 52:16.220 Ich muss mir angucken, Wörter der Länge 2. 52:17.100 --> 52:21.760 Also zum Beispiel 00, 01, 10, 11. 52:22.000 --> 52:25.180 Ich muss die alle vier noch durchgehen und gucken, ob ich noch 52:25.180 --> 52:27.400 irgendwas trennen kann, was noch nicht getrennt ist. 52:28.000 --> 52:32.380 Also kann ich zwei Grüne finden, so dass, wenn ich von dem einen Grün 52:32.380 --> 52:36.260 00 mache, ich akzeptiere und von dem anderen Grün 00 mache, ich 52:36.260 --> 52:36.800 ablehne. 52:37.120 --> 52:39.060 Wenn ja, werden die Grünen nochmal getrennt. 52:40.360 --> 52:45.660 Geht man halt alle sechs Paare von Grünen hier durch, merkt, die sind 52:45.660 --> 52:46.280 sich alle einig. 52:46.360 --> 52:50.320 Dann muss man auch alle sechs Paare von Blauen durchgehen, von Roten, 52:50.360 --> 52:51.020 von Weißen. 52:51.180 --> 52:53.220 Merkt sich, okay, 00 sind sich alle einig. 52:53.720 --> 52:56.440 Reicht aber noch nicht, jetzt muss ich mir noch 01 angucken. 52:56.640 --> 53:00.540 Wieder alle sechs Paare von Grünen, auf beiden muss ich 01 anwenden 53:00.540 --> 53:02.500 und gucken, ob die sich einig sind und so weiter. 53:03.720 --> 53:07.940 Dann merkt man, wenn man diese ganzen Fälle, aber endlich viele Fälle 53:07.940 --> 53:10.900 durchgespielt hat, merkt man, hier wird nichts mehr getrennt. 53:12.240 --> 53:17.620 Das heißt, es gibt keinen kürzesten Zeugen der Länge 2. 53:19.540 --> 53:22.600 Das heißt, ich habe alle kürzesten Zeugen schon gesehen. 53:23.620 --> 53:26.400 Das heißt, ich habe alles schon getrennt, was zu trennen geht. 53:26.620 --> 53:27.340 Ich bin fertig. 53:28.940 --> 53:30.800 Ich habe meine Äquivalenzklassen gefunden. 53:31.220 --> 53:33.520 Das sind die vier Farbklassen hier. 53:34.440 --> 53:38.160 Darauf kann ich jetzt Äquivalenzklassen Automaten schmeißen und kriege 53:38.160 --> 53:41.300 einen kleineren Automaten, der die gleiche Sprache akzeptiert. 53:42.280 --> 53:46.820 Ich habe das jetzt nicht so besonders Pseudocode-mäßig vorgestellt 53:46.820 --> 53:49.840 oder algorithmisch, aber Sie glauben ja, dass Sie das in einen 53:49.840 --> 53:51.140 Algorithmus transformieren können, oder? 53:56.190 --> 53:58.550 Ja, aber anders geht es nicht. 53:59.190 --> 54:01.510 Aber wichtig ist, dass es ein endlicher Algorithmus ist. 54:03.390 --> 54:05.310 Ich formuliere das hier gar nicht als Algorithmus. 54:05.550 --> 54:07.450 Ich sage zum Beispiel nichts über Laufzeit. 54:07.670 --> 54:10.030 Wie lang kann das im schlimmsten Fall gehen? 54:11.150 --> 54:12.350 Sie können sich gerne überlegen. 54:12.410 --> 54:12.970 Der ist polynomial. 54:13.230 --> 54:15.070 Der ist relativ schnell. 54:22.720 --> 54:24.160 Warum es keine Zeugen der Länge 3 gibt? 54:24.160 --> 54:26.160 Wenn es irgendwo... 54:26.780 --> 54:30.640 Wenn Sachen getrennt werden könnten, die noch nicht getrennt sind. 54:32.640 --> 54:36.120 Wenn zum Beispiel zwei Grüne noch getrennt werden könnten mit einem 54:36.120 --> 54:37.340 Wort der Länge 3. 54:39.120 --> 54:43.680 Dann würde ich mir das angucken, die beiden Grünen, und gehe diese 54:43.680 --> 54:45.740 drei Schritte und dann sind die sich uneinig. 54:46.640 --> 54:53.380 Nach dem ersten Schritt würde ich in zwei Zuständen landen, die mit 54:54.600 --> 54:56.760 einem Wort der Länge 2 getrennt werden können. 54:57.300 --> 54:57.600 Nicht wahr? 55:00.680 --> 55:06.340 Das heißt, die sind entweder schon getrennt, dann hätte ich aber die 55:06.340 --> 55:10.920 beiden Grünen schon mit einem Schritt getrennt, oder die sind noch 55:10.920 --> 55:14.820 nicht getrennt, dann hätten die aber einen Zeugen der Länge 2 und ich 55:14.820 --> 55:17.500 habe gesagt, kürzeste Zeugen der Länge 2 gibt es nicht. 55:18.620 --> 55:19.080 So ein bisschen? 55:35.470 --> 55:35.910 Ja. 55:38.870 --> 55:43.010 Wenn Sie testen wollen, ob ein Wort trennt und Sie sind unterwegs 55:43.010 --> 55:49.110 schon auf verschiedenen Äquivalenzklassen gelandet, dann wissen Sie, 55:50.130 --> 55:51.070 die werden getrennt. 55:51.690 --> 55:53.150 Aber das wird Ihnen nicht passieren. 55:54.970 --> 55:59.190 Wenn Sie testen die Zweier, dann werden Sie nicht merken, nach einem 55:59.190 --> 56:00.810 Schritt sind die schon getrennt, weil dann hätten Sie es schon 56:00.810 --> 56:04.290 gemerkt, als Sie davor alle einen Wörter der Länge 1 durchgegangen 56:04.290 --> 56:04.550 sind. 56:04.890 --> 56:06.010 Dann hätten Sie die schon getrennt. 56:06.390 --> 56:07.270 Dann hätten Sie es schon gemerkt. 56:12.730 --> 56:13.290 So. 56:17.410 --> 56:18.470 Oh, hier steht nochmal was. 56:19.430 --> 56:21.730 Fazit, das sind die Äquivalenzklassen, die vier Stück. 56:22.050 --> 56:25.030 Das heißt, wir haben vier Äquivalenzklassen. 56:25.570 --> 56:28.450 Die Äquivalenzklasse von dem Zustand 0,0. 56:28.950 --> 56:32.670 Also das sind alle, die zu dem Zustand 0,0 äquivalent sind. 56:32.810 --> 56:34.210 Das heißt, das sind die vier Stück. 56:34.950 --> 56:38.710 Oder die Gruppe von 0,1 und die Gruppe von 1,0 und die Gruppe von 1,1. 56:38.770 --> 56:39.730 Die kann ich jetzt so benennen. 56:39.830 --> 56:44.670 Das sind meine vier Gruppen und kann daraus den 56:44.670 --> 56:45.330 Äquivalenzklassenautomaten bauen. 56:45.590 --> 56:50.310 Ich muss jetzt auf den vier Zuständen noch die Übergänge festlegen und 56:50.310 --> 56:53.410 da gucke ich halt, wenn ich jetzt wissen will, zum Beispiel, wenn ich 56:53.410 --> 56:56.650 von Q1 eine 0 lese, wie mache ich das? 56:56.810 --> 56:59.770 Naja, ich klicke mal an, wer ist in Q1 in dieser Äquivalenzklasse 56:59.770 --> 56:59.990 drin? 57:00.070 --> 57:00.950 Zum Beispiel 0,1. 57:01.750 --> 57:03.850 Gucke ich nach in meinem Bild, wo ist denn 0,1? 57:04.130 --> 57:04.130 Da. 57:04.650 --> 57:05.270 Und was hatte ich gesagt? 57:05.330 --> 57:06.150 Ich will eine 0 lesen. 57:06.290 --> 57:07.510 Dann lande ich bei 1,1. 57:07.630 --> 57:10.490 Das heißt, ich muss in die Gruppe von 1,1 springen. 57:11.230 --> 57:13.070 Okay, und die Gruppe von 1,1 ist Q3. 57:13.210 --> 57:17.410 Also von Q1, wenn ich eine 0 lese, lande ich bei Q3 im 57:17.410 --> 57:18.430 Äquivalenzklassenautomat. 57:19.810 --> 57:20.090 Okay. 57:22.590 --> 57:23.290 Weitere Fragen. 57:27.740 --> 57:34.420 Dann noch eine kurze Zusammenfassung, was wir heute gemacht haben. 57:35.060 --> 57:40.380 Also, wir haben das Pumping Lemma verallgemeinert, wo wir den 57:41.380 --> 57:46.160 Beobachtungsbereich, wo geteilt werden muss zum Pumpen, nicht nur 57:46.160 --> 57:50.280 vorne haben, sondern an beliebiger Stelle in dem langen Wort. 57:51.260 --> 57:59.660 Das heißt, es ist schwieriger, nachzuweisen, dass es immer erfüllt 57:59.660 --> 58:00.760 ist, das Pumping Lemma. 58:00.980 --> 58:04.780 Also, dass egal, wo das Beobachtungsfenster ist, man pumpen kann. 58:05.160 --> 58:07.900 Man muss ja mehr zeigen, nicht nur für das erste Beobachtungsfenster, 58:08.020 --> 58:09.700 sondern für alle Beobachtungsfenster. 58:10.440 --> 58:13.660 Dadurch, dass es schwieriger nachzuweisen ist, dass es erfüllt ist, 58:13.720 --> 58:17.460 das Pumping Lemma, ist es einfacher nachzuweisen, dass es mal nicht 58:17.460 --> 58:18.180 erfüllt ist. 58:19.560 --> 58:23.940 Das heißt, damit können wir mehr Sprachen nachweisen, dass sie nicht 58:23.940 --> 58:24.720 regulär sind. 58:24.860 --> 58:28.360 Durch Nachweisen, durch Widerlegen der Aussage des Pumping Lemmas. 58:29.260 --> 58:31.640 Also, des verallgemeinerten Pumping Lemmas. 58:31.740 --> 58:36.220 Wieder nochmal, hier oben ist diese Aussage, nur die Aussage des 58:36.220 --> 58:39.240 verallgemeinerten Pumping Lemmas, dieses mit zwei Sternchen. 58:39.960 --> 58:46.360 Es existiert ein N, sodass für alle Wörter in der Sprache, die lang 58:46.360 --> 58:49.820 genug sind und für alle Aufteilungen dieser Wörter in ein 58:49.820 --> 58:54.320 Beobachtungsfenster Y der Länge N und was davor kommt P und dahinter 58:54.320 --> 58:59.840 kommt S, existiert eine Aufteilung dieses Beobachtungsfensters in ein 58:59.840 --> 59:05.440 Mittelteil V und was davor kommt U und dahinter kommt X, sodass für 59:05.440 --> 59:10.860 alle I dieses Mittelteil von dem Beobachtungsfenster I mal aufgepumpt 59:10.860 --> 59:13.020 werden kann und es bleibt in der Sprache. 59:13.680 --> 59:17.000 Wobei I kann 0 sein, kann 1 sein, dann ändert sich nichts. 59:17.000 --> 59:19.060 2 und beliebig groß. 59:21.600 --> 59:26.520 Das Pumping Lemma an sich sagt, dass jede reguläre Sprache die Aussage 59:26.520 --> 59:27.740 des Pumping Lemmas erfüllt. 59:28.840 --> 59:33.280 Das heißt, wir benutzen das, indem wir Nichtregularität beweisen. 59:33.600 --> 59:37.320 Durch eine Sprache erfüllt die Aussage des Pumping Lemmas nicht. 59:38.880 --> 59:42.200 Um zu zeigen, dass etwas das nicht erfüllt, müssen wir die Aussage so 59:42.200 --> 59:42.880 widerlegen. 59:43.400 --> 59:46.720 Nochmal, die Strategie ist, Sie drehen alle Quantoren um, aus dem 59:46.720 --> 59:51.100 existiert wird für alle, aus für alle wird existiert und am Ende sind 59:51.100 --> 59:56.840 Sie der existiert Spieler und Sie wollen, dass hier hinten das 59:56.840 --> 01:00:00.460 Statement, die Aussage nicht gilt, sodass Sie aus der Sprache 01:00:00.460 --> 01:00:01.140 rausfliegen. 01:00:01.820 --> 01:00:06.480 Und Sie sind der existiert Spieler in umgedrehten Quantoren. 01:00:07.000 --> 01:00:11.120 Sie haben keine Kontrolle über das N, Sie dürfen aber das Wort wählen 01:00:11.120 --> 01:00:12.680 und das Beobachtungsfenster. 01:00:12.680 --> 01:00:14.740 Sie haben keine Kontrolle über die Aufteilung des 01:00:14.740 --> 01:00:18.960 Beobachtungsfensters, Sie dürfen aber das I wählen, mit dem gepumpt 01:00:18.960 --> 01:00:19.420 werden muss. 01:00:23.520 --> 01:00:26.140 Dann haben wir noch den Äquivalenzklassenautomaten heute 01:00:26.140 --> 01:00:26.720 kennengelernt. 01:00:26.880 --> 01:00:31.700 Also die Idee ist, die Zustände in dem endlichen Automaten zu 01:00:31.700 --> 01:00:35.920 reduzieren, durch das Identifizieren von äquivalenten Zuständen, die 01:00:35.920 --> 01:00:40.280 quasi das gleiche Verhalten zeigen, wenn man sie einmal erreicht hat. 01:00:40.280 --> 01:00:42.160 Und dann könnte man sie halt auch zusammenlegen. 01:00:43.240 --> 01:00:46.380 Und das ist genau das, was der Äquivalenzklassenautomaten macht. 01:00:47.340 --> 01:00:51.460 Er legt äquivalente Zustände zusammen, in einen Zustand. 01:00:52.560 --> 01:00:56.240 Und wir haben gezeigt, dass man die Übergänge und das 01:00:56.240 --> 01:00:59.080 Akzeptanzverhalten da wohl definiert hinkriegen kann und dass es die 01:00:59.080 --> 01:01:00.460 gleiche Sprache akzeptiert. 01:01:01.820 --> 01:01:04.460 Und dann war nur noch die Frage, wie finde ich denn überhaupt 01:01:04.460 --> 01:01:06.900 äquivalente oder nicht äquivalente Zustände? 01:01:07.000 --> 01:01:12.100 Und da war die Beobachtung, okay, nicht Äquivalenz nachzuzeigen, geht 01:01:12.100 --> 01:01:15.940 relativ einfach durch das Finden eines kürzesten Zeugen. 01:01:17.520 --> 01:01:20.880 Für kürzeste Zeugen gehen wir die Wörter in aufsteigender Länge durch 01:01:20.880 --> 01:01:24.680 und gucken, ob sie irgendwas trennen, was noch nicht getrennt wurde. 01:01:24.820 --> 01:01:29.020 Und sobald wir für eine Länge von Wörtern alle Wörter dieser Länge 01:01:29.020 --> 01:01:32.160 durchprobiert haben und gemerkt haben, die sind keine Zeugen mehr für 01:01:32.160 --> 01:01:35.960 Sachen, die noch nicht getrennt sind, wissen wir, es kommt dahinter 01:01:35.960 --> 01:01:37.820 auch nichts Neues mehr zum Trennen. 01:01:38.060 --> 01:01:39.240 Dann können wir aufhören. 01:01:40.100 --> 01:01:41.480 Und so kriegen wir die Äquivalenzklassen. 01:01:41.720 --> 01:01:45.200 Dann können wir den Äquivalenzklassenautomaten bauen und der hat dann 01:01:45.200 --> 01:01:49.280 hoffentlich weniger Zustände als unser ursprünglicher Automat. 01:01:51.100 --> 01:01:55.220 Zum Abschluss noch, ich glaube, zwei Testen Sie sich Aufgaben. 01:01:56.220 --> 01:01:59.640 Also, wenn Sie heute gut aufgepasst haben und das alles verstanden 01:01:59.640 --> 01:02:01.240 haben, dann sollten Sie das lösen. 01:02:01.860 --> 01:02:05.600 Können, das geht nur in die eine Richtung. 01:02:05.860 --> 01:02:09.240 Wenn Sie heute alles verstanden haben, dann können Sie das lösen. 01:02:09.280 --> 01:02:11.460 Das heißt nicht, dass wenn Sie das lösen können, Sie heute alles 01:02:11.460 --> 01:02:12.120 verstanden haben. 01:02:15.100 --> 01:02:19.000 Also, Sprache über dem Alphabet 01, das sieht ein bisschen so ähnlich 01:02:19.000 --> 01:02:20.520 aus wie das, was wir schon gesehen haben. 01:02:20.640 --> 01:02:21.460 Also zwei Sprachen. 01:02:21.560 --> 01:02:23.740 Das eine ist die hier. 01:02:27.450 --> 01:02:28.970 Und das andere ist die da. 01:02:31.330 --> 01:02:37.170 Und die Frage ist, für welche der beiden Sprachen gilt die Aussage des 01:02:37.170 --> 01:02:38.830 verallgemeinerten Pumping Lemmas? 01:02:39.710 --> 01:02:43.910 Oder für welche können Sie die Aussage des verallgemeinerten Pumping 01:02:43.910 --> 01:02:44.850 Lemmas widerlegen? 01:02:45.710 --> 01:02:48.650 Was heißt das für die Regularität dieser Sprachen? 01:02:49.870 --> 01:02:50.010 Okay. 01:02:52.090 --> 01:02:53.150 Wirklich, trainieren Sie das. 01:02:55.750 --> 01:02:58.350 Zweites, zum Äquivalenzflaschenautomat. 01:02:58.650 --> 01:03:01.250 Hier ist der folgende Automat gegeben. 01:03:01.410 --> 01:03:04.070 Ich gebe Ihnen nicht das Bild, weil der Automat zu groß ist. 01:03:04.670 --> 01:03:07.650 Das ist ja gerade das Problem, was wir gerade hier behandeln wollen, 01:03:07.730 --> 01:03:08.730 wenn der Automat zu groß ist. 01:03:09.450 --> 01:03:10.450 Ich gebe Ihnen den so. 01:03:11.510 --> 01:03:15.390 Der hat zehn Zustände, Q0 bis Q9. 01:03:16.790 --> 01:03:18.370 Sein Startzustand ist Q0. 01:03:19.410 --> 01:03:21.830 Das Alphabet ist 0 bis 9. 01:03:22.370 --> 01:03:24.010 Also auch zehn Zeichen im Alphabet. 01:03:24.930 --> 01:03:28.530 Die Endzustände sind Q0, Q3, Q6 und Q9. 01:03:29.310 --> 01:03:32.710 Und die Übergangsfunktion Delta ist so gegeben. 01:03:32.990 --> 01:03:38.250 Wenn Sie sich fragen, wenn ich in einem Zustand QI bin und ich lese A, 01:03:38.350 --> 01:03:39.370 wo lande ich denn dann? 01:03:39.490 --> 01:03:44.110 Dann frage ich mich, wie verhalten sich denn dieser Index I und diese 01:03:44.110 --> 01:03:45.370 Zahl A zueinander? 01:03:45.970 --> 01:03:49.890 Die sind ja hier indiziert mit den Zahlen 0 bis 9 und die Symbole A 01:03:49.890 --> 01:03:51.730 sind ja auch Zahlen 0 bis 9. 01:03:52.250 --> 01:03:56.450 Und zwar, wenn I plus A kleiner gleich 9 ist, dann gehe ich in den 01:03:56.450 --> 01:03:58.230 Zustand QI plus A. 01:03:59.950 --> 01:04:03.270 Also wenn ich zum Beispiel aus Q0 eine 0 lese, lande ich in Q0. 01:04:03.950 --> 01:04:07.070 Wenn ich aus Q1 eine 2 lese, lande ich in Q3. 01:04:08.330 --> 01:04:12.810 Und wenn I plus A größer gleich 10 ist, dann gibt es ja so einen 01:04:12.810 --> 01:04:16.590 Zustand gar nicht, QI plus A, dann gehe ich in den QI plus A minus 10. 01:04:17.970 --> 01:04:23.190 Also wenn ich aus Q8 eine 4 lese, lande ich in Q2. 01:04:24.550 --> 01:04:24.950 Okay? 01:04:25.430 --> 01:04:27.690 So, das beschreibt mir einen Automaten. 01:04:29.090 --> 01:04:30.310 Und der ist ganz schön groß. 01:04:30.470 --> 01:04:33.390 Ich meine, so groß ist der nicht, der hat 10 Zustände, aber um jetzt 01:04:33.390 --> 01:04:35.370 hier den auf die Folie zu machen, ist er zu groß. 01:04:36.190 --> 01:04:41.270 Und die Frage ist, wie viele Zustände hat der 01:04:41.270 --> 01:04:42.290 Äquivalenzklassenautomat? 01:04:44.590 --> 01:04:48.810 Oder Bonus, finden Sie sogar den Äquivalenzklassenautomaten? 01:04:48.950 --> 01:04:50.570 Ist er klein genug, um ihn hinzumalen? 01:04:51.490 --> 01:04:54.810 Oder finden Sie sogar die Sprache, die von den beiden Automaten 01:04:54.810 --> 01:04:55.670 erkannt wird? 01:04:58.350 --> 01:04:58.830 Okay. 01:05:00.130 --> 01:05:02.710 So, das war es dann für mich für heute. 01:05:03.510 --> 01:05:06.050 Nächstes Mal, ich weiß nicht, Donnerstag oder so, kommt Frau Wagner 01:05:06.050 --> 01:05:06.350 wieder. 01:05:06.830 --> 01:05:10.090 Sie wird noch ein bisschen über Äquivalenzklassenautomaten und 01:05:10.090 --> 01:05:11.870 Automatenminimierung weitererzählen. 01:05:12.370 --> 01:05:14.090 Ansonsten, wir sehen uns vielleicht irgendwann nochmal. 01:05:14.710 --> 01:05:14.910 Tschüss!