WEBVTT 00:02.360 --> 00:06.320 Ja, willkommen zur dritten Vorlesung, Theoretische Grundlagen der 00:06.320 --> 00:07.100 Informatik. 00:08.100 --> 00:10.320 So, jetzt, was haben wir letzte Vorlesung gemacht? 00:10.400 --> 00:14.080 Wir haben letzte Vorlesung den Satz dort oben bewiesen, jede reguläre 00:14.080 --> 00:17.140 Sprache wird von einem deterministischen endlichen Automaten 00:17.140 --> 00:17.740 akzeptiert. 00:17.820 --> 00:22.100 Wir haben den Automaten tatsächlich nicht deterministisch gebaut, 00:22.500 --> 00:26.160 indem wir uns entlanggehangelt haben der induktiven Definition von 00:26.160 --> 00:29.520 regulären Sprachen, haben dann gezeigt, dass dieses nicht 00:29.520 --> 00:34.400 deterministisch tatsächlich in deterministisch umgewandelt werden 00:34.400 --> 00:37.040 kann, mit der sogenannten Potenzmengen-Konstruktion. 00:37.720 --> 00:41.980 Und dann hatte ich Ihnen letztes Mal diese drei Fragen als Ausblick 00:41.980 --> 00:45.480 gestellt, wobei bei der zweiten Frage mir ein Fehler unterlaufen war. 00:45.960 --> 00:48.320 Also, das sind die drei Fragen, die wir heute wirklich beantworten 00:48.320 --> 00:48.700 wollen. 00:50.060 --> 00:51.700 Zumindest die letzte teilweise. 00:52.240 --> 00:53.700 Doch, eigentlich beantworten wir die. 00:53.920 --> 00:55.920 Also, was sind die drei Fragen, die uns heute interessieren? 00:55.920 --> 01:00.840 Das Erste ist, was können nicht deterministische endliche Automaten, 01:00.900 --> 01:04.660 die zwar Wahlmöglichkeiten haben, aber diese komischen Epsilon 01:04.660 --> 01:05.480 -Übergänge nicht? 01:07.020 --> 01:12.160 Okay, das ist relativ losgelöst von dem Rest, werden wir aber zuerst 01:12.160 --> 01:12.960 anschauen. 01:13.720 --> 01:17.100 Der zweite Punkt, der letztes Mal ein bisschen falsch da drauf stand. 01:19.080 --> 01:24.100 Die Frage, die wir noch nicht wissen ist, gibt es Sprachen, die nicht 01:24.100 --> 01:27.920 deterministische endliche Automaten erkennen, die aber nicht regulär 01:27.920 --> 01:28.260 sind. 01:28.660 --> 01:31.580 Wir wissen, dass jede reguläre wird erkannt, aber vielleicht sind die 01:31.580 --> 01:34.040 nicht deterministischen endlichen Automaten ja noch mächtiger und 01:34.040 --> 01:36.260 können noch mehr als nur die regulären erkennen. 01:36.400 --> 01:37.360 Vielleicht erkennt ihr ja alles. 01:39.140 --> 01:40.680 Das gibt uns auch die dritte Frage. 01:40.820 --> 01:44.320 Gibt es irgendeine Sprache, die nicht erkannt werden kann von den 01:44.320 --> 01:46.020 nicht deterministischen endlichen Automaten? 01:47.720 --> 01:50.320 Und den Fragen wollen wir heute auf den Grund gehen. 01:50.840 --> 01:55.100 Ich wurde letztes Mal schon, hatte ich diese Folie, mit einer anderen 01:55.100 --> 01:57.460 zweiten Frage, aber hatte ich diese Folie hier herangeworfen und 01:57.460 --> 02:00.280 danach kam schon die Frage, wie sieht es denn aus mit diesen 02:00.280 --> 02:01.560 Implikationspfeilen? 02:02.460 --> 02:04.260 Welche davon lassen sich denn umdrehen? 02:04.860 --> 02:07.140 Also was davon sind tatsächlich Äquivalenzen? 02:08.880 --> 02:11.640 Und das erste ist tatsächlich eine Äquivalenz. 02:12.740 --> 02:15.440 Das haben wir nie so richtig formal bewiesen, sondern wir haben 02:15.440 --> 02:19.400 eigentlich so die regulären Sprachen, die regulären Ausdrücke Seite an 02:19.400 --> 02:23.060 Seite eingeführt und das ist auch ziemlich offensichtlich, dass das 02:23.060 --> 02:24.460 eigentlich das Gleiche beschreibt. 02:26.780 --> 02:32.260 Hier hinten ist die Implikation eingezeichnet, die eigentlich die 02:32.260 --> 02:35.340 schwierige Implikation ist, die diese Potenzmengen-Konstruktion 02:35.340 --> 02:36.440 gebraucht hat. 02:36.820 --> 02:41.060 Natürlich gilt es auch in die andere Richtung, weil wenn ich ein DEA 02:41.060 --> 02:46.360 habe, dann kann ich auch einfach sagen, dieser DEA ist einfach ein 02:46.360 --> 02:51.960 NEA, der seine Wahlmöglichkeiten nicht ausnutzt, wo einfach die Delta, 02:52.100 --> 02:55.220 die Übergangsfunktion, immer auf einelementige Teilmengen abbildet. 02:55.860 --> 02:59.960 Und Epsilon-Übergänge treten nicht auf oder wir sagen dann, dass der 02:59.960 --> 03:02.800 Epsilon -Übergang einem Zustand auf den Zustand selber wieder führt. 03:03.880 --> 03:07.940 Das heißt hier die von rechts nach links ist eigentlich einfach. 03:09.980 --> 03:13.020 Okay, das heißt wir haben hier die Äquivalenz zwischen den regulären 03:13.020 --> 03:15.960 Sprachen und regulären Ausdrücken und hier die Äquivalenz zwischen den 03:15.960 --> 03:19.360 Sprachen, die von NEAs erkannt werden und den Sprachen, die von DEAs 03:19.360 --> 03:19.960 erkannt werden. 03:20.020 --> 03:24.440 Und jetzt ist noch die Frage, das ist diese blaue Frage, wie sieht es 03:24.440 --> 03:25.460 denn in der Mitte aus? 03:27.920 --> 03:29.560 Gilt hier auch eine Äquivalenz? 03:30.220 --> 03:35.540 Oder wenn nicht, gibt es denn Sprachen, die NEAs erkennen können, aber 03:35.540 --> 03:36.840 die nicht regulär sind? 03:38.180 --> 03:40.840 Das werden wir noch beantworten. 03:41.200 --> 03:44.960 Wir machen aber erstmal der Reihe nach diese erste Frage. 03:45.200 --> 03:48.860 Um nochmal reinzukommen in NEAs und Epsilon-Übergänge und so weiter, 03:49.280 --> 03:54.320 wollen wir uns anschauen, was können NEAs, wenn wir ihnen die Epsilon 03:54.320 --> 03:55.260 -Übergänge wegnehmen. 03:55.660 --> 03:58.940 Wir erlauben ihnen die Wahlmöglichkeiten, aber wir nehmen ihnen die 03:58.940 --> 04:00.000 Epsilon -Übergänge weg. 04:02.360 --> 04:06.820 Und der Satz, ich sage es gleich vorne weg, es passiert nichts. 04:07.500 --> 04:11.400 Also es passiert in dem Sinne nichts, dass wir zu jedem NEA, der 04:11.400 --> 04:17.660 Epsilon -Übergänge eventuell hat, gibt es einen NEA-Schlange, ohne 04:17.660 --> 04:20.740 Epsilon -Übergänge, der dieselbe Sprache akzeptiert. 04:21.360 --> 04:24.880 Das sind also äquivalente Automaten, erkennen, akzeptieren dieselbe 04:24.880 --> 04:25.260 Sprache. 04:26.200 --> 04:31.180 Und wir müssen noch nicht mal mehr Zustände einführen. 04:32.180 --> 04:34.660 Das letzte Mal, wo wir so einen Automaten in den äquivalenten 04:34.660 --> 04:37.640 Automaten überführt haben, das war diese Potenzmengen-Konstruktion, da 04:37.640 --> 04:41.760 haben wir sehr viel mehr Zustände als im Ausgangsautomaten gehabt. 04:42.160 --> 04:43.520 Das brauchen wir hier noch nicht mal. 04:44.040 --> 04:47.720 Wir können sogar ohne neue Zustände, können wir diese ganzen Epsilon 04:47.720 --> 04:50.620 -Übergänge wegkonstruieren. 04:53.860 --> 04:57.660 Und der Beweis ist nicht schwierig, ich werde ihn trotzdem erst mal an 04:57.660 --> 05:02.740 diesem kleinen Ausschnitt oder diesem kleinen Automaten hier 05:02.740 --> 05:06.540 erläutern, die Idee, und danach machen wir eine Folie lang den 05:06.540 --> 05:07.340 formalen Beweis. 05:08.900 --> 05:12.620 Zur Erinnerung, wir werden brauchen diese Erweiterung von Delta, die 05:12.620 --> 05:14.800 wir das letzte Mal eingeführt haben, Delta-quer. 05:15.560 --> 05:20.240 Erinnern Sie sich, Delta an sich sagt einfach nur für einen Zustand 05:20.240 --> 05:25.620 und ein gelesenes Zeichen in einem NEA, in welche Menge von Zuständen 05:25.620 --> 05:29.060 der NEA dann wechseln darf, wenn er dieses Zeichen liest und vorher in 05:29.060 --> 05:29.940 diesem Zustand war. 05:31.260 --> 05:37.500 Und Delta-quer war jetzt, wenn wir nur wirklich hier bei einem Zustand 05:37.500 --> 05:41.080 bleiben und bei einem Zeichen bleiben, dann alles, was hier erweitert 05:41.080 --> 05:45.000 wurde, waren, dass die Epsilon-Übergänge mit einbezogen wurden in 05:45.000 --> 05:47.620 diese Übergangsfunktion. 05:48.320 --> 05:55.160 Also, ein Zustand P liegt in dieser Menge, Delta-quer Q A, genau dann, 05:55.320 --> 06:00.200 wenn der Zustand P erreichbar ist von Q durch beliebig viele Epsilon 06:00.200 --> 06:03.320 -Übergänge und genau einmal lesen des Zeichens A. 06:04.420 --> 06:09.280 Also, entweder erst ein paar Epsilon, dann dieses eine A, dann ein 06:09.280 --> 06:13.220 paar Epsilon oder auch keine Epsilon oder nur vor dem A oder nur 06:13.220 --> 06:13.800 hinter dem A. 06:16.100 --> 06:18.140 Machen wir das hier nochmal an diesem Beispiel. 06:18.280 --> 06:23.500 Wir haben hier diese vier Zustände und die vier Übergänge und jetzt 06:23.500 --> 06:26.100 gucken wir uns mal an, zu jedem Zustand, was ist denn diese Menge 06:26.100 --> 06:28.240 Delta -quer Q A. 06:29.820 --> 06:34.160 Also, zum Beispiel, wenn der Zustand einfach nur der Zustand F ist, 06:34.360 --> 06:37.720 dann, naja, wo kann ich hinkommen, indem ich beliebig viele oder gar 06:37.720 --> 06:40.260 keine Epsilon-Übergänge nehme und genau einmal das A? 06:40.600 --> 06:43.440 Na ja, ich kann nur diese Schlaufe hier laufen und nach F kommen. 06:44.820 --> 06:47.440 Ein bisschen interessanter wird es jetzt schon, wenn ich von U 06:47.440 --> 06:48.080 ausgehe. 06:49.740 --> 06:57.780 Delta, ohne das Quer, Delta von U A ist leer oder zumindest gibt es 06:57.780 --> 07:00.320 keinen ausgehenden Pfeil hier an dem U. 07:01.320 --> 07:06.820 Aber Delta-quer von U A enthält jetzt den Zustand F, weil ich da 07:06.820 --> 07:09.880 hinkommen kann, indem ich erst einen Epsilon-Übergang mache und dann 07:09.880 --> 07:10.720 dieses A lese. 07:12.460 --> 07:15.820 Okay, also das ist, Delta-quer von Q A ist auch F. 07:16.360 --> 07:21.000 Und wir wollen ja einen Automaten ändern, indem wir diese Epsilon 07:21.000 --> 07:22.460 -Übergänge irgendwie loswerden. 07:22.960 --> 07:27.060 Na ja, und die Anschauung ist jetzt, es ist möglich von U nach F zu 07:27.060 --> 07:28.360 kommen, indem wir A lesen. 07:28.600 --> 07:32.000 Das heißt, wir werden dann so einen Übergang hier einführen, der 07:32.000 --> 07:33.180 eigentlich vorher gar nicht da war. 07:34.720 --> 07:34.800 Okay. 07:36.020 --> 07:38.800 Gehen wir weiter nach vorne, der Zustand T. 07:39.720 --> 07:42.620 Was ist denn da im Delta-quer Q A drin? 07:43.120 --> 07:46.620 Na ja, ich kann entweder nach U kommen, indem ich einfach nur A lese, 07:46.720 --> 07:49.820 ohne irgendwelche Epsilon-Übergänge, oder ich kann sogar nach F 07:49.820 --> 07:52.420 kommen, indem ich A und dann noch Epsilon-Übergänge mache. 07:52.820 --> 07:57.780 Okay, das heißt, diese Delta-quer Menge von T ist die Menge U und F. 07:58.780 --> 08:05.540 Wiederum, das ist nicht gleich die einfach nur Delta-Menge von T und 08:05.540 --> 08:08.740 A, weil die würde nur U beinhalten und F nicht. 08:09.940 --> 08:12.680 Das heißt, wir wollen jetzt diesen Epsilon-Übergang da hinten 08:12.680 --> 08:16.780 loswerden, das heißt, wir müssen jetzt auch erlauben, dass von T nach 08:16.780 --> 08:20.380 F nur durch Lesen des Zeichens A gelangt wird. 08:23.660 --> 08:26.320 Und das Letzte ist von S. 08:27.700 --> 08:35.440 In dieser Menge Delta-quer von S A sind die Zustände U und F drin. 08:36.720 --> 08:39.720 Wundern Sie sich nicht, dass T da nicht drin ist, weil ich muss 08:39.720 --> 08:41.860 wirklich genau einmal das A lesen. 08:42.840 --> 08:47.140 Okay, das ist keine Bedingung, dass ich die relaxieren kann. 08:47.200 --> 08:50.640 Ich muss die exakt einmal lesen, das A, und bei den Epsilon-Übergängen 08:50.640 --> 08:51.540 kann ich machen, was ich will. 08:51.640 --> 08:52.440 Vorher, nachher. 08:54.300 --> 08:57.020 Und so kann ich zum Beispiel erst Epsilon und dann A, dann lande ich 08:57.020 --> 08:59.640 bei U, oder ich mache erst Epsilon, dann A, dann Epsilon, dann lande 08:59.640 --> 09:00.080 ich bei F. 09:00.380 --> 09:03.760 Das heißt, auch S hat diese Delta-quer Menge U und F. 09:04.060 --> 09:08.000 Und dadurch müssen wir jetzt auch für S diese Pfeile einrichten, die 09:08.000 --> 09:13.820 nach U und nach F gehen und mit A beschrieben sind. 09:14.560 --> 09:17.400 Und wenn wir das alles so gemacht haben, dann haben wir jetzt ein paar 09:17.400 --> 09:20.120 neue A-Übergänge eingeführt. 09:20.300 --> 09:23.140 Vielleicht sind ein paar die alten A-Übergänge sind auch da gewesen, 09:23.660 --> 09:29.560 aber dieser Automat jetzt schon ist äquivalent zu dem davor und wir 09:29.560 --> 09:32.260 können einfach die Epsilon-Übergänge wegnehmen und der bleibt 09:32.260 --> 09:32.900 äquivalent. 09:33.240 --> 09:33.960 Das ist so die Idee. 09:34.280 --> 09:35.600 Jetzt kommt der formale Beweis. 09:36.360 --> 09:40.800 Also, zur Änderung, wir wollen ein NEA nehmen mit Epsilon-Übergängen 09:40.800 --> 09:45.340 und einen äquivalenten NEA A-Schlange definieren. 09:45.920 --> 09:50.300 Das heißt, wir haben gegeben dieses 5-Tupel Q, Sigma, Delta, S und F 09:50.300 --> 09:54.680 und konstruieren jetzt ein neues 5-Tupel Q-Schlange, Sigma, bleibt 09:54.680 --> 09:57.020 gleich Delta-Schlange, S-Schlange, F-Schlange. 09:58.560 --> 10:00.880 Und die Konstruktion gebe ich jetzt einfach an und dann muss ich noch 10:00.880 --> 10:02.760 argumentieren, warum sie das Gewünschte tut. 10:02.760 --> 10:08.500 Gut, die Konstruktion ist ganz einfach für drei der fünf Sachen, also 10:08.500 --> 10:11.420 die Zustandsmenge bleibt die gleiche, der Startzustand bleibt der 10:11.420 --> 10:16.320 gleiche, die Endzustände bleiben die gleichen, die akzeptierenden 10:16.320 --> 10:17.000 Endzustände. 10:17.500 --> 10:24.180 Nur die Übergangsfunktion ändert sich, indem ich sage, Delta-Schlange, 10:24.620 --> 10:28.120 Schlange ist jetzt die zu dem Automaten A-Schlange, Delta-Schlange von 10:28.120 --> 10:34.260 Q -A definiere ich als, wenn A ein echtes Zeichen ist, als Delta-Quer 10:34.260 --> 10:35.000 von Q-A. 10:35.200 --> 10:39.300 Das sind alle Möglichkeiten, wo ich hinkommen kann mit meinem NEA 10:39.300 --> 10:44.340 durch Lesen genau eines As und beliebigen Epsilon-Übergängen davor 10:44.340 --> 10:44.980 oder danach. 10:46.820 --> 10:51.120 Und wenn A das leere Wort ist, also wenn es jetzt einen Epsilon 10:51.120 --> 10:55.200 -Übergang spezifizieren soll, dann sage ich, okay, Epsilon-Übergang 10:55.200 --> 10:59.140 von Q aus soll nicht möglich sein oder mich einfach wieder nur nach Q 10:59.140 --> 11:01.240 bringen, also dem Automaten nichts bringen. 11:01.700 --> 11:05.940 Also Delta-Schlange von Q-Epsilon ist einfach nur die Menge Q. 11:06.280 --> 11:07.360 Egal, was es vorher war. 11:08.640 --> 11:08.740 Okay? 11:10.140 --> 11:14.380 Damit habe ich jetzt meinen Automaten komplett spezifiziert. 11:15.420 --> 11:19.160 Sie merken, dass der Schlange-Automat, der hat keine Epsilon-Übergänge 11:19.160 --> 11:23.960 mehr oder keine nicht-trivialen Epsilon-Übergänge mehr und der enthält 11:23.960 --> 11:26.940 immer noch alle anderen Übergänge, die vorher da waren, aber jetzt 11:26.940 --> 11:27.700 vielleicht ein paar mehr. 11:28.020 --> 11:29.080 Siehe das Beispiel davor. 11:30.280 --> 11:33.340 Und die wichtige Erkenntnis ist jetzt dieser Satz hier unten. 11:35.180 --> 11:43.140 Ein Übergang einmal dem Pfeil folgen, ein echter Übergang in dem neuen 11:43.140 --> 11:49.700 Automaten A-Schlange entspricht einer Folge von Übergängen in dem 11:49.700 --> 11:56.540 alten Automaten A mit genau einmal Nicht-Epsilon. 11:58.320 --> 11:58.580 Okay? 11:58.840 --> 12:01.420 Also wieder ist es wieder das Gleiche. 12:01.500 --> 12:05.180 Wenn ich einen Übergang habe und der hat jetzt ein Symbol A drauf, 12:05.460 --> 12:08.620 dann entspricht es in meinem Automaten, mit dem ich gestartet bin, 12:09.060 --> 12:13.580 einer Folge von Übergängen, wobei exakt einmal dieses A drauf ist und 12:13.580 --> 12:14.620 der Rest waren Epsilons. 12:15.020 --> 12:15.200 Okay? 12:15.240 --> 12:17.940 Die Folge kann auch einfach nur simpel gewesen sein. 12:18.000 --> 12:20.900 Nur ein A vorher, aber eventuell waren da noch Epsilons. 12:21.540 --> 12:23.180 Und umgekehrt. 12:23.400 --> 12:26.840 Wann immer ich so eine Folge in meinem Automaten, den gegebenen 12:26.840 --> 12:31.040 Automaten mit Epsilon-Übergängen finde, sodass genau einmal Nicht 12:31.040 --> 12:34.640 -Epsilon drin ist, entspricht es genau einem Übergang, den habe ich 12:34.640 --> 12:37.660 gerade eingeführt, in meinem neuen Automaten. 12:38.140 --> 12:38.160 Okay? 12:39.080 --> 12:46.060 Und so sollte es ganz evident sein, dass die Abarbeitung des Automaten 12:46.060 --> 12:52.120 A entspricht einer Abarbeitung des Automaten A-Schlange und wir landen 12:52.120 --> 12:55.980 in N-Zuständen in A, genau dann, wenn wir in N-Zuständen in A-Schlange 12:55.980 --> 12:56.920 landen. 12:57.160 --> 13:01.560 Das heißt, die beiden Automaten erkennen dieselbe Sprache oder sie 13:01.560 --> 13:02.240 sind Äquivalent. 13:02.500 --> 13:08.960 Also die Moral von der Geschichte ist, dass wir erlauben in den NEAs 13:08.960 --> 13:13.980 die Epsilon-Übergänge und wir erlauben die Wahlmöglichkeiten, um die 13:13.980 --> 13:16.420 Konstruktion solcher Automaten zu vereinfachen. 13:16.560 --> 13:19.560 Erinnern Sie sich vielleicht an diese Vereinigungskonstruktion von 13:19.560 --> 13:20.380 zwei Sprachen? 13:20.860 --> 13:24.640 Einfach ein neuer Startzustand und zwei Epsilon-Übergänge, dass er 13:24.640 --> 13:28.140 automatisch aussuchen kann, wo er hingeht, ohne ein Zeichen zu lesen. 13:28.340 --> 13:32.140 Das ist ganz einfach, wenn man diese Tools hat, um diese Automaten zu 13:32.140 --> 13:32.720 konstruieren. 13:33.260 --> 13:38.180 Tatsächlich macht es die Automaten aber nicht mächtiger. 13:39.080 --> 13:39.580 Okay? 13:40.440 --> 13:44.420 Die Epsilon-Übergänge können wir relativ leicht wegkriegen, noch nicht 13:44.420 --> 13:46.100 mal durch Vergrößern des Automatens. 13:46.220 --> 13:49.520 Wir haben mehr Übergänge, aber die gleichen Zustände. 13:50.860 --> 13:53.940 Und Wahlmöglichkeiten, das ist diese Potenzmengenkonstruktion vom 13:53.940 --> 13:55.720 letzten Mal, die kriegen wir auch noch weg. 13:56.200 --> 13:59.460 Da müssen wir allerdings die Zustandsmenge ziemlich groß machen. 14:01.600 --> 14:01.860 Okay. 14:03.940 --> 14:06.060 Jetzt sind wir wieder auf dieser Folie. 14:06.160 --> 14:09.900 Wir haben diese erste Frage beantwortet. 14:10.420 --> 14:14.160 Was können NEAs, die zwar Wahlmöglichkeiten haben, aber keine Epsilon 14:14.160 --> 14:14.640 -Übergänge? 14:14.940 --> 14:20.520 Nun, sie können genau das Gleiche wie die echten NEAs mit Epsilon 14:20.520 --> 14:22.080 -Übergängen und Wahlmöglichkeiten. 14:22.620 --> 14:27.140 Was wiederum genau das Gleiche ist, was die DEAs können, die weder 14:27.140 --> 14:29.840 Epsilon -Übergänge noch Wahlmöglichkeiten haben. 14:32.340 --> 14:35.940 Jetzt kommen wir zu der spannenden Frage, was denn jetzt hier in der 14:35.940 --> 14:36.540 Mitte los ist. 14:38.860 --> 14:42.860 Kann ich diese Implikation in der Äquivalenz umformen? 14:43.640 --> 14:50.720 Also kann ich zu jedem NEA sagen, dass die Sprache, die dieser NEA 14:50.720 --> 14:53.220 erkennt, eine reguläre Sprache ist? 14:53.680 --> 14:57.320 Oder können NEAs auch irgendwas erkennen, was nicht regulär ist? 14:58.400 --> 14:58.500 Okay. 14:59.720 --> 15:04.580 Nun, die Antwort auf die Frage hier ist Nein. 15:05.060 --> 15:09.300 Es gibt keine Sprachen, die nicht regulär sind und von NEAs erkannt 15:09.300 --> 15:09.880 werden können. 15:10.840 --> 15:13.560 Das heißt, auch das hier wird eine Äquivalenz sein. 15:15.680 --> 15:19.160 Jede Sprache, die von einem NEA erkannt wird, ist regulär. 15:20.200 --> 15:24.300 Und wir werden das beweisen, indem wir sagen, dass jede Sprache, die 15:24.300 --> 15:27.680 von einem DEA erkannt wird, regulär ist, einfach weil es dann diese 15:27.680 --> 15:30.240 ganzen Wahlmöglichkeiten hat, es ist alles schön deterministisch, es 15:30.240 --> 15:31.340 ist einfacher zu beweisen. 15:31.340 --> 15:35.280 Also jede Sprache, die von einem DEA erkannt wird, dass die regulär 15:35.280 --> 15:38.300 ist, wir werden einen regulären Ausdruck für diese Sprache 15:39.260 --> 15:39.780 konstruieren. 15:40.180 --> 15:41.060 Das ist der Satz. 15:42.240 --> 15:45.160 Jede Sprache, die von einem endlichen Automaten erkannt wird, ob 15:45.160 --> 15:49.080 deterministisch oder nicht, ist regulär. 15:49.240 --> 15:49.380 Gut. 15:51.680 --> 15:53.800 Der Beweis, der ist jetzt wieder ein bisschen komplizierter. 15:54.500 --> 16:00.860 Der reguläre Ausdruck wird im Allgemeinen ziemlich lang werden und 16:00.860 --> 16:04.420 vielleicht auch nicht irgendwie der schlauste reguläre Ausdruck. 16:04.520 --> 16:07.580 Da werden ein paar Tautologien drin sein, das werden wir auch an einem 16:07.580 --> 16:08.500 Beispiel sehen. 16:08.640 --> 16:10.940 Aber es funktioniert, es ist ein regulärer Ausdruck. 16:12.300 --> 16:21.480 Also, wir starten mit einem DEA A, Q, Sigma, Delta, S und F und wir 16:21.480 --> 16:24.440 müssen zeigen, dass die Sprache, die er erkennt, regulär ist. 16:25.760 --> 16:28.480 Die Sprache, die er erkennt, nochmal zur Erinnerung, das ist die 16:28.480 --> 16:32.880 Sprache aller Wörter aus Sigma Stern, sodass der Automat nach 16:32.880 --> 16:37.480 Abarbeitung von dem Wort in einem Zustand aus F landet. 16:37.740 --> 16:41.240 Das ist ein deterministischer Automat, der hat diese Abarbeitung des 16:41.240 --> 16:43.120 deterministisch vorgegeben. 16:43.640 --> 16:47.060 Es gibt nur eine Abarbeitung dieses Wortes und diese eine Abarbeitung 16:47.060 --> 16:51.560 landet in genau einem Zustand und dieser Zustand ist in F, wenn das 16:51.560 --> 16:54.420 Wort aus der Sprache ist und der Zustand ist nicht in F, wenn das Wort 16:54.420 --> 16:55.860 nicht aus der Sprache ist. 16:57.520 --> 16:57.620 Okay. 16:59.260 --> 17:03.120 Wenn wir jetzt, wir wissen nicht genau, wie dieser DEA aussieht, aber 17:03.120 --> 17:06.180 wir wissen, wenn das Wort abgearbeitet wird, sagen wir mal, das hat K 17:06.180 --> 17:13.180 Zeichen, A1 bis AK, dann läuft der Automat von Beginn vom Startzustand 17:13.180 --> 17:17.680 mit jedem Lesen eines Zeichens in einen anderen Zustand. 17:17.840 --> 17:21.780 Also nach Lesen von A1 ist er dann in Q1, nach Lesen von A2 ist er in 17:21.780 --> 17:25.120 Q2 und am Ende nach Lesen von AK ist er in QK. 17:25.760 --> 17:29.620 Das heißt, wir kriegen so eine Folge von Zuständen, nicht 17:29.620 --> 17:33.300 notwendigerweise unterschiedlich, verschiedene Zustände. 17:33.500 --> 17:37.400 Der kann mehrmals durch den gleichen Zustand eventuell durchkommen. 17:39.020 --> 17:42.640 Und wir wissen, der erste hier, dieses S, ist der Startzustand und wir 17:42.640 --> 17:45.260 wissen der letzte, das ist ein Zustand aus F. 17:50.700 --> 17:53.900 Genau und wir suchen jetzt, wir sind interessiert an den Wörtern, 17:54.420 --> 17:57.880 sodass dieser letzte Zustand in so einer Folge hier in F ist. 17:58.620 --> 18:02.300 Und wir werden das so machen, indem wir sagen, okay, wir unterteilen 18:02.300 --> 18:08.020 das getrennt in die Wörter, sodass der letzte Zustand ein festes klein 18:08.020 --> 18:08.940 f aus F ist. 18:09.320 --> 18:13.300 In diesen N-Zuständen, da sind ja vielleicht 15 und wir machen jeden 18:13.300 --> 18:16.220 einzelnen N-Zustand, gibt mir eine F-Zustände, eine Menge von Wörtern, 18:16.340 --> 18:21.200 sodass die Abarbeitung in diesem exakten N-Zustand endet und dann 18:21.200 --> 18:24.360 nehmen wir einfach, am Ende können wir die Vereinigung über diese 15 18:25.260 --> 18:28.080 Sprachen nehmen und wenn wir wissen, dass jede einzelne Sprache 18:28.080 --> 18:31.380 regulär ist, dann ist auch die Vereinigung von 15 Sprachen regulär, 18:31.800 --> 18:33.540 nach der Definition von Regularität. 18:33.880 --> 18:36.960 Okay, also jetzt, wir werden das immer weiter vereinfachen, bis es 18:36.960 --> 18:40.420 sehr einfach wird, aber es wird sehr viele Teile in dieser 18:40.420 --> 18:41.440 Vereinfachung immer geben. 18:42.280 --> 18:43.640 Das ist die erste Vereinfachung. 18:43.920 --> 18:47.560 Wir betrachten nur einen festen N-Zustand f, um den wir uns jetzt 18:47.560 --> 18:48.060 kümmern müssen. 18:49.180 --> 18:52.960 Und wollen jetzt nur noch die Wörter, die Sprache aller Wörter, sodass 18:52.960 --> 18:57.400 für diesen Automaten und diesen N-Zustand, der die dorthin überführt. 18:59.820 --> 19:04.020 Also, formal definieren wir uns L und einen kleinen f, die Wörter w, 19:04.420 --> 19:07.920 sodass der Automat a nach Arbeitbehaltung von diesem Wort w in genau 19:07.920 --> 19:14.440 diesem Zustand f landet oder wir sagen, w überführt s in f. 19:14.720 --> 19:18.300 Er startet ja immer in s und er endet jetzt in f. 19:18.380 --> 19:22.260 Er überführt diese beiden Zustände oder das Wort überführt den 19:22.260 --> 19:26.060 Automaten von Zustand s in Zustand f. 19:27.740 --> 19:30.060 Und das hier unten ist das, was ich gerade schon gesagt habe. 19:30.200 --> 19:33.080 Unsere Sprache, die wir eigentlich zeigen wollen, ist jetzt die 19:33.080 --> 19:37.500 Vereinigung von diesen Sprachen und wenn wir also für jede von denen 19:37.500 --> 19:40.600 zeigen können, dass sie regulär ist, dann ist auch L regulär als 19:40.600 --> 19:42.540 Vereinigung von regulären Sprachen. 19:46.780 --> 19:50.340 Wieder zur Erinnerung, das ist jetzt diese, ich will das jetzt mal so 19:50.340 --> 19:56.420 formulieren, das sind die Wörter, die den Zustand s in den Zustand f 19:56.420 --> 19:57.080 überführen. 19:58.640 --> 20:02.680 Und jetzt will ich das wieder aufsplitten und zwar will ich sagen, für 20:02.680 --> 20:09.120 beliebige Zustände q, was ist das, r und qt, gucke ich mir jetzt die 20:09.120 --> 20:12.960 Wörter an, die qr in qt überführen. 20:17.220 --> 20:21.240 Letztendlich bin ich nur daran interessiert, wenn qr der Startzustand 20:21.240 --> 20:25.100 ist und qt dieser Endzustand f, aber ich würde es jetzt für beliebige 20:25.100 --> 20:29.420 Zustände, will ich sagen, angenommen der Automat sei in diesem Zustand 20:29.420 --> 20:35.960 qr und er liest ab jetzt nur noch das Wort w und dann ist er in qt, 20:36.140 --> 20:38.880 diese Wörter w, die das vollbringen. 20:39.800 --> 20:42.960 Diese Menge würde ich mir angucken und das sage ich, das ist jetzt die 20:42.960 --> 20:45.400 Menge l unten qr qt. 20:48.240 --> 20:51.760 Also insbesondere ist die Sprache, die mich jetzt eigentlich 20:51.760 --> 20:54.640 interessiert, einfach l unten s, f. 20:57.460 --> 21:00.540 Jetzt mache ich es mir noch ein bisschen kleinschrittiger. 21:03.140 --> 21:08.680 In dieser Sprache will ich jetzt noch mal unterscheiden, wie genau sie 21:08.680 --> 21:13.380 denn von den Automaten von qr nach qt überführen, diese Wörter. 21:14.200 --> 21:17.320 Und zwar was dazwischen, was die Zwischenzustände sind. 21:18.320 --> 21:22.220 Und ich sage mir jetzt einfach, ich nummeriere meine Zustände völlig 21:22.220 --> 21:28.140 willkürlich von q1 nach qn, wirklich willkürlich und sage für ein 21:28.140 --> 21:34.220 gegebenes i, hier ist ein kleines i, sind jetzt als Zwischenzustände, 21:35.360 --> 21:38.460 also nicht Start, nicht Ende, sondern das, was in der Mitte passiert, 21:38.780 --> 21:40.760 nur noch erlaubt von q1 bis qi. 21:43.920 --> 21:46.920 Also manche Wörter, die jetzt in dieser Sprache sind, die den 21:46.920 --> 21:51.040 Automaten von qr nach qt überführen, die brauchen nur die Zustände 1 21:51.040 --> 21:54.540 bis i und manche brauchen irgendwas außerhalb. 21:54.800 --> 21:56.840 Und die sage ich dann, die will ich jetzt wegschmeißen. 21:57.400 --> 22:06.020 Also die Sprache l und ein qr i qt sind die Wörter, sodass die 22:07.220 --> 22:13.480 Abarbeitung von w ausgehend oder startend am Zustand qr endend im 22:13.480 --> 22:18.760 Zustand qt nur Zwischenzustände in dieser Menge q1 bis qi hat. 22:24.390 --> 22:26.940 Also irgendwie bildlich wäre es das hier. 22:27.800 --> 22:31.780 Ich habe hier von qr, ich benutze irgendwelche Übergänge, am Ende bin 22:31.780 --> 22:34.940 ich bei qt und alles, was hier zwischen ist, ist nur aus q1 bis qi. 22:36.180 --> 22:39.020 Wenn ich jetzt natürlich i gleich n setze, dann ist als 22:39.020 --> 22:41.360 Zwischenzustand alles erlaubt. 22:41.720 --> 22:44.080 Das heißt, die Sprache, an der ich eigentlich jetzt schon interessiert 22:44.080 --> 22:49.140 bin, dieses l unten qr qt, ist das gleiche wie l unten qr n qt. 22:53.720 --> 22:55.020 So, jetzt nochmal. 22:55.020 --> 22:59.720 Wir haben das jetzt schon so weit zusammengestampft, dass wir nur noch 22:59.720 --> 23:00.360 darüber reden. 23:00.500 --> 23:02.820 l unten qr i qt. 23:04.260 --> 23:11.500 Jetzt wollen wir zeigen, dass diese Sprachen hier alle regulär sind. 23:13.440 --> 23:17.740 Es sind jetzt nicht mehr richtig Teile unserer ganz ursprünglichen 23:17.740 --> 23:20.100 Sprache, weil wir jetzt eigentlich nur noch an dem Teil interessiert 23:20.100 --> 23:24.920 sind, wo hinten n ist und wo vorne ein s ist und hinten irgendwas aus 23:24.920 --> 23:26.040 den n-Zuständen. 23:26.980 --> 23:29.540 Es sind irgendwelche Sprachen. 23:29.840 --> 23:35.680 Aber die sind alle regulär und insbesondere fällt da auch ein Teil 23:35.680 --> 23:39.320 unserer finalen Sprache drunter, wo nämlich vorne s, in der Mitte ein 23:39.320 --> 23:41.580 n und hinten ein f ist. 23:42.540 --> 23:44.900 Wir wollen zeigen, dass die alle regulär sind. 23:49.020 --> 23:53.900 Jetzt machen wir mal ein paar, bevor wir das exakt zeigen, machen wir 23:53.900 --> 23:55.340 mal ein paar erste Beobachtungen. 23:55.520 --> 23:59.500 Die erste Beobachtung ist, dass ich möchte gerne auch i gleich 0 23:59.500 --> 24:02.260 erlauben, was ein bisschen seltsam ist. 24:02.400 --> 24:07.320 Die Zwischenzustände sind aus der Menge q1 bis q0. 24:08.500 --> 24:14.820 Das ist so ein kleiner mathematischer Trick, um zu sagen, keiner ist 24:14.820 --> 24:16.420 erlaubt, kein Zwischenzustand. 24:16.840 --> 24:22.220 Wenn in so einem Laufindex der Start größer ist als das Ende, dann ist 24:22.220 --> 24:23.100 es einfach die leere Menge. 24:24.120 --> 24:33.540 Das heißt, diese Menge hier qr, qt mit einer 0 in der Mitte sind die 24:33.540 --> 24:37.200 Wörter, die qr nach qt überführen, ohne Zwischenzustände. 24:41.630 --> 24:46.590 Das ist insbesondere eine sehr einfache Sprache. 24:46.790 --> 24:50.450 Also entweder, wenn hier vorne und hinten der gleiche Zustand steht, 24:52.490 --> 24:57.870 dann ist das einfach, genau, dann ist es einfach diese Menge hier, 24:57.950 --> 25:01.510 also jetzt habe ich qr und qt mit r und t gleich, also vorne und 25:01.510 --> 25:02.530 hinten ist der gleiche Zustand. 25:03.130 --> 25:07.250 Dann ist es dort, wo der Übergang an qt oder qr, ist ja dasselbe, 25:07.770 --> 25:09.670 sagt, wenn ich a lese, bleibe dort. 25:09.750 --> 25:11.890 Das sind diese Loops mit einem a. 25:13.270 --> 25:14.990 Und dann, das a ist das Wort. 25:16.350 --> 25:18.070 Oder das ist das leere Wort. 25:18.150 --> 25:19.410 Das leere Wort wird es auch tun. 25:19.510 --> 25:23.210 Das wird mich von qr nach qt bringen, ohne Zwischenzustände. 25:25.010 --> 25:29.730 Und beide von diesen, diese Menge als Sprache gesehen ist regulär. 25:30.670 --> 25:31.970 Das ist diese Verankerung. 25:32.610 --> 25:35.790 Und diese Menge hier ist ja wirklich jetzt nur ein Wort und dieses 25:35.790 --> 25:40.010 Wort hat nur ein Zeichen und das ist auch regulär. 25:40.230 --> 25:43.750 Und dann die Vereinigung von denen ist regulär. 25:45.530 --> 25:49.950 Also jetzt haben wir es so simpel gemacht, dass die Verankerung von 25:49.950 --> 25:51.890 der Regularität zu Trage kommt. 25:52.990 --> 25:55.990 Wenn jetzt r nicht gleich t ist, also r und t wirklich zwei 25:55.990 --> 25:59.530 unterschiedliche Zustände sind, naja, dann mit dem leeren Wort, das 25:59.530 --> 26:00.510 hier hinten fällt, einfach weg. 26:00.590 --> 26:03.270 Dann ist es jetzt ein echter Pfeil, der nicht so eine Schleife ist, 26:03.790 --> 26:07.930 sondern wirklich von qr direkt nach qt mit genau einem Zeichen a. 26:08.690 --> 26:13.030 Und dann ist dieses Wort, was nur aus a besteht, das ist dann in 26:13.030 --> 26:14.230 dieser Sprache drin. 26:14.750 --> 26:19.790 Das überführt den Automaten von qr nach qt mit keinen erlaubten 26:19.790 --> 26:20.610 Zwischenzuständen. 26:22.110 --> 26:24.690 Und das zeigt uns schon so ein bisschen vielleicht so einen Hinweis, 26:24.770 --> 26:26.470 was wir eigentlich machen wollen. 26:28.290 --> 26:30.510 Vielleicht machen wir noch einen Schritt, i gleich 1. 26:31.950 --> 26:34.830 Wenn wir jetzt i gleich 1 haben, dann haben wir jetzt also von qr nach 26:34.830 --> 26:40.730 qt und als Zwischenzustände sind erlaubt aus der Menge q1 bis q1. 26:40.830 --> 26:43.430 Also nur q1 ist erlaubt als Zwischenzustand. 26:43.770 --> 26:46.490 Muss nicht benutzt werden, ist es erlaubt. 26:47.630 --> 26:52.130 Und dann können wir dieses Ding hier, das ist jetzt wirklich die 26:52.130 --> 26:55.370 wichtige Erkenntnis zu dem ganzen Beweis, wir können diese Sprache 26:55.370 --> 27:01.990 aufspalten in die, naja, die direkt von qr nach qt gehen, ohne diesen 27:01.990 --> 27:04.610 Zwischenzustand zu benutzen, der jetzt erlaubt wäre. 27:05.350 --> 27:07.950 Oder die, die den Zwischenzustand benutzen. 27:08.910 --> 27:13.450 Und die wiederum müssen ja jetzt das wirklich wie folgt tun, sie 27:13.450 --> 27:19.870 müssen zu dem Zwischenzustand gehen ohne Zwischenzustände von qr nach 27:19.870 --> 27:25.190 q1 dann können sie in diesem Zwischenzustand bleiben vielleicht durch 27:25.190 --> 27:31.810 Loops beliebig viel ohne Zwischenzustände also Hochstern und dann 27:31.810 --> 27:34.750 müssen sie von diesem Zwischenzustand zu dem Endzustand wieder ohne 27:34.750 --> 27:41.490 Zwischenzustände ok und so haben wir das ein bisschen kompliziertere, 27:41.650 --> 27:45.570 wenn wir hier mehr erlauben runtergebrochen auf Sachen, die weniger 27:45.570 --> 27:51.270 als Zwischenzustände erlauben ok, das heißt insbesondere, weil diese 27:51.270 --> 27:56.370 Menge hier regulär ist und diese auch, einfach egal was vorne und 27:56.370 --> 28:00.850 hinten steht, irgendwelche Zustände, die sind alle regulär und das 28:00.850 --> 28:05.530 Ding hier, die Verknüpfungen, die erlaubt sind für reguläre Sprachen, 28:05.950 --> 28:10.970 nämlich Klinische Abschluss, Produkt und Vereinigung nur benutzt ist 28:10.970 --> 28:16.630 diese ganze Menge wenn ich diesen einen Zwischenzustand erlaube auch 28:16.630 --> 28:22.150 wieder regulär ok und jetzt sehen sie vielleicht schon, wo das 28:22.150 --> 28:25.990 hinführen soll, wir wollen jetzt eigentlich sind wir ja auf dem Weg 28:25.990 --> 28:30.310 hier diesen Mittelindex bis n hoch zu kriegen und wir werden jetzt 28:30.310 --> 28:34.090 Induktion machen wir haben die Verankerung schon auf der letzten Folie 28:34.090 --> 28:37.710 gezeigt mit i gleich 0 und jetzt haben wir im Prinzip so den ersten 28:37.710 --> 28:42.530 Schritt gemacht von 0 auf 1 oder besserrum, Induktion sollte sich 28:42.530 --> 28:45.170 immer so vorstellen, wir wollen es für 1 zeigen und wir haben es 28:45.170 --> 28:49.830 runtergebrochen auf 0 und jetzt im Allgemeinen wollen wir es für i 28:49.830 --> 28:56.430 zeigen und es runterbrechen auf i minus 1 oder weniger ok und das ist 28:56.430 --> 29:01.250 jetzt exakt das gleiche Argument für den Induktionsschritt gilt genau 29:01.250 --> 29:06.730 das hier oben bloß mit i und i minus 1 machen sie sich das nochmal 29:06.730 --> 29:11.670 klar, wir wollen das hier ist die Sprache der Wörter die den Automaten 29:11.670 --> 29:16.470 überführen von Zustand qr nach qt und als Zwischenzustände sind 29:16.470 --> 29:23.630 erlaubt q1 bis qi diese Wörter unterteile ich jetzt in die die diesen 29:23.630 --> 29:28.670 letzten den qi, der jetzt neu erlaubt ist, die den benutzen und die, 29:28.830 --> 29:34.810 die den nicht benutzen die, die den nicht benutzen, sind jetzt aber in 29:34.810 --> 29:37.710 dieser Menge schon drin, weil sie jetzt als erlaubte Zwischenzustände 29:37.710 --> 29:43.310 haben nur q1 bis qi minus 1 von der Sprache weiß ich schon, dass sie 29:43.310 --> 29:48.170 regulär ist und wenn sie aber diesen Zwischenzustand benutzen hier 29:48.170 --> 29:51.250 habe ich einen kleinen Indexfehler, hier muss qi stehen wenn sie jetzt 29:51.250 --> 29:53.690 den benutzen, naja dann müssen sie ihn auch benutzen, das heißt sie 29:53.690 --> 29:59.810 müssen erstmal gehen von qr nach qi wenn sie das erste Mal auf qi 29:59.810 --> 30:03.050 treffen und dadurch, dass es das erste Mal ist, benutzen sie 30:03.050 --> 30:08.870 dazwischen nur die Zwischenzustände bis i minus 1 dann sind sie in dem 30:08.870 --> 30:11.990 qi, dann laufen sie eventuell nochmal rum und kommen an dem qi 30:11.990 --> 30:16.770 mehrmals vorbei dürfen aber zwischen zwei aufeinanderfolgenden 30:16.770 --> 30:21.450 Auftreten von qi immer wieder nur die Zwischenzustände 1 bis i minus 1 30:21.450 --> 30:28.070 benutzen und danach müssen sie von dem qi das letzte Auftreten von qi 30:28.070 --> 30:33.450 bis nach qt laufen wieder, auf dem Weg ist nur von 1 bis i minus 1 30:33.450 --> 30:37.150 erlaubt okay, exakt das gleiche bloß, dass ich hier einen kleinen Typo 30:37.150 --> 30:44.250 habe, den ich noch fixen werde gut, also schnüren wir den Sack zu das 30:44.250 --> 30:50.750 hier ist die wichtige Erkenntnis wie diese Sprachen, die wir uns so 30:50.750 --> 30:57.490 definiert haben, wie die zusammenhängen und weil jetzt die lqr iqt 30:57.490 --> 31:02.250 runtergebrochen werden kann nur auf Sprachen der Form l irgendwas, i 31:02.250 --> 31:08.250 minus 1 irgendwas mit Benutzung der Symbole Vereinigung, Produkt und 31:08.250 --> 31:14.370 Klimischen Abschluss können wir jetzt Induktionsvoraussetzung anwenden 31:15.290 --> 31:22.930 für i minus 1 wissen wir, dass die hier schon regulär sind dadurch ist 31:22.930 --> 31:25.930 auch gezeigt, dass die Menge, die jetzt hier dieses i hat, regulär 31:25.930 --> 31:32.090 ist, weil diese ganzen Teile regulär sind nach Induktionsvoraussetzung 31:32.090 --> 31:38.910 und ich die nur verbunden habe mit den erlaubten Sachen, die bei 31:38.910 --> 31:42.070 regulären Sprachen erlaubt sind das heißt, wir haben jetzt gezeigt, 31:42.250 --> 31:52.970 dass für alle qr, qt diese Menge lqr iqt regulär ist ja und damit ist 31:52.970 --> 31:56.950 gezeigt, dass insbesondere wenn ich jetzt qr gleich s setze und qt 31:56.950 --> 32:01.790 gleich f setze und i gleich n setze es ist einfach nur ein Spezialfall 32:01.790 --> 32:05.250 davon und es ist eigentlich der einzige Fall, der uns interessiert ist 32:05.250 --> 32:08.230 diese Menge regulär und wir hatten schon gesehen, naja, das ist ja 32:08.230 --> 32:11.010 jetzt hier keine Einschränkung mehr, ich darf alles benutzen als 32:11.010 --> 32:14.370 Zwischenzustände und das sind die Wörter, die von dem Startzustand in 32:14.370 --> 32:20.910 diesen spezifischen Endzustand f gehen, das ist diese Menge lf, die 32:20.910 --> 32:24.450 ist also jetzt regulär und nach dem, was wir am Anfang gesagt haben, 32:24.510 --> 32:27.530 ist die Sprache des Automatens die Vereinigung dieser regulären 32:27.530 --> 32:38.190 Sprachen und damit selber regulär okay gut so, das ist der Beweis und 32:38.190 --> 32:41.650 Sie merken vielleicht schon, dass wenn wir das jetzt einfach 32:42.270 --> 32:46.930 durchexerzieren, für ein Beispiel jedes Mal wir dieses Ding hier 32:46.930 --> 32:51.070 aufstellen und immer nur kriegen, dass das i um 1 sinkt und dann 32:51.070 --> 32:54.350 müssen wir das auch noch für jedes Paar vorne und hinten machen also 32:54.350 --> 32:57.990 es wird schon sehr, sehr, sehr langer regulärer Ausdruck den man da 32:57.990 --> 33:01.770 aus dem Beweis rauskriegt trotzdem will ich so einen kleinen Ansatz 33:01.770 --> 33:06.130 machen, das mal zu tun wir haben vielleicht Glück, weil es hier nicht 33:06.130 --> 33:11.990 so viele Zustände gibt also versuchen wir das mal das ist jetzt ein 33:11.990 --> 33:17.810 deterministischer endlicher Automat der hat zwei Zustände S und Q S 33:17.810 --> 33:24.510 ist Startzustand die Übergänge sind von S unterlesen von 0 oder 1 33:24.510 --> 33:27.850 lande ich bei Q und von Q unterlesen von 0 oder 1 lande ich bei S das 33:27.850 --> 33:31.510 heißt, der Automat geht immer so hin und her und der akzeptierende 33:31.510 --> 33:38.650 Endzustand ist S okay Sie können vielleicht schon durch bloßes 33:38.650 --> 33:42.370 Draufgucken erkennen was das für eine Sprache ist die dieser Automat 33:42.370 --> 33:45.950 erkennt aber der Beweis dadurch, dass es jetzt von einem endlichen 33:45.950 --> 33:49.470 Automaten kommt der Beweis liefert uns jetzt einen regulären Ausdruck 33:49.470 --> 33:52.590 für diese Sprache indem wir diesen Beweis durchexerzieren. 33:53.090 --> 33:59.530 Wir vereinfachen wann immer es möglich ist Achso, ich habe aus 33:59.530 --> 34:04.410 unerfindlichen Gründen auch noch S, Q1 genannt und Q, Q2 also was uns 34:04.410 --> 34:11.490 eigentlich interessiert ist das hier startend von Q1 endend in Q1 34:11.490 --> 34:14.810 einmal, weil das der Startzustand ist und der Endzustand und unter 34:14.810 --> 34:19.230 Benutzung aller möglichen Zwischenzustände ist die 2 hier, ist die 34:19.230 --> 34:23.430 Anzahl der Zustände das müssen wir jetzt runterbrechen und wir fangen 34:23.430 --> 34:29.970 an bei der Verankerung, wir wollen jetzt für jedes Paar also von Q1 34:29.970 --> 34:36.590 selber nach QI unter Benutzung keiner Zwischenzustände wissen, was 34:36.590 --> 34:40.070 sind das für Wörter die das tun naja, also wie kommt man von S nach S 34:40.070 --> 34:45.050 ohne Benutzung von Zwischenzuständen gar nicht das heißt die Wörter 34:45.050 --> 34:50.370 die das tun ist es nur das leere Wort und das gleiche von Q nach Q ist 34:50.370 --> 34:54.990 nur das leere Wort gut, wenn ich jetzt von I ungleich J ausgehe, also 34:54.990 --> 35:00.430 von Q1 nach Q2 oder von Q2 nach Q1 ohne Benutzung von 35:00.430 --> 35:02.990 Zwischenzuständen welche Wörter sind das? 35:04.090 --> 35:08.950 das sind jetzt Wörter das sind jetzt genau die beiden Wörter, nämlich 35:08.950 --> 35:12.530 nur das Wort was ein Zeichen hat und das Zeichen ist eine 0, das tut 35:12.530 --> 35:16.630 es und das Wort was ein Zeichen hat und das Zeichen ist eine 1, das 35:16.630 --> 35:22.370 tut es das heißt, das hier ist eine Beschreibung für diese Menge diese 35:22.370 --> 35:28.430 Sprache die insbesondere regulär ist wenn ich jetzt als 35:28.430 --> 35:34.990 Zwischenzustand den S erlaube, aber das Q noch nicht ich erlaube als 35:34.990 --> 35:37.690 Zwischenzustand das S und jetzt frage ich mich, wie komme ich denn von 35:37.690 --> 35:42.690 S nach S unter möglicherweise Zwischenzustand S und jetzt kann ich 35:42.690 --> 35:46.430 nachgucken und weiß, dass es durch diesen regulären Ausdruck gegeben 35:46.430 --> 35:50.470 ist, also ich kann entweder von S nach S ohne Zwischenzustand oder ich 35:50.470 --> 35:54.190 gehe erstmal von S zu diesem Zwischenzustand, der jetzt wieder S ist, 35:54.650 --> 35:58.790 ohne was anderes und so weiter und so weiter das heißt, das wird hier 35:58.790 --> 36:02.130 alles runtergebrochen auf das hier, was ich schon kenne, das ist das 36:02.130 --> 36:07.090 leere Wort, da habe ich Glück alles zusammen bleibt das leere Wort ok 36:10.230 --> 36:14.410 wenn ich jetzt zwischen zwei verschiedenen Zuständen gehe, sagen wir 36:14.410 --> 36:19.050 mal von S nach Q und ich darf als Zwischenzustand den S benutzen, kann 36:19.050 --> 36:22.470 ich jetzt wieder diese Formel mir angucken und alles einsetzen und 36:22.470 --> 36:25.550 dann sehe ich, ok entweder ich gehe direkt von S nach Q ohne 36:25.550 --> 36:31.050 Zwischenzustände, das war dieses oder ich gehe erstmal von S zu dem 36:31.050 --> 36:35.630 Zwischenzustand, der jetzt erlaubt ist, das wäre wieder S, das geht 36:35.630 --> 36:42.410 mit dem leeren Wort dann mache ich beliebig viele Umläufe zu diesem 36:42.410 --> 36:47.930 Zwischenzustand also zu dem S, das wäre wieder das leere Wort und dann 36:47.930 --> 36:53.730 gehe ich nochmal von dem Zwischenzustand zum Hinten, das wäre wieder 0 36:53.730 --> 36:59.710 ,1 das heißt, insgesamt habe ich 0,1 vereinigt mit 0,1, das ist 36:59.710 --> 37:04.910 einfach nur 0,1 ok und jetzt kann ich das gleiche wieder in die 37:04.910 --> 37:08.010 Rückrichtung machen, wenn ich von dorthin nach dorthin gehe und die 37:08.010 --> 37:12.970 Zwischenzustände sind erlaubt nur Q1, aber nicht Q2, wieder ähnlich 37:12.970 --> 37:14.950 trivial kommt wieder nur 0,1 raus. 37:15.590 --> 37:20.630 Und jetzt bin ich bei dem, was mich eigentlich interessiert äh ne, 37:20.750 --> 37:23.390 noch nicht, oh Gott, ich kann noch von Hinten nach Hinten unter 37:24.250 --> 37:29.190 Benutzung der Zwischenzustände und da merke ich, genau ich von Hinten 37:29.190 --> 37:32.970 nach Hinten, das ist jetzt interessant von Hinten nach Hinten unter 37:32.970 --> 37:38.630 möglicherweise Benutzung des Zwischenzustandes Q1 ok, das ist entweder 37:38.630 --> 37:43.010 ich benutze den Zustand nicht dann habe ich da keine Möglichkeit oder 37:43.010 --> 37:46.710 ich benutze ihn, dann muss ich da hingehen dann muss ich beliebig oft 37:46.710 --> 37:50.250 in diesem Zustand kreisen, was nicht geht und dann muss ich wieder 37:50.250 --> 37:55.970 zurückgehen ja, das ist einmal von dort nach dort und einmal von dort 37:55.970 --> 37:58.970 nach dort und das sind jetzt tatsächlich nicht triviale Sachen und 37:58.970 --> 38:07.270 rauskommt das hier 0,1 vereinigt äh ja, 0,1 mal 0,1, wobei 0 vereinigt 38:07.270 --> 38:11.910 1 mal 0 vereinigt 1 ok, das heißt das ist jetzt eine Menge, die hat 38:11.910 --> 38:15.030 zwei Wörter mit der Länge 2 38:18.570 --> 38:22.990 und jetzt das letzte, was mich eigentlich interessiert, ich gehe von 38:24.830 --> 38:31.050 ich erlaube alle möglichen Zwischenzustände und ich kann ich gehe von 38:31.050 --> 38:37.330 Q1 nach Q2 oder andersrum ach ne, und hier will ich jetzt von Q1 38:37.330 --> 38:39.970 wieder nach Q1, weil das mein Start und mein Ziel ist und dann gehe 38:39.970 --> 38:44.650 ich entsprechend diese Formel durch, jetzt muss ich manchmal an der 38:44.650 --> 38:49.390 geeigneten Stelle das einsetzen manchmal das hier einsetzen und dann 38:49.390 --> 38:54.750 komme ich auf diesen Ausdruck und der vereinfacht sich dann einfach zu 38:54.750 --> 38:58.270 dem hier und das ist vielleicht auch das, was Sie erwarten würden das 38:58.270 --> 39:03.690 sind nämlich beliebiges Wort der Länge 2 Buchstern, der klinische 39:03.690 --> 39:09.350 Abschluss davon, ja das ist nämlich, der Automat erkennt die Wörter, 39:09.590 --> 39:10.630 die eine gerade Länge haben. 39:10.930 --> 39:17.070 Gut, so das ist das Beispiel zu diesem Beweis was haben wir jetzt 39:17.070 --> 39:17.870 gezeigt? 39:18.970 --> 39:24.150 Wir haben gezeigt dass vom endlichen Automaten akzeptierte Sprachen 39:24.150 --> 39:28.090 immer regulär sind durch die explizite Konstruktion eines regulären 39:28.090 --> 39:33.870 Ausdrucks aus dem Automaten heraus Insgesamt mit dem, was wir letzte 39:33.870 --> 39:36.750 Vorlesung gesehen haben, nämlich zu jedem regulären Ausdruck gibt es 39:36.750 --> 39:39.910 einen Automaten, heißt es jetzt, dass reguläre Sprachen und endliche 39:39.910 --> 39:42.350 Automatensprachen exakt das gleiche sind. 39:43.310 --> 39:49.770 Und das wird als Satz von Kleen bezeichnet die von endlichen Automaten 39:49.770 --> 39:55.190 akzeptierten Sprachen sind genau die regulären Sprachen und wir haben 39:55.190 --> 39:58.490 tatsächlich diese Äquivalenz hier in der Mitte zwischen reguläre 39:58.490 --> 40:02.710 Sprachen und endliche Automaten auf der rechten Seite Dann kümmern wir 40:02.710 --> 40:10.990 uns jetzt um die letzte Frage die da heißt, gibt es denn Sprachen, die 40:10.990 --> 40:14.330 nicht die NEAs nicht erkennen können. 40:14.530 --> 40:17.290 Jetzt wissen wir, dass es gleichbedeutend mit der Frage, gibt es denn 40:17.290 --> 40:24.630 Sprachen, die nicht regulär sind und das ist ad hoc würde ich mal 40:24.630 --> 40:28.510 meinen, nicht so klar vielleicht wissen Sie schon die Antwort aber 40:28.510 --> 40:34.250 machen wir einfach mal ein Beispiel, das ist die folgende Sprache der 40:34.250 --> 40:39.810 korrekten Klammerausdrücke also mein Alphabet besteht aus zwei 40:39.810 --> 40:45.570 Zeichen, Klammerauf und Klammerzu und ein Wort ist jetzt eine Folge 40:45.570 --> 40:48.910 von Zeichen und ich sage, das Wort ist in der Sprache, wenn das 40:48.910 --> 40:54.030 sozusagen gelesen als Klammerausdruck Sinn macht also, dass es ein 40:54.030 --> 40:58.170 ordentlich geschachtelter Klammerausdruck ist, also insbesondere, das 40:58.170 --> 41:01.230 allererste muss ja auf jeden Fall mal eine Klammerauf sein und das 41:01.230 --> 41:04.170 allerletzte muss ja auf jeden Fall mal eine Klammerzu sein aber auch 41:04.170 --> 41:10.610 zwischendrin muss das Sinn ergeben also, das hier ist ein regulärer 41:10.610 --> 41:13.330 Klammerausdruck, Sie sehen das an der Größe der Klammern so ein 41:13.330 --> 41:18.350 bisschen angedeutet, wo die passenden Klammerzu- Klammeraufpaare sind 41:18.350 --> 41:23.330 und hier auf der rechten Seite, das sind Beispiele die nicht reguläre 41:23.330 --> 41:25.590 Klammerausdrücke sind, also hier zum Beispiel sieht eigentlich ganz 41:25.590 --> 41:29.530 gut aus, aber schon allein, weil es fünf Klammern sind, kann es ja gar 41:29.530 --> 41:33.890 nicht funktionieren also, die erste Klammer wir würden jetzt sagen, 41:33.990 --> 41:38.030 die erste Klammer, die geht gar nicht zu oder hier hinten, da sieht 41:38.030 --> 41:40.070 das ganz gut aus, aber hier wird irgendwie, jetzt kommt auf einmal 41:40.070 --> 41:42.790 eine Klammer zu, die gar nicht aufgemacht wurde, also schon da ist es 41:42.790 --> 41:46.710 kaputt und dann schon, wenn am Ende eine Klammer auf ist, also hier 41:46.710 --> 41:49.630 stimmt die Anzahl der Klammern, hier stimmt die Anzahl der Klammer auf 41:49.630 --> 41:53.810 und Klammer zu, aber irgendwie passen die nicht, die geht hier zu 41:53.810 --> 41:55.490 schnell zu und zu spät auf sozusagen. 41:57.250 --> 42:02.670 Okay, also Sie wissen, was gemeint ist, formal könnte man sagen, eine 42:02.670 --> 42:08.310 Klammerung heißt korrekt, wenn es erstmal gleich viele öffnende wie 42:08.310 --> 42:12.030 schließende Klammern gibt und wenn wir das Wort von links nach rechts 42:12.030 --> 42:17.150 lesen, dann gibt es zu keinem Zeitpunkt mehr schließende als öffnende 42:17.150 --> 42:17.590 Klammern. 42:18.690 --> 42:24.510 Es muss mindestens so viele öffnende Klammern auf dem Präfix geben wie 42:24.510 --> 42:25.210 schließende Klammern. 42:25.770 --> 42:28.510 Das ist, da müssen Sie sich mal kurz überlegen, das ist genau das, was 42:28.510 --> 42:28.970 man braucht. 42:29.350 --> 42:31.910 Am Ende muss es stimmen von der Anzahl der öffnenden und schließenden 42:31.910 --> 42:36.270 und zu jedem Präfix muss es mindestens so viele öffnende wie 42:36.270 --> 42:36.870 schließende geben. 42:37.270 --> 42:39.530 Es kann nicht, wenn es irgendwann mal mehr schließende als öffnende 42:39.530 --> 42:41.410 gibt, ist es klar, dass es irgendwie nicht klappt. 42:45.300 --> 42:48.660 Und jetzt ist die Frage, okay, was ist das für eine Sprache? 42:48.880 --> 42:51.900 Wie würde ein Automat aussehen, der so eine Sprache erkennt? 42:52.620 --> 43:01.440 Naja, und irgendwie müssten wir jetzt in der Lage sein, dieses 43:01.440 --> 43:05.780 mindestens so viele öffnende wie schließende irgendwie erkennen. 43:07.300 --> 43:11.400 Er müsste irgendwie wissen, dass er schon 17 Klammern aufgemacht hat, 43:11.480 --> 43:12.900 aber erst 13 geschlossen hat. 43:14.560 --> 43:21.300 Also er muss vorbereitet sein auf Situationen, wo die Anzahl der 43:22.000 --> 43:26.400 überschüssigen geöffneten Klammern, die noch zu schließen sind, wo er 43:26.400 --> 43:28.520 diese Anzahl, die muss er sich irgendwie merken können. 43:29.000 --> 43:33.040 Er muss wissen, ob er jetzt gerade bisher irgendwie, ob er noch zwei 43:33.040 --> 43:35.940 Klammern zu schließen hat oder ob er keine Klammern mehr zu schließen 43:35.940 --> 43:38.580 hat oder 137 Klammern noch zu schließen hat. 43:39.520 --> 43:42.140 Und das ist jetzt ein Problem für endliche Automaten. 43:43.420 --> 43:47.420 Der Automat kann sich Sachen nicht so richtig merken. 43:47.420 --> 43:50.340 Das Einzige, was er machen kann, er kann sich merken, indem er in 43:50.340 --> 43:55.760 einen bestimmten Zustand geht, der sozusagen repräsentiert, was er 43:55.760 --> 43:57.500 schon gesehen hat, dieser Zustand. 43:58.600 --> 44:03.420 Und er muss jetzt aber für unendlich viele Möglichkeiten gewappnet 44:03.420 --> 44:03.720 sein. 44:05.440 --> 44:10.760 Und das ist so ein bisschen, wo die Endlichkeit des Automaten das 44:10.760 --> 44:11.360 Problem ist. 44:11.800 --> 44:16.100 Er hat einfach nicht genügend Speicher, er kann nicht genügend Tile 44:16.100 --> 44:19.220 Strings unterscheiden am Anfang. 44:19.880 --> 44:25.860 Das ist so grob die Idee, warum es wahrscheinlich nicht gehen sollte, 44:25.980 --> 44:29.080 einen endlichen Automaten für diese Sprache zu konstruieren. 44:30.000 --> 44:31.640 Das ist kein formaler Beweis. 44:32.780 --> 44:35.240 Aber das ist so ein bisschen die Idee, man sagt auch manchmal, 44:35.320 --> 44:37.060 endliche Automaten können nicht zählen. 44:37.540 --> 44:43.320 Also oft, wenn irgendwie zählen involviert ist, haben endliche 44:43.320 --> 44:44.180 Automaten ein Problem. 44:44.520 --> 44:48.880 Die können nicht zählen und irgendwie vergleichen, wie viele Nullen 44:48.880 --> 44:51.720 und Einsen in dem Wort sind und irgendwie sowas. 44:55.080 --> 44:57.860 Zumindest können sie nur endlich weit zählen, weil sie endlich sind. 44:59.400 --> 45:05.140 So, das heißt, es wird wahrscheinlich keinen Automaten geben, der 45:05.140 --> 45:06.180 diese Sprache erkennt. 45:06.320 --> 45:08.960 Das heißt, was wir davor schon gezeigt haben, diese Sprache wird 45:08.960 --> 45:10.340 wahrscheinlich nicht regulär sein. 45:10.600 --> 45:11.320 Das ist das gleiche. 45:12.440 --> 45:15.440 Endliche Automaten Sprache und reguläre Sprache ist das gleiche. 45:15.980 --> 45:17.220 Aber wie zeigt man jetzt sowas? 45:19.820 --> 45:23.220 Dafür gibt es ein Tool, was ich Ihnen heute noch vorstellen werde. 45:23.720 --> 45:28.300 Das ist ein bisschen schwierig zu verdauen, aber wir versuchen das 45:28.300 --> 45:29.880 langsam und sorgfältig zu machen. 45:30.120 --> 45:31.820 Dieses Tool heißt Pumping Lemma. 45:33.520 --> 45:37.600 Ich lese Ihnen einmal die Formulierung des Pumping Lemmas vor und 45:37.600 --> 45:40.980 danach reden wir darüber, wie man das anwendet und wie man es beweist. 45:42.600 --> 45:49.280 Wenn L eine reguläre Sprache ist, dann existiert eine Zahl n aus den 45:49.280 --> 45:54.620 natürlichen Zahlen, sodass für jedes Wort w in der Sprache, dessen 45:54.620 --> 46:00.940 Länge größer als n ist, eine Darstellung oder Zerlegung, sagen wir 46:00.940 --> 46:02.220 auch, gefunden werden kann. 46:02.360 --> 46:09.620 W ist ein Präfix u, ein Teilwort v und ein Suffix x mit der 46:09.620 --> 46:13.800 Eigenschaft, dass alles außer den Suffix höchstens n lang ist. 46:14.340 --> 46:17.800 Das Wort ist eventuell sehr lang, sehr, sehr, sehr lang, es ist 46:17.800 --> 46:18.680 einfach nur größer als n. 46:19.620 --> 46:23.260 Ich darf vorne höchstens in den ersten beiden Teilen höchstens n 46:23.260 --> 46:24.000 Zeichen haben. 46:24.900 --> 46:28.200 Dieser mittlere Teil darf nicht leer sein, darf nicht alles in dem u 46:28.200 --> 46:37.020 drin stecken, sodass, also diese Zerlegung existiert, sobald das Wort 46:37.020 --> 46:41.760 lang genug ist, existiert diese Zerlegung, sodass ich diesen mittleren 46:41.760 --> 46:45.060 Teil, dieses v, aufpumpen kann. 46:46.280 --> 46:51.240 Das heißt, ich kann mir Wörter angucken, wo ich diesen mittleren Teil 46:51.240 --> 46:52.360 direkt wiederhole. 46:54.080 --> 46:58.540 Anstatt u, v, x, was ja das Originalwort w war, mache ich u, v, v, x. 46:59.620 --> 47:02.540 Oder ich pumpe es noch mehr auf, ich mache u, v, v, v, x. 47:02.860 --> 47:05.280 Oder u, v, v, v, v, v, v, x. 47:05.740 --> 47:09.000 Für jedes i, das ist die Wiederholung, wie oft ich dieses v hier 47:09.000 --> 47:14.820 benutze, für jedes Pumpen bleibt das Wort in der Sprache. 47:16.780 --> 47:16.900 Okay. 47:18.640 --> 47:23.320 Kleine Sache, das i ist aus n null, also ich kann, wenn ich i gleich 47:23.320 --> 47:26.840 null setze, dann ist das v auch null, dann ist das leere Wort. 47:27.240 --> 47:28.640 Das heißt, ich kann das v auch wegnehmen. 47:29.020 --> 47:30.820 Dann ist es einfach u, x. 47:31.800 --> 47:32.980 Auch das bleibt in der Sprache. 47:33.380 --> 47:34.540 Das ist ganz hilfreich manchmal. 47:36.760 --> 47:36.860 Okay. 47:38.980 --> 47:42.660 Das ist jetzt, mathematisch würde ich das so hinschreiben. 47:44.700 --> 47:47.000 Ich weiß nicht, was Sie besser finden. 47:47.240 --> 47:50.760 Ich bin tatsächlich Mathematiker und ich finde diese Schreibweise 47:50.760 --> 47:53.400 besser, aber ich verstehe auch, dass man das einmal gelernt haben 47:53.400 --> 47:54.860 muss, diese Sprache so zu lesen. 47:55.640 --> 48:00.980 Okay, also das ist eine ganz häufige Struktur von Aussagen. 48:01.300 --> 48:03.560 Und ich glaube, es ist hilfreich, wenn wir uns da einmal 48:04.300 --> 48:08.660 durchwursteln, wenn man das einmal verstanden hat, dann versteht man 48:08.660 --> 48:10.480 auch besser, wie man sowas anwendet. 48:10.940 --> 48:16.840 Okay, also die Struktur ist oft so, wenn Sie einen Satz haben, dann 48:16.840 --> 48:21.060 entweder der sagt etwas für alle oder der sagt etwas, es existiert. 48:21.060 --> 48:31.420 Okay, also zum Beispiel, und dann gibt es immer so eine alternierende 48:31.420 --> 48:32.020 Sequenz. 48:32.900 --> 48:34.040 Üblicherweise ist die ganz kurz. 48:34.260 --> 48:38.460 Also entweder zum Beispiel, wir haben heute gezeigt, für alle NEAs 48:39.060 --> 48:44.220 existiert ein NEA, sodass gilt, der ist äquivalent und hat keine 48:44.220 --> 48:45.060 Epsilon -Übergänge. 48:46.680 --> 48:50.820 Okay, also üblicherweise für alle existiert nur, manchmal ist es nur 48:50.820 --> 48:54.400 so existiert, manchmal ist es nur für alle und manchmal ist es halt 48:54.400 --> 48:56.020 leider auch ein bisschen länger, so wie hier. 48:58.020 --> 49:01.520 Für alle existiert, sodass für alle existiert, sodass für alle gilt. 49:02.840 --> 49:04.300 Okay, gut. 49:05.760 --> 49:09.120 In Formeln, das sind diese Quantoren hier, dieses umgedrehte A ist der 49:09.120 --> 49:12.440 All -Quantor und dieses umgedrehte E ist der Existenz-Quantor. 49:13.580 --> 49:14.620 Also, was sagt das aus? 49:15.800 --> 49:25.720 Für alle Sprachen L, die irregulär sind, existiert eine Zahl n, sodass 49:25.720 --> 49:30.500 für alle Wörter w, die in der Sprache sind und deren Länge größer als 49:30.500 --> 49:38.460 n ist, existiert eine Zerlegung uvx, w ist gleich uvx mit uv ist 49:38.460 --> 49:42.560 kleiner gleich n zusammen und v ist nicht das leere Wort, sodass für 49:42.560 --> 49:48.580 alle natürlichen Zahlen i, eingeschlossen der 0, gilt und jetzt kommt 49:48.580 --> 49:53.040 die finale Aussage, nämlich u aufgepumpt, das v ist i-fach aufgepumpt, 49:53.180 --> 49:55.140 x ist in der Sprache. 49:56.620 --> 49:56.760 Okay. 49:58.140 --> 50:02.840 Ganz schönes Monster, aber ja, so ist es. 50:03.180 --> 50:03.360 Okay. 50:05.540 --> 50:06.380 Was machen wir? 50:06.780 --> 50:08.260 Lassen Sie uns das mal beweisen. 50:09.460 --> 50:15.540 Also, wenn man sowas beweisen muss, dann müssen wir, immer wenn das 50:15.540 --> 50:19.540 für alle steht, dann können Sie sich vorstellen, es ist der böse 50:19.540 --> 50:25.120 Gegenspieler, der Ihnen sagt, worüber, was das jetzt genau ist. 50:25.600 --> 50:27.580 Es gibt ein paar Regeln, an die er sich halten muss. 50:27.960 --> 50:31.380 Zum Beispiel, der böse Gegenspieler gibt uns jetzt eine Sprache, die 50:31.380 --> 50:33.000 Regel ist, die muss aber regulär sein. 50:34.460 --> 50:37.960 Und immer wenn existiert steht, dann sind wir am Zuge und wir können 50:37.960 --> 50:39.180 eine clevere Wahl treffen. 50:41.060 --> 50:44.620 Und dann der Gegenspieler, der sieht unsere clevere Wahl und jetzt 50:44.620 --> 50:48.600 kann der böse Gegenspieler uns aber wieder was zuschieben, nämlich das 50:48.600 --> 50:52.820 Wort W, muss sich aber an die Regeln halten, die eventuell von unserer 50:52.820 --> 50:54.980 Wahl abhängen. 50:55.140 --> 50:58.940 Und dann egal, wie der böse Gegenspieler das Wort gewählt hat, können 50:58.940 --> 51:03.540 wir jetzt wieder clever wählen das nächste, nämlich wie wir dieses 51:03.540 --> 51:06.800 Wort, was der Gegenspieler uns gegeben hat, zerlegen. 51:06.800 --> 51:11.500 Dann sieht der böse Gegenspieler die Zerlegung und kann jetzt wieder 51:11.500 --> 51:14.820 basierend auf dieser Zerlegung uns das I geben. 51:16.300 --> 51:20.260 Und dann müssen wir argumentieren, dass er es aber trotzdem nicht 51:20.260 --> 51:22.800 geschafft hat, das Wort aus der Sprache rauszubringen. 51:24.080 --> 51:24.120 Okay? 51:24.540 --> 51:28.400 Das ist so ein bisschen, wie ich das sehe. 51:28.820 --> 51:29.800 Also, fangen wir an. 51:31.920 --> 51:33.460 Sei L eine reguläre Sprache. 51:33.520 --> 51:37.140 Das ist so dieser Standard-Jargon, das heißt einfach, L wurde uns 51:37.140 --> 51:39.840 gegeben vom bösen Gegenspieler und wir wissen nichts, außer, dass er 51:39.840 --> 51:40.820 sich an die Regeln gehalten hat. 51:40.880 --> 51:41.520 Die ist regulär. 51:44.460 --> 51:47.700 Jetzt wollen wir, wir wollen dann das N finden. 51:48.340 --> 51:49.560 Dann existiert eine Zahl N. 51:50.040 --> 51:51.360 Okay, wie finden wir das N? 51:51.520 --> 51:53.300 Naja, wir wissen, die Sprache ist regulär. 51:53.420 --> 51:56.340 Das heißt, es gibt einen endlichen Automaten, der L akzeptiert. 51:57.700 --> 51:59.260 Das haben wir gezeigt, das ist der Satz von Clean. 52:01.120 --> 52:05.860 Und dieser Automat hat gewisse Zustände und wir wählen uns das N als 52:05.860 --> 52:07.940 die Menge dieser Zustände von diesem Automaten. 52:08.120 --> 52:12.120 Die Kardinalität, also die Anzahl dieser Zustände von diesem 52:12.120 --> 52:12.620 Automaten. 52:13.600 --> 52:15.760 Okay, also dieses N hängt von dem L ab. 52:16.640 --> 52:19.060 Für ein anderes L kriegen wir einen anderen Automaten, kriegen wir ein 52:19.060 --> 52:19.500 anderes N. 52:20.080 --> 52:21.280 Okay, das ist unsere Wahl von N. 52:22.000 --> 52:24.780 Jetzt kommt wieder der böse Gegenspieler und wählt sich ein Wort aus 52:24.780 --> 52:27.860 der Sprache beliebig, aber er muss sich an die Regel halten, dass das 52:27.860 --> 52:32.900 Wort mindestens oder länger als N ist, also mehr als N Symbole hat. 52:33.740 --> 52:36.860 Also zum Beispiel, wir wissen wieder nichts, außer dass es aus der 52:36.860 --> 52:37.900 Sprache ist und lang genug. 52:38.120 --> 52:41.420 Also es besteht irgendwie aus A1 bis AN und dann kommt eventuell noch 52:41.420 --> 52:43.660 was hinten dran bis AM. 52:48.300 --> 52:49.200 Wo sind wir? 52:49.420 --> 52:54.540 Genau, sodass jedes Wort eine Darstellung existiert. 52:54.640 --> 52:56.340 Jetzt sind wir wieder dran, die Darstellung zu finden. 52:57.740 --> 52:57.940 Okay. 52:59.040 --> 53:00.380 Und zwar, wie machen wir das? 53:00.620 --> 53:04.600 Wir sind jetzt hier, der Gegenspieler hat uns das Wort gegeben und 53:04.600 --> 53:07.540 jetzt gucken wir uns an, wie dieses Wort von diesem Automaten 53:08.380 --> 53:09.020 abgearbeitet wird. 53:11.540 --> 53:14.180 Der Automat nimmt das Wort, liest Zeichen für Zeichen. 53:14.300 --> 53:17.060 Das ist ein deterministischer endlicher Automat, das heißt keine 53:17.060 --> 53:20.540 Wahlmöglichkeiten oder irgendwas und das korrespondiert jetzt zu einer 53:20.540 --> 53:23.600 Folge von Zuständen, wie das da durch den Automaten geht. 53:24.880 --> 53:27.480 Für jedes Zeichen macht der einen so einen Übergang, eventuell bleibt 53:27.480 --> 53:29.080 er bei einem Zustand oder was auch immer. 53:30.600 --> 53:37.560 Und jetzt, weil wir so clever waren und unser AN so gewählt haben, 53:37.620 --> 53:40.900 dass es die Anzahl der Zustände ist und unser Gegenspieler musste 53:40.900 --> 53:44.960 jetzt ein Wort wählen, was länger ist als die Anzahl der Zustände, 53:45.400 --> 53:50.840 wissen wir, dass der Automat in seinem Abarbeiten mindestens einmal an 53:50.840 --> 53:52.820 dem gleichen Zustand doppelt vorbeikommt. 53:55.100 --> 53:58.920 Einfach weil er mehr Schritte machen muss, als Zustände da sind. 53:59.860 --> 54:04.640 Das heißt irgendwie, keine Ahnung, fängt er von S an und dann läuft er 54:04.640 --> 54:06.940 diese Zustände lang von Q0 bis Qm. 54:07.360 --> 54:09.860 Am Ende ist es ein Endzustand, das wissen wir auch, weil das Wort in 54:09.860 --> 54:14.100 der Sprache ist und irgendwie muss es mal so einen Kreis geben. 54:14.200 --> 54:18.340 Er muss mal doppelt vorbeikommen an einem Zustand. 54:20.020 --> 54:24.280 Also sagen wir, das ist die erste Situation, wo das passiert. 54:24.480 --> 54:28.680 Es kann sein, dass wir laufen und immer neuer Zustand, neuer Zustand, 54:28.800 --> 54:31.140 neuer Zustand, neuer Zustand, neuer Zustand und irgendwann gibt es 54:31.140 --> 54:33.140 diesen Übergang, dass wir sagen, oh, den haben wir schon mal gesehen. 54:34.160 --> 54:39.340 Und dann gucken wir uns diese Schleife hier an, wo Qi gleich Qj ist, 54:39.380 --> 54:40.620 obwohl I ungleich J ist. 54:41.740 --> 54:44.120 Das muss existieren, weil das Wort so lang ist. 54:47.580 --> 54:53.640 Und jetzt gucken wir uns diesen Zykel an und sagen uns, okay, beim 54:53.640 --> 55:00.020 Abarbeiten dieses Zykels benutzt der Automat ein bestimmtes Teilwort. 55:00.920 --> 55:01.480 V. 55:02.420 --> 55:07.440 Das soll unser V sein, das diese Zerlegung hier bestimmt. 55:08.520 --> 55:12.980 Am Anfang hat er eventuell irgendeinen Präfix gemacht, der darf auch 55:12.980 --> 55:15.840 meinetwegen leer sein, wissen wir nicht, vielleicht ist ja S dieser 55:15.840 --> 55:19.680 erste wiederholende Zustand und das, was er hier gelesen hat, was ich 55:19.680 --> 55:23.540 sozusagen entlang dieser Pfeile ablese an Wort, das soll jetzt mein 55:23.540 --> 55:28.780 Teilwort V sein und am Ende geht er von dem, vielleicht wiederholt er 55:28.780 --> 55:31.320 dann nochmal ein paar Zustände, geht hier ganz wild durch und das 55:31.320 --> 55:32.500 alles, was danach kommt, ist X. 55:35.060 --> 55:37.340 Das ist jetzt meine Zerlegung, die ich wähle. 55:38.920 --> 55:40.300 Und warum ist die gut? 55:40.480 --> 55:44.460 Naja, weil es mir sagt, vielleicht machen wir zuerst mal der Fall I 55:44.460 --> 55:45.040 gleich 0. 55:45.880 --> 55:50.340 Wenn ich dieses V einmal gelesen habe, dann bin ich automatenmäßig im 55:50.340 --> 55:53.320 exakt den gleichen Zustand und der hat ja irgendwie keinen Speicher, 55:53.440 --> 55:56.020 der kann nicht unterscheiden, ob ich jetzt zum ersten Mal oder zum 55:56.020 --> 55:57.360 zweiten Mal in dem Zustand bin. 55:58.040 --> 56:00.520 Alles, was er weiß, er ist in dem Zustand und er hat noch was zu 56:00.520 --> 56:01.600 lesen. 56:01.720 --> 56:05.100 Dann kann ich ihm sagen, okay, dann hättest du den Weg auch nicht 56:05.100 --> 56:08.800 machen müssen und wär's genauso hier gelandet, wenn ich V 0 da gemacht 56:08.800 --> 56:08.980 hätte. 56:09.040 --> 56:15.240 Einfach nur U ohne diesen V-Zügel und jetzt X abarbeiten. 56:16.420 --> 56:19.600 Und das hätte den gleichen Effekt, wie wenn er den V-Zügel macht. 56:22.500 --> 56:22.560 Ja. 56:23.620 --> 56:26.360 Und genauso kann ich diesen Zügel jetzt natürlich auch mehrmals 56:26.360 --> 56:29.760 durchlaufen lassen, indem ich V hoch I nehme, egal was für ein I ich 56:29.760 --> 56:30.120 wähle. 56:30.800 --> 56:33.380 Wenn ein böser Gegenspieler sagt, jetzt I gleich 17, dann sage ich, 56:33.420 --> 56:35.560 alles klar, gut, dann gehen wir halt ganz normal lang. 56:35.640 --> 56:38.720 Ich weiß, was der Automat tut, der geht mit U hier hin, dann geht er 56:38.720 --> 56:43.060 17 Mal diesen Zügel rum und dann macht er X, was auch immer das X ist. 56:44.360 --> 56:48.740 Und es hat den gleichen Effekt, wie ganz am Anfang, U V X und dadurch, 56:48.880 --> 56:51.660 dass es am Anfang in der Sprache war, also in dem Endzustand geendet 56:51.660 --> 56:55.300 ist, geht auch U V hoch I X in den Endzustand. 57:00.900 --> 57:05.080 Gut, jetzt müssen wir noch einmal ganz kurz überprüfen, dass wir uns 57:05.080 --> 57:08.260 an die Spielregeln gehalten haben, immer wenn da existiert steht, dann 57:08.260 --> 57:09.980 wollen wir irgendwelche Eigenschaften nachweisen. 57:10.480 --> 57:12.960 Wir wollten diese Zerlegung finden und die sollte hier diese beiden 57:12.960 --> 57:13.880 Eigenschaften noch haben. 57:14.120 --> 57:14.800 Das war wichtig. 57:16.740 --> 57:21.020 Dieser Präfix plus dieses Teilwort sollen zusammen nicht länger als N 57:21.020 --> 57:21.320 sein. 57:21.480 --> 57:23.160 Jetzt erinnern wir uns, okay, was war das? 57:23.400 --> 57:27.620 Hier ist im Prinzip das U und hier ist das V und da N die Anzahl 57:27.620 --> 57:32.460 unserer Zustände ist, wird es 10 hauen, weil das ungefähr oder 57:32.460 --> 57:34.520 höchstens unsere Anzahl von Zuständen ist. 57:35.020 --> 57:38.180 Also wir haben wirklich vorne, gehen Sie davon aus, dass W sehr, sehr, 57:38.180 --> 57:41.480 sehr lang ist und wir haben vorne wirklich nur so einen kleinen Teil, 57:41.600 --> 57:43.160 als die erste Wiederholung kam. 57:43.960 --> 57:46.800 Davor war alles verschiedene Zustände, also höchstens N. 57:48.440 --> 57:52.600 Und das U darf leer sein, aber das V darf nicht leer sein und das 57:52.600 --> 57:56.560 heißt einfach nur, dass dieser Zykel hier mindestens eine Kante hat, 57:56.680 --> 57:57.720 mindestens einen Übergang. 57:58.880 --> 58:01.580 Vielleicht ist es einfach nur so ein Loop, gleich am S dran oder 58:01.580 --> 58:02.800 irgendwie sowas, kann ja sein. 58:02.800 --> 58:05.940 Aber es hat mindestens ein Zeichen, ist in dem V drin. 58:07.100 --> 58:08.660 Gut, und das haben wir auch. 58:11.340 --> 58:13.880 So, das ist der Beweis vom Pumping Lemma. 58:14.940 --> 58:15.720 Unglückliches I. 58:16.540 --> 58:20.360 Egal wie oft ich das V aufpumpe, durch mehrfach durchgehen durch das 58:20.360 --> 58:22.720 Zykel, bleibe ich in der Sprache. 58:24.680 --> 58:29.240 Jetzt ganz wichtig, wie verwenden Sie das Pumping Lemma? 58:30.000 --> 58:30.680 Ich habe gesagt, 58:39.940 --> 58:42.000 dass es eine Regularität von Sprachen gibt. 58:42.000 --> 58:44.440 Das ist das, was das Pumping Lemma besagt. 58:44.560 --> 58:49.820 Es sagt, wenn die Sprache regulär ist, dann gibt es diese Zahl N, so 58:49.820 --> 58:50.640 dass, egal wie, 58:56.850 --> 59:00.970 die Aussage des Pumping Lemmas widerlegen. 59:01.110 --> 59:03.930 Ich sage gleich auf der nächsten Folie, was die Aussage des Pumping 59:03.930 --> 59:04.450 Lemmas ist. 59:04.950 --> 59:07.010 Wenn wir das widerlegen, dann können wir damit zeigen, dass die 59:07.010 --> 59:09.050 Sprache auch nicht regulär gewesen sein kann. 59:11.190 --> 59:14.710 Weil jede reguläre Sprache hat ja diese Eigenschaft und wenn wir jetzt 59:14.710 --> 59:16.810 zeigen, okay, diese Eigenschaft gilt gar nicht für unsere Sprache, 59:16.870 --> 59:18.310 dann kann sie ja nicht regulär gewesen sein. 59:19.670 --> 59:21.550 Das ist so, wie wir das benutzen wollen. 59:23.470 --> 59:28.390 Andersrum, das Pumping Lemma ist im Allgemeinen keine hinreichende 59:28.390 --> 59:31.450 Bedingung für die Regularität von Sprachen. 59:31.610 --> 59:36.750 Also, wenn wir die Aussage des Pumping Lemmas nachweisen, heißt das 59:36.750 --> 59:37.410 noch gar nichts. 59:39.510 --> 59:41.590 Dann ist die Sprache eventuell regulär oder auch nicht. 59:41.690 --> 59:44.310 Das ist so ein bisschen wie, das Pumping Lemma, müssen Sie sich 59:44.310 --> 59:47.090 vorstellen, wenn es ein Feuerwehrauto ist, dann ist es rot. 59:48.190 --> 59:52.730 Und wir benutzen dieses Lemma, in dem wir zeigen, um zu entscheiden, 59:52.850 --> 59:54.110 ob etwas ein Feuerwehrauto ist. 59:54.810 --> 59:57.790 Und wir gucken uns die Farbe an und wenn es nicht rot ist, dann wissen 59:57.790 --> 59:59.170 wir, okay, dann ist es kein Feuerwehrauto. 01:00:00.810 --> 01:00:03.530 Durch Widerlegen der Eigenschaft, die vom Pumping Lemma garantiert 01:00:03.530 --> 01:00:07.230 wird, wenn es nicht rot ist, wissen wir, es ist kein Feuerwehrauto. 01:00:07.770 --> 01:00:11.650 Aber wenn wir zeigen, durch Nachweisen der Eigenschaft des Pumping 01:00:11.650 --> 01:00:14.290 Lemmas, wenn wir zeigen, dass etwas rot ist, wissen wir gar nichts. 01:00:14.390 --> 01:00:16.230 Es könnte ein Feuerwehrauto sein, muss aber nicht. 01:00:17.410 --> 01:00:18.410 Okay, das ist wichtig. 01:00:20.570 --> 01:00:25.350 Also, merke, jede reguläre Sprache erfüllt die Aussage des Pumping 01:00:25.350 --> 01:00:25.710 Lemmas. 01:00:25.890 --> 01:00:30.050 Eine Sprache, die die Aussage des Pumping Lemmas erfüllt, die dann 01:00:30.050 --> 01:00:32.650 nicht erfüllt, kann also auch nicht regulär sein. 01:00:32.730 --> 01:00:34.190 Und so werden wir das gebrauchen. 01:00:34.250 --> 01:00:37.550 Das ist ein Werkzeug, um zu zeigen, dass etwas nicht regulär ist. 01:00:39.790 --> 01:00:43.470 Gut, jetzt was meine ich genau mit der Aussage des Pumping Lemmas? 01:00:43.810 --> 01:00:46.890 Das ist quasi nochmal das gleiche. 01:00:47.830 --> 01:00:50.690 Das Pumping Lemma hat da vorne noch für alle reguläre Sprachen. 01:00:50.850 --> 01:00:52.470 Das ist jetzt weg, ja. 01:00:52.790 --> 01:00:56.510 Die Aussage des Pumping Lemmas ist dann nur dieses ab, es existiert. 01:00:56.910 --> 01:01:02.450 Also die Aussage des Pumping Lemmas für eine gegebene Sprache L ist 01:01:03.130 --> 01:01:08.710 für diese gegebene Sprache L existiert ein N, sodass für alle Wörter 01:01:08.710 --> 01:01:13.430 aus der Sprache, die lang genug sind, existiert eine Zerlegung mit 01:01:13.430 --> 01:01:16.910 diesen Eigenschaften, sodass für alle I aus den natürlichen Zahlen, 01:01:17.030 --> 01:01:23.490 inklusive 0, gilt U V I mal aufgepumpt X ist in der Sprache. 01:01:24.710 --> 01:01:26.710 Das ist die Aussage des Pumping Lemmas. 01:01:26.790 --> 01:01:29.950 Das meine ich, das ist ganz schön komplex, aber sehen Sie das als eine 01:01:29.950 --> 01:01:31.330 Eigenschaft der Sprache. 01:01:31.790 --> 01:01:35.810 Manche Sprachen haben diese Eigenschaft und manche nicht. 01:01:37.530 --> 01:01:40.510 Und wenn wir sie jetzt widerlegen wollen, dann müssen wir jetzt 01:01:40.510 --> 01:01:47.670 Aussagen logisch negieren und das geht indem wir diese für alle und 01:01:47.670 --> 01:01:52.390 Existenz Quantoren quasi einfach nur umdrehen und am Ende die Aussage, 01:01:52.450 --> 01:01:54.050 die hinter gilt steht, negieren. 01:01:55.050 --> 01:01:57.450 Das ist so elementare Aussagen logisch. 01:01:57.850 --> 01:02:03.150 Also wenn die Aussage des Pumping Lemmas nicht gilt, dann ist es 01:02:03.150 --> 01:02:05.910 nämlich so, dass dieses N oben nicht existiert. 01:02:06.030 --> 01:02:11.890 Das heißt, für alle N, egal was wir da versuchen, ist es nicht so, 01:02:11.990 --> 01:02:14.730 dass wir dann auf alle Wörter gefasst sind zu diesem N. 01:02:14.890 --> 01:02:19.050 Also egal welches N wir da oben wählen, existiert ein blödes Wort, was 01:02:19.050 --> 01:02:21.870 wir nicht geschafft haben, W, was die Eigenschaft hat. 01:02:22.690 --> 01:02:27.910 So dass jetzt wieder für alle Zerlegungen, das Wort ist blöd, weil es 01:02:27.910 --> 01:02:29.890 eben keine Zerlegung erlaubt. 01:02:30.030 --> 01:02:33.070 Also alle Zerlegungen, egal wie ich es versuche, es zu zerlegen mit 01:02:33.070 --> 01:02:39.950 diesen Regeln, ist die Zerlegung nicht gut in dem Sinne, dass alle I 01:02:39.950 --> 01:02:41.730 -Pumpen in der Sprache bleiben. 01:02:41.870 --> 01:02:46.510 Also mindestens ein I gibt es, sodass wenn ich das jetzt um I pumpe, 01:02:46.630 --> 01:02:47.990 es nicht in der Sprache liegt. 01:02:49.430 --> 01:02:49.990 Okay. 01:02:53.490 --> 01:02:56.650 So und das ist jetzt diese Kette von für alle existiert, für alle 01:02:56.650 --> 01:03:00.110 existiert, sodass gilt oder gerade nicht oder gilt nicht in der 01:03:00.110 --> 01:03:00.450 Sprache. 01:03:01.090 --> 01:03:04.110 Das ist die Kette, die wir eigentlich die meiste Zeit benutzen werden 01:03:04.110 --> 01:03:06.930 oder Sie, wenn Sie das Pumping Lemma verwenden. 01:03:07.490 --> 01:03:11.630 Sie verwenden das Pumping Lemma, indem Sie eine Gesprache von 01:03:11.630 --> 01:03:16.090 irgendjemandem bekommen und Sie weisen nach, dass die Aussage des 01:03:16.090 --> 01:03:18.550 Pumping Lemmas nicht gilt für die Sprache. 01:03:20.050 --> 01:03:23.270 Und dann können Sie daraus folgern, dass Ihre Sprache nicht regulär 01:03:23.270 --> 01:03:23.550 ist. 01:03:24.450 --> 01:03:24.470 Okay. 01:03:25.450 --> 01:03:28.610 Und wenn Sie die jetzt nachweisen, dass die Aussage des Pumping Lemmas 01:03:28.610 --> 01:03:33.790 nicht gilt, dann ist wieder für alle ist der böse Gegenspieler und 01:03:33.790 --> 01:03:36.010 existiert, da können Sie die clevere Wahl treffen. 01:03:38.190 --> 01:03:42.030 Sodass wieder für alle, egal was der böse Gegenspieler Ihre Wahl 01:03:42.030 --> 01:03:48.790 kennend Ihnen liefert, können Sie die clevere Wahl treffen von dem I, 01:03:49.150 --> 01:03:49.850 sodass es gilt. 01:03:50.610 --> 01:03:54.010 Wir machen das gleich an ein paar Beispielen. 01:03:54.850 --> 01:03:54.990 Gut. 01:03:56.110 --> 01:04:04.630 Also, die Beispiele sind so, dass ich werde zuerst eine Sprache L 01:04:04.630 --> 01:04:09.470 angeben und ich werde das, die Aussage des Pumping Lemmas überprüfen. 01:04:10.110 --> 01:04:12.990 Also eigentlich das, was ich gerade gesagt habe, wie Sie es nicht 01:04:12.990 --> 01:04:16.690 verwenden werden, aber einfach, um zu trainieren, wie man dieses, es 01:04:16.690 --> 01:04:19.810 existiert für alle, sodass es für alle existiert und so weiter. 01:04:20.930 --> 01:04:24.690 Also ich werde, Beispiel 1 ist, ich überprüfe die Aussage. 01:04:26.210 --> 01:04:29.090 Ich habe Ihnen gesagt, es sagt uns gar nichts über die Sprache. 01:04:29.230 --> 01:04:31.070 Nur weil es rot ist, muss es kein Feuerwehrauto sein. 01:04:31.370 --> 01:04:31.490 Okay. 01:04:31.630 --> 01:04:32.710 Trotzdem machen wir es einfach mal. 01:04:33.590 --> 01:04:36.570 Beispiel 2 ist dann tatsächlich so, wie Sie das Pumping Lemma immer 01:04:36.570 --> 01:04:40.290 anwenden werden, nämlich wir werden eine Sprache sehen und wir werden 01:04:41.630 --> 01:04:45.110 nachweisen, dass die Aussage des Pumping Lemmas nicht gilt. 01:04:45.290 --> 01:04:48.670 Also wir werden dieses, für alle existiert, für alle existiert, sodass 01:04:48.670 --> 01:04:50.010 gilt, nachweisen. 01:04:50.850 --> 01:04:55.830 Und das dritte ist wiederum eine Sprache, wo ich die Aussage hier oben 01:04:55.830 --> 01:04:56.950 nachweisen werde. 01:04:57.950 --> 01:05:00.730 Und der Unterschied ist, dass die erste Sprache, wo ich das da oben 01:05:00.730 --> 01:05:03.210 überprüfe, ist tatsächlich ein Feuerwehrauto. 01:05:04.530 --> 01:05:06.010 Ist eine reguläre Sprache. 01:05:06.410 --> 01:05:08.650 Und bei der zweiten Sprache, wo ich das machen werde, ist es 01:05:08.650 --> 01:05:11.470 tatsächlich kein Feuerwehrauto, obwohl ich beweise, dass es rot ist. 01:05:12.390 --> 01:05:15.650 Ich beweise, dass diese Aussage des Pumping Lemmas gilt, aber die 01:05:15.650 --> 01:05:16.690 Sprache ist gar nicht regulär. 01:05:19.770 --> 01:05:20.670 Beispiel 1. 01:05:20.790 --> 01:05:23.870 Nochmal oben das Pumping Lemma oder die Aussage des Pumping Lemmas. 01:05:24.550 --> 01:05:25.330 Hier ist die Sprache. 01:05:26.270 --> 01:05:27.670 Alphabet 0 1. 01:05:28.690 --> 01:05:35.550 Die Sprache ist alle Wörter W, sodass 1 0 nicht als Teilwort vorkommt. 01:05:36.270 --> 01:05:40.150 Die hatten wir in Vorlesung 1 oder 2 oder so schon mal. 01:05:40.930 --> 01:05:45.270 Wir hatten uns auch kurz überlegt, dass das eine reguläre Sprache ist, 01:05:45.410 --> 01:05:49.150 die diesem regulären Ausdruck entspricht, nämlich 0 Stern 1 Stern. 01:05:49.870 --> 01:05:52.530 Einfach eine Folge von Nullen, eventuell keine, gefolgt von einer 01:05:52.530 --> 01:05:53.910 Folge von Einsen, eventuell keine. 01:05:55.850 --> 01:05:59.250 Und jetzt will ich für diese Sprache das hier oben durchspielen. 01:05:59.450 --> 01:06:00.950 Es fängt an mit existiert. 01:06:01.110 --> 01:06:02.270 Das heißt, ich darf wählen. 01:06:03.710 --> 01:06:07.210 Und ich wähle N gleich 1. 01:06:08.350 --> 01:06:11.610 Einfach, weil ich weiß, dass es funktionieren wird mit N gleich 1 und 01:06:11.610 --> 01:06:13.650 weil N gleich 1 hinreichend simpel ist. 01:06:13.870 --> 01:06:15.990 Tatsächlich würde es auch mit anderen Ns funktionieren hier. 01:06:16.230 --> 01:06:17.290 Aber ich wähle N gleich 1. 01:06:17.530 --> 01:06:18.510 Ich muss ja nur 1 finden. 01:06:19.770 --> 01:06:23.130 Jetzt kommt der böse Gegenspieler, der sieht meine Wahl von N gleich 1 01:06:23.130 --> 01:06:24.710 und gibt mir ein Wort. 01:06:24.870 --> 01:06:28.430 Das liegt in der Sprache und das hat mehr als ein Zeichen. 01:06:31.270 --> 01:06:33.890 Ich weiß nicht genau, wie das Wort aussieht, außer nur, dass es in der 01:06:33.890 --> 01:06:34.470 Sprache ist. 01:06:35.630 --> 01:06:39.790 Jetzt kann ich mir das Wort angucken und muss basierend darauf, wie es 01:06:39.790 --> 01:06:41.770 aussieht, mir die Zerlegung wählen. 01:06:43.010 --> 01:06:46.130 Und tatsächlich brauche ich mir gar nicht das Wort an, ich wähle die 01:06:46.130 --> 01:06:47.790 Zerlegung egal, wie das Wort aussieht. 01:06:47.910 --> 01:06:51.190 Manchmal muss man, je nachdem, wie das Wort aussieht, die Zerlegung 01:06:51.190 --> 01:06:51.730 anders wählen. 01:06:52.690 --> 01:06:55.370 Aber wir sind ja hier in dem Fall, den Sie eh nicht benutzen. 01:06:55.370 --> 01:06:59.130 Die Zerlegung wird Ihnen immer gegeben werden vom bösen Gegenspieler, 01:06:59.250 --> 01:07:00.070 wenn Sie das Pumping nehmen. 01:07:00.190 --> 01:07:03.510 Aber hier will ich die Zerlegung wählen und ich wähle die Zerlegung 01:07:03.510 --> 01:07:09.950 so, ich nehme den Präfix gar nichts und das Teilwort ist eine 1. 01:07:11.770 --> 01:07:13.870 Das Teilwort hat Länge 1. 01:07:15.150 --> 01:07:17.830 Das ist einfach das erste Zeichen und x ist der Rest. 01:07:19.570 --> 01:07:22.310 Jetzt müssen wir kurz überprüfen, dass ich mich an die Regeln gehalten 01:07:22.310 --> 01:07:22.670 habe. 01:07:25.870 --> 01:07:28.430 Präfix und Teilwort zusammen ist höchstens 1 lang. 01:07:28.730 --> 01:07:29.930 Ja, das ist 0 und 1. 01:07:30.490 --> 01:07:32.450 Und das Teilwort v ist nicht leer. 01:07:32.590 --> 01:07:33.650 Ja, es hat ein Zeichen. 01:07:36.530 --> 01:07:40.170 Ich weiß, dass es so funktioniert, weil ich weiß, wenn Sie sich an den 01:07:40.170 --> 01:07:43.370 Beweis erinnern, wie der Endlich-Automat aussieht, der diese Sprache 01:07:43.370 --> 01:07:43.770 erkennt. 01:07:43.890 --> 01:07:46.370 Und ich weiß, dass der gleich vorne so eine Schleife hat. 01:07:47.050 --> 01:07:49.430 Und das ist die Schleife mit einer 0 dran. 01:07:50.250 --> 01:07:51.230 Das nutze ich jetzt aus. 01:07:51.230 --> 01:07:52.890 Dadurch weiß ich, dass ich Endlich 1 wähle. 01:07:55.470 --> 01:07:58.210 Jetzt kommt wieder der böse Gegenspieler und gibt mir ein beliebiges 01:07:58.210 --> 01:07:58.490 i. 01:07:58.650 --> 01:08:00.790 Ich weiß nichts darüber, das könnte 0 sein. 01:08:02.450 --> 01:08:08.690 Und jetzt muss ich zeigen, dass wenn ich dieses mittlere Ding mit i 01:08:08.690 --> 01:08:11.050 aufpumpe, dass es in meiner Sprache drin bleibt. 01:08:12.950 --> 01:08:14.170 Gehen wir die Fälle durch. 01:08:14.430 --> 01:08:17.930 Wenn der böse Gegenspieler i gleich 0 gewählt hat, dann hat er im 01:08:17.930 --> 01:08:19.770 Prinzip dieses V rausgestrichen. 01:08:21.130 --> 01:08:24.670 Und durch Rausstreichen kann jetzt nicht irgendwas Böses passiert 01:08:24.670 --> 01:08:24.870 sein. 01:08:24.950 --> 01:08:28.590 Wenn vorher 1,0 nicht drin war, ist nach Rausstreichen des ersten 01:08:28.590 --> 01:08:31.950 Zeichens 1,0 auch nicht drin. 01:08:34.610 --> 01:08:40.170 Und wenn er was Größeres gewählt hat, naja, dann habe ich das erste 01:08:40.170 --> 01:08:41.510 Zeichen aufgepumpt. 01:08:41.790 --> 01:08:43.490 Jetzt benutze ich, wie meine Sprache aussieht. 01:08:43.750 --> 01:08:47.690 Ich weiß ja, egal wie das Wort ist, was er mir gegeben hat, es hat 01:08:47.690 --> 01:08:48.290 diese Form. 01:08:48.410 --> 01:08:51.130 Das heißt entweder es hat vorne eine 0, dann hat er jetzt eine 01:08:51.130 --> 01:08:52.590 einzelne 0 aufgepumpt vorne. 01:08:53.370 --> 01:08:54.330 Und das ist immer noch gut. 01:08:54.790 --> 01:08:56.970 Oder das ganze Ding bestand nur aus Einsen. 01:08:57.650 --> 01:09:00.750 Dann hat er jetzt dieses erste Zeichen, was eine 1 war, aufgepumpt. 01:09:01.770 --> 01:09:05.110 Und egal wie es ist, egal wie das i aussieht, das bleibt in der 01:09:05.110 --> 01:09:05.490 Sprache. 01:09:05.830 --> 01:09:10.210 Das heißt, diese Sprache erfüllt die Aussage des Pumping Lemmas. 01:09:11.150 --> 01:09:13.510 Heißt jetzt erstmal per se nichts über die Sprache. 01:09:13.630 --> 01:09:14.830 Einfach nur, es ist rot. 01:09:17.590 --> 01:09:18.310 Zweites Beispiel. 01:09:18.430 --> 01:09:20.510 Das ist jetzt, wo wir die Aussage widerlegen wollen. 01:09:21.010 --> 01:09:22.310 Passen Sie hier besonders gut auf. 01:09:24.750 --> 01:09:25.970 Sprache ist wie folgt. 01:09:26.070 --> 01:09:31.530 Das Alphabet ist wieder 0,1 und die Wörter sind von der Form 0 hoch K, 01:09:31.630 --> 01:09:36.070 1 hoch K für eine natürliche Zahl K, eventuell 0. 01:09:36.530 --> 01:09:39.910 Also die Sprache sieht so aus, wenn K gleich 0 ist, dann ist das das 01:09:39.910 --> 01:09:40.470 leere Wort. 01:09:40.890 --> 01:09:43.050 Wenn K gleich 1 ist, ist es das Wort 0,1. 01:09:43.650 --> 01:09:48.850 Für K gleich 2 ist es 0,0,1,1 und dann ist es 0,0,0,1,1 und so weiter. 01:09:50.350 --> 01:09:57.070 Das ist also ähnlich wie davor, anfängliche Nullen und hinten geht es 01:09:57.070 --> 01:10:00.230 weiter mit Einsen, aber jetzt ist es so, dass die Anzahl der Nullen 01:10:00.230 --> 01:10:02.490 vorne ist genau die Anzahl der Einsen hinten. 01:10:03.250 --> 01:10:05.530 Und das ist dieses Zählen, was der Automat nicht kann. 01:10:05.650 --> 01:10:08.650 Die Sprache wird nicht regulär sein, weil man da quasi zählen muss. 01:10:09.810 --> 01:10:14.990 Gut, also wir wollen es widerlegen, das heißt wir wollen das hier 01:10:14.990 --> 01:10:15.270 machen. 01:10:16.030 --> 01:10:21.410 Es fängt an mit für alle, das heißt der böse Gegenspieler gibt mir das 01:10:21.410 --> 01:10:21.570 N. 01:10:22.010 --> 01:10:23.530 Ich habe keine Kontrolle über das N. 01:10:25.010 --> 01:10:25.890 Er gibt mir das N. 01:10:27.410 --> 01:10:28.290 Weiß ich nichts drüber. 01:10:29.130 --> 01:10:30.830 Jetzt kann ich aber das Wort wählen. 01:10:33.470 --> 01:10:37.090 Ich wähle mein Wort und ich muss mich an die Regeln halten, es muss in 01:10:37.090 --> 01:10:40.130 der Sprache sein und es muss mehr als N Zeichen haben. 01:10:41.810 --> 01:10:45.250 Und da wählt man sich natürlich möglichst irgendwas Einfaches, damit 01:10:45.250 --> 01:10:47.670 man danach das irgendwie ordentlich handhaben kann. 01:10:48.810 --> 01:10:52.190 Was ich mir hier wähle ist, okay, hier habe ich nicht so viele 01:10:52.190 --> 01:10:53.050 Auswahlmöglichkeiten. 01:10:53.570 --> 01:10:55.510 Ich wähle mir einfach 0 hoch N, 1 hoch N. 01:10:56.830 --> 01:11:01.830 Das ist definitiv lang genug, es ist länger als N und es liegt in der 01:11:01.830 --> 01:11:02.370 Sprache drin. 01:11:02.630 --> 01:11:03.090 Das sehen Sie. 01:11:03.610 --> 01:11:06.790 Jetzt kommt wieder der böse Gegenspieler und sagt, ich kann das aber 01:11:06.790 --> 01:11:07.310 zerlegen. 01:11:08.550 --> 01:11:15.970 Ja und sagt, hier ist die Zerlegung UVX UV habe ich zusammen höchstens 01:11:15.970 --> 01:11:18.250 N Zeichen gebraucht und V ist nicht leer. 01:11:20.230 --> 01:11:22.830 Okay und jetzt muss ich basierend auf der Zerlegung, ich weiß nicht 01:11:22.830 --> 01:11:26.650 genau wie die aussieht, basierend auf der Zerlegung muss ich das I ihm 01:11:26.650 --> 01:11:30.630 zeigen, so dass ich, wenn ich das mit diesem I pumpe, es nicht mehr in 01:11:30.630 --> 01:11:31.330 der Sprache liegt. 01:11:32.930 --> 01:11:41.010 Und hier ist es tatsächlich so, naja, I gleich 0 wird klappen, egal 01:11:41.010 --> 01:11:42.170 wie er das Wort zerlegt hat. 01:11:43.650 --> 01:11:47.950 Und zwar, was ich weiß ist, er musste sich ja daran halten, dass die 01:11:47.950 --> 01:11:52.290 Präfix plus V darf höchstens N Zeichen sein und ich habe mein Wort so 01:11:52.290 --> 01:11:54.370 gewählt, dass die ersten N Zeichen, das sind alles Nullen. 01:11:55.990 --> 01:12:00.330 Also er hat ein paar anfängliche von den Nullen hat er in U reingetan 01:12:00.330 --> 01:12:03.310 und dann hat er mindestens eine Null, vielleicht ein paar mehr in V 01:12:03.310 --> 01:12:03.910 reingetan. 01:12:04.270 --> 01:12:06.030 Das weiß ich so ungefähr, sieht seine Zerlegung aus. 01:12:06.130 --> 01:12:08.330 Und X ist dann, hat die ganzen Einsen drin. 01:12:09.390 --> 01:12:13.990 Und wenn ich jetzt I gleich 0 wähle, da V insbesondere irgend so ein 0 01:12:13.990 --> 01:12:20.390 hoch A ist, für A mindestens 1, V darf nicht leer sein, ist, wenn ich 01:12:20.390 --> 01:12:24.170 das rausstreiche, habe ich quasi aus dem Wort einfach A Nullen 01:12:24.170 --> 01:12:24.950 rausgestrichen. 01:12:28.560 --> 01:12:32.800 Dann sieht das Wort also so aus, dass es 0 hoch N minus A, 1 hoch N 01:12:32.800 --> 01:12:33.500 ist. 01:12:36.740 --> 01:12:39.380 Und das Wort liegt nicht in der Sprache, weil es nicht die gleiche 01:12:39.380 --> 01:12:40.600 Anzahl Nullen wie Einsen hat. 01:12:41.340 --> 01:12:47.500 Also habe ich damit gezeigt, dass die Aussage des Pumping Lemmas nicht 01:12:47.500 --> 01:12:48.280 erfüllt ist. 01:12:49.440 --> 01:12:52.260 Das Ding ist nicht rot, also kann es auch kein Feuerwehrauto sein. 01:12:52.380 --> 01:12:54.260 Also kann die Sprache nicht regulär sein. 01:12:54.380 --> 01:12:57.820 Diese Sprache ist eine relativ einfache Sprache, die wird nicht von 01:12:57.820 --> 01:12:59.160 einem endlichen Automaten erkannt. 01:12:59.600 --> 01:13:02.440 Es gibt keinen endlichen Automaten, Sie können keinen bauen, der diese 01:13:02.440 --> 01:13:03.080 Sprache erkennt. 01:13:05.660 --> 01:13:06.540 Letztes Beispiel. 01:13:07.720 --> 01:13:10.900 Jetzt versuche ich sie mal schon ein bisschen zu fordern. 01:13:11.020 --> 01:13:12.860 Das ist die Aussage des Pumping Lemmas. 01:13:14.620 --> 01:13:18.040 Also es existiert ein N, sodass für alle W aus der Sprache mit W 01:13:18.040 --> 01:13:22.800 größer, also größer von W größer als N, es existiert UVW gleich W, 01:13:23.020 --> 01:13:25.660 also UVX gleich W, eine Zerlegung von W in UV und X. 01:13:26.280 --> 01:13:30.000 Die ersten beiden Teile zusammen höchstens N, V ist nicht leer, sodass 01:13:30.000 --> 01:13:35.240 für alle I aus den natürlichen Zahlen, inklusive der 0 gilt, UV hoch 01:13:35.240 --> 01:13:36.580 IX ist in der Sprache. 01:13:36.660 --> 01:13:39.660 Das ist die Aussage des Pumping Lemmas in mathematischer Notation. 01:13:41.200 --> 01:13:42.740 Und jetzt will ich wieder die... 01:13:42.740 --> 01:13:46.360 für eine dritte Sprache will ich diese Aussage jetzt wieder 01:13:46.360 --> 01:13:47.100 nachweisen. 01:13:47.480 --> 01:13:51.880 Wiederum das ist nicht das, was Sie üblicherweise tun werden, weil nur 01:13:51.880 --> 01:13:55.300 weil ich diese Aussage nachweise, heißt es gar nichts über die 01:13:55.300 --> 01:13:56.480 Regularität der Sprache. 01:13:57.300 --> 01:13:58.660 Aber lassen Sie uns das tun. 01:13:59.240 --> 01:14:04.120 Folgende Sprache, Alphabet ist wieder 01, die Wörter in der Sprache 01:14:04.120 --> 01:14:10.180 sind von der Form zweierlei Art, entweder das Wort besteht nur aus 01:14:10.180 --> 01:14:20.320 Einsen, also 1 hoch K für K größer 0, okay, besteht nur aus Einsen, 01:14:20.320 --> 01:14:26.280 oder das Wort hat eine gewisse Teilmenge von Nullen am Anfang und dann 01:14:26.280 --> 01:14:32.000 eine Sequenz von Einsen und die Sequenz von Einsen ist irgendwie eine 01:14:32.000 --> 01:14:34.580 Quadratzahl, die Anzahl der Einsen, die da hinten kommt. 01:14:34.680 --> 01:14:38.880 Eine beliebige Folge von Nullen, 0 hoch J, mindestens eine und hinten 01:14:38.880 --> 01:14:42.260 ist eine Quadratzahl anzahlige Folge von Einsen. 01:14:43.280 --> 01:14:43.740 Warum nicht? 01:14:44.640 --> 01:14:47.020 Komische Sprache, aber die wollen wir machen. 01:14:47.840 --> 01:14:52.600 So, ich möchte dieses Ding hier verifizieren, ich sehe ein 01:14:53.160 --> 01:14:54.860 Existenzquantor, das heißt, ich darf wählen. 01:14:55.000 --> 01:14:58.180 Ich wähle in weiser Voraussicht N gleich 1. 01:14:59.080 --> 01:15:03.060 Dann kommt ein Allquantor, das heißt, mein böser Gegenspieler gibt mir 01:15:03.060 --> 01:15:06.500 ein beliebiges Wort W aus der Sprache, muss ich in die Regeln halten, 01:15:06.580 --> 01:15:10.180 dass es aus der Sprache kommt und lang genug ist. 01:15:10.880 --> 01:15:14.960 Dann sehe ich ein Existenzquantor, das heißt, ich wähle, hier in dem 01:15:14.960 --> 01:15:18.800 Fall ist es die Zerlegung und ich wähle wieder die Zerlegung, dass U 01:15:18.800 --> 01:15:24.760 ist leer und V ist einfach der Länge 1, das heißt, ich nehme wieder 01:15:24.760 --> 01:15:29.580 die Zerlegung in kein Präfix, das Mittelstück ist der erste Buchstabe 01:15:29.580 --> 01:15:32.380 des Wortes und X ist der Rest, egal was das Wort war. 01:15:34.580 --> 01:15:38.160 Wir überprüfen kurz, dass ich mich an die Regeln gehalten habe, dass V 01:15:38.160 --> 01:15:42.180 ist und gleich leer und UV zusammen ist höchstes N, mein N war 1, das 01:15:42.180 --> 01:15:42.620 funktioniert. 01:15:44.240 --> 01:15:47.920 Jetzt kommt wieder der böse Gegenspieler für diesen Allquantor, der 01:15:47.920 --> 01:15:51.020 mir gibt ein beliebiges I und ich habe keine Kontrolle darüber. 01:15:51.380 --> 01:15:52.860 Ich muss zu Notfälle unterscheiden. 01:15:54.840 --> 01:15:57.400 Jetzt mache ich, jetzt unterscheide ich die Fälle und zwar, ich habe 01:15:57.400 --> 01:16:01.580 keine Kontrolle über das W und keine Kontrolle über das I und muss 01:16:01.580 --> 01:16:05.060 jetzt alles abhandeln können, was passieren könnte. 01:16:05.240 --> 01:16:10.260 Später müssen Sie dann Fälle unterscheiden über die Zerlegung, wie Ihr 01:16:10.260 --> 01:16:13.560 böser Gegenspieler die Zerlegung Ihres gewählten Wortes gewählt hat. 01:16:15.500 --> 01:16:18.400 So, der erste Fall ist, dass das Wort, was er sich gewählt hat, hier 01:16:18.400 --> 01:16:19.220 von dieser Art war. 01:16:19.320 --> 01:16:20.840 Das war einfach nur eine Folge von Einsen. 01:16:21.800 --> 01:16:25.100 Na gut, dann weiß ich aber auch, dass mein erstes Zeichen, was hier in 01:16:25.100 --> 01:16:28.200 V drin war, eine Eins war und egal, wie er das aufpumpt, dann wird es 01:16:28.200 --> 01:16:31.160 einfach nur eine Folge von Einsen bleiben, also in der Sprache. 01:16:33.900 --> 01:16:37.960 Zweiter Fall, der Gegenspieler hat sich als Wort hier irgendwas von 01:16:37.960 --> 01:16:41.140 der Art gewählt, das heißt, es ist irgendeine Folge von Nullen, 01:16:42.580 --> 01:16:45.680 gefolgt von Eins hoch Quadratzahl. 01:16:53.540 --> 01:16:56.700 Und das I hat er sich auch noch gewählt, muss ich auch noch 01:16:56.700 --> 01:17:01.700 unterscheiden, wenn er sich jetzt als I Null gewählt hat, dann wurde 01:17:01.700 --> 01:17:07.560 im Prinzip hier vorne das V gelöscht und das war eine Null. 01:17:08.180 --> 01:17:12.900 Also es ist entweder jetzt einfach eine Null weniger oder das war die 01:17:12.900 --> 01:17:14.920 einzige Null und dann ist es nur noch Einsen. 01:17:15.380 --> 01:17:17.880 Aber in beiden Fällen ist es gut, das ist ein Wort aus unserer 01:17:17.880 --> 01:17:18.700 Sprache. 01:17:19.860 --> 01:17:23.000 Oder er hat so ein Wort hier hinten gewählt für irgendein J und ein K 01:17:23.000 --> 01:17:25.940 und er hat sich ein anderes I gewählt, was nicht Null war und hat das 01:17:25.940 --> 01:17:28.300 jetzt wirklich verlängert. 01:17:29.820 --> 01:17:33.400 Und dann ist das Aufblähen des ersten Zeichens, fügt aber nur noch 01:17:33.400 --> 01:17:38.040 Nullen hinzu und dann, weil das hier vorne unbeschränkt war, also 01:17:38.040 --> 01:17:41.560 keine Einschränkung hat über die Anzahl der Nullen, ist es immer gut. 01:17:42.180 --> 01:17:44.780 Also auch das Pumpen da vorne, diese einen Nullen, ist gut und bleibt 01:17:44.780 --> 01:17:45.340 in der Sprache. 01:17:48.240 --> 01:17:50.180 Die Aussage des Pumping Lemmas gilt. 01:17:52.460 --> 01:17:55.860 Die Sprache, also das sagt mir aber nichts über die Regularität der 01:17:55.860 --> 01:17:56.120 Sprache. 01:17:56.720 --> 01:17:59.560 Tatsächlich, ich verrate ihm im Geheimen, dass die Sprache nicht 01:17:59.560 --> 01:18:00.160 regulär ist. 01:18:00.160 --> 01:18:02.760 Obwohl es rot ist, ist es kein Feuerwehrauto. 01:18:03.160 --> 01:18:07.060 Das ist, weil dieses Quadratzeilen hier oben, das können endliche 01:18:07.060 --> 01:18:08.200 Automaten nicht erkennen. 01:18:09.740 --> 01:18:10.160 Gut. 01:18:11.000 --> 01:18:13.040 Dann fassen wir zusammen. 01:18:13.980 --> 01:18:15.280 Wir haben heute eine ganze Menge gemacht. 01:18:17.120 --> 01:18:20.760 Das erste, was wir gemacht haben, ist nicht deterministische endliche 01:18:20.760 --> 01:18:25.040 Automaten, beliebige, überführt in äquivalente Automaten ohne Epsilon 01:18:25.040 --> 01:18:25.520 -Übergänge. 01:18:26.900 --> 01:18:30.500 Das zweite, was wir gemacht haben, ist, wir haben einen 01:18:30.500 --> 01:18:34.460 deterministischen Automaten beliebig genommen und haben daraus einen 01:18:34.460 --> 01:18:38.500 regulären Ausdruck für die entsprechende Sprache konstruiert. 01:18:38.580 --> 01:18:39.900 Das war schon ein bisschen komplizierter. 01:18:40.300 --> 01:18:43.760 Das zeigt insbesondere diese Äquivalenz hier in der Mitte und beweist 01:18:43.760 --> 01:18:44.620 den Satz von clean. 01:18:46.040 --> 01:18:48.980 Das war schon komplizierter. 01:18:49.960 --> 01:18:53.580 Und dann haben wir im zweiten Teil der Vorlesung dieses Pumping Lemma 01:18:53.580 --> 01:18:59.680 uns angeguckt, was wirklich ein zentraler Punkt ist in der Vorlesung. 01:18:59.740 --> 01:19:04.720 Das müssen Sie mindestens dreimal auf den Hausaufgabenblättern machen. 01:19:06.100 --> 01:19:11.640 Das Pumping Lemma nochmal zur Erinnerung. 01:19:11.760 --> 01:19:15.520 Das hier, was ich jetzt einfach mal mit Sternen label, ist die Aussage 01:19:15.520 --> 01:19:16.540 des Pumping Lemmas. 01:19:17.520 --> 01:19:23.240 Das Pumping Lemma selber ist, wenn eine Sprache regulär ist, dann 01:19:23.240 --> 01:19:24.900 erfüllt sie diese Stern-Eigenschaft. 01:19:26.340 --> 01:19:27.860 Das haben wir bewiesen. 01:19:28.540 --> 01:19:32.740 Aber benutzen tun wir das, indem wir sagen, wir widerlegen die Aussage 01:19:32.740 --> 01:19:36.380 des Pumping Lemmas und zeigen so die Nicht-Regularität einer Sprache. 01:19:37.040 --> 01:19:43.580 Also, wenn eine Sprache L-Stern nicht erfüllt, dann ist L nicht 01:19:43.580 --> 01:19:44.160 regulär. 01:19:45.140 --> 01:19:48.120 Was jetzt natürlich äquivalent dazu ist, es gibt keinen endlichen 01:19:48.120 --> 01:19:49.700 Automaten, der die Sprache erkennt. 01:19:51.240 --> 01:19:53.600 Das ist, wofür wir das Pumping Lemma eigentlich haben. 01:19:54.560 --> 01:19:57.620 Wir werden noch mehr Pumping Lemmas kennenlernen. 01:19:58.520 --> 01:19:59.760 Das ist das Einfachste. 01:20:03.520 --> 01:20:04.320 Testen Sie sich! 01:20:06.260 --> 01:20:09.740 Heute gebe ich Ihnen wieder ein paar Aufgaben mit, um sich selbst zu 01:20:09.740 --> 01:20:13.940 testen, ob Sie heute aus der Vorlesung gut mitgekommen sind. 01:20:15.720 --> 01:20:19.660 Sie haben dieses folgende Alphabet, die Ziffern von 0 bis 9 und so ein 01:20:19.660 --> 01:20:20.420 Schrägstrich. 01:20:21.100 --> 01:20:23.780 Und ich gebe Ihnen diesmal den Automaten. 01:20:25.820 --> 01:20:29.180 Das ist ein endlicher Automat und der erkennt irgendwelche komischen 01:20:29.180 --> 01:20:31.000 Wörter über diesem Alphabet. 01:20:31.900 --> 01:20:32.960 Ich verrate Ihnen nicht was. 01:20:34.080 --> 01:20:37.100 Dadurch, dass es aber ein Automat ist, müsste ich ja eigentlich einen 01:20:37.100 --> 01:20:42.320 regulären Ausdruck finden können für die Sprache, weil alles, was von 01:20:42.320 --> 01:20:44.520 einem endlichen Automaten erkannt wird, regulär ist. 01:20:45.560 --> 01:20:47.400 Finden Sie so einen regulären Ausdruck? 01:20:48.440 --> 01:20:53.160 Wollen Sie dazu den Beweis durchgehen, den wir heute gemacht haben, 01:20:53.280 --> 01:20:56.260 oder finden Sie das irgendwie durch Draufschauen oder durch Verstehen 01:20:56.260 --> 01:20:56.740 der Sprache? 01:20:57.780 --> 01:20:58.520 Zweiter Punkt. 01:20:59.320 --> 01:21:01.800 Gilt die Aussage des Pumping Lemmas? 01:21:04.300 --> 01:21:08.620 Wenn Ihnen das zu einfach ist, einfach nur so Ja, Nein zu antworten, 01:21:10.420 --> 01:21:14.680 der erste Punkt in der Aussage des Pumping Lemmas war, es existiert 01:21:14.680 --> 01:21:15.840 ein N so das. 01:21:18.880 --> 01:21:20.260 Gibt es nur ein so ein N? 01:21:21.180 --> 01:21:22.680 Oder welche Ns sind gut? 01:21:24.500 --> 01:21:25.740 Welche Ns sind vielleicht schlecht? 01:21:29.380 --> 01:21:32.920 Und nochmal Pumping Lemma, weil es so wichtig ist, ein bisschen eine 01:21:32.920 --> 01:21:36.440 andere Sprache, die Zeichen sind jetzt nur von 1 bis 9 und so ein 01:21:36.440 --> 01:21:43.760 Istgleichzeichen und die Wörter sind von der Form UVU, wobei U nur aus 01:21:43.760 --> 01:21:48.520 1 bis 9 besteht und das V ist dieses Istgleichzeichen. 01:21:52.700 --> 01:21:53.760 Sprache verstanden. 01:21:54.420 --> 01:21:56.840 Gilt die Aussage des Pumping Lemmas für diese Sprache? 01:21:59.040 --> 01:21:59.940 Testen Sie sich. 01:22:00.400 --> 01:22:03.400 Gut, dann am Donnerstag geht es weiter mit einer Übung und wir sehen 01:22:03.400 --> 01:22:03.940 uns nächste Woche.