WEBVTT 00:08.040 --> 00:11.160 Hallo zusammen, es geht weiter mit der Vorlesung. 00:12.920 --> 00:17.540 Wir beschäftigen uns ja in der Vorlesung im Moment mit regulären 00:17.540 --> 00:19.460 Sprachen und mit endlichen Automaten. 00:20.240 --> 00:26.160 Und nochmal ganz kurz zur Erinnerung, was in der letzten Vorlesung 00:26.160 --> 00:27.920 insbesondere besprochen wurde. 00:28.560 --> 00:34.140 Also Sie kennen endliche Automaten, Sie kennen reguläre Sprachen, also 00:34.140 --> 00:35.420 sozusagen die Definition. 00:35.420 --> 00:39.740 Und da ist eben die Frage aufgetaucht, haben die beiden Konzepte 00:39.740 --> 00:41.320 irgendwas miteinander zu tun? 00:42.980 --> 00:50.140 Und als allererstes sozusagen die Idee zu beweisen, dass es für jede 00:50.140 --> 00:56.040 reguläre Sprache einen endlichen Automaten gibt, der diese akzeptiert. 00:56.040 --> 01:00.360 Dann haben sie mal angefangen, das zu beweisen. 01:01.840 --> 01:06.040 Zu dem Zeitpunkt kannten sie nur deterministische endliche Automaten 01:06.040 --> 01:11.460 und da hat sich sehr schnell gezeigt, dass man sozusagen den 01:11.460 --> 01:16.740 Determinismus aufgeben würde, dass es vielleicht leichter geht, das zu 01:16.740 --> 01:17.140 zeigen. 01:18.140 --> 01:23.500 Sozusagen eine reguläre Sprache hernehmt und entsprechend der Art und 01:23.500 --> 01:29.020 Weise, wie diese reguläre Sprache aufgebaut ist, dann einen endlichen 01:29.020 --> 01:31.840 Automaten konstruiert, der diese akzeptiert. 01:33.960 --> 01:39.000 Dann wurde der Beweis sozusagen unterbrochen oder zurückgestellt und 01:39.000 --> 01:43.180 jetzt mal das Konzept nicht deterministischer endlicher Automaten 01:43.180 --> 01:44.000 angeschaut. 01:45.600 --> 01:49.940 Zur Erinnerung, bei deterministischen endlichen Automaten ist die 01:49.940 --> 01:54.780 Übergangsfunktion eine Funktion, die also ganz eindeutig für jeden 01:54.780 --> 01:59.640 Zustand und jedes mögliche Symbol aus dem Alphabet, das man in dem 01:59.640 --> 02:03.400 Zustand lesen kann, sagt, was der Folgezustand ist. 02:04.520 --> 02:08.460 Dem gegenübergestellt wurde das Konzept des nicht deterministischen 02:08.460 --> 02:16.010 endlichen Automaten, nicht Determinismus, das heißt, es gibt eventuell 02:16.010 --> 02:21.570 Wahlmöglichkeiten, wenn man in einem Zustand ist, ein bestimmtes 02:21.570 --> 02:25.430 Symbol liest, das heißt, es gibt nicht den einen eindeutigen 02:25.430 --> 02:32.550 Folgezustand, sondern aus dem Zustand kann man bei Lesen eines Symbols 02:32.550 --> 02:37.550 in verschiedene Zustände übergehen und es kann sogar so sein, dass man 02:37.550 --> 02:43.390 ohne Lesen eines Symbols in einen anderen Zustand übergehen kann, also 02:43.390 --> 02:45.550 dass es Epsilon-Übergänge gibt. 02:48.530 --> 02:52.670 Da würde sich natürlich gleich mal die Frage stellen, was heißt denn 02:52.670 --> 02:58.110 dann noch Akzeptieren, wenn man ein nicht deterministisches 02:58.110 --> 03:03.690 Berechnungsmodell hat. 03:03.690 --> 03:07.430 Beim deterministischen Berechnungsmodell ist das ganz klar, Sie haben 03:07.430 --> 03:12.410 Ihren Automaten, es gibt die ausgezeichneten Endzustände und alle 03:12.410 --> 03:19.190 Wörter, die vom Anfangszustand in einen Endzustand führen, werden 03:19.190 --> 03:20.030 akzeptiert. 03:20.690 --> 03:24.870 Und da das eindeutig ist, was passiert, wenn Sie ein Wort lesen, ist 03:24.870 --> 03:28.230 das eine ganz klare Sache, was Akzeptieren heißt. 03:28.230 --> 03:33.410 Bei einem nicht deterministischen Modell könnte es jetzt so sein, dass 03:33.410 --> 03:40.510 Sie, wenn Sie ein bestimmtes Wort eingeben, der Automat nach 03:40.510 --> 03:45.110 Abarbeitung des Wortes mal in dem einen, mal in dem anderen Zustand 03:45.110 --> 03:46.370 endet. 03:47.290 --> 03:50.890 Und da fragt man sich schon, wie definiere ich denn dann Akzeptieren? 03:52.090 --> 03:56.350 Akzeptieren ist so definiert, dass ein Wort genau dann akzeptiert 03:56.350 --> 04:01.850 wird, wenn es eine Abarbeitung nicht deterministischen endlichen 04:01.850 --> 04:09.430 Automaten gibt, bei Lesen dieses Wortes in einem Endzustand endet. 04:10.030 --> 04:14.130 Eine gibt, aber es kann viele verschiedene geben, einige enden in 04:14.130 --> 04:14.850 Endzuständen. 04:16.230 --> 04:22.010 So, jetzt haben wir also diese beiden Modelle erstmal und da stellt 04:22.010 --> 04:24.190 sich natürlich die Frage, sind die äquivalent? 04:25.410 --> 04:27.810 Sie haben bewiesen, die sind äquivalent. 04:29.050 --> 04:33.150 Das heißt, wenn Sie einen beliebigen nicht deterministischen Automaten 04:33.150 --> 04:38.450 hernehmen, können Sie dazu einen deterministischen endlichen Automaten 04:38.450 --> 04:42.290 konstruieren, der genau dieselbe Sprache akzeptiert. 04:43.690 --> 04:47.930 Die Konstruktion war die sogenannte Potenzmengenkonstruktion. 04:48.930 --> 04:54.110 Potenzmengenkonstruktion deshalb, weil Sie beim Übergang von der 04:54.110 --> 04:59.150 Zustandsmenge Ihres nicht deterministischen endlichen Automaten zu 04:59.150 --> 05:03.210 einem äquivalenten deterministischen endlichen Automaten als 05:03.210 --> 05:07.950 potenzielle Zustandsmenge des deterministischen endlichen Automaten 05:07.950 --> 05:13.710 die Potenzmenge der Zustandsmenge nicht deterministischen endlichen 05:13.710 --> 05:14.910 Automaten hernehmen. 05:15.910 --> 05:23.090 Und das ist irgendwie klar, dass dabei die Größe von Ihrem Konstrukt 05:23.090 --> 05:24.510 explodiert. 05:25.770 --> 05:27.570 Zumindest kann das vorkommen. 05:28.010 --> 05:31.870 Von N Zuständen beim nicht deterministischen endlichen Automaten 05:31.870 --> 05:38.750 können Sie potenziell zu 2 hoch N Zuständen des äquivalenten 05:38.750 --> 05:42.830 deterministischen Automaten kommen. 05:43.650 --> 05:46.330 Das behalten wir im Hinterkopf, da müssen wir uns nochmal mit 05:46.330 --> 05:47.030 beschäftigen. 05:47.350 --> 05:51.210 Aber nachdem Sie also dies bewiesen haben, zu jedem nicht 05:51.210 --> 05:54.490 deterministischen endlichen Automaten gibt es einen äquivalenten 05:54.490 --> 05:58.770 deterministischen endlichen Automaten, sind Sie dann zurückgegangen zu 05:58.770 --> 06:01.530 dem, was Sie eigentlich zeigen wollten, nämlich dass es für jede 06:01.530 --> 06:07.070 reguläre Sprache einen endlichen Automaten gibt, der diese akzeptiert. 06:11.100 --> 06:15.100 Dann war es plötzlich einfach, man schaut sich einfach an, wie sind 06:15.100 --> 06:20.360 reguläre Sprachen aufgebaut und entsprechend dem Aufbau gibt man 06:20.360 --> 06:25.340 endliche Automaten an, die genau die entsprechenden Sprachen 06:25.340 --> 06:26.320 akzeptieren. 06:28.340 --> 06:34.420 Und diese endlichen Automaten, die da konstruiert wurden, die waren 06:34.420 --> 06:36.580 nicht deterministisch, aber das macht nichts. 06:38.460 --> 06:41.500 Die nicht deterministischen können Sie dann jeweils auch per 06:41.500 --> 06:47.380 Potenzmengenkonstruktion einen deterministischen endlichen Automaten 06:47.380 --> 06:47.700 bauen. 06:47.880 --> 06:54.940 Und nur zur Erinnerung, so sahen die drei Hauptkonstruktionen aus. 06:56.380 --> 07:00.820 Also nochmal, jede reguläre Sprache wird von einem deterministischen 07:00.820 --> 07:03.240 endlichen Automaten akzeptiert. 07:03.910 --> 07:07.460 Wir schauen uns an, wie sind reguläre Sprachen aufgebaut. 07:09.060 --> 07:13.160 Sie sind so aufgebaut, man startet mit Anfangssprachen. 07:14.760 --> 07:18.820 Die reguläre Sprache ist regulär und die einelementigen Sprachen sind 07:18.820 --> 07:22.960 regulär und aus regulären Sprachen können Sie neue reguläre Sprachen 07:22.960 --> 07:31.900 bauen, per Vereinigung, per Produktbildung und per klinischer 07:31.900 --> 07:32.540 Abschluss. 07:34.560 --> 07:38.040 Endliche Automaten anzugeben für die leere Menge oder einelementige 07:38.040 --> 07:39.500 Sprachen ist trivial. 07:39.960 --> 07:41.700 Das steht jetzt hier nicht mehr auf der Folie. 07:42.140 --> 07:44.780 Und dann müssen Sie einfach induktiv sagen, naja gut, wenn ich 07:44.780 --> 07:48.860 endliche Automaten habe zu zwei regulären Sprachen, dann kann ich aus 07:48.860 --> 07:52.500 den beiden auch einbauen für die Vereinigung dieser beiden Sprachen. 07:53.980 --> 07:57.500 Für das Produkt dieser beiden Sprachen oder für eine reguläre Sprache 07:57.500 --> 08:02.400 kann ich aus dem Automaten für diese reguläre Sprache einbauen für den 08:02.400 --> 08:03.360 klinischen Abschluss. 08:04.080 --> 08:08.780 Und diese Automaten, die man da baut, die sahen also so aus. 08:08.880 --> 08:12.260 Vereinigung, da muss man ja einfach die beiden Automaten nebeneinander 08:12.260 --> 08:18.860 stellen und von einem neuen Startzustand, den man neu dazu nimmt, 08:18.860 --> 08:23.040 einfach Epsilon-Übergänge in die Anfangs- oder Startzustände des einen 08:23.040 --> 08:24.540 und des anderen zulassen. 08:25.440 --> 08:29.800 Der Rest bleibt gleich, also die Endzustände, Vereinigung der 08:29.800 --> 08:31.740 Endzustandsmengen der beiden Automaten. 08:32.220 --> 08:34.220 Und für das Produkt müssen Sie einfach so etwas hintereinander 08:34.220 --> 08:39.320 schalten und für den klinischen Abschluss einfach so einen Zykel 08:39.320 --> 08:39.880 einbauen. 08:41.100 --> 08:44.540 Aber Sie sehen hier, die sind hochgradig, in Anführungszeichen nicht 08:44.540 --> 08:45.340 deterministisch. 08:45.340 --> 08:48.280 Sie brauchen hier insbesondere Epsilon-Übergänge. 08:53.620 --> 08:57.740 Okay, was bleibt jetzt noch zu tun oder was könnte man sich jetzt noch 08:57.740 --> 08:58.580 so alles fragen? 09:01.360 --> 09:06.520 Man könnte sich angesichts dieses Satzes insbesondere auch fragen, 09:06.960 --> 09:08.600 gilt auch die Umkehrung? 09:10.220 --> 09:18.180 Gibt es zu jedem endlichen Automaten eine reguläre Sprache? 09:20.140 --> 09:24.280 Die Frage ist, sind die regulären Sprachen genau die Automaten? 09:24.860 --> 09:28.280 Der Frage werden wir uns gleich widmen, ich werde aber noch eine Sache 09:28.280 --> 09:33.360 zwischenschalten, die irgendwie zu dieser Potenzmengen-Konstruktion 09:33.360 --> 09:34.360 gut passt. 09:35.160 --> 09:42.140 Wenn Sie sich so nicht-deterministische endliche Automaten angucken, 09:43.660 --> 09:46.920 dann drückt sich der Nicht-Determinismus in zwei Dingen aus. 09:47.620 --> 09:50.540 In den Epsilon-Übergängen und in den Wahlmöglichkeiten. 09:52.860 --> 09:57.660 Und wie ich eben gesagt habe, Sie erinnern sich, diesen Nicht 09:57.660 --> 10:03.020 -Determinismus sozusagen wegzukonstruieren, der Potenzmengen 10:03.020 --> 10:09.260 -Konstruktion führt zu einer Explosion der Zustandsmenge. 10:09.480 --> 10:14.860 Also Sie kriegen sozusagen exponentiell viele Zustände bei dieser 10:14.860 --> 10:15.520 Potenzmenge. 10:16.880 --> 10:21.280 Und die Frage ist jetzt, kann ich denn allein die Epsilon-Übergänge 10:21.280 --> 10:27.320 unterdrücken, ohne dass meine Zustandsmenge stark anwächst? 10:28.140 --> 10:31.040 Und dieser Satz hier sagt, ja, das geht. 10:31.680 --> 10:36.580 Der Satz sagt, zu jedem Nicht-Deterministischen Endlichen Automaten A 10:36.580 --> 10:41.100 mit Epsilon-Übergängen gibt es einen Nicht-Deterministischen Endlichen 10:41.100 --> 10:46.740 Automaten, nennen wir den A-Schlange, ohne Epsilon-Übergänge, der 10:46.740 --> 10:50.840 äquivalent ist, also dieselbe Sprache akzeptiert und nicht mehr 10:50.840 --> 10:51.720 Zustände hat. 10:51.880 --> 10:54.800 Also um die Epsilon-Übergänge loszuwerden, brauche ich jetzt keine 10:54.800 --> 10:56.420 Erweiterung der Zustände. 10:57.320 --> 10:59.820 Aber das überlegen wir uns mal ganz schnell, das ist wirklich nichts 10:59.820 --> 11:00.340 Schwieriges. 11:00.880 --> 11:02.940 Es ist wie gesagt auch nur gut zu wissen. 11:06.450 --> 11:09.190 Schauen wir uns mal hier dieses Beispiel an. 11:09.450 --> 11:12.570 Also ein ganz einfacher, kleiner Nicht-Deterministischer Endlicher 11:12.570 --> 11:14.590 Automat mit Epsilon-Übergängen. 11:15.610 --> 11:18.710 Also es gibt einen Epsilon-Übergang von S nach T, es gibt einen 11:18.710 --> 11:21.970 Epsilon -Übergang vom Zustand U zum Zustand F. 11:24.170 --> 11:27.130 Wie kann ich diese Epsilon-Übergänge loswerden? 11:29.290 --> 11:31.170 Ich fange mal von hinten an. 11:31.890 --> 11:35.150 Also hier habe ich mir so eine Tabelle gemacht mit den Zuständen. 11:36.050 --> 11:40.390 Und wenn ich von hinten anfange, naja gut, ich muss so den Epsilon 11:40.390 --> 11:45.130 -Abschluss von den Zuständen bilden und dann die Übergangsfunktion 11:45.130 --> 11:48.010 anpassen auf sozusagen die neuen Zustände. 11:48.310 --> 11:53.150 Wenn ich den Epsilon-Abschluss von F, von unserem Endzustand hier 11:53.150 --> 11:58.610 bilde, dann ist das nichts anderes als F, denn von F nach F oder von F 11:58.610 --> 12:02.210 gibt es keinen Epsilon-Übergang zu irgendeinem anderen Zustand. 12:03.110 --> 12:06.070 Diesen von Epsilon bleibe ich hier in F. 12:07.190 --> 12:10.510 Und dementsprechend ändert sich hier auch nichts an der 12:10.510 --> 12:12.110 Übergangsfunktion. 12:13.230 --> 12:17.710 Der Automat ist sehr klein, bewusst, damit wir hier bei der 12:17.710 --> 12:20.190 Konstruktion nicht zu viel angucken müssen. 12:20.190 --> 12:22.790 Insbesondere haben wir hier nur ein Symbol. 12:23.350 --> 12:25.070 Das Alphabet enthält nur A. 12:25.270 --> 12:28.390 Das heißt, ich muss, wenn ich die neue Übergangsfunktion bilde, auch 12:28.390 --> 12:29.950 nur dieses eine Symbol angucken. 12:30.170 --> 12:35.730 Also wenn ich jetzt von F aus schauen will, wenn ich jetzt den Epsilon 12:35.730 --> 12:39.590 -Abschluss von F betrachte und betrachte, wo komme ich denn dahin bei 12:39.590 --> 12:45.390 Lesen von A, muss ich also nur schauen, da der Epsilon-Abschluss von 12:45.390 --> 12:49.050 F, F ist, wo komme ich denn durch Lesen von A hin und muss keine 12:49.050 --> 12:50.150 anderen Symbole angucken. 12:50.710 --> 12:51.670 Und das ist wieder F. 12:51.930 --> 12:53.430 Hier hinten ist klar, was passiert. 12:53.570 --> 12:56.390 So, und jetzt arbeite ich mich nach vorne. 12:56.870 --> 12:58.250 Ich gucke mir das U an. 12:59.170 --> 13:03.310 Ich gucke mir an, wo komme ich denn durch Lesen von Epsilon von U aus 13:03.310 --> 13:03.530 hin. 13:03.610 --> 13:06.290 Was ist der Epsilon-Abschluss von U? 13:09.830 --> 13:13.230 Entweder komme ich durch Lesen von Epsilon von U nach U, also bleibe 13:13.230 --> 13:17.870 bei U oder weil es einen echten Epsilon-Übergang zu F gibt, komme ich 13:17.870 --> 13:18.290 zu F. 13:18.710 --> 13:22.630 Das heißt, der Epsilon-Abschluss von U ist U, F. 13:23.450 --> 13:27.490 Und jetzt muss ich mir nur angucken, wo komme ich hin, wenn ich von U 13:27.490 --> 13:28.750 aus A lese. 13:31.810 --> 13:35.730 Kann ich erstmal Epsilon lesen und dann A lesen? 13:37.070 --> 13:41.210 Oder angucken, was passiert, wenn ich von U aus direkt A lese. 13:41.990 --> 13:45.230 Wir haben uns ja gesagt, dass wir bei nicht-deterministischen 13:45.230 --> 13:49.630 endlichen Automaten nur die echten Übergänge, die es gibt, hinmalen. 13:51.050 --> 13:54.450 Und hier gibt es nur einen Übergang bei Lesen von Epsilon. 13:56.130 --> 13:59.230 Wenn ich aus Epsilon sozusagen loswerden will, muss ich also jetzt den 13:59.230 --> 14:03.570 Epsilon -Abschluss von U angucken und gucken, wo führt mich die 14:03.570 --> 14:08.390 Übergangsfunktion denn hin vom Epsilon-Abschluss von U aus, wenn ich A 14:08.390 --> 14:08.830 lese. 14:08.830 --> 14:10.470 Und das ist hier F. 14:13.470 --> 14:15.570 Und dann arbeite ich mich weiter vor. 14:16.950 --> 14:18.810 Ich gucke mir T an. 14:20.610 --> 14:23.650 Der Epsilon-Abschluss von T ist T. 14:24.210 --> 14:26.390 Von T aus gibt es keinen weiteren Epsilon-Übergang. 14:28.570 --> 14:32.530 Lesen von A führt mich von T aus nach U. 14:33.430 --> 14:36.370 Aber von U aus komme ich auch mit Epsilon nach F. 14:36.370 --> 14:44.670 Das heißt, vom Epsilon-Abschluss von T aus komme ich bei Lesen von A 14:44.670 --> 14:46.350 nach U und nach F. 14:50.720 --> 14:56.380 Sozusagen bei der Sache hier habe ich als echten Übergang für meinen 14:56.380 --> 15:02.460 Automaten, bei denen die Epsilon-Übergänge unterdrückt wurden, von U 15:02.460 --> 15:06.000 bei Lesen von A diesen hier entdeckt. 15:06.000 --> 15:08.520 Deshalb ist er hier jetzt grün eingezeichnet. 15:09.080 --> 15:11.900 Und hier habe ich jetzt entdeckt, na gut, das gab es vorher schon, und 15:11.900 --> 15:17.220 das hier gibt es noch als direkten Übergang bei Lesen von A von T aus, 15:18.760 --> 15:25.100 wenn ich hier sozusagen diesen Epsilon-Übergang einbeziehe, um ihn 15:25.100 --> 15:27.860 dann nicht mehr zu verwenden. 15:28.380 --> 15:33.340 Hier habe ich den echten Übergang von T nach F bei Lesen von A 15:33.340 --> 15:34.040 entdeckt. 15:34.040 --> 15:37.300 So, und jetzt gehe ich eben wieder eins vor, gucke mir S an, den 15:37.300 --> 15:42.340 Epsilon -Abschluss von S, das ist ST, von S aus kann ich durch Lesen 15:42.340 --> 15:46.440 von Epsilon bei S bleiben oder zu T kommen, und dann der entsprechende 15:46.440 --> 15:48.800 Übergang bei Lesen von A. 15:53.980 --> 15:59.120 Ich komme nach U, und von U aus komme ich auch nach F. 16:01.680 --> 16:09.520 Das heißt also, Delta Epsilon-Abschluss von S, A SUF. 16:11.780 --> 16:20.240 Und das heißt insgesamt, ich habe diese grünen Übergänge sozusagen 16:20.240 --> 16:25.060 ermittelt, durch sozusagen unterdrückende Epsilon-Übergänge. 16:26.380 --> 16:32.100 Was ich also bekomme jetzt ist folgender nicht deterministischer 16:32.100 --> 16:36.780 endlicher Automat, der dasselbe kann wie der, den ich vorher auf der 16:36.780 --> 16:40.120 Folie hatte, der aber keine Epsilon-Übergänge mehr hat. 16:40.280 --> 16:43.060 Der hat die gleiche Anzahl von Zuständen. 16:44.280 --> 16:48.340 Weil ich mache hier so eine Art Potenzmengen-Konstruktion, nur für 16:48.340 --> 16:54.240 jeden Zustand kommt dann nur eine Menge von Zuständen rein, der 16:54.240 --> 16:56.900 Epsilon -Übergang des Zustands, sonst nichts. 16:57.620 --> 16:59.300 Und die kann ich dann wieder gleichsetzen. 17:01.540 --> 17:04.780 Und das machen wir jetzt einfach formal in diesem Beweis. 17:06.300 --> 17:10.840 Also ich habe so einen endlichen Automaten A, der ist nicht 17:10.840 --> 17:14.660 deterministisch, der hat Epsilon-Übergänge, und dazu baue ich jetzt 17:14.660 --> 17:19.980 eine Schlange, einen neuen, nicht deterministischen endlichen 17:19.980 --> 17:23.880 Automaten, der keine Epsilon-Übergänge hat, und das mache ich wie 17:23.880 --> 17:24.360 folgt. 17:25.460 --> 17:29.580 Erstmal bei der Zustandsmenge, da kann ich im Wesentlichen dieselbe 17:29.580 --> 17:30.280 Menge nehmen. 17:31.380 --> 17:34.440 Ich muss allerdings bei den Endzuständen aufpassen. 17:37.460 --> 17:43.000 Sie können über Epsilon-Übergänge von einem Nicht-Endzustand in einen 17:43.000 --> 17:47.060 Endzustand kommen, in ihrem nicht deterministischen endlichen 17:47.060 --> 17:49.040 Automaten mit Epsilon-Übergängen. 17:49.740 --> 17:53.520 Und wenn ich die Epsilon-Übergänge sozusagen unterdrücke, durch die 17:53.520 --> 17:58.340 Konstruktion, die wir eben im Beispiel hatten, heißt das also, dass 17:58.340 --> 18:04.060 sie Zustände, die vorher Nicht-Endzustände waren, als Endzustände 18:04.060 --> 18:05.280 interpretieren müssen. 18:05.600 --> 18:09.460 Weil die entsprechende Menge, die dazu gehört, der Epsilon-Abschluss, 18:09.920 --> 18:11.800 einen Endzustand enthält. 18:12.360 --> 18:18.500 Und deshalb definieren wir Q-Schlange so, dass wir aus Q F rausnehmen 18:18.500 --> 18:23.500 und eine neue Endzustandsmenge F-Schlange definieren. 18:23.860 --> 18:28.320 Und das soll gerade die Menge der Zustände sein, deren Epsilon 18:28.320 --> 18:35.080 -Abschluss einen nicht leeren Schlitt mit der Zustandsmenge hat, für 18:35.080 --> 18:36.160 den Ausgangsautomaten. 18:38.200 --> 18:39.160 Hier ein Beispiel. 18:41.420 --> 18:43.740 Haben wir das noch nicht eingezeichnet. 18:45.960 --> 18:53.740 Da hier der Epsilon-Abschluss von U F enthält, ist das hier auch ein 18:53.740 --> 18:54.560 Endzustand. 19:01.450 --> 19:05.450 Der Startzustand bleibt der gleiche und die Übergangsfunktion ist 19:05.450 --> 19:05.950 jetzt klar. 19:07.710 --> 19:13.110 Im Prinzip nehme ich, wenn ich die Schlange von Q,A bilde, den Epsilon 19:13.110 --> 19:19.770 -Abschluss von Q und schaue, wo komme ich denn durch Lesen von A von 19:19.770 --> 19:20.470 da aus hin. 19:21.170 --> 19:24.610 Und ich muss natürlich für den Fall, dass A gleich Epsilon ist, noch 19:24.610 --> 19:25.870 den Übergang definieren. 19:26.330 --> 19:30.890 Nun in unserem endlichen Automat, ohne Epsilon-Übergänge, bleibt man 19:30.890 --> 19:33.070 im Zustand D. 19:34.190 --> 19:41.530 Das heißt also, Delta-Schlange von Q,A ist einfach Q, wenn A Epsilon 19:41.530 --> 19:46.250 ist und ist ansonsten Delta, die Übergangsfunktion unseres 19:46.250 --> 19:51.510 Ausgangsautomaten, von Epsilon-Abschluss von Q,A. 19:52.350 --> 19:52.910 That's it. 19:54.530 --> 20:00.890 Und auf die Art bekommen Sie nicht mehr Zustände und die Sprache, die 20:00.890 --> 20:03.590 akzeptiert wird, ist auch dieselbe, per Konstruktion. 20:04.530 --> 20:07.850 Also das ist keine schwierige Sache, aber es ist gut zu wissen, dass 20:07.850 --> 20:14.330 das Loswerden von Epsilon-Übergängen bei einem nicht deterministischen 20:14.330 --> 20:19.990 endlichen Automat noch nicht zu einem Anwachsen der Zustandsslänge 20:19.990 --> 20:20.370 führt. 20:21.430 --> 20:26.210 Das kommt erst rein, wenn Sie die Wahlmöglichkeiten loswerden wollen. 20:32.390 --> 20:37.050 Jetzt aber zu der wichtigeren Frage, die wir eben gestellt haben. 20:37.050 --> 20:43.110 Wie ist das denn, wenn ich jetzt einfach einen endlichen Automaten 20:43.110 --> 20:43.570 habe? 20:46.230 --> 20:50.250 Was ist denn die Eigenschaft der entsprechenden Sprache? 20:51.130 --> 20:56.530 Also wir haben schon festgestellt, für den regulären Sprachen gehören 20:56.530 --> 21:00.430 die endlichen Automaten in dem Sinne, dass ich zu jeder regulären 21:00.430 --> 21:04.730 Sprache einen endlichen Automaten angeben kann, der diese akzeptiert. 21:05.730 --> 21:08.450 Und das ist jetzt sozusagen die Umkehrung. 21:08.730 --> 21:14.710 Kann ich auch für jeden endlichen Automaten eine entsprechende 21:14.710 --> 21:20.350 reguläre Sprache angeben, die genau die ist, die von dem endlichen 21:20.350 --> 21:21.810 Automaten akzeptiert wird? 21:22.150 --> 21:25.930 Also insgesamt heißt das dann, wenn der Satz auch stimmt, die 21:25.930 --> 21:30.130 regulären Sprachen, das sind genau die Sprachen, die von endlichen 21:30.130 --> 21:31.630 Automaten akzeptiert werden. 21:33.650 --> 21:37.530 Also wir wollen beweisen, jede Sprache, die von einem endlichen 21:37.530 --> 21:39.490 Automaten erkannt wird, ist regulär. 21:40.170 --> 21:43.650 Und wenn das keine Rolle spielt, ob wir es jetzt mit einem 21:43.650 --> 21:47.410 deterministischen oder nicht deterministischen endlichen Automaten zu 21:47.410 --> 21:49.290 tun haben, sagen wir das auch nicht dazu. 21:49.690 --> 21:52.590 Da wir jetzt wissen, deterministische und nicht deterministische 21:52.590 --> 21:57.710 endliche Automaten sind äquivalent, können dasselbe, ist das bei dem 21:57.710 --> 22:06.610 Satz jetzt auch nicht relevant, sozusagen, dass jede Sprache, die von 22:06.610 --> 22:10.010 einem deterministischen oder nicht deterministischen endlichen 22:10.010 --> 22:15.550 Automaten erkannt wird, dass jede solche Sprache regulär ist. 22:16.310 --> 22:17.750 Ja, das müssen wir beweisen. 22:19.350 --> 22:21.270 Wie beweist man sowas? 22:22.110 --> 22:28.890 Naja, jetzt starten wir von dem endlichen Automaten und wir müssen 22:28.890 --> 22:33.230 jetzt sozusagen die Sprache, die von dem endlichen Automaten 22:33.230 --> 22:38.810 akzeptiert wird, so beschreiben, dass man der Beschreibung ansieht, 22:38.970 --> 22:40.670 dass diese Sprache regulär ist. 22:41.490 --> 22:45.230 Das heißt, die Beschreibung sollte möglichst Beschreibung durch einen 22:45.230 --> 22:46.630 regulären Ausdruck sein. 22:47.770 --> 22:50.950 Das wäre natürlich auch schön, wenn wir das systematisch machen 22:50.950 --> 22:54.790 könnten, sodass wir, wenn wir jetzt mal in Zukunft irgendeinen 22:54.790 --> 23:00.830 endlichen Automaten vorgelegt bekommen, nicht nur durch, ich sag mal, 23:00.890 --> 23:07.250 scharfes Hinsehen versuchen können, zu sagen, welche Sprache das ist, 23:07.310 --> 23:12.070 die von dem Automaten akzeptiert wird, sondern wirklich, dass wir 23:12.070 --> 23:15.370 durch eine Konstruktion diese Sprache auch aufbauen können. 23:16.070 --> 23:22.390 So, es ist hier ganz praktisch, bei einem deterministischen endlichen 23:22.390 --> 23:24.750 Automaten zu starten. 23:25.410 --> 23:29.810 Diese Konstruktion wird so sein, dass Sie aus dem deterministischen 23:29.810 --> 23:34.770 endlichen Automaten einen regulären Ausdruck bauen können, der die 23:34.770 --> 23:38.010 Sprache beschreibt, die von diesem deterministischen endlichen 23:38.010 --> 23:39.570 Automaten akzeptiert wird. 23:40.010 --> 23:43.810 Wenn Sie einen nicht deterministischen endlichen Automaten vorgelegt 23:43.810 --> 23:49.850 bekommen, müssen Sie möglicherweise erst mal diesen Umweg gehen, per 23:49.850 --> 23:52.510 Potenzmengenkonstruktion einen deterministischen endlichen Automaten 23:52.510 --> 23:57.170 ausbauen und dann die Konstruktion, die hier im Beweis kommt, 23:57.990 --> 24:00.350 anwenden, um zur regulären Sprache zu kommen. 24:01.230 --> 24:04.770 Also was wir machen müssen ist, wir müssen zeigen, dass die Sprache, 24:04.850 --> 24:09.990 die von dem DAA akzeptiert wird, regulär ist. 24:11.210 --> 24:15.310 Was ist die Sprache, die von dem DAA akzeptiert wird? 24:16.190 --> 24:23.450 Das ist die Menge all der Worte aus Sigma-Stern, deren Abarbeitung von 24:23.450 --> 24:26.050 S in einen Endzustand führt. 24:26.870 --> 24:32.630 Also L gleich Menge aller W aus Sigma-Stern, A endet nach Abarbeitung 24:32.630 --> 24:35.290 von W in einem Zustand aus der Menge F. 24:35.290 --> 24:39.990 So können wir diese Sprache L von A beschreiben. 24:40.810 --> 24:43.950 Der Beschreibung sieht man jetzt noch nicht an, dass das eine reguläre 24:43.950 --> 24:44.510 Sprache ist. 24:44.590 --> 24:47.850 Wir müssen jetzt die Arbeitsweise des endlichen Automaten irgendwie 24:47.850 --> 24:48.250 benutzen. 24:49.630 --> 24:54.070 Dafür gucken wir uns mal an, wie so eine Abarbeitung eines Wortes 24:54.070 --> 24:55.270 aussieht. 24:55.990 --> 25:02.570 Bei einem Wort W gleich A1 bis AK, also irgendein Wort der Länge K aus 25:02.570 --> 25:05.390 Sigma -Stern, passiert folgendes. 25:06.310 --> 25:12.430 Das erste Symbol führt uns vom Startzustand aus in einen anderen 25:12.430 --> 25:13.130 Zustand. 25:13.390 --> 25:15.310 Anders, der muss nicht verschieden sein. 25:16.390 --> 25:20.210 Das nächste Symbol wieder in einen Zustand, das nächste Symbol wieder 25:20.210 --> 25:21.530 in einen Zustand und so weiter. 25:21.530 --> 25:29.410 Also A1 bis AK führt uns irgendwie von dem ersten Zustand S zu einem 25:29.410 --> 25:33.370 weiteren Zustand, zum weiteren Zustand, zum weiteren Zustand und so 25:33.370 --> 25:33.830 weiter. 25:35.950 --> 25:42.730 Also Abarbeitung von A1 bis AK bewirkt das Durchlaufen von Zuständen 25:42.730 --> 25:48.030 S, Q1, Q2, Q3 und so weiter bis QK. 25:49.230 --> 25:51.950 Und diese Zustände, die müssen nicht verschieden sein. 25:52.230 --> 25:55.150 Bei der Abarbeitung kann das schon irgendwie mal so im Kreis gehen. 25:57.530 --> 26:04.910 Und wir suchen jetzt, wir interessieren uns für die Wörter, die 26:04.910 --> 26:10.650 akzeptiert werden von dem endlichen Automaten, wo uns A1 bis AK also 26:10.650 --> 26:14.110 in einen QK führt, das Endzustand ist. 26:14.810 --> 26:18.310 Wir suchen die Wörter, sodass der letzte Zustand in F ist. 26:20.930 --> 26:24.790 So und jetzt ist der erste Schritt, wir reduzieren jetzt so ein 26:24.790 --> 26:29.170 bisschen die Sprache, die wir beschreiben wollen, auf Teilsprachen. 26:29.970 --> 26:33.030 Dass wir über Teilsprachen angelangt sind, die wir so beschreiben 26:33.030 --> 26:34.770 können, dass man sieht, die sind regulär. 26:35.910 --> 26:40.110 Und unsere Reduzierung ist so, dass man von denen dann aber auch zur 26:40.110 --> 26:43.570 Ausgangssprache kommt, durch nur sowas wie Vereinigung oder 26:43.570 --> 26:45.870 Produktbildung oder klinische Abschlussbildung. 26:46.890 --> 26:50.290 Und das allererste, was wir machen können, ist, dass wir einfach 26:50.290 --> 26:54.610 getrennt für jeden Endzustand nachschauen, wie sieht denn die Sprache 26:54.610 --> 27:02.070 aus, die aus den Worten besteht, deren Abarbeitung uns in diesen 27:02.070 --> 27:03.650 bestimmten Endzustand führt. 27:03.650 --> 27:07.150 Wenn wir für jede dieser Sprachen, also wir gehen alle Endzustände aus 27:07.150 --> 27:12.250 F durch, wenn wir für jede dieser Sprachen eine reguläre Beschreibung, 27:12.490 --> 27:17.810 einen regulären Ausdruck angeben können, dann ist auch die Vereinigung 27:17.810 --> 27:19.470 dieser Sprachen regulär. 27:20.590 --> 27:23.070 Das heißt also, dann ist die Sprache, die uns interessiert, auch 27:23.070 --> 27:23.490 regulär. 27:23.550 --> 27:27.470 Also wir brauchen eigentlich nur, ich sag mal, LF anzugucken. 27:27.470 --> 27:29.030 Hier steht es auch. 27:29.410 --> 27:35.190 Zu F Endzustand definiere LF als die Menge der Wörter aus Sigma Stern. 27:35.590 --> 27:39.370 A endet nach Abarbeitung dieses Wortes in F. 27:40.790 --> 27:42.730 Und die kann ich auch anders hinschreiben. 27:43.670 --> 27:45.970 Die Menge der Wörter aus B aus Sigma Stern. 27:46.410 --> 27:49.710 B überführt S in F im Automaten A. 27:50.770 --> 27:52.590 Das ist jetzt irgendwie so ganz wichtig. 27:52.990 --> 27:55.090 Wir schauen uns also jetzt wieder an, was passiert bei der 27:55.090 --> 27:55.770 Abarbeitung. 27:56.630 --> 27:59.110 Was werden da an Zwischenzustände durchlaufen? 27:59.290 --> 28:01.770 Wir versuchen danach, das Ganze nochmal aufzuspalten. 28:02.970 --> 28:08.330 Also wenn wir all diese LF für alle kleinen F aus Groß F haben, dann 28:08.330 --> 28:12.590 ist ja die Sprache, die uns interessiert, gerade die Vereinigung über 28:12.590 --> 28:16.730 kleinen F aus Groß S, F LF. 28:18.050 --> 28:22.570 Und wenn diese kleinen F regulär sind, dann ist auch diese Vereinigung 28:22.570 --> 28:23.270 regulär. 28:27.080 --> 28:29.440 So, das L klein F. 28:30.420 --> 28:32.240 Menge der Wörter aus Sigma Stern. 28:32.360 --> 28:38.260 W überführt S in klein F in dem Automaten A. 28:39.520 --> 28:42.500 So, jetzt geht es ans wirkliche Konstruieren. 28:43.260 --> 28:46.900 Jetzt nummerieren wir unsere Zustände einfach durch, irgendwie. 28:47.500 --> 28:49.580 Q1 bis QN. 28:50.220 --> 28:52.140 Unser Automat habe N Zustände. 28:52.660 --> 28:54.000 Das nennen wir die Q1 bis QN. 28:56.890 --> 29:07.610 Und dann definieren wir für jedes Zustandspaar QRQT die Sprache LQRQT 29:07.610 --> 29:13.610 als die Sprache der Wörter Sigma Stern, die von QR nach QT führen. 29:15.570 --> 29:20.130 Das sind jetzt allgemeinere Sprachen als die Sprache zu dem Automat. 29:20.130 --> 29:25.130 Einfach nur die Wörter, die von einem Zustand, den wir QR nennen, zu 29:25.130 --> 29:28.130 einem Zustand, den wir QT nennen, führen. 29:28.830 --> 29:30.390 Das ist für alle Zustandspaare. 29:31.330 --> 29:34.490 Egal, ob es N Zustände oder nicht N Zustände sind. 29:35.570 --> 29:36.750 Schauen wir uns mal die an. 29:38.610 --> 29:44.390 Wenn wir die alle als reguläre Sprachen durch reguläre Ausdrücke 29:44.390 --> 29:47.670 beschreiben können, dann wissen wir insbesondere auch, dass die 29:47.670 --> 29:50.550 Sprache LF, die uns hier interessiert, regulär ist. 29:50.910 --> 29:52.450 Nämlich, die ist eine von der Sorte. 29:53.210 --> 29:59.530 Die ist nämlich so geschrieben, L unten kleinen s, kleinen f. 30:00.890 --> 30:04.070 Also QR ist s, QT ist kleinen f. 30:06.510 --> 30:13.990 Und diese LQRQT für beliebige Zustandspaare QRQT, die unterteilen wir 30:13.990 --> 30:14.950 jetzt noch weiter. 30:16.130 --> 30:20.790 LQRQT, das sind einfach die Wörter, die von QR nach QT führen, in A. 30:22.050 --> 30:24.170 Über irgendwelche Zwischenzustände. 30:25.030 --> 30:29.470 Jetzt machen wir dieses irgendwelche Zwischenzustände ein bisschen 30:29.470 --> 30:34.930 spezifischer und sagen, wir gucken systematisch an, welche Zustände 30:34.930 --> 30:37.210 wir als Zwischenzustände erlauben. 30:38.210 --> 30:41.370 Und dafür ist diese Nummerierung wichtig. 30:41.710 --> 30:45.930 Wir haben die irgendwie nach irgendeiner Reihenfolge durchnummeriert, 30:45.950 --> 30:48.430 die Zustände in Q1 bis QN. 30:49.090 --> 30:54.070 Und jetzt schauen wir sozusagen als potenzielle Zwischenzustände an. 30:54.910 --> 30:56.270 Nur Q1. 30:56.790 --> 30:58.570 Oder Q1, Q2. 30:58.830 --> 31:00.590 Oder Q1, Q2, Q3. 31:01.350 --> 31:02.890 Oder Q1 bis QI. 31:04.250 --> 31:08.850 Für alle Möglichkeiten, was I sein kann, also auch bis zu QN hin. 31:09.830 --> 31:15.430 Also wir definieren jetzt nochmal als eine Teilsprache von LQRQT, 31:16.410 --> 31:19.150 LQRIQT. 31:20.190 --> 31:25.970 Und das soll die Menge der W aus Sigma Stern sein, für die gilt, 31:26.610 --> 31:33.930 Abarbeitung von W, ausgehend von QR, führt nach QT. 31:36.550 --> 31:43.250 Aber dazwischen werden nur Zustände aus Q1 bis QI durchlaufen. 31:45.610 --> 31:51.030 Also wir gucken sozusagen von unserer Zustandsmenge Q1 bis QN immer 31:51.030 --> 31:52.690 diese Anfangsstücke an. 31:53.070 --> 31:53.670 Für alle I. 31:55.050 --> 31:58.430 Und sagen, nur die sollen erlaubt sein als Zwischenzustände. 32:00.330 --> 32:03.090 Also hier haben wir jetzt eine ganze Menge von Sprachen. 32:03.410 --> 32:06.290 Alle möglichen Paare QRQT kommen hier in Frage. 32:06.810 --> 32:11.710 Und als Zwischenzustände für jedes I jeweils die Menge Q1 bis QI. 32:11.710 --> 32:15.490 Also anders ausgedrückt oder mal hingemalt. 32:16.510 --> 32:22.010 Also W ist in QRIQT, wenn W also folgendes bewirkt. 32:22.450 --> 32:27.770 Bei Abarbeiten von W kommen wir von QR nach QT und dazwischen 32:27.770 --> 32:31.810 durchlaufen werden nur Zustände aus Q1 bis QI. 32:32.790 --> 32:36.510 Wenn wir diese Sprachen alle durch reguläre Ausdrücke beschreiben 32:36.510 --> 32:39.870 können, dann können wir auch folgende Sprache durch einen regulären 32:39.870 --> 32:40.870 Ausdruck beschreiben. 32:40.870 --> 32:48.930 Die Sprache, die wir hier LQRQT genannt haben, die ist nämlich in der 32:48.930 --> 32:54.650 Schreibweise nichts anderes als LQR, N, QT. 32:56.050 --> 33:00.510 Also das N steht für alle Zustände, Q1 bis QN sind als 33:00.510 --> 33:01.330 Zwischenzustände. 33:04.390 --> 33:08.990 Wenn die alle regulär sind, dann ist auch die regulär. 33:09.410 --> 33:14.110 Wenn die regulär ist, dann ist auch unser LSF regulär. 33:14.550 --> 33:19.770 Und dann ist auch unsere Vereinigung über alle Endzustände LF. 33:23.730 --> 33:28.110 Und an die hier kommen wir jetzt von unten ran. 33:28.110 --> 33:33.050 Indem wir erstmal gar keinen Zwischenzustand erlauben, dann nur Q1 als 33:33.050 --> 33:36.890 Zwischenzustand erlauben, dann nur Q1, Q2 und so weiter. 33:37.530 --> 33:41.330 Und das Prinzip, das hier angewendet wird, ein algorithmisches 33:41.330 --> 33:45.450 Prinzip, das Sie kennen, ist ein Prinzip der dynamischen 33:45.450 --> 33:46.810 Programmierung. 33:47.570 --> 33:50.930 Wir fangen so bei 0 an, dann 1 und so weiter. 33:51.450 --> 33:59.570 Und dann irgendwann mal allgemein, wie können wir LQR, I plus 1, QT 33:59.570 --> 34:09.390 ausdrücken, indem wir LQR, I plus 1, QT zurückführen auf irgendwelche 34:09.390 --> 34:12.190 LQR, I, QT. 34:15.950 --> 34:22.450 Also, wir zeigen LQR, I, QT ist für beliebige zustandsbare QR, QT aus 34:22.450 --> 34:25.990 Q und beliebiges I zwischen 1 und N regulär. 34:26.130 --> 34:28.130 Und das machen wir systematisch von unten. 34:28.510 --> 34:32.710 Wir betrachten zunächst direkte Übergänge, also I gleich 0. 34:33.130 --> 34:35.510 Also kein Zwischenzustand ist erlaubt. 34:35.510 --> 34:42.890 Also per sozusagen Definition ist LQR 0 QT die Menge der Worte, die 34:42.890 --> 34:46.590 von QR nach QT führt, ohne überhaupt einen Zwischenzustand zu 34:46.590 --> 34:47.110 benutzen. 34:47.750 --> 34:51.230 Abarbeitung von W führt von QR nach QT ohne Zwischenzustand. 34:52.370 --> 34:57.750 Jetzt gibt es zwei Fälle, entweder das R ist gleich T oder das R ist 34:57.750 --> 34:58.410 ungleich T. 35:00.250 --> 35:03.590 Wenn R gleich T ist, dann ist also QR gleich QT. 35:04.810 --> 35:12.690 Dann ist LQR 0 QT die Menge der Symbole, für die gilt Delta QTA ist 35:12.690 --> 35:13.670 wieder QT. 35:14.050 --> 35:15.510 Das QR ist ja gleich QT. 35:17.810 --> 35:21.710 Also alle Symbole, die vom Zustand zu sich selbst führen. 35:22.710 --> 35:25.390 Und, und deshalb ist das jetzt wichtig, dass wir hier genau hingucken, 35:25.390 --> 35:26.830 natürlich Epsilon. 35:27.250 --> 35:28.730 Epsilon kommt hier jetzt rein. 35:29.430 --> 35:33.170 Denn bei dem Zustand bleiben, das ist ja nichts anderes als das, was 35:33.170 --> 35:37.170 wir hier betrachten, tun wir auch, indem wir Epsilon lesen. 35:39.270 --> 35:45.210 Also für R gleich T oder QR gleich QT ist LQR 0 QT die Menge der 35:45.210 --> 35:50.330 Symbole A aus Sigma, Delta QTA ist QT, vereinigt mit Epsilon. 35:51.190 --> 35:56.910 Und jetzt ansonsten, wenn QR und QT verschieden sind, betrachten wir 35:56.910 --> 36:03.950 alle Wörter, für die gilt Delta QR W ist QT, ohne dass irgendein 36:03.950 --> 36:07.210 Zwischenzustand benutzt wurde. 36:08.370 --> 36:14.470 Also LQR 0 QT für QR ungleich QT ist ja dann nichts anderes als die 36:14.470 --> 36:15.630 Menge der Symbole. 36:15.630 --> 36:18.710 Längere Worte können da nicht vorkommen, weil wir keine 36:18.710 --> 36:20.450 Zwischenzustände benutzen dürfen. 36:21.010 --> 36:26.010 Menge der Symbole A aus Sigma, Delta QR A ist genau QT. 36:27.150 --> 36:28.170 Ganz einfach. 36:28.990 --> 36:34.410 Das ist sozusagen unser Induktionsanfang und nur um es mal 36:34.410 --> 36:37.910 festzuhalten, diese Sprachen, die sind regulär. 36:39.630 --> 36:43.750 Das sind ja einfach Vereinigungen von einelementigen Sprachen. 36:43.950 --> 36:44.790 Die sind regulär. 36:45.630 --> 36:53.290 Und mit denen bauen wir jetzt systematisch LQR 1 QT, LQR und so weiter 36:53.290 --> 36:57.450 bis LQR I QT für beliebiges I. 37:00.860 --> 37:05.900 Also nochmal die Konstruktion jetzt auch richtig zu verstehen von I 37:05.900 --> 37:06.820 nach I plus 1. 37:07.020 --> 37:10.500 Gucken wir uns I gleich 1 an, von 0 auf 1 sozusagen. 37:11.200 --> 37:14.760 Also LQR 1 QT ist die Menge der Wörter aus Sigma Stern. 37:14.760 --> 37:21.940 W überführt von QR nach QT und dabei darf nur Q1 verwendet werden. 37:23.080 --> 37:29.540 Das heißt entweder direkt, sogar ohne Q1 zu verwenden, oder nur in 37:29.540 --> 37:31.040 Verwendung von Q1. 37:37.610 --> 37:43.190 Direkt, hier mal genauer aufschreiben, direkt von QR nach QT ohne 37:43.190 --> 37:50.150 Zwischenzustand, führt uns genau die Sprache LQR 0 QT. 37:52.390 --> 37:57.090 Das ist ja die Sprache der Wörter, die von QR nach QT führt, ohne 37:57.090 --> 37:59.270 irgendeinen Zwischenzustand zu verwenden. 37:59.670 --> 38:04.090 Und jetzt fisseln wir auseinander, was passiert, wenn wir von QR nach 38:04.090 --> 38:07.790 QT kommen und dazwischen tatsächlich Q1 verwenden. 38:08.570 --> 38:12.670 Diese 1 sagt ja, wir dürfen höchstens Q1 als Zwischenzustand. 38:14.430 --> 38:16.210 Ja, wie sehen denn die Worte aus? 38:16.310 --> 38:20.090 Das sind Worte, die führen uns von QR nach Q1. 38:24.330 --> 38:30.650 Möglicherweise hängen da dran Worte, die uns von Q1 nach Q1 führen und 38:30.650 --> 38:33.610 irgendwann geht es dann weiter direkt nach QT. 38:35.210 --> 38:38.630 Das ist das Einzige, was passieren kann, wenn wir nur Q1 als 38:38.630 --> 38:40.050 Zwischenzustand verwenden. 38:40.050 --> 38:53.750 Das heißt also, LQR 0 QT ist vereinigt mit LQR 0 Q1, die Sprache, die 38:53.750 --> 39:04.370 uns ohne Zwischenzustand von QR nach Q1 führt, mal LQ1 0 Q1 Stern, die 39:04.370 --> 39:09.050 Sprache, die uns von Q1 nach Q1 führt, nur über Q1, 39:12.750 --> 39:22.870 ohne Zwischenzustand, mal Q1 0 QT, die Sprache, die uns von Q1 nach QT 39:22.870 --> 39:24.810 führt, ohne Zwischenzustand. 39:26.310 --> 39:33.250 Das Schöne ist, die Art und Weise, wie wir die Sprache beschreiben 39:33.250 --> 39:36.890 können, entspricht wieder einem regulären Ausdruck. 39:37.510 --> 39:42.770 Es kommt nur Konkatenation oder Mal, also Produkt der Sprachen und 39:42.770 --> 39:43.750 klinischer Abschluss vor. 39:44.810 --> 39:50.090 Das heißt also, insgesamt ist dieses LQR 1 QT auch wieder regulär. 39:50.090 --> 39:54.330 Wenn die hier alle regulär sind, von denen wissen wir das ja schon, 39:54.450 --> 39:56.170 das war sozusagen unser Anfang. 39:56.920 --> 40:11.160 So, und jetzt allgemein können wir also LQR I plus 1 QT nach demselben 40:11.160 --> 40:20.140 Schema zurückführen auf LQR I, QT für beliebige Paare QR QT und 40:20.140 --> 40:24.320 beachte, QR oder QT kann auch QI plus 1 sein. 40:25.420 --> 40:29.080 Wenn wir hier in der Mitte einschränken, dann betrifft das nur die 40:29.080 --> 40:29.380 Zwischenzustände. 40:30.520 --> 40:36.740 Das heißt also, LQR I plus 1 QT können wir beschreiben als LQR I QT. 40:37.300 --> 40:42.440 Das sind die Wörter, die von QR nach QT führen, nur unter Benutzung 40:42.440 --> 40:44.940 von Zuständen aus Q1 bis QI. 40:46.080 --> 40:50.740 Und die Sprache, die uns von QR nach QT führt, unter Benutzung von 40:50.740 --> 40:52.620 zusätzlich QI plus 1. 40:53.020 --> 40:57.360 Und die können wir aufspalten in die Sprache, die uns von QR nach QI 40:57.360 --> 41:02.060 plus 1 führt, nur unter Benutzung von Zuständen aus Q1 bis QI. 41:03.000 --> 41:08.400 Mal die Sprache, die uns von QI plus 1 zu QI plus 1 führt, nur unter 41:08.400 --> 41:11.380 Benutzung von Zuständen aus Q1 bis QI. 41:12.190 --> 41:13.800 Und davon der klinische Abschluss. 41:14.600 --> 41:19.660 Mal die Sprache, die uns von QI plus 1 nach QT führt, nur unter 41:19.660 --> 41:21.780 Benutzung von Q1 bis QI. 41:22.520 --> 41:23.180 Fertig. 41:24.480 --> 41:28.740 Das heißt also, jede dieser Sprachen für beliebiges I können wir so 41:28.740 --> 41:29.400 beschreiben. 41:29.660 --> 41:33.580 Und das ist eine Beschreibung, die direkt als regulärer Ausdruck 41:33.580 --> 41:35.360 dasteht. 41:36.740 --> 41:41.260 Das heißt also, wir haben für beliebige Zustandspaare, und die 41:41.260 --> 41:44.180 Zustandspaare schreibe ich jetzt gar nicht mehr hin, dafür schreibe 41:44.180 --> 41:47.760 ich hier nur so einen Punkt hier vorne und einen Punkt hier hinten 41:47.760 --> 41:52.280 hin, jede beliebige Zustandspaare haben wir gezeigt, dass die 41:52.280 --> 41:58.040 entsprechende Sprache, bei der nur Zwischenzustände I bis I plus 1 41:58.040 --> 42:04.420 verwendet werden, aufgebaut werden kann durch diese Sprachen, die nur 42:04.420 --> 42:10.140 Zwischenzustände aus Q1 bis QI verwenden, nur unter Benutzung von 42:10.140 --> 42:14.300 Vereinigung, Produktbildung und klinischer Abschluss von Sprachen. 42:14.920 --> 42:17.960 Das heißt also, wenn die regulär sind, dann sind die auch regulär. 42:18.820 --> 42:21.600 Und im Prinzip haben wir hier eine Induktion gemacht. 42:21.880 --> 42:26.240 Wir haben also per Induktion gezeigt, dass alle diese Sprachen für 42:26.240 --> 42:32.980 alle I plus 1 zwischen 1 und N regulär sind, für beliebige 42:32.980 --> 42:40.340 Zustandspaare, und damit gilt besonders, die sind auch regulär für die 42:40.340 --> 42:45.400 Zustandspaare SF, F ist ein N-Zustand, und damit haben wir im Prinzip 42:45.400 --> 42:47.860 das bewiesen, was wir beweisen wollten. 42:51.750 --> 42:53.370 Der Beweis ist hier fertig. 42:55.490 --> 43:01.310 Der Beweis ist algorithmisch, die Konstruktion ist nichts anderes als 43:01.310 --> 43:02.770 dynamische Programmierung. 43:04.190 --> 43:09.630 Wenn man die wirklich anwendet, auf einem deterministischen endlichen 43:09.630 --> 43:13.110 Automaten, der nicht klein ist, dann ist das mühselig. 43:13.910 --> 43:17.590 Aber das Prinzip ist ganz einfach und wenn Sie das zwei, dreimal 43:17.590 --> 43:21.190 angewendet haben, dann werden Sie das aus dem FF können. 43:21.590 --> 43:25.810 Wir gucken uns jetzt einfach mal ein ganz kleines Beispiel an, damit 43:25.810 --> 43:27.030 das überschaubar bleibt. 43:28.170 --> 43:32.190 Wir gehen von folgendem deterministischen endlichen Automaten aus. 43:32.790 --> 43:35.430 Der Automat hat zwei Zustände, S und Q. 43:35.430 --> 43:40.770 S ist gleichzeitig auch N-Zustand und die Übergangsfunktion ist, von S 43:40.770 --> 43:44.870 kommt man durch Lesen von 0 oder 1 nach Q und von Q kommt man durch 43:44.870 --> 43:47.970 Lesen von 0 oder 1 nach S. 43:49.150 --> 43:52.970 Hier sieht man auch dem Automaten schon an, welche Sprache der 43:52.970 --> 43:53.430 akzeptiert. 43:55.110 --> 43:58.390 Beliebige Wörter über 0, 1, die gerade Länge haben. 43:59.590 --> 44:02.570 Die Frage ist aber, wie können wir die jetzt durch einen regulären 44:02.570 --> 44:06.870 Ausdruck beschreiben und vor allem die Systematik, wie können wir 44:06.870 --> 44:09.390 diesen regulären Ausdruck systematisch aufbauen. 44:12.570 --> 44:15.870 Wir nummerieren die Zustände durch, also die nennen wir jetzt nicht 44:15.870 --> 44:18.470 mehr S und Q, sondern die nennen wir Q1 und Q2. 44:21.290 --> 44:24.710 Alphabet ist 0, 1, N-Zustand ist S. 44:25.950 --> 44:32.370 Gesucht ist also jetzt die Sprache zu dem Automat und welche ist das 44:32.370 --> 44:33.910 nach unserer Systematik? 44:35.730 --> 44:42.230 Das ist die Sprache der Wörter, die von Q1 nach Q1 führt, unter 44:42.230 --> 44:46.650 Benutzung von beliebigen Zwischenzuständen. 44:48.070 --> 44:53.750 Und da wir nur zwei haben, ist das also unter Benutzung von Zuständen 44:53.750 --> 44:55.910 aus der Zustandsmenge Q1, Q2. 44:56.270 --> 45:00.650 Nach unserer Schreibweise ist das nichts anderes als LQ1, 2Q1. 45:02.310 --> 45:07.630 Also das erste Q1 steht für Startzustand, S, das zweite Q1 steht für 45:07.630 --> 45:10.350 Endzustand, was hier jetzt auch S ist. 45:11.530 --> 45:13.910 Und 2 steht für Q1, Q2. 45:14.670 --> 45:18.930 Und die bauen wir von unten auf, indem wir erstmal die, wo in der 45:18.930 --> 45:23.990 Mitte steht 0, aufbauen und dann die, wo in der Mitte steht 1. 45:25.230 --> 45:28.930 Und darauf können wir dann LQ1, 2Q1 drauf aufbauen. 45:29.990 --> 45:33.090 Also erstmal für beliebige Zustandspaare QI, QJ. 45:35.530 --> 45:41.670 LQI, QJ und dazwischen darf gar kein Zwischenzustand verwendet werden. 45:42.310 --> 45:47.010 Erstmal, wenn I und J gleich sind, dann ist das Epsilon. 45:48.150 --> 45:54.490 Also von S nach S können wir nur durch gar nichts lesen und von Q nach 45:54.490 --> 45:56.570 Q können wir nur durch gar nichts lesen. 45:56.970 --> 45:59.770 Also LQI, 0QI ist Epsilon. 46:01.210 --> 46:04.670 Und dann interessiert uns noch LQI, 0QJ. 46:05.150 --> 46:07.230 Also wie kommen wir von QI nach QJ? 46:07.730 --> 46:09.130 QI ist ungleich QJ. 46:10.910 --> 46:17.610 Ohne einen Zwischenzustand, also LQI, 0QJ, IJ aus 1, 2I ungleich J. 46:18.270 --> 46:23.470 Also wie kommen wir von da nach da ohne Zwischenzustand und wie kommen 46:23.470 --> 46:25.290 wir von da nach da ohne Zwischenzustand? 46:26.430 --> 46:31.070 Von da nach da ohne Zwischenzustand kommen wir durch Lesen von 0 oder 46:31.070 --> 46:31.550 1. 46:32.950 --> 46:39.230 Und von hier nach hier können wir auch durch Lesen von 0 oder 1. 46:39.650 --> 46:46.390 Das heißt also LQI, 0QJ, diese Sprachen, das sind ja jetzt zwei 46:46.390 --> 46:53.750 verschiedene, nämlich LQ1, 0Q2 und LQ2, 0Q1, sind jeweils 0 vereinigt 46:53.750 --> 46:53.990 ein. 46:55.210 --> 46:55.930 Reguläre Haut. 46:56.830 --> 46:58.210 Beschreibt es einfach so. 46:59.090 --> 47:04.070 So und jetzt geht es los mit dem Aufbauen unter Benutzung von den 47:04.070 --> 47:04.630 Sprachen. 47:06.050 --> 47:12.370 Erstmal für QI, QJ ist jeweils Q1, also LQ1, 1Q1. 47:13.690 --> 47:19.910 Führen wir nach dem Schema zurück auf Sprachen, wo in der Mitte das 0 47:19.910 --> 47:20.350 steht. 47:20.350 --> 47:34.910 Nämlich das ist LQ1, 0Q1 vereinigt LQ1, 0Q1, LQ1, 0Q1, Stern mal LQ1, 47:34.970 --> 47:35.870 0Q1. 47:36.790 --> 47:39.630 So und dann müssen wir für die hier einfach nur nachgucken. 47:39.970 --> 47:44.350 Da steht jeweils die Sprache hier oben, das ist nämlich jeweils 47:44.350 --> 47:44.770 Epsilon. 47:45.010 --> 47:53.970 Also das ist Epsilon, das hier und das hier bleibt Epsilon. 47:55.770 --> 48:01.530 Das heißt also LQ1, 1Q1 ist nichts anderes als Sprache, die nur 48:01.530 --> 48:02.370 Epsilon enthält. 48:04.050 --> 48:09.410 Dann schauen wir das Paar IQJ an mit I gleich 1, J gleich 2. 48:09.750 --> 48:12.710 Also die Sprache LQ1, 1Q2. 48:14.790 --> 48:20.070 Einfach stupide zurückgeführt auf die Sprachen, wo hier eine 0 steht, 48:20.210 --> 48:20.750 die passenden. 48:20.750 --> 48:29.890 Dann nichts anderes als LQ1, 0Q2 vereinigt mit, wir kommen von Q1 nach 48:29.890 --> 48:35.550 dem neuen Zwischenzustand, den wir erlauben, nämlich Q1 ohne 48:35.550 --> 48:36.550 Zwischenzustand. 48:38.370 --> 48:42.250 Wir kommen von dem Zustand ohne Zwischenzustand in den Zustand selber. 48:43.610 --> 48:47.910 Wir kommen von dem Zustand ohne Zwischenzustand nach Q2. 48:47.910 --> 48:55.910 Also das ist einfach LQ1, 0Q1 mal LQ1, 0Q1 Stern mal LQ1, 0Q2. 48:56.450 --> 48:59.250 Und für die gucken wir einfach hier nach, hier oben. 49:01.810 --> 49:06.030 LQ1, 0Q2 steht hier ist 0 vereinigt 1. 49:06.030 --> 49:10.370 Dann LQ1, 0Q1 steht hier ist Epsilon. 49:10.970 --> 49:15.630 LQ1, 0Q1 Sternchen, Epsilon Stern. 49:16.170 --> 49:20.550 LQ1, 0Q2 sehen wir hier ist 0,1. 49:20.750 --> 49:27.430 Also das Ganze ist die Sprache 0 vereinigt 1 vereinigt Epsilon Epsilon 49:27.430 --> 49:29.630 Sternchen mal 0 vereinigt 1. 49:29.950 --> 49:32.350 Das ist nichts anderes als 0 vereinigt 1. 49:34.570 --> 49:37.990 So, dann das nächste Paar, das wir angucken. 49:38.470 --> 49:44.310 Das nächste Paar QIQJ ist jetzt Q2Q1 und wir nehmen neu hinzu als 49:44.310 --> 49:46.650 erlaubten Zwischenzustand Q1. 49:47.230 --> 49:52.670 Also LQ2, 1Q1 wird genauso systematisch aufgebaut. 49:52.670 --> 50:09.590 Das ist LQ2, 0Q1 steht hier vereinigt LQ2, 0Q1 mal LQ1, 0Q1 Epsilon 50:09.590 --> 50:14.950 Stern mal LQ1, 0Q1 das ist Epsilon. 50:14.950 --> 50:19.690 Das heißt also insgesamt ist das 0 vereinigt 1 vereinigt 0 vereinigt 1 50:19.690 --> 50:20.930 mal Epsilon Stern mal Epsilon. 50:21.390 --> 50:22.910 Das ist nichts anderes als 0 vereinigt 1. 50:23.670 --> 50:29.150 So und jetzt das letzte mit Q1 ist neu als Zwischenzustand erlaubt. 50:29.490 --> 50:33.090 Q2, 1 für das Zustandspaar Q2Q2. 50:33.090 --> 50:41.630 Also LQ2, 1Q2, also erstmal von Q2 nach Q2 ohne Zwischenzustand 50:41.630 --> 50:57.130 Epsilon, dann von Q2 nach Q1 ohne Zwischenzustand 0 vereinigt 1 mal 50:57.130 --> 51:04.690 von Q1 nach Q1, das ist Epsilon Stern und dann von Q1 nach Q2 ist 51:04.690 --> 51:06.290 wieder 0 vereinigt 1. 51:06.910 --> 51:10.690 Das heißt also diese Sprache ist nichts anderes als Epsilon vereinigt 51:10.690 --> 51:13.170 0 vereinigt 1 mal 0 vereinigt. 51:13.910 --> 51:18.230 So und jetzt können wir zu allen möglichen Zwischenzuständen 51:18.230 --> 51:18.810 übergehen. 51:19.150 --> 51:23.170 Also wir erlauben zusätzlich noch Q2 als Zwischenzustand und da 51:23.170 --> 51:26.170 brauchen wir nicht alle möglichen Sprachen zu betrachten, also nicht 51:26.170 --> 51:33.710 alle Zustandspaare QIQJ, sondern nur das Zustandspaar, das es hier 51:33.710 --> 51:36.990 gibt, Anfangszustand zu Endzustand. 51:37.110 --> 51:40.330 Wir haben ja nur einen Endzustand, also ist das nur ein Zustandspaar 51:40.330 --> 51:45.090 und da Anfangs- und Endzustand gleich ist, ist das also, und zwar Q1, 51:45.450 --> 51:48.610 ist das also die Sprache LQ1 2Q1. 51:48.610 --> 51:53.470 Damit die jetzt unter Benutzung von den Sprachen beschreiben können, 51:53.570 --> 51:55.570 dann sind wir fertig, da haben wir unser L beschrieben. 51:56.150 --> 52:02.790 So und LQ1 2Q1 ist ja nichts anderes als LQ1 1Q1 vereinigt. 52:04.250 --> 52:10.150 LQ1 1Q2, also wir dürfen neu nach Q2 gehen, nur unter Benutzung von 52:10.150 --> 52:10.910 Q1. 52:12.410 --> 52:20.910 Mal, wir dürfen bei Q2 bleiben ohne Benutzung von Q2, also nur unter 52:20.910 --> 52:23.990 Benutzung von Q1, das ist LQ2 1Q2. 52:24.310 --> 52:29.630 Wir dürfen von Q2 nach Q1 kommen, nur unter Benutzung von Q1, das ist 52:29.630 --> 52:31.390 LQ2 1Q1. 52:31.390 --> 52:35.010 So und die lesen wir alle hier ab, die stehen hier irgendwo. 52:35.550 --> 52:41.530 Das ist nichts anderes als hierfür kriegen wir Y vereinigt 0,1 mal, 52:41.910 --> 52:52.990 hier in der Mitte haben wir 0,1 mal 0,1 in Klammern Sternchen mal 0,1. 52:53.790 --> 52:58.110 So, wenn wir jetzt das Y da vorne mal außen vor lassen und nur das 52:58.110 --> 53:08.510 hier angucken, das ist die Sprache von Worten, die bestehen aus 0 und 53:08.510 --> 53:18.910 1, aber hier dürfte wegen dem 0 vereinigt 1 am Anfang und dem 0 53:18.910 --> 53:24.430 vereinigt 1 hier 0 vereinigt 1 am Schluss das leere Wort nicht 53:24.430 --> 53:24.890 vorkommen. 53:24.970 --> 53:29.190 Da kommt das leere Wort nicht vor, nur das hier betrachtet. 53:29.350 --> 53:32.730 Aber da hier vorne auch noch das leere Wort hinzukommt, können wir 53:32.730 --> 53:36.390 diese ganze Sprache wieder schreiben als 0 vereinigt 1 mal 0 vereinigt 53:36.390 --> 53:38.030 1 in Klammern Sternchen. 53:40.110 --> 53:43.950 In diesem regulären Ausdruck sieht man natürlich jetzt an, dass er 53:43.950 --> 53:48.030 genau die Worte über 0,1 beschreibt, die gerade Länge haben. 53:48.570 --> 53:52.910 Das heißt, da muss eine 0 oder eine 1 kommen, gefolgt von nochmal 53:52.910 --> 53:56.450 einer 0 oder einer 1 und das dann beliebig oft. 54:01.320 --> 54:08.880 Okay, so, das schon mal jetzt zu betonen, was wir insgesamt haben im 54:08.880 --> 54:11.820 Zusammenhang mit endlichen Automaten und regulären Sprachen. 54:12.240 --> 54:17.860 Nochmal der Satz, die von endlichen Automaten akzeptierten Sprachen 54:17.860 --> 54:21.460 sind genau die regulären Sprachen. 54:21.460 --> 54:27.380 Wir haben beide Richtungen getrennt bewiesen und dieser Satz, das ist 54:27.380 --> 54:31.300 der Satz von Klini, der ist wichtig. 54:35.510 --> 54:36.370 Okay, 54:43.120 --> 54:53.730 also die von endlichen Automaten akzeptierten Sprachen sind genau die 54:53.730 --> 54:54.830 regulären Sprachen. 54:55.650 --> 55:00.390 Da kann man jetzt die Frage stellen, was können die denn nicht, also 55:00.390 --> 55:05.290 was ist sozusagen die Grenze dieses Berechnungsmodells endlicher 55:05.290 --> 55:05.970 Automat? 55:06.390 --> 55:09.230 Gibt es irgendwo Sprachen in der Welt, die von endlichen Automaten 55:09.230 --> 55:10.330 nicht akzeptiert werden? 55:11.310 --> 55:13.130 Ganz grundlegende Frage. 55:13.550 --> 55:16.570 Die kann man natürlich jetzt auch anders stellen, kann man auch so 55:16.570 --> 55:20.010 stellen, dass man sagt, gibt es nicht reguläre Sprachen? 55:20.750 --> 55:26.110 Die Antwort ist klar, das wissen Sie auch aus GBI, die Antwort ist ja, 55:26.290 --> 55:30.090 natürlich, endliche Automaten sind gewisserweise beschränkt. 55:30.890 --> 55:35.990 Was wir gerne hätten, wäre ein Werkzeug, um für eine Sprache zu 55:35.990 --> 55:42.190 beweisen, sie ist keine reguläre Sprache oder sie kann nicht von einem 55:42.190 --> 55:44.730 endlichen Automaten erkannt werden. 55:44.730 --> 55:45.750 Das wäre schön. 55:47.290 --> 55:51.610 Aber erstmal vorne weggeschaltet, also was sind Sprachen, die nicht 55:51.610 --> 55:57.330 von endlichen Automaten erkannt werden können und woran liegt das? 55:59.130 --> 56:04.430 Wissen Sie aus GBI, dass die Sprache der korrekten Klammerausdrücke 56:04.430 --> 56:09.210 nicht von endlichen Automaten erkannt wird? 56:09.210 --> 56:14.170 Korrekter Klammerausdruck, naja gut, ein Ausdruck über dem Alphabet 56:14.170 --> 56:20.610 Klammerauf, Klammerzu, der interpretiert als Klammerausdruck wirklich 56:20.610 --> 56:21.470 korrekt ist. 56:21.710 --> 56:26.370 Das heißt also, Sie haben zu jeder Klammerauf später auch eine 56:26.370 --> 56:31.950 Klammerzu und Sie haben auch zu keinem Zeitpunkt mehr Klammerzu als 56:31.950 --> 56:34.110 Klammerauf, wenn Sie von vorn nach hinten gehen. 56:37.630 --> 56:42.390 Das sind korrekte Klammerausdrücke, das hier ist kein korrekter 56:42.390 --> 56:46.950 Klammerausdruck, weil diese Klammerauf nicht mehr geschlossen wird, 56:48.050 --> 56:48.890 zum Beispiel. 56:51.310 --> 56:53.870 Das andere scheint mir in Ordnung zu sein. 56:55.450 --> 57:02.870 Das heißt also, Klammerung ist genau korrekt, wenn erstmal gleich 57:02.870 --> 57:06.910 viele öffnende wie schließende Klammern vorkommen, aber außerdem, wenn 57:06.910 --> 57:12.270 man den Ausdruck von links nach rechts liest, es nie mehr Klammerzu 57:12.270 --> 57:17.510 als Klammerauf bis dahin gibt. 57:20.520 --> 57:25.440 So, jetzt ein endlicher Automat, der das erkennt, der muss also für 57:25.440 --> 57:30.440 beliebig lange Ausdrücke nachhalten können, wie viele Klammern von 57:30.440 --> 57:35.260 denen, die geöffnet wurden, sind denn schon geschlossen worden. 57:40.210 --> 57:45.630 Das können beliebige Konstellationen sein, die sich auch im Prinzip 57:45.630 --> 57:47.330 voneinander unterscheiden. 57:47.670 --> 57:52.090 Der braucht also sowas wie ein unendliches Gedächtnis, unendlich 57:52.090 --> 57:56.190 verschiedene Situationen, also echt verschiedene Situationen muss der 57:56.190 --> 57:57.470 erkennen können. 57:58.470 --> 58:03.570 Und das ist jetzt sozusagen die Handwaving-Argumentation, warum 58:03.570 --> 58:07.350 endliche Automaten korrekte Klammerausdrücke nicht erkennen können, 58:07.730 --> 58:14.650 weil endliche Automaten nur ein endliches Gedächtnis haben, Gedächtnis 58:14.650 --> 58:22.570 sozusagen als Menge der Zustände aufgefasst. 58:22.570 --> 58:26.310 Sie können ja umgekehrt, wenn sie so einen endlichen Automaten 58:26.310 --> 58:29.890 angucken, sozusagen die Zustände, die sind diejenigen, die für eine 58:29.890 --> 58:37.710 bestimmte Situation stehen, das kann man interpretieren als 58:37.710 --> 58:38.430 Gedächtnis. 58:39.570 --> 58:42.110 Endliche Automaten heißen endlich, weil sie nur eine endliche 58:42.110 --> 58:45.450 Zustandsmenge haben, wenn sie aber unendlich viele verschiedene 58:45.450 --> 58:50.590 Situationen auseinanderhalten können, sollen, dann müssen sie 58:50.590 --> 58:52.330 unendlich viele Zustände haben. 58:52.670 --> 58:55.090 Wie gesagt, das ist die Handwaving-Argumentation. 58:56.010 --> 59:00.430 Und wir hätten gerne sozusagen einen Satz, ein Lemma, das wir anwenden 59:00.430 --> 59:04.810 können, um zum Beispiel für die Sprache der korrekten Klammerausdrücke 59:04.810 --> 59:07.450 nachzuweisen, dass sie nicht regulär ist. 59:08.530 --> 59:11.630 Dann automatisch heißt es, dazu gibt es keinen endlichen Automaten. 59:12.590 --> 59:16.370 Und der Satz, mit dem man das machen kann, ist das sogenannte Pumping 59:16.370 --> 59:16.670 -Lemma. 59:18.510 --> 59:26.290 Pumping -Lemma heißt Pumping-Lemma, Pumping für Pumpen, weil da was 59:26.290 --> 59:31.870 vorkommt, wo Worte aufgepumpt werden. 59:33.510 --> 59:35.990 Und wir gucken uns das Lemma mal genauer an. 59:36.710 --> 59:39.470 Das ist so ein bisschen gewöhnungsbedürftig, aber eigentlich gar nicht 59:39.470 --> 59:41.650 schwer, wenn man mal verstanden hat, was dahinter ist. 59:42.110 --> 59:45.370 Das Lemma beschreibt eine Eigenschaft regulärer Sprachen. 59:45.930 --> 59:50.870 Und zwar sagt das, sei L eine reguläre Sprache. 59:50.870 --> 59:53.810 Wenn wir eine reguläre Sprache betrachten, dann gilt folgendes. 59:54.490 --> 01:00:02.070 Dann existiert eine Zahl n, sodass für jedes Wort aus der Sprache, das 01:00:02.070 --> 01:00:08.190 länger ist als n, eine Darstellung existiert, die so aussieht. 01:00:08.190 --> 01:00:18.790 Jedes Wort kann hingeschrieben werden als uvx mit Anfangsteil uv, ist 01:00:18.790 --> 01:00:28.990 nicht länger als n, Länge von uv ist kleiner gleich n, und v ungleich 01:00:28.990 --> 01:00:36.590 leer, sodass jedes Wort, das ich bekomme, indem ich v entweder 01:00:36.590 --> 01:00:41.610 weglasse oder beliebig oft hintereinander schreibe in der Mitte von 01:00:41.610 --> 01:00:44.970 dem Wort, wieder in L ist. 01:00:44.970 --> 01:00:53.450 Also, sodass auch uv hoch ix wieder in L ist, für alle i aus n null. 01:00:58.120 --> 01:01:04.660 Also, für eine reguläre Sprache gilt, es gibt so eine Zahl n, sodass 01:01:04.660 --> 01:01:13.660 ich jedes Wort, das länger ist als dieses n, darstellen kann als uvx, 01:01:14.660 --> 01:01:23.920 uv ist kleiner gleich n, v ist ungleich leer, sodass uv hoch ix für 01:01:23.920 --> 01:01:33.620 beliebiges i, also auch ux oder uv quadrat x oder uv hoch tausend x 01:01:33.620 --> 01:01:35.400 wieder in der Sprache ist. 01:01:36.200 --> 01:01:43.960 Also, ab einer gewissen Wortlänge sind die Worte einer regulären 01:01:43.960 --> 01:01:46.900 Sprache so, dass sie irgendwelche Wiederholungen drin haben. 01:01:51.930 --> 01:01:53.570 So, das beweisen wir jetzt. 01:01:59.250 --> 01:02:00.990 Wir hatten eine reguläre Sprache. 01:02:01.650 --> 01:02:06.090 Und jetzt benutzen wir das, was wir insgesamt bewiesen haben, dass die 01:02:06.090 --> 01:02:08.370 regulären Sprachen genau die Automatensprachen sind. 01:02:08.370 --> 01:02:12.370 Wir benutzen nämlich, dass es dazu einen endlichen Automaten gibt, der 01:02:12.370 --> 01:02:14.270 die Sprache akzeptiert. 01:02:14.750 --> 01:02:18.850 Und ich habe ja eben gesagt, diese Begrenztheit von endlichen 01:02:18.850 --> 01:02:23.490 Automaten, die liegt daran, dass sie eine endliche Anzahl von 01:02:23.490 --> 01:02:26.110 Zuständen haben. 01:02:26.110 --> 01:02:31.370 Das heißt, wenn Worte abgearbeitet werden, können von einem Automaten, 01:02:31.470 --> 01:02:37.070 aber beliebig lang werden können, dann muss da irgendwas immer wieder 01:02:37.070 --> 01:02:38.850 durchlaufen werden in dem Automaten. 01:02:42.210 --> 01:02:49.270 Das hier bezieht sich auf Wörter, die sehr lang werden, Länge haben, 01:02:49.350 --> 01:02:50.410 die größer als n sind. 01:02:50.410 --> 01:02:54.590 Wenn wir jetzt das n für unseren Beweis suchen, dann werden wir 01:02:54.590 --> 01:02:59.270 wahrscheinlich da irgendwo im Umfeld der Anzahl der Zustände unseres 01:02:59.270 --> 01:03:00.630 Automaten fündig. 01:03:01.910 --> 01:03:08.010 Der Satz ist genau so formuliert, dass wir mit n gleich Anzahl der 01:03:08.010 --> 01:03:10.570 Zustände des Automaten prima hinkommen. 01:03:12.430 --> 01:03:14.870 Unsere Sprache ist regulär, unsere Ausgangssprache. 01:03:14.950 --> 01:03:19.230 Wir nehmen einfach den zugehörigen endlichen Automaten her und sagen, 01:03:19.390 --> 01:03:23.510 wir definieren schon mal das n, das es hier nach dem Satz geben soll, 01:03:24.130 --> 01:03:28.570 als Anzahl der Zustände des Automaten. 01:03:29.170 --> 01:03:33.590 Und jetzt gucken wir irgend so ein Wort an, aus unserer regulären 01:03:33.590 --> 01:03:36.070 Sprache, das länger ist als n. 01:03:36.430 --> 01:03:39.950 Wir gucken so ein w an, Länge von w größer n. 01:03:40.510 --> 01:03:46.370 Das w sieht dann irgendwie so aus, a1 und so weiter, an und so weiter 01:03:46.370 --> 01:03:47.050 bis am. 01:03:47.450 --> 01:03:52.390 Das ist so ein a1 bis am, m echt größer als n. 01:03:52.650 --> 01:03:54.290 Das n-te Symbol ist hier irgendwo. 01:03:55.950 --> 01:04:00.910 Und jetzt gucken wir uns mal an, was passiert, wenn unser endlicher 01:04:00.910 --> 01:04:03.730 Automat dieses Wort abarbeitet. 01:04:05.750 --> 01:04:10.110 Also das Wort hat eine Länge größer n, das sieht so aus, a1 bis am. 01:04:11.090 --> 01:04:14.430 Das heißt, wenn der Automat das Wort abarbeitet, dann werden 01:04:14.430 --> 01:04:19.730 irgendwelche Zwischenzustände oder Zustände q0 bis qm durchlaufen, 01:04:19.870 --> 01:04:23.870 wobei diese Zustände nicht alle verschieden sind. 01:04:23.870 --> 01:04:27.910 Die können sogar nicht alle verschieden sein, weil m größer n ist. 01:04:28.590 --> 01:04:32.870 Das heißt, irgendwo, und wenn das Wort akzeptiert wird, dann ist das 01:04:32.870 --> 01:04:34.310 qm insbesondere in f. 01:04:35.090 --> 01:04:38.690 Aber wenn das m größer als n ist, dann muss also irgendwo mal ein 01:04:38.690 --> 01:04:41.410 Zustand zum ersten Mal wieder durchlaufen werden. 01:04:42.010 --> 01:04:44.530 Also irgendwann kommen wir zum Zustand wieder zurück. 01:04:44.530 --> 01:04:47.390 Gucken wir uns einfach mal so eine Situation an. 01:04:47.510 --> 01:04:53.810 Das sind also jetzt Zustände qi, qj in dieser Folge, die aber 01:04:53.810 --> 01:04:54.790 eigentlich gleich sind. 01:04:55.250 --> 01:04:59.550 Die Indizes i und j sind verschieden, entsprechend der Nummerierung 01:04:59.550 --> 01:05:03.230 hier dieser Zustandsfolge, aber qi und qj sind dasselbe. 01:05:04.090 --> 01:05:06.690 Und ob der a soll i kleiner als j sein. 01:05:06.690 --> 01:05:12.150 Das heißt also, bei Abarbeitung von b gleich a1 bis am geht es 01:05:12.150 --> 01:05:15.610 irgendwann mal so, dass wir hier nach qi kommen. 01:05:17.430 --> 01:05:22.650 Aber nachdem wir a1 bis ai gelesen haben und dann wird ai plus 1 01:05:22.650 --> 01:05:24.450 gelesen und so weiter und so fort. 01:05:24.810 --> 01:05:27.470 Irgendwann mal kommen wir wieder zu qi zurück. 01:05:27.990 --> 01:05:29.950 Das qj ist gerade wieder hier qi. 01:05:29.950 --> 01:05:32.730 Und dann geht es weiter, hier fehlen ein paar Pünktchen. 01:05:33.990 --> 01:05:36.930 Nicht nur zwei Übergänge, hier fehlen ein paar Pünktchen und dann geht 01:05:36.930 --> 01:05:37.590 es nach qm. 01:05:38.170 --> 01:05:41.770 Also insbesondere wissen wir aber, wenn wir so ein langes Wort haben, 01:05:41.890 --> 01:05:46.390 das länger ist als die Anzahl der Zustände des Automaten, dann muss 01:05:46.390 --> 01:05:51.890 bei der Abarbeitung so ein Kreis in dem Automat durchlaufen werden. 01:05:52.690 --> 01:05:54.690 Einfach die Zustandsfolge, die durchlaufen. 01:05:55.330 --> 01:05:56.490 So hintereinander und so. 01:05:57.670 --> 01:06:02.350 Okay, wenn aber bei Abarbeitung von w dieser Kreis durchlaufen wird, 01:06:03.830 --> 01:06:10.010 bevor wir schließlich in einem Endzustand landen, dann können wir auch 01:06:10.010 --> 01:06:13.390 mit einem Wort in den Endzustand kommen, das diesen Kreis nicht 01:06:13.390 --> 01:06:17.410 durchläuft, das einfach hier schnurstracks durchgeht. 01:06:18.930 --> 01:06:23.610 Oder bei dem dieser Kreis zweimal durchlaufen wird, einmal oder 01:06:23.610 --> 01:06:24.150 viermal. 01:06:26.630 --> 01:06:30.210 Das ist ja genau das, was dieses Lemma sagt, man kann dieses w 01:06:30.210 --> 01:06:37.990 irgendwie aufteilen in uvx und insbesondere ist uv kleiner gleich n, 01:06:39.570 --> 01:06:43.410 sodass auch uv hoch ix wieder in der Sprache ist. 01:06:44.390 --> 01:06:46.610 Die Aufteilung, die können wir hier ablesen. 01:06:48.450 --> 01:06:52.850 Mit u kommen wir hier hin, nach qi, von s nach qi. 01:06:52.850 --> 01:07:00.190 Mit v kommen wir hier durch und mit x kommen wir dann von ui dahin. 01:07:01.510 --> 01:07:06.550 Und natürlich muss diese Wiederholung spätestens beim enden Zustand 01:07:06.550 --> 01:07:07.090 vorkommen. 01:07:07.830 --> 01:07:13.970 Das heißt also uv hat eine Länge kleiner gleich n. 01:07:15.110 --> 01:07:18.830 Und dieser Zykel existiert, das heißt v ist ungleich leer. 01:07:19.570 --> 01:07:24.210 Das heißt also aus dieser Abarbeitung von w können wir die Aufteilung 01:07:24.210 --> 01:07:25.150 ablesen. 01:07:25.230 --> 01:07:27.890 Hier steht nochmal, da muss es so einen Zykel geben. 01:07:28.870 --> 01:07:32.690 Den können wir auch weglassen oder mehrfach durchlaufen, dann kommen 01:07:32.690 --> 01:07:33.870 wir trotzdem nach qm. 01:07:34.490 --> 01:07:42.690 Das heißt also, wir können das w zerlegen in a1 bis ai, den Teil der 01:07:42.690 --> 01:07:45.390 abgearbeitet wird, bevor wir zu diesem qi kommen. 01:07:45.390 --> 01:07:51.670 Das ist u, gefolgt von dem Teil ai plus 1 bis aj. 01:07:52.290 --> 01:07:55.330 Das ist der Teil, der abgearbeitet wird, indem man durch den Zykel 01:07:55.330 --> 01:07:55.650 geht. 01:07:55.990 --> 01:07:58.690 Das ist v und das ist insbesondere ungleich leer. 01:07:58.910 --> 01:08:01.490 Dann muss es einen Zykel geben bei der Abarbeitung von w. 01:08:01.930 --> 01:08:05.610 Gefolgt von dem Rest, aj plus 1 bis am. 01:08:06.770 --> 01:08:14.410 Und wenn das Wort abgearbeitet werden kann, dann kann auch uv hoch ix 01:08:14.410 --> 01:08:14.410 abgearbeitet werden. 01:08:15.390 --> 01:08:20.700 Die aus n0 Abarbeitung. 01:08:23.800 --> 01:08:27.640 Wenn Sie sich das einprägen und was dahinter ist, dann können Sie sich 01:08:27.640 --> 01:08:29.080 den Satz auch merken. 01:08:30.300 --> 01:08:36.280 Ich gebe zu, erst mal ein bisschen gewöhnungsbedürftig, dieser Satz 01:08:36.280 --> 01:08:40.320 oder das Pampim Lema, wenn man das anwenden will, sollte man das aber 01:08:40.320 --> 01:08:41.700 so richtig parat haben. 01:08:41.700 --> 01:08:46.240 Und das kriegen Sie in den Kopf rein, indem Sie sich immer dieses 01:08:46.240 --> 01:08:47.100 Bildchen vorstellen. 01:08:47.360 --> 01:08:47.480 Ja, 01:08:50.570 --> 01:08:52.130 da kann es auch mehr Zykel geben. 01:08:52.490 --> 01:08:57.030 Das ist ja auch nur eine Aussage, es existiert ein n. 01:08:57.330 --> 01:09:01.970 Und es existiert für jedes Wort der Länge n so eine Darstellung. 01:09:02.250 --> 01:09:08.150 Da kann es auch mehrere Darstellungen geben, wo an mehreren Stellen 01:09:08.150 --> 01:09:09.110 aufgeblasen wird. 01:09:09.790 --> 01:09:12.890 Das ist ja nur eine Existenzaussage für den. 01:09:15.170 --> 01:09:18.390 Was wir jetzt noch machen wollen, ist dieses Lema anwenden. 01:09:18.830 --> 01:09:20.570 Gewinnbringend anwenden, sage ich mal. 01:09:20.710 --> 01:09:24.710 Also das Lema ist eine Aussage über reguläre Sprachen. 01:09:25.130 --> 01:09:28.290 Wenn die Sprache regulär ist, dann erfüllt sie dieses Lema. 01:09:29.970 --> 01:09:33.190 Wie kann man so einen Satz verwenden? 01:09:41.060 --> 01:09:48.360 Das Blöde ist, das ist nur ein Satz, der nur eine notwendige Bedingung 01:09:48.360 --> 01:09:51.440 für regulär beinhaltet. 01:09:54.400 --> 01:10:01.100 Wenn eine Sprache diese Bedingung nicht erfüllt, dann ist eins 01:10:01.100 --> 01:10:01.820 glasklar. 01:10:02.060 --> 01:10:03.420 Die Sprache ist nicht regulär. 01:10:04.260 --> 01:10:06.180 Dafür kann man es verwenden, das Lema. 01:10:06.800 --> 01:10:13.600 Aber ich warne, da eben diese Eigenschaft, es gibt ein n, so dass für 01:10:13.600 --> 01:10:18.100 jedes Wort der Länge größer n es eine Darstellung gibt, als u, v, x, 01:10:18.360 --> 01:10:25.240 v, kleiner gleich n, v, ungleich epsilon, so dass u, v hoch i, L ist 01:10:25.240 --> 01:10:25.940 für alle i. 01:10:27.660 --> 01:10:31.780 Das kann auch zutreffen für Sprachen, die nicht regulär sind. 01:10:32.620 --> 01:10:34.280 Das ist nicht hinreichend. 01:10:35.020 --> 01:10:39.860 Das heißt also, wenn Sie so eine Sprache hernehmen, den Verdacht 01:10:39.860 --> 01:10:44.980 haben, die ist nicht regulär, können Sie es vielleicht mit dem Pumping 01:10:44.980 --> 01:10:45.800 Lema beweisen. 01:10:46.900 --> 01:10:50.060 Vielleicht haben Sie auch Pech und diese Sprache ist zwar nicht 01:10:50.060 --> 01:10:51.980 regulär, erfüllt aber das Pumping Lema. 01:10:52.100 --> 01:10:54.840 Jetzt wollen wir mal einfach so anwenden, üben. 01:10:56.660 --> 01:10:57.620 Erstes Beispiel. 01:10:57.860 --> 01:10:59.480 Das erste Beispiel ist harmlos. 01:11:00.200 --> 01:11:04.880 Da gucken wir uns nämlich eine reguläre Sprache an, von der wir ja 01:11:04.880 --> 01:11:07.400 wissen, dass sie das Pumping Lema erfüllt, denn das haben wir ja 01:11:07.400 --> 01:11:08.140 gerade bewiesen. 01:11:09.320 --> 01:11:12.320 Ich habe schön immer das Pumping Lema nochmal in voller 01:11:12.320 --> 01:11:13.920 Ausführlichkeit hier stehen. 01:11:14.320 --> 01:11:16.860 Also wir gucken uns die Sprache an, L. 01:11:17.140 --> 01:11:23.660 L enthält alle Wörter aus 0,1 Sternen oder über 0,1, für die gilt, W 01:11:23.660 --> 01:11:26.680 enthält 1, 0 nicht als Teilwort. 01:11:26.680 --> 01:11:29.980 Die Sprache hatten wir in der allerersten Vorlesung schon als ein 01:11:29.980 --> 01:11:34.920 Beispiel und da haben wir schon sofort gesehen, ja, die ist regulär 01:11:34.920 --> 01:11:36.740 oder dazu gibt es einen endlichen Automaten. 01:11:38.020 --> 01:11:44.640 Enthält 1, 0 nicht als Teilwort, heißt ja nichts anderes als nach der 01:11:44.640 --> 01:11:48.240 ersten 1 darf keine 0 mehr kommen. 01:11:49.100 --> 01:11:53.060 Das kann man beschreiben als 0 Stern, 1 Stern. 01:11:53.820 --> 01:11:57.180 Da können beliebig viele Nullen kommen, aber wenn dann irgendwann mal 01:11:57.180 --> 01:11:59.060 eine 1 kommt, dann darf keine 0 mehr kommen. 01:11:59.520 --> 01:12:01.400 0 Stern, 1 Stern. 01:12:01.900 --> 01:12:02.560 Das ist regulär. 01:12:03.240 --> 01:12:06.860 Das heißt also, die muss das Pumping Lema erfüllen und das ist auch 01:12:06.860 --> 01:12:07.520 irgendwie klar. 01:12:07.640 --> 01:12:11.280 Ich muss einfach jetzt irgendwie nur so ein N angeben, sodass für 01:12:11.280 --> 01:12:15.800 jedes Wort, das länger ist als dieses N, ich so eine Darstellung, uvx, 01:12:15.900 --> 01:12:21.200 angeben kann mit uv kleiner gleich n, v und gleich y, sodass auch uvx 01:12:21.200 --> 01:12:24.640 für jedes i in L ist. 01:12:25.180 --> 01:12:27.940 Und ich gebe hier einfach mal n gleich 1 an. 01:12:29.420 --> 01:12:33.900 Die Darstellung ist w gleich uvx und ich sage einfach und bei der 01:12:33.900 --> 01:12:36.060 Darstellung ist u gleich y. 01:12:36.620 --> 01:12:38.300 Es muss ja nur eine Darstellung geben. 01:12:40.020 --> 01:12:44.380 Dann entspricht v also dem allerersten Buchstaben von w. 01:12:45.200 --> 01:12:52.440 Wenn ich sage, b soll länger als 1 sein, eine Länge haben, die länger 01:12:52.440 --> 01:12:57.380 als 1 ist, also nicht leer sein heißt das insbesondere, und u bei der 01:12:57.380 --> 01:13:00.440 Darstellung von w als uvx soll u leer sein. 01:13:01.240 --> 01:13:04.200 Das ist ja nichts anderes als v ist der erste Buchstabe von b. 01:13:04.660 --> 01:13:12.420 Wenn jetzt b1,0 nicht als Teilwort enthält, dann kann ich auch den 01:13:12.420 --> 01:13:17.020 ersten Buchstaben weglassen oder den ersten Buchstaben tausendmal 01:13:17.020 --> 01:13:17.820 hinschreiben. 01:13:19.480 --> 01:13:23.360 Dadurch kann kein 1,0 entstehen. 01:13:26.940 --> 01:13:33.800 Das da vorne ist entweder eine 0, die kann ich auch weglassen oder 01:13:33.800 --> 01:13:36.280 beliebig oft wiederholen. 01:13:36.580 --> 01:13:38.960 Dadurch kommt da kein 1,0 rein. 01:13:38.960 --> 01:13:41.080 Oder das erste ist eine 1. 01:13:41.440 --> 01:13:44.340 Dann ist aber dieses ganze w nur eine Folge von Einsen. 01:13:44.720 --> 01:13:47.760 Da kann ich auch diese 1 nochmal x-mal wiederholen oder weglassen. 01:13:47.880 --> 01:13:50.760 Dadurch kommt wieder kein 1,0 als Teilwort. 01:13:51.340 --> 01:13:55.380 Okay, also hier haben wir nur verifiziert, dass eine reguläre Sprache 01:13:55.380 --> 01:13:59.080 das erfüllt, was sie, nachdem wir es bewiesen haben, erfüllen soll. 01:14:00.540 --> 01:14:02.140 Die Aussage ist pumping lemma. 01:14:02.580 --> 01:14:04.100 Hier wird es jetzt interessanter. 01:14:05.540 --> 01:14:09.980 Können wir mit dem pumping lemma zeigen, dass die Sprache der 01:14:09.980 --> 01:14:13.400 korrekten Klammerausdrücke nicht regulär ist? 01:14:14.880 --> 01:14:15.520 Ja. 01:14:16.680 --> 01:14:20.820 Können wir sogar für eine speziellere Sprache zeigen können, dass sie 01:14:20.820 --> 01:14:21.760 nicht regulär ist. 01:14:22.080 --> 01:14:28.080 Nämlich die Sprache der Wörter, die so aussehen, 0 hoch i, 1 hoch i. 01:14:28.400 --> 01:14:29.340 Für beliebiges i. 01:14:30.260 --> 01:14:34.120 Also eine Anzahl von Nullen gefolgt von genau derselben Anzahl von 01:14:34.120 --> 01:14:34.520 Einsen. 01:14:35.420 --> 01:14:38.720 Sie erinnern sich, in der ersten Vorlesung hatten wir ja am Schluss 01:14:38.720 --> 01:14:39.720 kontextfreie Grammatiken. 01:14:40.200 --> 01:14:41.560 Da haben wir eine Grammatik angegeben, 01:14:44.880 --> 01:14:47.320 über die diese Sprache erzeugt wird. 01:14:47.900 --> 01:14:52.480 Und da habe ich so gesagt, naja, also ist die Sprache L gleich Menge 01:14:52.480 --> 01:14:53.220 aller Wörter. 01:14:53.420 --> 01:14:59.460 Wörter hat die Form 0 hoch N, 1 hoch N, für beliebiges N, ist ja wohl 01:14:59.460 --> 01:15:00.340 regulär. 01:15:01.980 --> 01:15:06.200 Oder, ich weiß nicht, ob Sie es mitgekriegt haben, da haben wir da 01:15:06.200 --> 01:15:07.880 Zweifel und das offengelassen. 01:15:08.360 --> 01:15:12.180 Wenn Sie jetzt wirklich da aufgepasst haben und dann Ihr Zweifel Sie 01:15:12.180 --> 01:15:16.460 jetzt zwei Wochen lang beschäftigt hat, also jetzt wird es aufgelöst, 01:15:16.540 --> 01:15:18.140 die Sprache ist nicht regulär. 01:15:18.240 --> 01:15:19.320 Und das können wir zeigen. 01:15:21.580 --> 01:15:27.000 Wir wählen, wir betrachten beliebiges N. 01:15:27.540 --> 01:15:29.640 Ah, das vielleicht jetzt nochmal genauer. 01:15:29.640 --> 01:15:34.020 Wenn wir das Pumping Lemma benutzen, um für eine Sprache zu zeigen, 01:15:34.100 --> 01:15:38.220 sie ist nicht regulär, dann müssen wir hier hinten die Negation 01:15:38.220 --> 01:15:38.760 zeigen. 01:15:39.180 --> 01:15:41.400 Also die Sprache darf das nicht erfüllen. 01:15:42.500 --> 01:15:51.240 Das muss also gelten, für alle N gibt es ein Wort, oder gibt es ein 01:15:51.240 --> 01:15:52.720 Wort, das länger ist als N. 01:15:53.120 --> 01:15:59.240 Sodass für jede beliebige Darstellung des Wortes als uvx mit uv, 01:15:59.780 --> 01:16:10.900 kleiner gleich N, v, epsilon, als ein i gibt, sodass uv hoch ix nicht 01:16:10.900 --> 01:16:11.540 in L ist. 01:16:12.220 --> 01:16:13.740 Das ist die Negation von dem da hinten. 01:16:14.900 --> 01:16:20.540 Nehmen wir also ein beliebiges N und jetzt ein Wort w, das länger ist 01:16:20.540 --> 01:16:26.920 als N und nur eins zu nehmen, was sozusagen hier zum Widerspruch führt 01:16:26.920 --> 01:16:28.320 zu dieser Eigenschaft hier. 01:16:28.740 --> 01:16:31.440 Dafür nehmen wir 0 hoch N, 1 hoch N. 01:16:32.600 --> 01:16:34.360 Dieses w ist größer N. 01:16:35.820 --> 01:16:42.420 Und jetzt gucken wir jede beliebige Darstellung von dem w als uvx mit 01:16:42.420 --> 01:16:46.120 uv, kleiner gleich N, v und gleich epsilon an. 01:16:46.880 --> 01:16:53.740 Wenn uv eine Länge hat, die kleiner gleich N ist, dann ist das uv hier 01:16:53.740 --> 01:16:55.480 in dem vorderen Teil zu finden. 01:16:55.700 --> 01:16:57.340 Also uv besteht nur aus Nullen. 01:16:58.020 --> 01:16:58.960 Und das ist der Trick. 01:16:59.920 --> 01:17:04.580 Wenn das v und gleich leer ist, wenn wir das weglassen, 01:17:05.140 --> 01:17:11.940 beispielsweise, haben wir nicht mehr die Anzahl von Nullen gefolgt von 01:17:11.940 --> 01:17:14.180 derselben Anzahl von Einsen. 01:17:14.900 --> 01:17:16.380 Dann haben wir plötzlich eine Null weniger. 01:17:17.440 --> 01:17:18.500 Nicht mehr in der Sprache. 01:17:18.500 --> 01:17:24.860 Also für jede Darstellung von diesem w als uvx mit uv, kleiner gleich 01:17:24.860 --> 01:17:28.680 N gilt, und v und gleich epsilon gilt. 01:17:28.880 --> 01:17:35.500 Wenn ich das v weglasse, kriege ich 0 hoch L, 1 hoch N, L kleiner N. 01:17:36.440 --> 01:17:40.240 Das ist nicht mehr ein Wort aus dieser Sprache. 01:17:42.980 --> 01:17:43.580 So. 01:17:45.100 --> 01:17:55.260 Das ist die Art und Weise, wie Sie am häufigsten das Pumping Lemma 01:17:55.260 --> 01:17:57.880 anwenden werden sollten. 01:17:58.020 --> 01:18:02.720 Denn das ist eine Anwendung, die einem wirklich einen Wissensgewinn 01:18:02.720 --> 01:18:03.080 bringt. 01:18:03.380 --> 01:18:07.000 Sie haben eine Sprache, Sie vermuten, die ist nicht regulär, damit 01:18:07.000 --> 01:18:08.720 können Sie zeigen, sie ist nicht regulär. 01:18:08.800 --> 01:18:10.980 Wenn Sie so einen Beweis führen können. 01:18:10.980 --> 01:18:15.000 Aber meine Warnung war ja, das wird nicht immer hinhauen. 01:18:15.160 --> 01:18:19.680 Es gibt nicht reguläre Sprachen, die erfüllen das Pumping Lemma. 01:18:20.200 --> 01:18:22.100 Und dafür habe ich jetzt das dritte Beispiel. 01:18:22.280 --> 01:18:25.660 Eine Sprache, der sieht man eigentlich sofort an, die kann nicht 01:18:25.660 --> 01:18:26.520 regulär sein. 01:18:26.980 --> 01:18:30.560 Aber unverschämterweise erfüllt sie unser Pumping Lemma. 01:18:31.360 --> 01:18:32.220 Und das ist folgende. 01:18:33.960 --> 01:18:36.380 Sprache der Wörter w aus Sigma Stern. 01:18:36.380 --> 01:18:43.160 W hat entweder die Form, das sind K1, also W gleich 1 hoch K, K größer 01:18:43.160 --> 01:18:43.420 0. 01:18:43.920 --> 01:18:50.120 Oder es hat die Form, das sind J0, gefolgt von einer quadratischen 01:18:50.120 --> 01:18:51.420 Anzahl von Einsen. 01:18:52.560 --> 01:18:56.520 Quadratische Anzahl von Einsen, den endlichen Automat will ich sehen, 01:18:56.640 --> 01:18:58.820 der das erkennen kann. 01:18:59.340 --> 01:18:59.960 Der Punkt. 01:18:59.960 --> 01:19:03.260 Also, Menge der Wörter über 0,1. 01:19:03.780 --> 01:19:06.300 W ist entweder 1 hoch K, K größer 0. 01:19:06.440 --> 01:19:09.180 Oder W ist 0 hoch J, 1 hoch K Quadrat. 01:19:09.900 --> 01:19:12.080 J größer gleich 1, K größer gleich 0. 01:19:12.280 --> 01:19:14.260 Also hier quadratische Anzahl von Einsen. 01:19:15.300 --> 01:19:15.380 So. 01:19:16.960 --> 01:19:18.720 Die Sprache erfüllt das Pumping Lemma. 01:19:18.880 --> 01:19:22.620 Für das Pumping Lemma müssen wir ja nur ein N angeben, sodass für 01:19:22.620 --> 01:19:28.680 jedes Wort der Größe der Länge länger als N so eine Aufteilung gibt. 01:19:29.400 --> 01:19:29.920 X. 01:19:31.080 --> 01:19:35.500 Sodass UV hoch IX für alle I wieder in der Sprache ist. 01:19:35.780 --> 01:19:38.660 Und hier kann ich so ein N angeben, nämlich N gleich 1. 01:19:40.180 --> 01:19:43.580 Wenn ich jetzt so ein Wort aus L betrachte, ein beliebiges Wort aus L, 01:19:43.660 --> 01:19:50.240 das länger ist als 1, dann kann ich dafür so eine Darstellung als UVX 01:19:50.240 --> 01:19:54.180 angeben mit UV kleiner gleich N und V ungleich Y. 01:19:55.200 --> 01:19:59.600 Nämlich Sätze U gleich Y und Länge von V gleich 1. 01:20:00.560 --> 01:20:01.400 Einzige Möglichkeit. 01:20:02.820 --> 01:20:03.860 Länge von V gleich 1. 01:20:05.140 --> 01:20:07.760 Das heißt also, V ist das erste Symbol. 01:20:08.900 --> 01:20:11.620 So, und dann gucke ich jetzt an und was passiert, wenn ich jetzt 01:20:11.620 --> 01:20:15.400 dieses erste Symbol weglasse oder beliebig oft wiederhole. 01:20:16.760 --> 01:20:21.760 Es gibt jetzt zwei Fälle, wie das W aussehen kann und was das heißen 01:20:21.760 --> 01:20:21.960 kann. 01:20:22.060 --> 01:20:24.280 Das W kann so ein 1 hoch K sein. 01:20:25.200 --> 01:20:30.820 Naja gut, wenn ich jetzt die erste 1 von 1 hoch K weglasse oder 01:20:30.820 --> 01:20:35.320 beliebig oft wiederhole, kommt ein 1 hoch L raus. 01:20:36.060 --> 01:20:38.000 Das ist wieder ein Wort aus L. 01:20:40.260 --> 01:20:44.700 Oder B hat so eine Form 0 hoch J, 1 hoch K Quadrat. 01:20:45.160 --> 01:20:48.120 J ist aber wohlgemerkt größer gleich 1. 01:20:48.560 --> 01:20:50.880 Das heißt, das erste Symbol ist so eine 0. 01:20:50.880 --> 01:20:57.160 Wenn ich jetzt die 0 weglasse oder ein paar 0 mehr dazu schreibe, 01:20:58.580 --> 01:21:03.600 tangiert das den kritischen Teil, dass hinten die Anzahl der Einsen 01:21:03.600 --> 01:21:07.080 quadratisch sein, Quadratzahl sein muss. 01:21:07.380 --> 01:21:08.220 Überhaupt nicht. 01:21:09.580 --> 01:21:13.940 Das heißt, in anderen Worten, wenn ich dann so ein W gleich 0 hoch J, 01:21:14.320 --> 01:21:20.380 1 hoch K Quadrat betrachte und unser V ist das erste Symbol, dann ist 01:21:20.380 --> 01:21:29.660 auch U V hoch 0 X in L beziehungsweise U V hoch I, I größer gleich 1 X 01:21:29.660 --> 01:21:30.120 in L. 01:21:30.260 --> 01:21:33.440 Denn in dem ersten Fall, naja gut, dann fällt halt einfach die 01:21:33.440 --> 01:21:34.640 Vorrunde 0 weg. 01:21:34.800 --> 01:21:35.620 Das ist nicht schlimm. 01:21:35.980 --> 01:21:38.920 Das ist selbst dann nicht schlimm, wenn es nur eine führende 0 gab. 01:21:39.000 --> 01:21:41.220 Da bleibt immer noch 1 hoch K Quadrat übrig. 01:21:41.720 --> 01:21:44.160 Und 1 hoch K Quadrat ist ein Wort von dem Muster. 01:21:47.090 --> 01:21:52.750 Oder aber da kommen noch so ein paar Nullen dazu, wenn I größer gleich 01:21:52.750 --> 01:21:57.250 1 ist, aber das tangiert hinten die Eins quadratisch. 01:21:58.410 --> 01:22:04.050 Das heißt also, diese Sprache hier sieht so gar nicht regulär aus, ist 01:22:04.050 --> 01:22:06.570 auch nicht regulär, erfüllt aber das Pumping-Lemma. 01:22:12.360 --> 01:22:14.860 Die Welt ist schlecht, aber so schlecht ist sie doch nicht. 01:22:14.860 --> 01:22:17.980 Zumindest für die Sprache haben wir noch ein allgemeineres Pumping 01:22:17.980 --> 01:22:21.460 -Lemma, mit dem man zeigen kann, die Sprache ist nicht regulär. 01:22:22.300 --> 01:22:25.400 Aber auch dies verallgemeinerte Pumping-Lemma, das wir das nächste Mal 01:22:25.400 --> 01:22:30.020 dann genauer betrachten, das sieht halt dann noch schwieriger aus als 01:22:30.020 --> 01:22:33.240 das hier. 01:22:34.140 --> 01:22:40.560 Auch dieses verallgemeinerte Pumping-Lemma beschreibt nur eine 01:22:40.560 --> 01:22:45.380 notwendige Bedingung für Regularität, keine hinreichende, hat also 01:22:45.380 --> 01:22:46.740 auch irgendwo dann Grenzen. 01:22:48.980 --> 01:22:50.160 Ja, und das wär's für heute.