WEBVTT 00:07.540 --> 00:11.100 Wir hatten uns beim letzten Mal angeschaut, wie man reguläre 00:11.100 --> 00:18.260 Ausdrücke, was das ist und was die mit regulären Sprachen zu tun 00:18.260 --> 00:18.560 haben. 00:19.200 --> 00:22.800 Also zur Erinnerung, reguläre Ausdrücke sind induktiv definiert. 00:22.920 --> 00:28.020 Wir haben das leere Mengensymbol, das leere Wortsymbol und die 00:28.020 --> 00:31.060 Buchstaben unseres Alphabets. 00:31.060 --> 00:34.840 Und wir können Vereinigungsmengen bilden, Produkte, also 00:34.840 --> 00:38.640 aneinanderhängende Zeichen in Teilsprachen. 00:39.200 --> 00:42.940 Wir haben ein Klammersymbol und wir können die klinische Hülle bilden, 00:43.040 --> 00:46.180 beziehungsweise die positive Hülle, also Wörter wiederholen. 00:47.800 --> 00:53.280 Und die Beobachtung ist, dass das genügt, um die regulären Sprachen, 00:54.200 --> 00:58.960 also Chomsky-3-Sprachen zu spezifizieren. 01:01.460 --> 01:05.000 Ganz wichtige Unterscheidung war zwischen Syntax und Semantik. 01:05.520 --> 01:09.840 Also die linke Spalte hier war der Syntax und die rechte Spalte hier 01:09.840 --> 01:14.880 ist die Menge der Wörter über dem Alphabet, die dadurch beschrieben 01:14.880 --> 01:15.220 werden. 01:15.700 --> 01:21.060 Auch wenn das hier oft ähnlich aussieht, weil wir hier zum Beispiel 01:21.060 --> 01:24.960 das Vereinigungsmengensymbol auf beiden Seiten benutzen, ist das hier 01:24.960 --> 01:28.740 halt selber wieder eine Zeichenkette, während das hier eine Menge von 01:28.740 --> 01:33.100 Wörtern ist, die auch unendlich groß sein kann. 01:37.140 --> 01:42.760 Wir haben uns Beispiele angeschaut und der Plan war jetzt zu zeigen, 01:42.920 --> 01:48.140 dass das das Gleiche ist wie Typ-3-Sprachen, und zwar ausgehend von 01:48.140 --> 01:51.580 diesem Kreis, den wir beim letzten Mal geschlossen hatten, dass 01:51.580 --> 01:55.300 nämlich deterministische endliche Automaten, Chomsky-3-Grammatiken und 01:55.300 --> 01:58.960 nicht -deterministische endliche Automaten die gleichen Sprachen 01:58.960 --> 02:02.760 spezifizieren, wollen wir jetzt das Ganze in zwei Schritten zeigen, 02:02.880 --> 02:07.560 nämlich einerseits, dass man aus regulären Ausdrücken nicht 02:07.560 --> 02:11.220 -deterministische endliche Automaten machen kann, andererseits, dass 02:11.220 --> 02:14.420 man aus deterministischen endlichen Automaten reguläre Ausdrücke 02:14.420 --> 02:18.080 machen kann, die jeweils die gleiche Sprache beschreiben. 02:20.260 --> 02:23.400 Wir hatten angefangen mit der Konstruktion nicht-deterministischer 02:23.400 --> 02:29.340 endlicher Automaten aus regulären Ausdrücken und die Beweisidee war, 02:30.000 --> 02:32.760 dass man für Teilausdrücke Automaten baut, die man dann 02:32.760 --> 02:34.080 zusammenstöpselt. 02:35.720 --> 02:39.600 Dafür brauchen wir natürlich einen Basisfall, aber die leere Menge, 02:39.800 --> 02:43.160 die Menge, die das leere Wort enthält und die Menge, die genau einen 02:43.160 --> 02:46.460 Buchstaben enthält, da gibt es ganz einfache Automaten dafür. 02:48.020 --> 02:51.600 Und jetzt hatten wir angefangen mit dem ersten nicht-trivialen Teil, 02:52.020 --> 02:59.180 nämlich wie baue ich einen nicht-deterministischen endlichen Automaten 02:59.180 --> 03:00.380 für die Vereinigungsmenge. 03:10.130 --> 03:18.270 Und da war die Idee, ich setze diese beiden, ich baue Automaten für 03:18.270 --> 03:24.070 L1, einen Automaten A1, der L1 akzeptiert, einen Automaten A2, der L2 03:24.070 --> 03:25.830 akzeptiert, setze die nebeneinander. 03:26.490 --> 03:30.970 Was ich dafür tun muss, ist lediglich, dass die Zustandsmengen der 03:30.970 --> 03:36.170 beiden Automaten disjunkt sind und ich führe einen zusätzlichen 03:36.170 --> 03:37.350 Startzustand ein. 03:37.730 --> 03:42.490 Also in unserer Notation ist das jetzt, wenn ich einen Automaten A1 03:42.490 --> 03:48.130 habe mit Zustandsmenge Q1 und Übergangsfunktionen Delta 1, Startsymbol 03:48.130 --> 03:54.790 S1, Endzustandsmenge F1 und A2, entsprechend Q2, Sigma, Delta 2, S2, 03:54.870 --> 03:55.410 F2. 03:56.410 --> 04:01.610 Dann bilde ich einen neuen Automaten A, dessen Zustandsmenge ist neuer 04:01.610 --> 04:06.370 Startzustand S vereinigt mit Q1 vereinigt mit Q2. 04:11.730 --> 04:18.270 Das S ist der neue Startzustand und ich muss mir noch überlegen, was 04:18.270 --> 04:21.250 die Endzustandsmenge ist und was die Übergangsfunktion ist. 04:21.750 --> 04:25.750 Die Idee ist aber ganz einfach, Delta verhält sich wie Delta 1 bzw. 04:26.030 --> 04:31.530 Delta 2, je nachdem, ob wir uns in einem Zustand in Q1 oder in Q2 04:31.530 --> 04:32.530 befinden. 04:36.610 --> 04:39.650 Jetzt muss ich mir nur noch überlegen, was ich mit den Startzuständen 04:39.650 --> 04:39.950 mache. 04:41.390 --> 04:46.010 Der neue Startzustand, der muss sozusagen die Funktionen der alten 04:46.010 --> 04:47.530 Startzustände nachbauen. 04:49.110 --> 04:52.770 Und das kann ich aber ganz leicht definieren, indem ich sage, Delta S, 04:52.990 --> 04:59.590 A, also der Übergang vom Startzustand bei Eingabe des Buchstabens A, 04:59.590 --> 05:04.010 ist die Vereinigung aus Delta S1, A und Delta S2, A. 05:04.730 --> 05:08.490 Damit baut er sozusagen das Verhalten von S1 und S2 nach. 05:11.830 --> 05:15.250 Und bei der Endzustandsmenge ist es im Wesentlichen die 05:15.250 --> 05:18.950 Vereinigungsmenge von F1 und F2. 05:19.110 --> 05:22.170 Das heißt, wenn einer der beiden Automaten das Wort akzeptiert, dann 05:22.170 --> 05:24.350 soll mein neuer Automat das auch akzeptieren. 05:24.350 --> 05:33.230 Und ich muss jetzt nur noch aufpassen, wenn S1 oder S2 Endzustände 05:33.230 --> 05:37.290 sind, da ich deren Verhalten ja nachbaue, muss ich aus S auch einen 05:37.290 --> 05:38.130 Endzustand machen. 05:38.910 --> 05:42.710 Und eine abstraktere Art, wie man sich überlegen kann, was bedeutet 05:42.710 --> 05:48.890 das ist, ich habe jetzt sozusagen meinen Automat, also meine Eingabe, 05:48.890 --> 05:52.350 ich probiere praktisch beide Automaten aus, ich lasse die parallel 05:52.350 --> 05:55.370 laufen, das kann ich mit einer nicht deterministischen Maschine 05:55.370 --> 05:55.770 machen. 05:57.350 --> 05:59.910 Und wenn einer davon akzeptiert, dann habe ich halt insgesamt 05:59.910 --> 06:00.650 akzeptiert. 06:01.690 --> 06:04.250 Und das ist jetzt eine wichtige Eigenschaft von einer nicht 06:04.250 --> 06:05.350 deterministischen Maschine. 06:05.510 --> 06:09.410 Ich kann durch nicht deterministische Übergänge sozusagen mehrere 06:09.410 --> 06:11.010 Maschinen parallel laufen lassen. 06:11.990 --> 06:18.310 Und deshalb wäre es jetzt nicht möglich, die gleiche Beweisidee mit 06:18.310 --> 06:20.370 deterministischen Automaten umzusetzen. 06:22.010 --> 06:24.210 Gibt es Fragen zu dieser Konstruktion? 06:24.210 --> 06:25.270 Okay, 06:52.910 --> 06:57.170 wir haben gefragt, warum muss S ein Startzustand sein? 06:57.790 --> 07:01.090 Sie haben was von Epsilon-Übergängen gesagt, ich aber nicht. 07:02.310 --> 07:04.590 Wir kommen gegen Ende der Vorlesung noch dazu. 07:05.130 --> 07:08.230 Es gibt verschiedene Varianten von endlichen Automaten. 07:08.230 --> 07:12.210 Es gibt welche, bei denen man sogenannte Epsilon-Übergänge zulässt, 07:12.330 --> 07:16.190 das heißt der Automat macht einen Zustandsübergang, selbst wenn gar 07:16.190 --> 07:17.430 nichts eingegeben wurde. 07:18.790 --> 07:20.970 Aber das haben wir im Moment nicht erlaubt. 07:21.990 --> 07:25.810 Sie haben recht, wenn ich Epsilon-Übergänge erlaube, dann wird das 07:25.810 --> 07:26.630 Ganze einfacher. 07:27.750 --> 07:31.030 Nur richte ich mich hier nach dem Schöning, der das nicht erlaubt, 07:31.630 --> 07:35.350 weil dann werden andere Sachen wieder einfacher. 07:36.370 --> 07:38.970 Wir müssen hier bei der Konstruktion ein bisschen mehr aufpassen. 07:39.130 --> 07:43.310 Wir müssen da dieses Nachbauen von Zuständen einbauen, was Sie nicht 07:43.310 --> 07:44.970 brauchen, wenn Sie Epsilon-Übergänge haben. 07:45.450 --> 07:46.730 Aber das ist jetzt sozusagen ein Vorgriff. 07:46.930 --> 07:50.930 Aber hier brauchen Sie es halt, weil in dem Automaten darf es nur 07:50.930 --> 07:52.270 einen Startzustand geben. 07:52.390 --> 07:54.830 Ich kann nicht einfach sagen, die sind jetzt beide Startzustände. 07:59.830 --> 08:00.710 Weitere Fragen? 08:01.630 --> 08:05.190 Okay, also jetzt unser Beweis in zwei Teilen. 08:05.210 --> 08:09.470 Erstmal, dass L1 vereinigt L2 Teilmenge von LA ist. 08:11.190 --> 08:12.950 Das zeige ich in zwei Teilen. 08:13.790 --> 08:18.990 Entweder wir schauen uns ein beliebiges W in L1 vereinigt L2 an. 08:19.410 --> 08:26.610 Dann mache ich eine Fallunterscheidung W1 in L1 oder W in L2. 08:26.610 --> 08:30.210 Die beiden Fälle sind völlig analog, deshalb zeige ich jetzt 08:30.210 --> 08:31.670 detailliert nur den ersten Teil. 08:33.910 --> 08:37.890 Also nehmen wir mal an, wir wollen zeigen, dass ein beliebiges Wort 08:37.890 --> 08:40.710 aus L1 in L von A ist. 08:43.030 --> 08:49.510 Und da mache ich jetzt eine Induktion über die Länge des Wortes für 08:49.510 --> 08:50.550 ein leeres Wort. 08:51.310 --> 08:57.030 Es ist so, wenn das leere Wort in L1 ist, heißt das, dass S1 ein 08:57.030 --> 08:57.950 Endzustand ist. 08:59.130 --> 09:03.570 Das bedeutet aber nach unserer Definition, dass auch S ein Endzustand 09:03.570 --> 09:03.970 ist. 09:05.270 --> 09:06.710 Und damit ist W in L von A. 09:07.870 --> 09:12.590 Damit ist das leere Wort in L von A, das ist ja jetzt in diesem Fall 09:12.590 --> 09:13.070 unser W. 09:13.910 --> 09:17.070 Jetzt schauen wir uns an, dass W die Form hat, ein Buchstabe A und 09:17.070 --> 09:18.710 dann ein anderes Teilwort X. 09:20.770 --> 09:27.910 Wenn W in L1 ist, heißt das, es gibt einen Pfad P1 durch den Automaten 09:27.910 --> 09:32.860 für L1. 09:33.240 --> 09:41.060 Der fängt bei Startzustand 1 an und geht dann unter Eingabe von A in 09:41.060 --> 09:43.780 einen Zustand Q1, in GroßQ1 über. 09:44.660 --> 09:49.220 Und dann unter Eingabe von X mit mehreren Zustandsübergängen, das kann 09:49.220 --> 09:55.240 jetzt ein ganzes Teilwort sein, in einen Endzustand vom Automaten A1. 09:58.280 --> 10:03.380 Dieser Pfad ist fast ein Pfad in A. 10:04.480 --> 10:07.420 Das Einzige, was ich ändern muss, ich nehme jetzt statt diesem 10:07.420 --> 10:12.880 Übergang S1 A Q1, nehme ich den Übergang S A Q1. 10:13.020 --> 10:15.560 Nach Definition von A gibt es diesen Übergang. 10:18.300 --> 10:25.000 Genau so habe ich die Zustandsübergangsfunktionen für S definiert, 10:25.040 --> 10:28.180 dass sie nämlich die Übergänge von S1 und S2 nachbauen können. 10:29.620 --> 10:35.720 Und damit habe ich einen Pfad in meinem Automaten A konstruiert, der 10:35.720 --> 10:43.540 in F1 endet, aber F1 ist ja in GroßF1 und damit auch in GroßF. 10:44.080 --> 10:47.820 F1 ist damit ein Endzustand von A, also ist W in L von A. 10:48.480 --> 10:51.140 Und für W in L2 gilt das Gleiche. 10:51.400 --> 10:52.280 Fragen Ihnen dazu? 10:53.560 --> 10:55.280 Genau, also der Beweis war sehr einfach. 10:55.980 --> 10:59.540 Es ist nur minimal schwieriger, die andere Richtung zu zeigen. 10:59.760 --> 11:02.420 L von A Teilmenge L1 vereinigt L2. 11:03.240 --> 11:06.220 Also betrachten wir ein beliebiges Wort in L von A. 11:06.820 --> 11:10.000 Jetzt fangen wir wieder mit dem Fall an, dass es das leere Wort ist. 11:10.000 --> 11:17.700 Das bedeutet, dass S ein Endzustand sein muss, weil es wird ja 11:17.700 --> 11:20.000 akzeptiert, also das leere Wort wird akzeptiert. 11:21.320 --> 11:26.340 Das kann aber nur dann ein Endzustand sein nach Definition von A, wenn 11:26.340 --> 11:32.800 S1 ein Endzustand von A1 ist oder S2 ein Endzustand von A2. 11:34.300 --> 11:40.380 Das bedeutet aber, dass Epsilon in L1 oder L2 sein muss und damit auch 11:40.380 --> 11:41.520 in der Vereinigungsmenge. 11:42.480 --> 11:43.740 Also habe ich mein Ding bewiesen. 11:44.380 --> 11:49.100 Jetzt wieder der Induktionsschritt für ein Wort der Form AX. 11:50.560 --> 11:56.740 Wenn das Wort in L von A ist, heißt das, es gibt einen Pfad S, Eingabe 11:56.740 --> 12:02.500 von A dann in einen Zustand Q und dann Übereingabe von X in einen 12:02.500 --> 12:06.620 Endzustand F von dem Automaten A. 12:08.280 --> 12:12.240 Jetzt mache ich wieder eine Fallunterscheidung, die völlig symmetrisch 12:12.240 --> 12:12.580 ist. 12:13.460 --> 12:16.900 Dieser Zustand Q ist entweder in Q1 oder in Q2. 12:19.020 --> 12:21.840 Nehmen wir OBDA an, er ist in Q1. 12:22.400 --> 12:31.700 Das heißt, es gibt einen Pfad, der in S1 anfängt, unter Eingabe von A 12:31.700 --> 12:39.480 nach Q1 übergeht und dann unter Eingabe von X nach F übergeht. 12:41.120 --> 12:42.320 Warum ist das so? 12:44.600 --> 12:47.580 Angefangen habe ich mit einem Pfad, der bei S losgeht, unter Eingabe 12:47.580 --> 12:48.620 von A nach Q. 12:53.270 --> 12:56.370 Jetzt ist es so, es gibt zwei verschiedene Möglichkeiten, was hier 12:56.370 --> 12:57.050 passieren kann. 12:57.050 --> 12:59.050 Welche Übergänge von S gibt es? 12:59.090 --> 13:01.610 Das sind die Übergänge von S1 und die von S2. 13:02.170 --> 13:05.890 Aber ich weiß, die Übergänge von S1, die gehen nur nach Q1 und die 13:05.890 --> 13:08.170 Übergänge von S2 gehen nur nach Q2. 13:10.190 --> 13:16.670 Und ich habe ja hier die Fallunterscheidung gemacht, dass Q1 in Q1 13:16.670 --> 13:16.990 ist. 13:17.350 --> 13:18.970 Das heißt, ich bin in diesem ersten Fall. 13:18.970 --> 13:28.870 Das heißt, dieser Übergang S A Q1, der kam aus einem Übergang S1 nach 13:28.870 --> 13:32.470 Q1 unter Eingabe von A aus dem Automaten A1. 13:33.710 --> 13:40.130 Und damit habe ich also durch Umbiegen dieses Übergangs S A Q1 nach S1 13:40.130 --> 13:45.370 A Q1 einen Pfad konstruiert, der sich komplett in dem Automaten A1 13:45.370 --> 13:45.850 bewegt. 13:47.950 --> 13:56.270 Das gilt auch für den Endzustand, weil wenn ich einmal in Q1 bin, 13:56.290 --> 13:57.410 komme ich da nicht wieder raus. 13:59.030 --> 14:00.750 Auch in dem neuen Automaten A. 14:01.670 --> 14:06.090 Wirklich muss das F ein Endzustand von Automaten A1 sein. 14:08.430 --> 14:14.950 Es gibt also einen solchen Pfad in A1, der bei S1 beginnt, im 14:14.950 --> 14:18.790 Startzustand von A1 und in einem Endzustand von A1 endet. 14:19.550 --> 14:26.430 Das heißt, das Wort W wird auch vom Automaten A1 akzeptiert. 14:26.630 --> 14:28.090 Das heißt, W ist in L1. 14:28.090 --> 14:31.810 Und L1 ist eine Teilmenge von L1 vereinigt L2. 14:33.610 --> 14:38.930 Genau, und den Analog kann ich das Ganze machen, wenn der erste 14:38.930 --> 14:40.970 Übergang in einen Zustand von Q2 geht. 14:41.610 --> 14:42.570 Gibt es Fragen dazu? 14:45.150 --> 14:48.790 Das sind also diese klassischen Beweise, die immer wieder die 14:48.790 --> 14:52.150 Definition aufrufen, strukturelle Induktion in diesem Fall über das 14:52.150 --> 14:52.770 Wort machen. 14:53.870 --> 14:56.550 Bisschen mühsam, aber eigentlich alles ganz einfach. 14:56.670 --> 15:00.490 Ich werde deshalb die Beweise ab jetzt ein bisschen verkürzen. 15:00.890 --> 15:05.590 Wir müssen jetzt das gleiche Spiel machen für alle Operatoren, die 15:05.590 --> 15:09.430 benutzt werden können, um reguläre Ausdrücke zu definieren. 15:11.650 --> 15:14.610 Jetzt hier L1, Produkt L2. 15:15.650 --> 15:20.790 Was ich da mache, ich nehme wieder die beiden Automaten für A1 und A2. 15:24.100 --> 15:26.420 Und hänge die sozusagen hintereinander. 15:27.780 --> 15:30.780 Also grob gesagt wird der neue Startzustand das S1. 15:32.100 --> 15:34.980 Ich brauche also hier auch gar keinen neuen Startzustand selber. 15:36.020 --> 15:40.480 Und die Endzustände werden die Endzustände von A2. 15:45.630 --> 15:48.490 Ich muss jetzt nur aufpassen, es gibt einen Spezialfall. 15:51.210 --> 16:05.890 Wenn der Startzustand von S2 ein Endzustand von F2 ist, das heißt A2 16:05.890 --> 16:07.090 enthält das leere Wort, 16:11.570 --> 16:17.850 dann muss ich praktisch sagen, alle Endzustände von F1 sind 16:17.850 --> 16:21.350 gleichzeitig Endzustände des ganzen Automaten. 16:22.010 --> 16:24.110 Aber das muss ich glaube ich noch ein bisschen genauer erklären. 16:24.710 --> 16:28.110 Also was hier passiert ist, die Idee ist, wir lassen erstmal den 16:28.110 --> 16:30.910 Automaten A1 laufen und dann den Automaten A2. 16:32.310 --> 16:35.310 Aber das ist eine deterministische Sichtweise, die nicht ganz 16:35.310 --> 16:35.950 funktioniert. 16:37.090 --> 16:39.670 Ich weiß ja gar nicht genau, wenn jetzt ein Wort eingegeben wird, das 16:39.670 --> 16:47.430 besteht aus einem Präfix, der vom Automaten A1 akzeptiert wird und der 16:47.430 --> 16:50.090 Rest wird vom Automaten A2 akzeptiert. 16:50.930 --> 16:53.630 Aber ich weiß nicht genau, wann dieser Übergang ist. 16:54.750 --> 16:57.750 Brauche ich auch bei einem nicht deterministischen endlichen Automaten 16:57.750 --> 16:58.430 nicht zu wissen. 16:58.430 --> 17:04.250 Der Trick, den ich mache ist, dass alle Endzustände von A1, hier in 17:04.250 --> 17:11.930 F1, haben einerseits die gleiche Funktionalität wie in A1, können 17:11.930 --> 17:16.430 andererseits aber auch den Startzustand von A2 nachbauen. 17:17.450 --> 17:24.810 Und dadurch diese Definition, Delta Q, A ist Delta 1 Q, A, falls es 17:24.810 --> 17:29.370 sich um einen Zustand aus Q1 handelt, der kein Endzustand ist. 17:30.350 --> 17:34.450 Es ist Delta 2 Q, A in sonstigen Fällen. 17:34.610 --> 17:40.390 Und dann gibt es halt die Endzustände von Automat A1, da ist es die 17:40.390 --> 17:46.090 Vereinigungsmenge aus Delta 1 Q, A und Delta 2 von S2, A. 17:46.430 --> 17:50.650 Also Endzustände des ersten Automaten simulieren zusätzlich den 17:50.650 --> 17:52.410 Startzustand des zweiten Automaten. 17:53.470 --> 18:00.750 Und das bedeutet, dass sie das auch bezüglich der endgültigen 18:00.750 --> 18:02.770 Akzeption eines Buchstabens machen. 18:03.110 --> 18:08.550 Das heißt, wenn S2 ein Startzustand ist, wenn S2 ein Endzustand von A2 18:08.550 --> 18:14.730 ist, dann müssen die Endzustände von A1 auch Endzustände des neuen 18:14.730 --> 18:15.610 Automaten werden. 18:17.410 --> 18:19.730 Also die Idee ist ganz einfach. 18:20.730 --> 18:23.170 Mit Epsilon-Übergängen wird es dann noch einfacher. 18:25.690 --> 18:27.630 Aber so schwierig ist es ja auch nicht. 18:28.390 --> 18:30.210 Fragen zu dieser Konstruktion? 18:31.230 --> 18:35.770 Den Beweis werde ich nicht machen, der funktioniert ziemlich analog zu 18:35.770 --> 18:39.370 diesem Vereinigungsmengenbeweis. 18:39.370 --> 18:42.430 Also Sie machen das wieder in zwei Teilen, machen schrittweise 18:42.430 --> 18:45.970 Induktion über die Wortlänge und dann muss man immer nur die 18:45.970 --> 18:51.530 Definition an der richtigen Stelle einsetzen, um den Gesamtbeweis zu 18:51.530 --> 18:52.170 basteln. 18:53.250 --> 18:56.170 Sonst noch Fragen zu dem Beweis oder der Konstruktion? 18:58.070 --> 19:00.290 Dann gucken wir uns die positive Hülle an. 19:02.370 --> 19:07.670 Also beliebig viele Wiederholungen von Wörtern aus der Sprache L. 19:09.370 --> 19:10.550 Aber mindestens eine. 19:11.170 --> 19:16.930 Also gegeben ein Automat A, der L akzeptiert, konstruieren wir einen 19:16.930 --> 19:21.470 Automaten A+, der L plus akzeptiert. 19:22.710 --> 19:25.530 Und der sieht folgendermaßen aus. 19:26.850 --> 19:33.090 Der hat den gleichen Startzustand wie A, die gleiche Zustandsmenge, 19:33.790 --> 19:37.690 sowieso das gleiche Alphabet, auch die gleiche Endzustandsmenge. 19:37.690 --> 19:40.710 Das Einzige, was ich machen muss, ist, dass ich die Übergangsfunktion 19:40.710 --> 19:42.910 ein bisschen aufpeppe. 19:43.910 --> 19:49.890 Nämlich, aber das ist auch ganz einfach, die meisten Einträge bleiben 19:49.890 --> 19:56.670 gleich für Nicht-Endzustände, aber Endzustände von A simulieren 19:56.670 --> 19:58.750 gleichzeitig den Startzustand von A. 19:59.670 --> 20:06.610 Indem man setzt Delta Q, A vereinigt Delta S, A als neuen Wert von 20:06.610 --> 20:08.230 Delta plus Q, A. 20:12.470 --> 20:13.630 Fragen dazu? 20:16.030 --> 20:20.730 Das werde ich jetzt beweisen, weil die Konstruktion noch ein bisschen 20:20.730 --> 20:23.650 anders ist als bei diesen binären Operatoren. 20:25.450 --> 20:29.850 Also, erster Teil des Beweises, wir müssen zeigen, dass L von A plus 20:29.850 --> 20:32.750 Teilmenge von L plus ist. 20:33.570 --> 20:37.950 Wir betrachten also ein beliebiges Wort W aus L von A plus. 20:41.630 --> 20:46.990 Wir nehmen ohne Bedenken des Autors an, dass W nicht das leere Wort 20:46.990 --> 20:47.350 ist. 20:47.350 --> 20:54.190 Naja, ganz einfach, weil, wenn es das leere Wort ist, dann ist S 20:54.190 --> 20:57.170 sowieso ein Endzustand und dann wird das Ding einfach akzeptiert, das 20:57.170 --> 20:58.650 ist ziemlich klar. 20:59.790 --> 21:02.410 Also, wenn wir nicht leeres Wort W haben, 21:06.620 --> 21:17.080 dann heißt das, es gibt einen Pfad in diesem Automatengrafen, der bei 21:17.080 --> 21:18.000 S startet. 21:22.860 --> 21:31.240 Und bei F endet und es gibt mindestens einen echten Übergang, nämlich 21:31.240 --> 21:32.720 S, A0 nach Q0. 21:36.860 --> 21:43.180 Und jetzt ist die Idee, ich nehme immer möglichst größe Teilpfade, die 21:43.180 --> 21:47.800 schon Pfade in dem Automatengrafen für A sind. 21:49.680 --> 21:55.140 Und immer wenn es einen Übergang gibt, der nicht passt, der also durch 21:55.140 --> 21:58.780 A selber nicht erklärt wird, spalte ich das Ding auf. 21:59.040 --> 22:08.520 Also ich zerlege den Pfad an Übergängen der Form Fj, Aj, Qj mit 22:08.520 --> 22:10.060 folgenden Eigenschaften. 22:12.220 --> 22:16.360 Qj ist nicht in Delta Fj, Aj. 22:16.580 --> 22:19.940 Das heißt, dieser Übergang ist nicht spezifiziert durch das Verhalten 22:19.940 --> 22:20.960 vom Automaten A. 22:26.650 --> 22:33.390 Und das kann nur dann sein, wenn dieses Fj ein Endzustand ist. 22:34.790 --> 22:40.510 So ist meine Definition der Übergangsfunktion von A+. 22:42.750 --> 22:46.030 Und nichts anderes steht hier. 22:46.710 --> 22:50.490 Gucken wir uns diese Zerlegung mal an. 22:54.050 --> 22:56.770 Wir haben also S, A0, Q0. 22:57.410 --> 23:01.670 Dann kommen Eingaben, die durch A erklärt werden bis zu F1, ein 23:01.670 --> 23:03.590 Endzustand von A. 23:03.590 --> 23:07.470 Dann kommt ein nicht erklärter Übergang A1 nach Q1. 23:07.910 --> 23:14.350 Dann gibt es wieder Übergänge, die durch A erklärt werden, X1 und so 23:14.350 --> 23:15.150 weiter und so fort. 23:15.270 --> 23:18.330 Das letzte Segment ist wieder ein Endzustand Fi. 23:19.350 --> 23:22.350 Buchstabe Ai wird eingegeben in Zustand Qi. 23:23.630 --> 23:28.970 Und dann Xi und dann lande ich in einem Endzustand von A+. 23:30.150 --> 23:36.030 Und jetzt kann ich für jedes dieser Segmente, also für das J-Segment 23:36.030 --> 23:44.970 hier drin, definiere ich einen neuen Pfad Pj, S, Aj, Qj, Xj, Fj plus 23:44.970 --> 23:45.430 1. 23:46.170 --> 23:51.510 Also ich nehme jedes Segment, also jedes Paar von Dingern hier und 23:51.510 --> 23:53.010 baue daraus einen Pfad in A. 23:53.990 --> 24:01.150 Und das kann ich machen, weil jeder dieser nicht erklärten Übergänge 24:01.150 --> 24:08.230 in dieser Zerlegung, hängt ja zusammen damit, das ist ein Endzustand, 24:09.030 --> 24:12.750 der jetzt plötzlich den Startzustand von A simuliert. 24:12.750 --> 24:21.590 Das heißt, ich mache aus diesem Übergang Fj nach Qj, mache ich einen 24:21.590 --> 24:23.430 Übergang S nach Qj. 24:23.550 --> 24:27.770 Und den gibt es, weil Delta plus so definiert ist. 24:29.250 --> 24:34.090 Das heißt, ich habe hier ganz viele Pfade, die jeweils Wörter in L von 24:34.090 --> 24:35.250 A definieren. 24:37.670 --> 24:43.450 Und das heißt ja nichts anderes, dass diese Teilwörter, die durch 24:43.450 --> 24:45.910 diese Teilpfade definiert werden, alle in L sind. 24:46.510 --> 24:50.750 Es gibt mindestens eins davon, das ist ja nichts anderes, als dass ich 24:50.750 --> 24:53.110 ein Element von L plus habe. 24:54.210 --> 24:55.070 Fragen dazu? 24:57.130 --> 24:58.530 Jetzt die andere Richtung. 25:01.430 --> 25:10.450 Ich zeige jetzt, dass L hoch I, also genau I-Wiederholung von Wörtern 25:10.450 --> 25:15.730 aus L, in L von A plus ist, für I größer gleich 1. 25:17.370 --> 25:21.630 Das ist eigentlich der einfachere Fall, weil jetzt ist mir schon 25:21.630 --> 25:26.430 vorgegeben, ich weiß, wenn ein Wort in L hoch I ist, dann gibt es eine 25:26.430 --> 25:36.850 Zerlegung W gleich W1 bis Wi, sodass jedes dieser Teilwörter W1 bis Wi 25:36.850 --> 25:37.810 in L ist. 25:40.950 --> 25:44.870 Das bedeutet aber, dass es für jedes dieser Teilwörter so Pfade der 25:44.870 --> 25:56.100 Form gibt S, Qj, Fj, erster Buchstabe eingegeben und der Rest. 25:57.660 --> 25:59.540 Die in einem Endzustand enden. 26:01.340 --> 26:05.480 Und was ich jetzt immer mache ist, das ist praktisch das Umgekehrte, 26:05.520 --> 26:06.340 was ich hier gemacht habe. 26:06.400 --> 26:11.440 Da habe ich einen Pfad in A plus zerlegt und hier nehme ich Pfade in A 26:11.440 --> 26:12.540 und hänge die aneinander. 26:13.480 --> 26:21.680 Das heißt, ich ersetze jeweils das SQJ durch den Übergang von dem 26:21.680 --> 26:24.400 letzten Endzustand, den ich hatte, nach QJ. 26:24.400 --> 26:27.040 Und das kann ich nach Definition von Delta plus. 26:28.820 --> 26:29.780 Fragen dazu? 26:39.390 --> 26:45.250 So, die Klien'sche Hülle ist fast das gleiche wie das L plus, nur dass 26:45.250 --> 26:47.590 auch Nullwiederholungen erlaubt sind. 26:48.350 --> 26:52.030 Aber das ist ganz einfach, weil den Vereinigungsmengenoperator habe 26:52.030 --> 26:52.390 ich schon. 26:53.150 --> 26:55.790 Lstern ist ja gerade Y vereinigt L plus. 26:56.410 --> 26:59.930 Dann baue ich einfach den nicht deterministischen endlichen Automaten 26:59.930 --> 27:00.570 für L plus. 27:00.570 --> 27:05.530 Ich nehme den nicht deterministischen endlichen Automaten für Y und 27:05.530 --> 27:07.850 mache die Konstruktion für die Vereinigungsmengenbildung. 27:09.510 --> 27:12.510 Und damit habe ich diesen Teil abgeschlossen. 27:12.650 --> 27:14.270 Das sind alle Operatoren, die ich brauche. 27:14.830 --> 27:18.470 Diese Klammeroperation ist ja was rein Syntaktisches, die verändert ja 27:18.470 --> 27:19.210 die Sprache nicht. 27:20.590 --> 27:24.130 Gibt es weitere Fragen zu diesem Schritt, wie man reguläre Ausdrücke 27:24.130 --> 27:26.910 in nicht deterministische endliche Automaten übersetzt? 27:27.970 --> 27:29.510 Machen wir mal ein paar Beispiele. 27:30.250 --> 27:31.910 Das war jetzt doch recht abstrakt. 27:37.700 --> 27:41.420 Ja, also hier ist ein Automaten, der genau die Null akzeptiert. 27:42.280 --> 27:45.380 Könnte sich jetzt noch ein Automaten anschauen, der genau die Eins 27:45.380 --> 27:45.600 akzeptiert. 27:46.940 --> 27:50.480 Jetzt mache ich mal die Vereinigungsmengenkonstruktion Null vereinigt 27:50.480 --> 27:50.980 Eins. 27:52.020 --> 27:52.960 Was ist das? 27:53.020 --> 27:56.940 Ich setze diese beiden Automaten, der akzeptiert die Null, der 27:56.940 --> 27:57.800 akzeptiert die Eins. 27:57.880 --> 28:04.060 Setze ich nebeneinander, baue einen neuen Startzustand und der verhält 28:04.060 --> 28:06.420 sich so wie die beiden Startzustände. 28:06.640 --> 28:12.540 Das heißt, bei Eingabe von Null geht er hier rüber, bei Eingabe von 28:12.540 --> 28:13.740 Eins geht er hier rüber. 28:14.600 --> 28:17.980 Und jetzt mache ich so ganz einfache Vereinfachungen. 28:18.580 --> 28:22.440 Wir sehen jetzt in dieser Konstruktion sind die Startzustände S1 und 28:22.440 --> 28:24.000 S2 gar nicht mehr erreichbar. 28:24.740 --> 28:27.140 Dann kann ich die auch weglassen und ich kriege jetzt einen neuen 28:27.140 --> 28:28.560 Graphen, der so aussieht. 28:31.690 --> 28:35.050 Wir werden aber sehen, dass das keineswegs minimal ist. 28:35.210 --> 28:39.710 Man könnte zum Beispiel die beiden Zustände hier noch vereinigen, weil 28:39.710 --> 28:41.310 die völlig äquivalent sind zueinander. 28:41.310 --> 28:47.470 Das sehen wir dann in der nächsten Woche oder vielleicht auch schon am 28:47.470 --> 28:48.370 Mittwoch. 28:54.130 --> 28:57.650 Das wäre ein einfaches Beispiel für Vereinigungsmengenbildung. 29:00.790 --> 29:02.290 Jetzt positive Hülle. 29:02.530 --> 29:05.790 Ich nehme jetzt diesen Automaten, Null vereinigt Eins und will davon 29:05.790 --> 29:07.070 die positive Hülle machen. 29:08.470 --> 29:09.570 Wie war das? 29:09.670 --> 29:13.590 Da müssen die Endzustände das Verhalten des Startzustands nachbauen. 29:14.270 --> 29:19.870 Das bedeutet, dass ich hier diese Übergänge mit Null und Eins da 29:19.870 --> 29:21.730 einfüge. 29:25.000 --> 29:29.200 Das ist hier so eine Konstruktion mit der Null Eins Stern. 29:29.380 --> 29:33.600 Da wird dann für das leere Wort ein Automat dazugebaut und ich mache 29:33.600 --> 29:36.610 einen neuen Startzustand, der das irgendwie nachbaut. 29:37.640 --> 29:40.300 Und dann kann man das wieder vereinfachen und dann kriege ich diesen 29:40.300 --> 29:41.340 Automaten hier. 29:42.400 --> 29:46.480 Ich baue jetzt stückweise so Sachen auf in den Beispielen. 29:48.500 --> 29:51.860 Das ist unser Null Eins Stern Automat. 29:52.240 --> 29:55.520 Jetzt sage ich Null Eins Stern und dann eine Null hinten dran. 29:55.820 --> 29:57.280 Da fehlt ein Punkt vielleicht. 29:57.960 --> 30:00.220 Aber das habe ich schon gesagt, dass ich den manchmal weglasse. 30:02.480 --> 30:04.540 Das ist also jetzt diese Produktbildung. 30:05.640 --> 30:06.340 Wie war das? 30:06.660 --> 30:08.260 Da habe ich den Automaten. 30:08.940 --> 30:10.040 Den findet man hier wieder. 30:10.640 --> 30:12.920 Und dann den Automaten für die Null. 30:13.060 --> 30:13.680 Das ist der. 30:14.460 --> 30:15.060 Dahinter geklebt. 30:16.360 --> 30:19.600 Und ich habe gesagt, die Endzustände von dem ersten Automaten, das 30:19.600 --> 30:24.280 sind die beiden, simulieren jetzt das Verhalten von dem Startzustand 30:24.280 --> 30:24.920 von dem anderen. 30:25.040 --> 30:26.140 Kriege ich diese Übergänge. 30:26.840 --> 30:30.020 Jetzt merke ich, dass der wieder rausfliegt, wenn ich das vereinfachen 30:30.020 --> 30:30.360 will. 30:32.780 --> 30:37.300 Hier ist jetzt mal Null Eins Punkt Null Eins ein Automat. 30:37.860 --> 30:43.700 Das Null Eins sah ja so aus. 30:44.640 --> 30:46.720 Den klebe ich zweimal hintereinander. 30:50.000 --> 30:55.980 Und diese beiden Endzustände müssen hier den Startzustand nachbauen. 30:56.320 --> 30:57.660 Kriege ich den Automaten. 31:00.760 --> 31:02.280 Und das kann ich so weitermachen. 31:02.420 --> 31:06.700 Ich kann das Ding Produktbildung mit Null Eins Stern Null und dann 31:06.700 --> 31:08.140 Null Eins Null Eins. 31:08.440 --> 31:10.080 Kriege ich diesen Automaten. 31:10.140 --> 31:13.120 Den kann ich noch leicht vereinfachen, indem ich den Startzustand hier 31:13.120 --> 31:13.660 weglasse. 31:17.070 --> 31:19.470 Jetzt habe ich hier einfach nochmal einen Übertrag gemacht. 31:19.470 --> 31:23.770 Das war also jetzt unter Anwendung unserer Konstruktion nicht 31:23.770 --> 31:32.100 deterministischer endlicher Automaten eine Übersetzung dieses 31:32.100 --> 31:34.260 regulären Ausdrucks in den Automaten. 31:34.340 --> 31:36.020 Der sieht ziemlich hässlich aus. 31:37.620 --> 31:41.920 Und tatsächlich ist es so, Sie können die gleiche Sprache akzeptieren 31:41.920 --> 31:45.240 mit diesem ganz einfachen Automaten, der nur vier Zustände hat, 31:45.800 --> 31:47.540 während der hier sieben hatte. 31:50.560 --> 31:51.700 Also gucken Sie sich das nochmal an. 31:51.800 --> 31:55.620 Null Eins Stern, Null, Null Eins, Null Eins. 31:55.960 --> 31:59.900 Okay, Null Eins Stern ist einfach, ich bleibe im Startzustand unter 31:59.900 --> 32:03.280 Eingabe von Null und Eins, kann aber auch nicht deterministisch unter 32:03.280 --> 32:06.380 Eingabe einer Null, die hier ja ist, in den nächsten Zustand 32:06.380 --> 32:06.920 übergehen. 32:07.400 --> 32:11.780 Und dann muss eine Null oder eine Eins kommen und dann noch eine Null 32:11.780 --> 32:14.620 oder eine Eins und dann bin ich fertig und bin im Endzustand. 32:14.620 --> 32:19.780 Also so intuitiv kann man relativ leicht sehen, dass das hier auch 32:19.780 --> 32:20.080 geht. 32:21.400 --> 32:26.720 Aber wir sehen auch schon, das wäre ja spannend, eine Minimierung hier 32:26.720 --> 32:27.180 vorzunehmen. 32:27.260 --> 32:29.640 Kann ich vielleicht, wenn ich diesen nicht deterministischen endlichen 32:29.640 --> 32:33.300 Automaten habe, ihn so umbauen, dass ich den hier kriege? 32:34.000 --> 32:35.920 Eine Minimierung der Zustandszahl. 32:37.000 --> 32:39.600 Und das gleiche könnte man sich natürlich auch überlegen für einen 32:39.600 --> 32:41.280 deterministischen Automaten. 32:43.980 --> 32:47.120 Gibt es an dieser Stelle noch Fragen zu den regulären Ausdrücken? 32:51.360 --> 32:54.780 So, dann haben wir jetzt auch schon die erste Stelle, wo man über 32:54.780 --> 33:00.500 Anwendungen mal reden kann, weil diese Mechanismen, die ich hier 33:00.500 --> 33:04.040 vorgestellt habe, sind halt integraler Bestandteil wichtiger 33:04.040 --> 33:05.740 Werkzeuge. 33:06.620 --> 33:09.180 Zum Beispiel das Unix-Werkzeug GREP. 33:10.120 --> 33:11.440 Wer kennt GREP? 33:13.120 --> 33:14.300 Wer kennt GREP nicht? 33:16.220 --> 33:18.960 Okay, die so halbe halbe habe ich den Eindruck. 33:18.960 --> 33:25.640 Also wenn Sie in Unix oder Linux auf der Kommandozeile eingeben GREP, 33:26.340 --> 33:32.140 einen regulären Ausdruck und dann einen Dateinamen, dann durchsucht er 33:32.140 --> 33:39.100 diese Datei nach allen Vorkommen von Zeichenketten, die zu diesem 33:39.100 --> 33:40.600 regulären Ausdruck passen. 33:43.600 --> 33:46.200 Also das macht er glaube ich Zeile für Zeile. 33:47.060 --> 33:51.200 Und in jeder Zeile sucht er jeden möglichen Startpunkt, lässt den 33:51.200 --> 33:55.840 Automaten da loslaufen und guckt, ob er irgendwo einen Endzustand 33:55.840 --> 33:56.300 erreicht. 33:56.300 --> 34:02.760 Und man kann jetzt diesen regulären Ausdruck, da baut man dann noch 34:02.760 --> 34:08.720 einen Sigma-Stern davor und dann hat man dafür endlich einen Automaten 34:08.720 --> 34:11.560 und dann sucht man nach Endzuständen darin im Endeffekt. 34:14.160 --> 34:22.060 Wenn Sie sich jetzt die Manpages dieses Befehls anschauen, sind die 34:22.060 --> 34:26.440 relativ lang, also es gibt noch deutlich mehr Konstrukte als wir hier 34:26.440 --> 34:30.380 vorgestellt haben, aber die lassen sich alle sehr einfach in diese 34:30.380 --> 34:33.920 rudimentären regulären Ausdrücke, die wir kennengelernt haben, 34:34.300 --> 34:34.800 übersetzen. 34:35.740 --> 34:42.800 Zum Beispiel, es gibt dann so Bereiche, man kann sagen A bis G, also 34:42.800 --> 34:46.800 Buchstaben zwischen A und G, aber das ist ja nichts anderes als die 34:46.800 --> 34:50.360 Vereinigungsmenge A vereinigt B vereinigt C vereinigt D vereinigt F 34:50.360 --> 34:51.080 vereinigt G. 34:52.120 --> 34:56.880 Also das A bis G ist lediglich eine Abkürzung für einen längeren 34:56.880 --> 35:00.160 regulären Ausdruck, den Sie aber auch automatisch generieren können. 35:01.200 --> 35:04.340 Oder es gibt dann vordefinierte Ausdrücke. 35:05.020 --> 35:08.260 Alnum steht, glaube ich, für ein alphanumerisches Zeichen. 35:09.100 --> 35:12.380 Also A bis Z klein, A bis Z groß oder eine Ziffer. 35:12.380 --> 35:19.570 Oder Sie können sagen, vorgegebene Anzahl Wiederholungen. 35:19.890 --> 35:30.150 Und wenn da jetzt steht A 42 Mal wiederholt, dann ist das einfach eine 35:30.150 --> 35:33.350 Abkürzung für A A A A A A A A 42 Mal. 35:38.010 --> 35:43.070 Und der Trick ist, was man dann macht, man übersetzt diesen regulären 35:43.070 --> 35:46.570 Ausdruck in einen nicht-deterministischen endlichen Automaten mit der 35:46.570 --> 35:48.370 Konstruktion, die wir gerade gesehen haben. 35:49.590 --> 35:52.430 Dieser nicht-deterministische endliche Automat wird mit der 35:52.430 --> 35:55.430 Potenzmengen -Konstruktion in einen deterministischen endlichen 35:55.430 --> 35:56.630 Automaten übersetzt. 35:56.630 --> 35:59.150 Was wir noch nicht gesehen haben, man macht da noch eine 35:59.150 --> 36:00.230 Zustandsminimierung. 36:01.730 --> 36:04.690 Hier in der Vorlesung werden wir davon separaten Algorithmus 36:04.690 --> 36:05.290 kennenlernen. 36:05.450 --> 36:09.190 Ich bin nicht sicher, ob die Implementierungen das nicht irgendwie 36:09.190 --> 36:12.210 alles in eins machen, damit sie nicht zwischendurch riesig viel 36:12.210 --> 36:13.050 Speicher brauchen. 36:14.110 --> 36:15.170 Müssen wir mal nachschauen. 36:18.790 --> 36:22.790 Dann füttert man einfach die Buchstaben dieser Datei in diesen 36:22.790 --> 36:24.490 deterministischen endlichen Automaten. 36:25.230 --> 36:30.210 Immer wenn man einem Endzustand endet, wird ein Unterprogramm 36:30.210 --> 36:36.170 aufgerufen, das den matchenden String da ausgibt. 36:38.840 --> 36:42.600 Und das Ganze ist halt sehr schnell, weil Sie müssen eigentlich immer 36:42.600 --> 36:48.660 nur Buchstabe, Zustand, Tabellenzugriff, und dann kriegen Sie den 36:48.660 --> 36:49.440 nächsten Buchstaben. 36:49.560 --> 36:57.240 Also wenn diese Tabelle in den Speicher passt und Sie die Datei zum 36:57.240 --> 37:00.080 Beispiel von einer Platte lesen, dann ist das komplett IO-bound. 37:02.540 --> 37:08.480 Sie können da also mehr oder weniger beliebig schnell nach beliebigen 37:08.480 --> 37:09.880 regulären Ausdrücken suchen. 37:11.220 --> 37:13.800 Wahrscheinlich kann man so eine Denial-of-Service-Attacke 37:13.800 --> 37:17.680 konstruieren, indem man einen regulären Ausdruck wählt, der zu einem 37:17.680 --> 37:19.540 exponentiell großen Automaten führt. 37:19.540 --> 37:21.180 Aber da muss man jetzt aufpassen. 37:31.290 --> 37:37.930 Eine weitere Anwendung sind Scanner-Generatoren. 37:38.110 --> 37:42.930 Das ist die allererste Verarbeitungsstufe in Compilern. 37:46.330 --> 37:49.810 Und da gibt es eben Werkzeuge, die es Ihnen erlauben, so etwas selber 37:49.810 --> 37:50.550 zu generieren. 37:51.110 --> 37:53.770 Also dieser Generator ist sozusagen ein Meta-Werkzeug. 37:53.890 --> 37:57.150 Das ist kein Compiler selber, sondern er hilft Ihnen, einen wichtigen 37:57.150 --> 37:59.170 Teil eines Compilers zu bauen. 38:01.450 --> 38:03.590 Tools, die ich da kenne, sind Lex und Flex. 38:03.910 --> 38:10.050 Wahrscheinlich gibt es inzwischen noch alle möglichen anderen, die 38:10.050 --> 38:11.810 aber dann meistens kompatibel sind dazu. 38:11.810 --> 38:15.230 Also Eingabe des Generators, der kriegt ein System von regulären 38:15.230 --> 38:21.830 Ausdrücken, die Teile einer Programmiersprache beschreiben. 38:22.590 --> 38:28.030 Identifier, Zahl, Schlüsselwörter usw. 38:28.830 --> 38:32.730 Eine Ausgabe ist ein deterministischer ähnlicher Automat, und zwar 38:32.730 --> 38:35.050 implementiert als C-Code. 38:35.050 --> 38:37.630 Da ist es dann zum Teil so, dass der noch nicht mal mehr 38:37.630 --> 38:41.550 Zustandsübergänge macht, sondern das in harte Fallunterscheidungen 38:41.550 --> 38:43.470 codiert, wenn das schneller geht. 38:44.830 --> 38:50.430 Und dieses C-Programm, das dann generiert wird, kriegt zur Laufzeit 38:50.430 --> 38:55.450 das Programm als Zeichenkette und hat als Ausgabe eine Folge von 38:55.450 --> 38:55.870 Token. 38:55.870 --> 39:01.650 Also Token sind nichts anderes als Pakete, die immer für 39:01.650 --> 39:05.970 Teilzeichenketten in der Eingabe stehen, die eben eine bestimmte 39:05.970 --> 39:07.830 Bedeutung in der Programmiersprache haben. 39:08.130 --> 39:12.330 So ein Token könnte sein, hier ist eine Zahl, dort ist ein Bezeichner, 39:12.550 --> 39:17.670 da ist ein Schlüsselwort, Kommentare werden bereits weggeworfen usw. 39:21.770 --> 39:25.890 Dieses Scanner sind sehr zeitkritisch, weil das die einzige Stelle in 39:25.890 --> 39:28.850 einem Compiler ist, die wirklich alle Zeichen einzeln verarbeitet. 39:29.990 --> 39:34.090 Von da an wird dann eben auf dieser Token-Ebene gearbeitet, was 39:34.090 --> 39:38.270 wahrscheinlich in Faktor 10 weniger Objekte sind als die 39:38.270 --> 39:39.790 Eingabezeichen Ihres Programms. 39:42.130 --> 39:46.310 Es werden außerdem Dezimalzahlen bereits in Binärzahlen gewandelt, 39:46.390 --> 39:51.350 Kommentare werden weggelassen, Leerzeichen werden weggelassen und das 39:51.350 --> 39:53.690 Ganze wird auch bis zu einem gewissen Grad schon normiert. 39:56.660 --> 39:57.580 Z.B. 39:58.500 --> 40:01.220 dadurch, dass Leerzeichen weggelassen werden, dass verschiedene 40:01.220 --> 40:05.240 Varianten von Zahlrepräsentationen bereits aufgelöst werden usw. 40:06.020 --> 40:09.680 Und das Ganze vereinfacht dann die nachfolgende Syntaxanalyse. 40:10.980 --> 40:14.220 Fragen zu GREP, Scanner-Generatoren? 40:16.500 --> 40:20.100 Die gleiche Funktionalität findet sich in vielen anderen Werkzeugen 40:20.100 --> 40:20.780 wieder, z.B. 40:21.000 --> 40:23.900 in leistungsfähigen Editoren wie Emacs. 40:24.160 --> 40:24.980 Wer kennt Emacs? 40:27.740 --> 40:29.660 Auch eine ganze Reihe, aber nicht alle. 40:29.660 --> 40:32.480 Es gibt auch andere Script-Sprachen wie Perl oder JavaScript. 40:33.640 --> 40:40.300 Java und C++ haben Bibliotheken, die Regex jeweils heißen und sowas 40:40.300 --> 40:41.060 implementieren. 40:41.180 --> 40:43.380 Im.NET-Framework gibt es sowas auch. 40:44.740 --> 40:48.520 Und beim Parsing von XML-Dokumenten wird auch sowas als 40:48.520 --> 40:50.020 Vorverarbeitungsstufe gemacht. 40:51.540 --> 41:05.520 Also es findet sich eigentlich überall, wo Texte in eine vom Computer 41:05.520 --> 41:08.360 zu verarbeitende Form übersetzt werden. 41:09.580 --> 41:13.060 Und zwar ist es nur so eine Vorverarbeitung, weil wir werden sehen, 41:13.180 --> 41:17.600 dass man Schachtelungen nicht mit abdecken kann. 41:19.480 --> 41:25.560 Aber da man hier besonders mächtige, schnelle Werkzeuge hat, macht man 41:25.560 --> 41:29.360 erstmal den regulären Teil einer Sprache über diese regulären 41:29.360 --> 41:31.480 Ausdrücke, Scanner-Generatoren usw. 41:32.360 --> 41:34.100 Fragen zu den Anwendungen? 41:40.260 --> 41:42.780 Jetzt komme ich zu diesen Epsilon-Übergängen. 41:43.840 --> 41:48.020 Die sind in dieser Vorlesung eigentlich nicht notwendig, man könnte 41:48.020 --> 41:53.060 sie auch weglassen, aber die finden sich in vielen Büchern und machen 41:53.060 --> 41:54.440 auch bestimmte Dinge leichter. 41:55.180 --> 41:58.980 Also ein Epsilon-Übergang erlaubt spontane Übergänge ohne Verbrauch 41:58.980 --> 41:59.660 eines Eingabezeichens. 42:00.660 --> 42:08.680 Und ein Epsilon-Nicht-Deterministischer-Endlicher-Automat ist ganz 42:08.680 --> 42:11.920 ähnlich wie ein normaler Nicht-Deterministischer-Endlicher-Automat. 42:12.480 --> 42:18.180 Der einzige Unterschied ist, dass die Übergangsfunktion nicht paare 42:18.180 --> 42:23.480 Zustand Eingabebuchstaben umwandelt, sondern dass es auch erlaubt ist, 42:24.380 --> 42:27.680 ein paar Zustand Epsilon anzuschauen. 42:30.500 --> 42:33.400 Und die Verarbeitung ist, wie man sich das vorstellt, also das 42:33.400 --> 42:36.600 Eingabeband wird nicht weitergerückt, wenn so ein Epsilon-Übergang 42:36.600 --> 42:37.660 stattfindet. 42:38.620 --> 42:42.620 Fragen zur Definition von Epsilon-NFAs? 42:45.080 --> 42:48.620 Für Epsilon-Deterministische-Automaten sind irgendwie nicht so 42:48.620 --> 42:49.660 spannend, weil... 42:51.220 --> 42:54.460 Ich könnte jetzt rein syntaktisch einen Deterministischen-Endlichen 42:54.460 --> 42:59.560 -Automaten nehmen und dem zusätzlich Epsilon-Übergänge erlauben, aber 42:59.560 --> 43:03.960 dann kriege ich sozusagen die Nicht-Determinismus durch die Hintertür 43:03.960 --> 43:04.720 wieder mit rein. 43:05.560 --> 43:08.080 Also das macht keinen Sinn, den anzuschauen. 43:10.320 --> 43:18.860 Und hier ist es jetzt so, wir können eigentlich diese Operatoren der 43:18.860 --> 43:23.240 regulären Ausdrücke hier noch viel natürlicher verarbeiten, als das 43:23.240 --> 43:23.840 eben war. 43:24.280 --> 43:28.080 Weil da mussten wir mal sagen, dieser Zustand muss auf zwei Hochzeiten 43:28.080 --> 43:31.660 tanzen, irgendeinen anderen nachbauen und das kann ich jetzt einfach 43:31.660 --> 43:33.000 durch Epsilon-Übergänge machen. 43:33.000 --> 43:37.840 Wenn ich zum Beispiel jetzt Nicht-Deterministische-Endliche-Automaten 43:37.840 --> 43:41.940 für 0 Stern und 1 Stern habe, dann kann ich einen für die 43:41.940 --> 43:45.340 Vereinigungsmenge machen, indem ich einfach einen neuen Startzustand 43:45.340 --> 43:51.640 nehme und Epsilon-Übergänge zu den Startzuständen der Teilautomaten 43:51.640 --> 43:51.920 nehme. 43:52.280 --> 43:56.940 Das funktioniert für beliebige Vereinigungsmengen-Operationen. 43:58.600 --> 44:00.300 Nichts anderes steht hier auch. 44:02.600 --> 44:06.760 Also damit würde dieser Beweis nochmal viel einfacher, den wir eben 44:06.760 --> 44:07.440 gemacht haben. 44:08.000 --> 44:11.500 Aber wir müssten natürlich dann einen zusätzlichen Beweis einbauen, 44:12.600 --> 44:17.900 wie man einen Epsilon-NFA transformiert in einen NFA und da kommt die 44:17.900 --> 44:19.460 ganze Komplexität wieder hoch. 44:20.760 --> 44:23.600 Deshalb habe ich mir gesagt, das sparen wir uns und ich erkläre Ihnen 44:23.600 --> 44:24.980 nur, wie das grundsätzlich geht. 44:27.940 --> 44:31.620 Also jetzt ist die Konstruktion für die Vereinigungsmenge ganz 44:31.620 --> 44:32.000 trivial. 44:32.260 --> 44:37.360 Wir haben Automaten A1 und A2 mit disjunkten Zustandsmengen. 44:37.440 --> 44:41.440 Der neue Automat ist die Zustandsmengen der beiden alten Automaten, 44:41.540 --> 44:42.580 neuer Zustand S. 44:44.740 --> 44:47.180 Endzustandsmenge ist einfach die Vereinigung der beiden 44:47.180 --> 44:50.120 Endzustandsmengen, Startzustand ist S. 44:54.300 --> 44:59.680 Und ich habe spontane Zustandsübergänge von S nach S1 bzw. 44:59.820 --> 45:00.620 S nach S2. 45:02.760 --> 45:12.700 Also Delta S, Epsilon ist gleich S1, aber auch Delta S, Epsilon ist S1 45:12.700 --> 45:13.620 vereinigt S2. 45:14.940 --> 45:16.940 Fragen zu der Konstruktion? 45:20.920 --> 45:23.140 Genauso einfach geht das mit der Produktmenge. 45:23.780 --> 45:28.760 Da ist das jetzt so, dass ich einfach die Endzustände von A1 nehme und 45:28.760 --> 45:33.560 Epsilon -Übergänge zum Startzustand von A2 einführe. 45:35.660 --> 45:36.800 Und mehr brauche ich nicht tun. 45:37.760 --> 45:42.040 Vorher war das so, dass die Endzustände von A1 dann S2 nachbauen 45:42.040 --> 45:45.140 mussten, jetzt gehen sie da einfach mit einem leeren Übergang rüber. 45:46.300 --> 45:48.580 So ähnlich ist das bei der positiven Hülle. 45:49.700 --> 45:55.220 Dann nehme ich einfach den Automaten A für die Teilwörter und mache 45:55.220 --> 45:59.600 Epsilon -Übergänge von den Endzuständen von A zum Startzustand von A 45:59.600 --> 46:00.620 dazu. 46:01.320 --> 46:04.180 Und schon habe ich einen Automaten für die positive Hülle. 46:06.240 --> 46:07.040 Fragen dazu? 46:10.740 --> 46:17.240 Jetzt ganz kurz eine Skizze, wie ich einen Epsilon-NFA A in einen 46:17.240 --> 46:19.900 normalen NFA A quer überführe. 46:28.700 --> 46:35.400 Da ist es einfach so, ich gucke mir den Automaten-Graphen hier an und 46:35.400 --> 46:44.460 da gibt es jetzt Pfade der Form Epsilon-Übergang und dann einen 46:44.460 --> 46:46.400 einzelnen Übergang mit einem Buchstaben. 46:47.700 --> 46:50.580 Die suche ich mir alle, das können sehr viele sein, aber es sind 46:50.580 --> 46:51.220 endlich viele. 46:52.880 --> 46:58.560 Und für jeden dieser Pfade der Länge 2 führe ich einen explizit neuen 46:58.560 --> 46:59.980 Übergang in A quer ein. 47:01.460 --> 47:04.400 Und man muss dann noch ein bisschen aufpassen mit den Endzuständen. 47:05.300 --> 47:08.500 Aber mehr sage ich dazu nicht, weil ich habe das hier wirklich nur 47:08.500 --> 47:11.420 eingeführt, damit man mal gesehen hat, was ein Epsilon-Übergang ist. 47:11.420 --> 47:14.980 Wir brauchen diese Konstruktionen irgendwo anders, deshalb verzichte 47:14.980 --> 47:17.060 ich hier auf den detaillierten Beweis. 47:17.620 --> 47:19.880 Wäre aber sicherlich auch eine schöne Übung. 47:22.880 --> 47:24.900 Fragen zu Epsilon-Übergängen? 47:31.150 --> 47:34.050 Genau, also was wir jetzt haben ist, wir wissen bereits, dass 47:34.050 --> 47:38.170 deterministische Endlichautomaten, Chomsky-3-Grammatiken und nicht 47:38.170 --> 47:39.590 -deterministische Äquivalent sind. 47:40.010 --> 47:42.690 Wir können reguläre Ausdrücke in nicht-deterministische übersetzen. 47:45.110 --> 47:49.430 Ich könnte jetzt dazwischen noch ein Epsilon-NFA schreiben, wenn ich 47:49.430 --> 47:51.310 diese Übersetzung zweischrittig mache. 47:52.610 --> 47:55.050 Aber was jetzt noch fehlt, ist dieser Übergang. 47:55.110 --> 47:59.210 Wie komme ich von einem deterministischen Endlichen Automaten zu einem 47:59.210 --> 48:00.150 regulären Ausdruck? 48:00.870 --> 48:04.270 Und das ist tatsächlich jetzt so ein bisschen gegen den Strich 48:04.270 --> 48:05.330 gebürstet, sage ich mal. 48:05.390 --> 48:07.990 Da müssen wir eine etwas komplexere Konstruktion bauen. 48:10.250 --> 48:13.430 Trotzdem ist das aus theoretischer Sicht sicherlich sinnvoll. 48:14.010 --> 48:15.670 Wir wollen ja keinen Sprachen-Zoo. 48:15.770 --> 48:19.630 Wir wollen ja nicht, dass jemand sagt, naja, vielleicht ist es so, 48:20.150 --> 48:24.810 dass es irgendwie Chomsky-3-Grammatiken oder nicht-deterministische 48:24.810 --> 48:27.550 Endlichautomaten oder was immer gibt, die sich nicht durch einen 48:27.550 --> 48:29.190 regulären Ausdruck beschreiben lassen. 48:33.070 --> 48:34.810 Und das will man eigentlich nicht. 48:35.770 --> 48:38.670 Vor allem, weil diese regulären Ausdrücke damit dann zu einem 48:38.670 --> 48:40.290 universellen Interface werden. 48:40.670 --> 48:43.070 Die sind für die Menschen noch am leichtesten lesbar. 48:44.790 --> 48:49.070 Außer vielleicht diesen Automatenbildern, die aber wiederum für einen 48:49.070 --> 48:50.630 Computer schlecht lesbar sind. 48:51.130 --> 48:54.130 Also reguläre Ausdrücke sind irgendwas, was sowohl der Computer als 48:54.130 --> 48:56.210 auch ein Mensch ganz gut handhaben können. 48:57.230 --> 49:04.810 Und man könnte auch argumentieren, dass man vielleicht irgendwo einen 49:04.810 --> 49:08.130 deterministischen Endlichen Automaten in einem Binary oder so findet 49:08.130 --> 49:10.330 und verstehen will, was der tut. 49:10.970 --> 49:16.030 Und den dann in einem Menschen lesbare Form überführt als regulärer 49:16.030 --> 49:16.450 Ausdruck. 49:17.630 --> 49:23.050 Ja, wir werden allerdings sehen, dass die Konstruktion, die wir gleich 49:23.050 --> 49:27.810 verwenden, zu regulären Ausdrücken führt, die alles andere als 49:27.810 --> 49:29.730 menschenlesbar sind. 49:30.530 --> 49:33.910 Das heißt, wenn Sie das wirklich verwenden wollten, müssten Sie 49:33.910 --> 49:38.350 zusätzlich noch irgendwie einen Vereinfacher für reguläre Ausdrücke 49:38.350 --> 49:38.730 bauen. 49:39.290 --> 49:43.610 Der dann irgendwie algebraische Ersetzungsregeln oder sowas macht, 49:43.710 --> 49:44.150 keine Ahnung. 49:46.910 --> 49:49.710 Jedenfalls das Reverse Engineering wird in den Büchern manchmal 49:49.710 --> 49:51.810 angegeben und ich bezweifle das so ein bisschen. 49:52.930 --> 49:55.490 Aber es ist trotzdem etwas, was man sich überlegen kann. 49:57.950 --> 50:01.630 Also, wir wollen jetzt beweisen, gegeben ein deterministischer 50:01.630 --> 50:08.390 Endlichen Automat A besucht ein regulärer Ausdruck Alpha mit L von A 50:08.390 --> 50:09.390 gleich L von Alpha. 50:10.190 --> 50:10.750 Ja. 50:12.790 --> 50:16.330 Und wir werden jetzt in mehreren Schritten das Problem vereinfachen, 50:16.450 --> 50:20.130 aber so, dass das Ganze OBDA ist, beziehungsweise dass wir am Ende 50:20.130 --> 50:22.150 dann das Endergebnis ablesen können. 50:23.250 --> 50:28.590 Der erste Schritt ist, dass wir uns jeden Endzustand von A einzeln 50:28.590 --> 50:29.190 anschauen. 50:29.190 --> 50:37.010 Wir definieren jetzt Lf als die Menge der Wörter, die halt in L von A 50:37.010 --> 50:39.190 sind, aber im Zustand F enden. 50:41.430 --> 50:45.450 Das heißt formal, das ist die Menge aller W in Sigma Stern, für die 50:45.450 --> 50:47.830 gilt Delta Dach von S, W ist gleich F. 50:48.750 --> 50:50.110 So, warum ist das OBDA? 50:50.110 --> 50:56.830 Na ja, ganz einfach, wenn wir die Lf's kennen für alle F, können wir 50:56.830 --> 51:03.150 einfach sagen, wir bilden die Vereinigungsmenge über alle Lf. 51:05.250 --> 51:08.450 Und das ist ja einfach, das ist ja ein Operator für reguläre 51:08.450 --> 51:08.910 Ausdrücke. 51:09.270 --> 51:13.430 Also wir nehmen die regulären Ausdrücke für die Lf's und hängen die 51:13.430 --> 51:16.510 mit dem Vereinigungsoperator alle hintereinander und dann haben wir 51:16.510 --> 51:17.910 einen regulären Ausdruck für L. 51:19.150 --> 51:22.870 Also wir haben das Ganze jetzt vereinfacht, wir müssen nur noch 51:22.870 --> 51:26.410 endliche Automaten anschauen, die einen einzigen Endzustand haben. 51:28.290 --> 51:34.030 Also das Problem ist jetzt gegeben, ein endlicher Automat Af mit 51:34.030 --> 51:39.850 Endzustandsmenge ein einzelnes Element F und wir machen eine weitere 51:39.850 --> 51:40.930 Verallgemeinerung. 51:41.750 --> 51:48.070 Wir nehmen jetzt an, dass unsere Zustandsmenge einfach die Zahlen von 51:48.070 --> 51:49.110 1 bis N sind. 51:49.730 --> 51:54.110 Das ist auch OBDA, ich kann andere Zustandsmengen ja durch Umbenennung 51:54.110 --> 51:56.250 entsprechend transformieren. 51:58.430 --> 52:03.130 Und wir suchen einen regulären Ausdruck, Alpha mit Lf gleich L von Af. 52:04.550 --> 52:14.670 So, jetzt definiere ich neue Sprachen, ganz viele, nämlich Lij sei die 52:14.670 --> 52:18.090 Sprache, die von einem neuen Automaten akzeptiert wird, nämlich der 52:18.090 --> 52:23.130 hat die gleiche Zustandsmenge, die gleiche Übergangsfunktion, aber I 52:23.130 --> 52:26.270 ist der Startzustand und J ist der Endzustand. 52:27.390 --> 52:30.730 Also ich gucke mir jetzt an, ich nehme diesen Automaten, vergesse 52:30.730 --> 52:34.410 erstmal, was Start- und Endzustand ist und gucke mir für alle Paare 52:34.410 --> 52:38.630 von Zuständen an, was wäre denn, wenn das hier der Startzustand und 52:38.630 --> 52:39.650 das hier der Endzustand ist. 52:39.770 --> 52:41.270 I ist der Startzustand, J der Endzustand. 52:43.710 --> 52:50.710 Wenn ich das gemacht habe, dann kann ich Lf einfach als Lsf ablesen. 52:54.370 --> 52:58.010 Das ist jetzt so ein bisschen die gleiche Idee wie in Algorithmen 1 52:58.010 --> 52:59.410 bei dynamischer Programmierung. 53:00.190 --> 53:06.570 Ich baue ganz viele Teillösungen und kann die dann benutzen, um die 53:06.570 --> 53:09.130 Gesamtlösung abzulesen. 53:11.470 --> 53:17.730 So, jetzt haben wir ganz viele Sprachen und jetzt mache ich es noch 53:17.730 --> 53:18.530 komplizierter. 53:18.530 --> 53:21.570 Ich definiere eine Sprache Lijm. 53:21.710 --> 53:26.270 Also für jedes Lij definiere ich neue Sprachen Lijm. 53:27.450 --> 53:30.630 Und das sind aber jetzt wieder Vereinfachungen oder Einschränkungen. 53:32.170 --> 53:36.730 Lijm ist nämlich die Menge aller Worte aus Sigma Stern, die auf eine 53:36.730 --> 53:39.190 ganz bestimmte Weise akzeptiert werden. 53:39.710 --> 53:46.370 Von diesem Automaten, der I als Startzustand und J als Endzustand hat. 53:47.150 --> 53:51.690 Nämlich es gibt einen Abarbeitungsfad, der mit I anfängt und J endet. 53:53.590 --> 53:59.570 Und zusätzlich die Eigenschaft hat, der fängt mit I an, endet mit J. 53:59.650 --> 54:01.370 Dazwischen sind andere Zustände. 54:04.570 --> 54:07.750 Die dürfen aber nur die Zustände 1 bis M benutzen. 54:10.150 --> 54:14.030 Also ich schränke die Zustandsmenge ein, außer den Start- und 54:14.030 --> 54:14.710 Endzustand. 54:16.370 --> 54:24.390 Und das Lij ist dann einfach L-I-J-N, wo bei N die Gesamtanzahl 54:24.390 --> 54:25.190 Zustände ist. 54:26.030 --> 54:28.210 Das ist wieder wie bei dynamischer Programmierung. 54:28.310 --> 54:33.590 Ich baue jetzt Automaten auf, die nur eine Teilmenge der Zustände 54:33.590 --> 54:35.190 benutzen dürfen, schrittweise. 54:35.810 --> 54:38.930 Und baue daraus aber immer komplexere, die immer mehr Zustände 54:38.930 --> 54:39.730 benutzen dürfen. 54:40.610 --> 54:42.990 Und da müssen wir uns jetzt angucken, wie das funktioniert. 54:44.870 --> 54:46.610 Also nochmal, Definition. 54:47.890 --> 54:51.270 Lijm ist die Menge aller Sigma-Sternen mit der Eigenschaft, dass es 54:51.270 --> 54:54.950 einen Abarbeitungsfad gibt, der bei I anfängt, bei J endet. 54:55.190 --> 54:56.310 Die Eingabe ist W. 54:57.450 --> 54:59.110 Der hat die Form I, P, J. 54:59.850 --> 55:04.490 Und P ist eine Zeichenfolge von 1 bis M, aus 1 bis M Sternen. 55:04.570 --> 55:07.210 Also es werden nur die Zustände 1 bis M verwendet. 55:14.330 --> 55:17.930 Und ich mache jetzt eine induktive Konstruktion. 55:18.110 --> 55:25.750 Ich nehme also an, dass für alle k kleiner m, ich bereits reguläre 55:25.750 --> 55:29.650 Ausdrücke, passende reguläre Ausdrücke habe. 55:30.070 --> 55:36.590 Also reguläre Ausdrücke Alpha IJK mit der Eigenschaft, dass L von 55:36.590 --> 55:40.870 Alpha IJK gleich LIJK ist. 55:48.950 --> 55:49.470 Genau. 55:49.650 --> 55:55.870 Und aus denen baue ich ein Alpha IJM, das die Eigenschaft hat, dass L 55:55.870 --> 55:57.490 davon das LIJM ist. 55:58.510 --> 55:59.030 Gut. 55:59.130 --> 56:00.330 Induktive Konstruktion. 56:00.410 --> 56:03.250 Dafür brauche ich immer einen Basisfall für M gleich 0. 56:04.430 --> 56:06.510 Da mache ich zwei Fallunterscheidungen. 56:06.650 --> 56:08.350 M gleich 0 und I gleich J. 56:08.910 --> 56:11.830 Bedeutet nichts anderes, als ich gucke mir die Pfade an, die bei I 56:11.830 --> 56:14.590 starten und I enden und dazwischen passiert gar nichts. 56:15.510 --> 56:16.810 Das ist ganz einfach. 56:22.360 --> 56:30.520 Das kann entweder das leere Wort sein oder ich habe eine Folge von 56:30.520 --> 56:32.720 Zustandsübergängen von I in sich selber. 56:34.460 --> 56:35.920 Und mehr habe ich hier nicht geschrieben. 56:36.180 --> 56:41.120 Also das ist Epsilon vereinigt mit der Vereinigung von allen A in 56:41.120 --> 56:43.520 Sigma, für die gilt Delta I, A gleich I. 56:45.860 --> 56:47.460 Die Gleichheit darf ich hier machen. 56:47.580 --> 56:49.420 Wir sind wieder bei deterministischen Automaten. 56:49.640 --> 56:51.580 Delta ist einfach ein neuer Zustand. 56:56.320 --> 56:59.300 Und das hier ist eine endliche Menge von Buchstaben. 56:59.400 --> 57:01.320 Das kann ich einfach so hintereinander schreiben. 57:02.000 --> 57:06.180 Endlich viele Anwendungen dieses Vereinigungsmengenoperators und dann 57:06.180 --> 57:09.980 entsprechend einen regulären Ausdruck dafür bauen. 57:09.980 --> 57:17.380 Der Basisfall für I ungleich J ist sogar noch einfacher, weil in 57:17.380 --> 57:22.640 deterministischen endlichen Automaten, damit ich tatsächlich irgendwo 57:22.640 --> 57:36.960 hinkomme, muss 57:40.730 --> 57:44.210 ich tatsächlich auch was eingeben. 57:44.350 --> 57:46.750 Also das Epsilon kann nicht passieren, ansonsten ist es das gleiche 57:46.750 --> 57:47.070 wie hier. 57:47.070 --> 57:52.430 Das ist Vereinigung aller A in Sigma, für die gilt, dass Delta I, A 57:52.430 --> 57:53.050 gleich J ist. 57:54.390 --> 57:57.050 Das sind alles einbuchstabige Sprachen. 58:00.550 --> 58:02.470 Und ich habe das hier so ein bisschen illustriert. 58:02.730 --> 58:05.990 Also wie sieht das aus? 58:06.070 --> 58:11.250 Der Automat, den ich dann habe, ist Startzustand gleich Endzustand, 58:11.310 --> 58:11.990 Eingabe A. 58:11.990 --> 58:16.810 Die anderen Übergänge vom Zustand I lasse ich sozusagen weg. 58:17.410 --> 58:18.750 Erlaube ich nicht, schaue ich nicht an. 58:19.310 --> 58:23.690 Und hier ist dieser Automat, den ich mir angucke für diesen Fall. 58:24.530 --> 58:26.410 Und jetzt kommt natürlich der spannende Schritt. 58:27.090 --> 58:28.910 Schritt von M nach M plus 1. 58:29.610 --> 58:31.550 Jetzt gucke ich mir am besten mal dieses Bild an. 58:32.350 --> 58:36.150 Das sieht jetzt aus wie ein endlicher Automat, ist es aber nicht ganz, 58:36.290 --> 58:40.450 weil ich habe hier zwar den Startzustand markiert und den Endzustand, 58:41.110 --> 58:43.810 aber mich interessieren jetzt eigentlich die Eingaben nicht. 58:43.930 --> 58:49.570 Das ist eher so eine abstrakte Repräsentation möglicher Pfade in dem 58:49.570 --> 58:50.590 Graphen. 58:51.170 --> 58:56.170 Wie kann denn so ein Pfad aussehen, der nur die Zustände 1 bis M 58:56.170 --> 59:00.050 annimmt, zwischen dem Zustand I und dem Zustand J? 59:00.870 --> 59:05.030 Naja, es gibt einen Fall, ich nehme nur die Buchstaben 1 bis M, die 59:05.030 --> 59:08.770 Zustände 1 bis M, den kenne ich schon. 59:08.770 --> 59:14.810 Oder aber ich mache Zustände 1 bis M und dann irgendwann kommt das 59:14.810 --> 59:19.990 erste Mal der Zustand M plus 1 und dann kann ich aber beliebig oft 59:19.990 --> 59:24.050 dazwischen wieder Zustände 1 bis M einnehmen und dann nochmal M plus 1 59:24.050 --> 59:26.910 und dann 1 bis M und dann J. 59:28.110 --> 59:29.370 Wobei das auch leer sein kann. 59:29.370 --> 59:29.830 Frage? 59:38.250 --> 59:39.210 Schockiertes Abreisen. 59:48.110 --> 59:52.030 Das ist jetzt eher so ein konzeptionelles Bild, das zeigt, was kann da 59:52.030 --> 59:55.290 passieren und das kann ich aber nachbauen durch reguläre Ausdrücke. 59:55.290 --> 59:59.850 Weil dieser Pfad, das ist einfach Alpha I, J, M, den kenne ich schon. 01:00:01.210 --> 01:00:04.790 Und die Vereinigung mit diesem Ding hier. 01:00:05.370 --> 01:00:06.410 Wie sieht das Ding aus? 01:00:06.550 --> 01:00:16.090 Erst irgendwas aus Alpha I, I nach M plus 1 unter Verwendung der 01:00:16.090 --> 01:00:17.310 Zustände 1 bis M. 01:00:18.110 --> 01:00:22.450 Also ich starte in I, ende in M plus 1, verwende zwischendurch nur 01:00:22.450 --> 01:00:23.590 Sachen von 1 bis M. 01:00:24.070 --> 01:00:26.070 Das ist dieser Teil von dem Pfad. 01:00:32.380 --> 01:00:35.660 Dann darf ich beliebig oft, das ist hier diese klinische Hülle, 01:00:38.160 --> 01:00:42.720 starten in M plus 1, enden in M plus 1 und dazwischen aber nur 1 bis M 01:00:42.720 --> 01:00:43.240 verwenden. 01:00:45.220 --> 01:00:45.700 Produkt. 01:00:46.640 --> 01:00:55.320 Also erst das, dann das hier beliebig oft und dann wieder das. 01:00:55.820 --> 01:01:01.100 Alpha M, ich starte in M plus 1, ende in J, darf zwischendurch nur 1 01:01:01.100 --> 01:01:01.900 bis M verwenden. 01:01:02.320 --> 01:01:07.180 Das heißt, ich habe sozusagen diesen Graphen nachgebaut durch einen 01:01:07.180 --> 01:01:08.120 regulären Ausdruck. 01:01:10.320 --> 01:01:14.140 Und diese Konstruktion muss ich jetzt mehrfach hintereinander anwenden 01:01:14.140 --> 01:01:15.040 für jeden Zustand. 01:01:16.660 --> 01:01:17.420 Mal ein Beispiel. 01:01:24.390 --> 01:01:28.130 Ich habe folgenden nicht deterministisch ähnlichen Automaten mit zwei 01:01:28.130 --> 01:01:29.750 Zuständen, 1 und 2. 01:01:31.230 --> 01:01:33.350 Mit nur einem Endzustand, das ist die 2. 01:01:33.910 --> 01:01:36.690 Und jetzt muss ich diese Alphas bauen. 01:01:36.690 --> 01:01:40.490 Und da fange ich an mit dem Null im Exponenten. 01:01:40.550 --> 01:01:47.430 Alpha 1, 1, 0, Alpha 2, 2, 0, Alpha 1, 2, 0 und Alpha 2, 1, 0. 01:01:51.800 --> 01:01:56.200 Und dann kann ich mir überlegen, wie die aussehen. 01:01:56.880 --> 01:01:59.760 Da habe ich diese Basisfälle einfach eingesetzt. 01:02:00.920 --> 01:02:08.060 Alpha 1, 1, 0 ist 1 vereinigt Epsilon, weil ich habe einen Übergang 01:02:08.060 --> 01:02:10.040 von 1 nach 1 mit 1. 01:02:10.660 --> 01:02:11.960 Oder ich bleibe halt da. 01:02:12.980 --> 01:02:16.300 Alpha 2, 2, 0 ist analog, 0 vereinigt Epsilon. 01:02:17.440 --> 01:02:20.260 Während die anderen Übergänge gehen ja da raus, das ist hier nicht 01:02:20.260 --> 01:02:20.820 erlaubt. 01:02:21.160 --> 01:02:24.940 Oder Alpha 1, 2, 0, wie komme ich von 1 nach 2? 01:02:24.940 --> 01:02:26.540 Na ja, nur mit einer Null. 01:02:27.060 --> 01:02:31.540 Und von 2 nach 1 komme ich nur mit einer 1 direkt, ohne was 01:02:31.540 --> 01:02:32.020 dazwischen. 01:02:32.460 --> 01:02:33.800 Das sind unsere Basisfälle. 01:02:34.640 --> 01:02:37.220 Jetzt setze ich einfach diese Konstruktion ein. 01:02:37.320 --> 01:02:42.620 Alpha 1, 2, 1 ist Alpha 1, 2, 0 vereinigt Alpha 1, 1, 0. 01:02:43.280 --> 01:02:47.240 Alpha 1, 1, 0 Stern Alpha 1, 2, 0. 01:02:48.120 --> 01:02:53.100 Und so ähnlich Alpha 2, 2, 1 ist Alpha 2, 2, 0 vereinigt Alpha 2, 1, 01:02:53.160 --> 01:02:53.440 0. 01:02:54.920 --> 01:02:58.100 Alpha 1, 1, 0 Stern Alpha 1, 2, 0. 01:02:58.760 --> 01:03:02.780 Und dann habe ich die hier, das ist einfach die Konstruktion eben. 01:03:03.160 --> 01:03:04.820 Und die habe ich jetzt mal vereinfacht. 01:03:06.280 --> 01:03:09.240 Also indem ich diese Alphas da einsetze, dann kriege ich hier 0 01:03:09.240 --> 01:03:14.320 vereinigt 1, vereinigt Epsilon, 1 vereinigt Epsilon Stern, 0. 01:03:14.900 --> 01:03:17.940 Und die habe ich jetzt manuell mal vereinfacht, das ist 1 Stern 0. 01:03:17.940 --> 01:03:20.240 Damit man das Ganze am Ende noch lesen kann. 01:03:20.360 --> 01:03:23.060 Und das hier ist 1 Stern 0 oder Epsilon. 01:03:24.380 --> 01:03:30.540 Jetzt nächste Konstruktion Alpha 1, 2, 2 ist Alpha 1, 2, 1 vereinigt 01:03:30.540 --> 01:03:31.880 Alpha 1, 2, 1. 01:03:32.240 --> 01:03:37.220 Und dann Alpha 2, 2, 1 Stern Alpha 2, 2, 1. 01:03:37.300 --> 01:03:41.340 Die kann ich hier ablesen, die Ausdrücke dafür hier einsetzen. 01:03:41.600 --> 01:03:44.620 Also ich habe jetzt die vereinfachten Sachen schon eingesetzt. 01:03:44.620 --> 01:03:47.160 Und dann kriege ich halt dieses Gerät hier. 01:03:48.220 --> 01:03:50.320 Und das habe ich wieder manuell vereinfacht. 01:03:53.840 --> 01:03:58.100 Und das ist Alpha 1, 2, 2 ist jetzt schon das, was ich haben will. 01:03:58.860 --> 01:04:03.040 Weil 1 ist ja mein Startzustand des Automaten, 2 ist der echte 01:04:03.040 --> 01:04:03.840 Endzustand. 01:04:04.520 --> 01:04:09.400 Und es gibt sowieso nur zwei Zustände, sodass das 2 hier bereits alle 01:04:09.400 --> 01:04:10.540 Zustände erlaubt. 01:04:11.400 --> 01:04:15.060 Und damit habe ich einen regulären Ausdruck für mein Ding. 01:04:15.480 --> 01:04:19.400 Wenn ich hier diese manuelle Vereinfachung nicht gemacht hätte, würde 01:04:19.400 --> 01:04:21.860 das wahrscheinlich gar nicht mehr auf eine Zeile passen. 01:04:21.960 --> 01:04:24.700 Obwohl das hier ein total simpler regulärer Ausdruck ist. 01:04:25.060 --> 01:04:27.060 Das muss man sich bedenken dabei. 01:04:27.660 --> 01:04:30.300 Aber wir haben eine systematische Konstruktion dafür. 01:04:31.700 --> 01:04:32.920 Fragen dazu? 01:04:40.320 --> 01:04:44.220 So, das schließt jetzt einen wichtigen Teil über reguläre Ausdrücke 01:04:44.220 --> 01:04:44.520 ab. 01:04:45.860 --> 01:04:47.200 Jetzt schon aufzuhören. 01:04:47.280 --> 01:04:50.580 Es ist ein bisschen früh, deshalb einmal kräftig durchatmen. 01:04:51.260 --> 01:04:54.820 Und es kommt ein anderes, sehr kurzes, aber sehr wichtiges Teil, 01:04:54.940 --> 01:04:55.300 Kapitel. 01:04:58.300 --> 01:05:06.820 Wir haben uns ja angeschaut, dieses Bild für die Chomsky-Hierarchie. 01:05:07.720 --> 01:05:13.320 L3, L2, L1, L0 hatten da jeweils Beispiele für konstruiert. 01:05:13.320 --> 01:05:21.960 Aber wir hatten noch nicht bewiesen, dass sozusagen der Level genau 01:05:21.960 --> 01:05:22.840 der richtige war. 01:05:23.040 --> 01:05:26.700 Wir hatten zum Beispiel diese Sprache A hoch N, B hoch N als Typ-2 01:05:26.700 --> 01:05:28.100 -Sprache klassifiziert. 01:05:28.760 --> 01:05:32.700 Und wir hatten gezeigt, dass sie tatsächlich in Chomsky-II drin ist, 01:05:32.880 --> 01:05:37.860 indem wir eine Typ-2-Grammatik angegeben haben, die A hoch N, B hoch N 01:05:37.860 --> 01:05:38.660 akzeptiert. 01:05:42.180 --> 01:05:45.880 Aber wir haben noch nicht gezeigt, dass man nicht vielleicht auch eine 01:05:45.880 --> 01:05:47.960 Chomsky -III-Grammatik angeben könnte. 01:05:49.260 --> 01:05:53.880 Dieses Pumping Lemma erlaubt uns gerade solche Aussagen. 01:05:58.540 --> 01:06:00.240 Also, was ist das Pumping Lemma? 01:06:00.320 --> 01:06:02.000 Ich sage es erstmal in natürlichen Wörtern. 01:06:02.940 --> 01:06:07.800 Das sagt, hinreichend lange Worte einer regulären Sprache lassen sich 01:06:07.800 --> 01:06:12.940 durch Wiederholung eines nicht-trivialen Mittelteils aufpumpen. 01:06:14.200 --> 01:06:17.440 Und wenn man genauer hinguckt, steht hier noch ein bisschen mehr. 01:06:17.520 --> 01:06:21.840 Man kann sie nämlich auch ein bisschen zusammenschrumpfen, als einen 01:06:21.840 --> 01:06:23.120 Spezialfall davon. 01:06:27.710 --> 01:06:30.130 Und ja, dieser Mittelteil ist nicht trivial. 01:06:30.590 --> 01:06:33.930 Also, wenn es erlaubt wäre, dass so ein Mittelteil das leere Wort ist, 01:06:34.030 --> 01:06:37.670 wäre das eine triviale, wenig nützliche Aussage. 01:06:40.710 --> 01:06:42.450 Jetzt gucken wir uns das mal formal an. 01:06:42.590 --> 01:06:43.810 Also, was sagen wir hier genau? 01:06:47.250 --> 01:06:48.750 L ist regulär. 01:06:50.170 --> 01:06:55.750 Das bedeutet, es gibt eine natürliche Zahl n, sodass für alle Wörter 01:06:55.750 --> 01:07:00.970 mit Länge mindestens n in der Sprache Folgendes gilt. 01:07:01.950 --> 01:07:07.050 Das Wort w lässt sich zerlegen in Teilwörter u, v, x mit der 01:07:07.050 --> 01:07:09.550 Eigenschaft, dass v nicht leer ist. 01:07:09.550 --> 01:07:11.370 Also, v-Betrag größer gleich 1. 01:07:12.090 --> 01:07:15.770 Und eine Zusatzsache, die wir nicht immer brauchen, aber die halt 01:07:15.770 --> 01:07:17.030 außerdem auch noch gilt. 01:07:17.590 --> 01:07:19.750 Die Länge von u, v ist kleiner gleich n. 01:07:21.110 --> 01:07:23.730 Also, das sagt jetzt, wie kann ich das aufteilen. 01:07:24.210 --> 01:07:26.030 Und jetzt kommt der eigentliche Pumpteil. 01:07:29.230 --> 01:07:32.650 Bei dieser Faktorisierung kann ich jetzt hergehen und das v beliebig 01:07:32.650 --> 01:07:34.670 oft wiederholen. 01:07:34.670 --> 01:07:35.810 Und zwar auch nullmal. 01:07:36.270 --> 01:07:38.790 Ich kann es also auch weglassen und kriege wieder ein Wort in der 01:07:38.790 --> 01:07:39.210 Sprache. 01:07:40.930 --> 01:07:44.250 Das ist jetzt auf den ersten Blick überraschend. 01:07:44.650 --> 01:07:48.610 Also, wir haben irgendwie einen relativ allgemeinen Mechanismus, 01:07:48.710 --> 01:07:52.230 ähnliche Automaten, reguläre Ausdrücke, was immer. 01:07:53.170 --> 01:07:56.990 Und jetzt kann ich plötzlich Wörter nehmen, zerlegen und einfach 01:07:56.990 --> 01:07:59.550 Sachen wiederholen. 01:08:00.950 --> 01:08:02.110 Warum ist das so? 01:08:02.530 --> 01:08:04.830 Aber der Beweis ist eigentlich ziemlich einfach. 01:08:06.250 --> 01:08:08.670 Sie müssen sich eigentlich nur dieses Bild hier anschauen. 01:08:12.050 --> 01:08:15.890 Das heißt, vielleicht fangen wir doch mal mit dem formalen Beweis an. 01:08:16.110 --> 01:08:18.550 Also, die ersten zwei Zeilen sind einfach noch mal eine Wiederholung 01:08:18.550 --> 01:08:19.230 der Aussage. 01:08:21.090 --> 01:08:26.190 Der eigentliche Beweis ist jetzt, wir schauen uns einen 01:08:26.190 --> 01:08:30.830 deterministischen endlichen Automaten A an, der L akzeptiert. 01:08:32.810 --> 01:08:38.070 Der hat eine Zustandsmenge Q und wir setzen jetzt N gleich Q Betrag. 01:08:39.490 --> 01:08:41.830 Anzahl Zustände des endlichen Automaten. 01:08:44.840 --> 01:08:48.500 Und jetzt schauen wir uns ein Wort an, der Länge größer N. 01:08:53.480 --> 01:08:58.140 Dieser Automat verarbeitet das Wort, indem er ja M Zustandsübergänge 01:08:58.140 --> 01:09:02.940 macht und dann in einem akzeptierenden Zustand endet. 01:09:03.080 --> 01:09:08.460 Also, der startet im Startzustand, endet in einem Zustand QM, der ein 01:09:08.460 --> 01:09:12.560 N -Zustand ist und zwischendurch nimmt er M Zustände an. 01:09:14.960 --> 01:09:19.360 Die können nicht alle verschieden sein, weil M größer N. 01:09:20.380 --> 01:09:23.340 Das heißt, es gibt mindestens einen Zustand, der mehrfach angenommen 01:09:23.340 --> 01:09:25.540 wird und da haken wir jetzt ein. 01:09:26.140 --> 01:09:31.660 Sei jetzt QI der erste Zustand, der mehrfach angenommen wird. 01:09:32.080 --> 01:09:36.040 Das heißt, ich fange an mit Q0, Q1 und so weiter bis QI und hier habe 01:09:36.040 --> 01:09:38.700 ich jedes Mal einen neuen Zustand. 01:09:43.240 --> 01:09:45.360 Und jetzt gucke ich mir an, 01:09:51.120 --> 01:09:56.180 dass das zweite Mal das QI angenommen wird. 01:09:58.800 --> 01:10:02.720 Und dazwischen wird ein Wort V eingegeben, das nicht leer ist. 01:10:02.980 --> 01:10:04.160 Mindestens ein Buchstabe. 01:10:06.020 --> 01:10:08.260 So, und dann interessiert mich nicht, was dann passiert. 01:10:08.340 --> 01:10:09.380 Dann kommt irgendwas. 01:10:20.470 --> 01:10:25.170 So, jetzt habe ich hier einen Pfad durch diesen Automatengrafen, der 01:10:25.170 --> 01:10:35.330 geht hier einmal rum und landet dann hier. 01:10:36.210 --> 01:10:37.970 Und jetzt lese ich ab. 01:10:38.770 --> 01:10:42.910 Dieser Teil ist U, das was eingegeben wird, bis ich das erste Mal bei 01:10:42.910 --> 01:10:43.450 QI bin. 01:10:44.110 --> 01:10:49.570 Dann das V ist das, was eingegeben wird, bis ich das zweite Mal bei QI 01:10:49.570 --> 01:10:50.850 bin und X ist der Rest. 01:10:51.370 --> 01:10:53.670 Das ist jetzt meine Zerlegung des Wortes. 01:10:54.050 --> 01:10:58.450 Das stimmt, U, V, X ist gerade W, so habe ich das definiert. 01:10:59.250 --> 01:11:02.510 Und jetzt kann ich sehen, was passiert, wenn ich das V weglasse oder 01:11:02.510 --> 01:11:03.050 wiederhole. 01:11:03.650 --> 01:11:04.650 Das ändert sich nichts. 01:11:04.650 --> 01:11:08.670 Wenn ich V weglasse, kriege ich diesen Pfad und das Wort wird auch 01:11:08.670 --> 01:11:09.350 akzeptiert. 01:11:09.630 --> 01:11:13.110 Wenn ich das V mehrfach wiederhole, kriege ich einen Pfad, der sich 01:11:13.110 --> 01:11:16.970 entsprechend oft durch diesen Kreis läuft, aber das Wort wird wieder 01:11:16.970 --> 01:11:17.650 akzeptiert. 01:11:26.460 --> 01:11:29.180 Jetzt müssen wir, glaube ich, nur noch zeigen, dass U, V kleiner 01:11:29.180 --> 01:11:30.020 gleich N ist. 01:11:31.780 --> 01:11:39.120 Kann es sein, dass das zweite Auftauchen von QI später ist als nach N 01:11:39.120 --> 01:11:39.760 Übergängen? 01:11:40.000 --> 01:11:43.180 Nein, das kann nicht sein, weil das ist das erste, was sich wiederholt 01:11:43.180 --> 01:11:48.840 und es kann höchstens N Übergänge geben, wo sich nichts wiederholt. 01:11:51.560 --> 01:11:54.620 Das heißt, wenn das hier größer N wäre, hätte sich irgendwas anderes 01:11:54.620 --> 01:11:58.420 schon wiederholt und das widerspricht der Definition, dass QI der 01:11:58.420 --> 01:12:00.660 erste Zustand ist, der sich überhaupt wiederholt. 01:12:03.540 --> 01:12:05.660 Und damit ist mein Lemma bewiesen. 01:12:06.600 --> 01:12:08.700 Fragen zu dem Pumping-Lemma-Beweis? 01:12:11.020 --> 01:12:12.420 Ne, das ist nicht der Fall. 01:12:12.740 --> 01:12:13.860 Jetzt wenden wir das mal an. 01:12:14.620 --> 01:12:17.260 Das ist genau diese Sprache, die ich eben erwähnt habe. 01:12:18.240 --> 01:12:20.000 A hoch K, B hoch K für K-Element N. 01:12:21.840 --> 01:12:24.600 Wir haben gesehen, das ist eine Chomsky-II-Sprache. 01:12:25.140 --> 01:12:28.140 Wir beweisen jetzt, dass es keine Chomsky-III-Sprache ist. 01:12:29.160 --> 01:12:32.760 Beweis, Annahme L wäre regulär, also eine Chomsky-III-Sprache. 01:12:34.700 --> 01:12:38.960 Sei N der Wert aus dem Pumping-Lemma, also angenommen, das wäre 01:12:38.960 --> 01:12:42.000 regulär, dann gibt es ja insbesondere einen deterministischen 01:12:42.000 --> 01:12:44.120 endlichen Automaten, der L akzeptiert. 01:12:44.860 --> 01:12:49.900 Sei N die Anzahl Zustände dieses hypothetischen endlichen Automaten. 01:12:50.140 --> 01:12:51.420 Wir machen Widerspruch-Beweis. 01:12:54.580 --> 01:12:57.460 Dann schau doch mal das Wort auch N, B hoch N an. 01:12:58.500 --> 01:13:03.460 Laut dem Pumping-Lemma lässt sich das zerlegen in UVx. 01:13:07.680 --> 01:13:10.300 Und mit den Eigenschaften vom Pumping-Lemma. 01:13:10.300 --> 01:13:14.720 UV-Betrag ist kleiner gleich N, V-Betrag ist größer gleich 1. 01:13:15.360 --> 01:13:18.140 Und wir wissen nach dem Pumping-Lemma, UX ist auch ein L. 01:13:18.760 --> 01:13:20.560 Jetzt gucken wir uns mal an, wie das aussieht. 01:13:22.420 --> 01:13:24.940 Wir wissen UV-Betrag kleiner gleich N. 01:13:28.140 --> 01:13:33.740 Das heißt, UV sind einfach As. 01:13:34.300 --> 01:13:37.540 Weil das Wort, das wir uns angucken, ist A hoch N, B hoch N. 01:13:40.300 --> 01:13:45.440 Und das V ist eben auch irgendwie ein A hoch L mit L größer gleich 1. 01:13:46.040 --> 01:13:51.460 Also es ist eine nicht leere Anzahl von As, aus denen das V besteht. 01:13:51.880 --> 01:13:54.080 Und die Behauptung ist jetzt, die kann ich einfach weglassen und 01:13:54.080 --> 01:13:55.300 kriege ein neues Wort in L. 01:13:56.120 --> 01:14:01.100 Das hieße, A hoch N minus L, B hoch N wäre in L. 01:14:01.920 --> 01:14:03.560 Wobei L ist größer gleich 1. 01:14:03.560 --> 01:14:08.300 Das ist aber ein Widerspruch zu der Annahme, dass unser Automat nur 01:14:08.300 --> 01:14:11.600 Wörter akzeptiert mit gleich vielen As wie Bs. 01:14:12.840 --> 01:14:13.960 Beweis erbracht. 01:14:14.780 --> 01:14:16.380 Fragen zu diesem Beweis. 01:14:17.660 --> 01:14:21.560 Das ist eine wunderbare Quelle von Klausuraufgaben. 01:14:22.800 --> 01:14:26.500 Wir geben Ihnen eine Sprache und sagen, beweisen Sie, dass sie nicht 01:14:26.500 --> 01:14:27.260 regulär ist. 01:14:30.780 --> 01:14:33.820 Dann wird man im Allgemeinen gucken, ob man das mit dem Pumping-Lemmer 01:14:33.820 --> 01:14:34.440 zeigen kann. 01:14:37.900 --> 01:14:39.700 Jetzt machen wir ein weiteres Beispiel. 01:14:39.860 --> 01:14:41.340 Wohlgeformte Klammerausdrücke. 01:14:44.840 --> 01:14:47.540 Annahme dieses L-Klammern ist regulär. 01:14:50.120 --> 01:14:52.640 Sei wieder N der Wert aus dem Pumping-Lemmer. 01:14:52.640 --> 01:14:56.780 Wenn es regulär ist, gibt es einen deterministischen endlichen 01:14:56.780 --> 01:14:59.860 Automaten, der L-Klammern akzeptiert. 01:15:00.340 --> 01:15:03.320 Sei N die Anzahl Zustände des deterministischen endlichen Automaten. 01:15:04.820 --> 01:15:11.080 Zerlege das Ding in uvx, sodass uv-Betracht kleiner gleich N, v 01:15:11.080 --> 01:15:12.280 -Betracht größer 1. 01:15:13.240 --> 01:15:17.260 Dann heißt das, dass v nur aus öffnenden Klammern besteht. 01:15:18.260 --> 01:15:21.060 Und das Pumping-Lemmer sagt uns, dass ich die einfach weglassen kann. 01:15:21.780 --> 01:15:25.640 Aber das ist sicherlich kein wohlgeformter Klammerausdruck mehr. 01:15:26.120 --> 01:15:27.080 Ich habe einen Widerspruch. 01:15:31.720 --> 01:15:32.800 Fragen dazu? 01:15:37.190 --> 01:15:39.250 Machen wir mal etwas Exotischeres. 01:15:39.390 --> 01:15:43.070 Das ist jetzt nämlich keine Typ-II-Grammatik mehr, sondern was? 01:15:43.610 --> 01:15:46.650 Nehmen wir an Typ-I oder sogar Typ-0. 01:15:48.050 --> 01:15:52.090 Die Menge aller 0 hoch p, sodass p eine Primzahl ist. 01:15:55.430 --> 01:15:57.330 Wieder, Annahme L sei regulär. 01:15:57.490 --> 01:15:59.830 Das heißt, es gibt einen deterministischen endlichen Automaten. 01:15:59.950 --> 01:16:02.890 Sei N die Anzahl Zustände dieses endlichen Automaten. 01:16:07.150 --> 01:16:11.730 Jetzt betrachte ich eine Primzahl p größer gleich N plus 2. 01:16:12.630 --> 01:16:16.290 Die gibt es, weil wir aus der Zahlentheorie wissen, dass es unendlich 01:16:16.290 --> 01:16:17.410 viele Primzahlen gibt. 01:16:20.770 --> 01:16:23.210 Das bedeutet 0 hoch p ist denn L. 01:16:24.910 --> 01:16:29.030 Und es erfüllt die Anforderungen des Pumpinglemmas. 01:16:29.190 --> 01:16:33.930 Das heißt, ich kann es zerlegen in uvw mit v Betrag größer gleich 1 01:16:33.930 --> 01:16:39.210 und uw größer gleich 2. 01:16:41.290 --> 01:16:43.090 Warum ist das so? 01:16:43.270 --> 01:16:45.270 p ist größer N plus 2. 01:16:45.430 --> 01:16:46.810 uv ist kleiner gleich N. 01:16:46.990 --> 01:16:48.930 Folglich muss uw größer gleich 2 sein. 01:16:49.010 --> 01:16:49.610 Das ist wichtig. 01:16:49.610 --> 01:16:51.390 Das werden wir gleich sehen, warum. 01:16:53.010 --> 01:16:55.870 Jetzt benutzen wir das Pumpinglemma mal in die andere Richtung. 01:16:55.990 --> 01:16:57.910 Wir pumpen und zwar ziemlich massiv. 01:16:58.450 --> 01:17:03.370 Wir nehmen nämlich das Wort u, v hoch uw Betrag, w. 01:17:04.990 --> 01:17:06.930 Wie viele Buchstaben hat das? 01:17:08.450 --> 01:17:08.850 Na ja, 01:17:14.090 --> 01:17:17.070 uw Betrag mal v plus uw. 01:17:18.670 --> 01:17:23.430 Das heißt, die Anzahl Buchstaben ist uw Betrag mal 1 plus v Betrag. 01:17:24.630 --> 01:17:27.490 Außerdem ist v Betrag größer gleich 1. 01:17:28.430 --> 01:17:32.070 uw Betrag ist auch größer gleich 2. 01:17:33.630 --> 01:17:36.090 Also 1 plus v Betrag ist größer gleich 2. 01:17:36.610 --> 01:17:41.670 Das heißt, wir haben hier gezeigt, das ist p, eine Primzahl 01:17:41.670 --> 01:17:42.290 wohlgemerkt. 01:17:47.790 --> 01:17:50.630 Ach nee, genau, wir haben das Pumpinglemma angewendet. 01:17:50.930 --> 01:17:51.930 Wir finden ein neues Wort. 01:17:56.930 --> 01:18:00.310 Das besteht aus so vielen Nullen. 01:18:00.530 --> 01:18:02.850 uw Betrag mal 1 plus v Betrag Nullen. 01:18:03.210 --> 01:18:04.170 Es ist aber auch ein L. 01:18:05.030 --> 01:18:06.630 Das heißt, es ist eine Primzahl. 01:18:07.390 --> 01:18:08.450 Aber das ist ja komisch. 01:18:08.530 --> 01:18:11.110 Wir haben eine Primzahl mit zwei nicht trivialen Faktoren. 01:18:11.250 --> 01:18:13.610 Nämlich uw Betrag und 1 plus v Betrag. 01:18:14.350 --> 01:18:15.450 Das ist ein Widerspruch. 01:18:16.970 --> 01:18:20.470 Folglich ist diese Sprache keine reguläre Sprache. 01:18:21.790 --> 01:18:22.850 Fragen dazu? 01:18:25.170 --> 01:18:25.810 Okay. 01:18:27.490 --> 01:18:29.350 Dann noch eine kleine Bemerkung. 01:18:29.470 --> 01:18:32.970 Das Pumpinglemma ist keine hinreichende Bedingung für Regularität. 01:18:33.570 --> 01:18:37.670 Also Sie sollten nicht denken, wenn ich jetzt eine Sprache habe, wo 01:18:37.670 --> 01:18:44.690 ich dieses Aufpumpen machen kann, dass man dann automatisch eine 01:18:44.690 --> 01:18:45.670 reguläre Sprache hat. 01:18:45.970 --> 01:18:48.690 Also hier ist ein Beispiel, eine nicht reguläre Sprache. 01:18:49.390 --> 01:18:51.990 C hoch M, A hoch L, B hoch L. 01:18:52.450 --> 01:18:56.870 Also das ist beliebig viele Cs und dann gleich viele As wie Bs. 01:18:57.670 --> 01:19:00.910 Das ist ziemlich klar, dass das so ähnlich ist, wie dieses A hoch L, B 01:19:00.910 --> 01:19:01.630 hoch L alleine. 01:19:02.270 --> 01:19:03.350 Eine Typ-2-Sprache. 01:19:11.650 --> 01:19:16.550 Aber sei N beliebig, also das ist sogar was stärkeres, als wir ein 01:19:16.550 --> 01:19:25.090 Pumpinglemma haben, und W ein beliebiges Wort aus der Sprache mit W 01:19:25.090 --> 01:19:26.410 -Betrag größer gleich N. 01:19:30.110 --> 01:19:32.370 Nehmen wir gleich den interessanteren Fall. 01:19:32.870 --> 01:19:37.290 B gleich auch M, A hoch L, B hoch L. 01:19:38.690 --> 01:19:41.790 Jetzt schreibe ich das Wort als folgende Faktorisierung. 01:19:41.790 --> 01:19:48.850 Faktorisierung 1C und dann M-1Cs und dann A hoch L, B hoch L. 01:19:49.870 --> 01:19:52.750 Und dann kriege ich lauter Wörter aus dem L. 01:19:53.970 --> 01:19:55.690 Also die Richtung ist nicht so interessant. 01:19:56.030 --> 01:19:58.130 Das ist jetzt nicht so spannend. 01:19:58.310 --> 01:20:03.250 Ich will das nur darauf hinweisen, dass Sie das Pumpinglemma richtig 01:20:03.250 --> 01:20:05.750 benutzen und nicht Schlüsse ziehen, die nicht gelten. 01:20:07.370 --> 01:20:13.270 Das ist jetzt ein natürlicher Schnitt, wo wir zum Mittagessen 01:20:13.270 --> 01:20:13.990 aufbrechen können. 01:20:14.490 --> 01:20:14.890 Vielen Dank.