WEBVTT 00:00.000 --> 00:01.640 So, schönen guten Morgen. 00:01.780 --> 00:09.000 Ich begrüße Sie zur Fortsetzung der Vorlesung Grundlagen der 00:09.000 --> 00:10.280 Informatik II. 00:12.160 --> 00:15.860 Das Mikrofon müsste wohl noch ein bisschen lauter, etwas lauter. 00:15.960 --> 00:17.100 Ich glaube, das reicht, das reicht. 00:17.540 --> 00:18.400 Sonst wird es zu laut. 00:19.220 --> 00:22.060 Es muss ja noch ein bisschen Anreiz sein, dass Sie leiser werden. 00:22.940 --> 00:25.260 Also ich finde es erstmal gut, dass Sie überhaupt heute gekommen sind, 00:25.320 --> 00:26.900 weil heute ein Brückentag ist. 00:26.900 --> 00:30.060 Morgen ist Feiertag, also herzlich willkommen. 00:31.080 --> 00:35.600 Wir sind dabei, die Vorlesung Grundlagen der Informatik II zu machen. 00:36.280 --> 00:41.540 Kleiner Hinweis, ich habe ja immer die schönen Werkzeuge, die Feedback 00:41.540 --> 00:42.380 -Werkzeuge an. 00:42.500 --> 00:45.980 Mittlerweile ist die NuKit-App auch über den App Store verfügbar, 00:46.120 --> 00:49.880 können Sie also da problemlos runterladen und dann hier einsetzen, 00:49.980 --> 00:51.160 sofern Sie das möchten. 00:51.160 --> 00:53.060 Das können Sie gerne machen. 00:53.520 --> 00:54.940 Also, was haben wir letztes Mal gemacht? 00:55.020 --> 00:58.220 Wir haben uns beschäftigt mit einer Reihe von Themen. 00:59.000 --> 01:01.360 Die Automaten hat was schon längst hinter uns gelassen, 01:01.540 --> 01:04.140 beziehungsweise da schon einiges getan. 01:05.140 --> 01:09.220 Ich hatte Ihnen letztes Mal, genau, einiges erzählt zu 01:09.220 --> 01:12.480 Konfigurationen, hatte Ihnen Beispiele genannt. 01:12.480 --> 01:18.080 Wir hatten uns die Sprache von Automaten betrachtet, hatten uns 01:18.080 --> 01:20.520 verschiedenste Beispiele angesehen. 01:21.980 --> 01:25.280 Ich hatte Ihnen, das war ja auch schon das Mal davor, da hatten wir 01:25.280 --> 01:29.220 schon mal dieses Pumping Lemma für EA-Sprachen definiert, ein 01:29.220 --> 01:30.360 wesentlicher Punkt. 01:30.360 --> 01:37.820 Wesentliche Erkenntnis, dass wir eben bei endlichen Systemen bei einer 01:37.820 --> 01:41.980 Betrachtung einer langen Folge von Situationen, bei denen wir nur eine 01:41.980 --> 01:44.840 endliche Zahl von Situationen unterscheiden können, immer 01:44.840 --> 01:48.400 Wiederholungen haben und das hat deutliche Auswirkungen auf die 01:48.400 --> 01:52.620 Möglichkeiten, solche Systeme zu untersuchen oder Eigenschaften zu 01:52.620 --> 01:53.020 untersuchen. 01:53.020 --> 01:56.660 Und wir haben das Lemma bewiesen, haben dann Erfolge uns angeschaut, 01:56.760 --> 02:00.260 gesehen, wie wir das nutzen können, nämlich so, dass wir zeigen, dass 02:00.260 --> 02:04.500 bestimmte Sprachen nicht von endlichen Automaten akzeptierbar sind, 02:05.100 --> 02:09.820 haben das dann gemacht für das Beispiel der Sprache im Prinzip der 02:09.820 --> 02:13.880 einfachen Klammerschachtelungen oder A hoch I, B hoch I oder A hoch N, 02:13.960 --> 02:14.480 B hoch N. 02:16.140 --> 02:21.380 Wir haben dann gesehen, dass es natürlich, da diese eine Sprache nicht 02:21.380 --> 02:25.160 akzeptiert werden kann von endlichen Automaten, gibt es eben Sprachen, 02:25.340 --> 02:26.500 die nicht erkennbar sind. 02:26.660 --> 02:30.920 Das heißt, das ist eine echte Teilmenge der Menge aller Sprachen. 02:31.760 --> 02:34.300 Dann haben wir uns mit der Äquivalenz und Minimierung endlicher 02:34.300 --> 02:35.300 Automaten beschäftigt. 02:35.300 --> 02:40.680 Ich habe Ihnen gezeigt, wie wir Automaten minimieren können, indem wir 02:40.680 --> 02:43.920 die Äquivalenz von Zuständen betrachten. 02:44.060 --> 02:47.760 Und wir hatten dann mit einem Algorithmus gesehen, wie man das 02:47.760 --> 02:50.660 tatsächlich machen kann, indem man systematisch eine Tabelle 02:50.660 --> 02:56.260 aufschreibt, in der man sich anschaut, inwieweit Zustandspaare 02:56.260 --> 02:58.580 äquivalent sein können oder nicht. 02:58.580 --> 03:02.060 Und wir haben in dieser Tabelle sukzessive, beginnend von der Null 03:02.060 --> 03:08.980 -Äquivalenz, die Felder markiert, in denen Paare nicht Null 03:08.980 --> 03:12.520 -Äquivalente oder nicht Eins-Äquivalente oder nicht Zwei-Äquivalente 03:12.520 --> 03:16.000 auftauchen. 03:16.500 --> 03:20.920 Und die Felder, die dann am Ende frei bleiben, sind gerade die Felder, 03:21.600 --> 03:24.580 die äquivalente Zustände charakterisieren. 03:24.580 --> 03:29.440 Also, ein sehr einfacher Ansatz, nutzt das Prinzip der dynamischen 03:29.440 --> 03:33.240 Programmierung, von einfachen Situationen auf komplexere zu schließen. 03:34.320 --> 03:37.440 Und damit hatten wir dann diesen Automaten reduziert und wir hatten 03:37.440 --> 03:39.680 gesehen, dass der dann eben etwas kleiner aussieht. 03:39.760 --> 03:43.220 Das war der ursprüngliche Automat hier links und rechts ist dann der 03:43.220 --> 03:44.280 reduzierte Automat. 03:45.140 --> 03:49.540 Und damit haben wir dann gewusst, wie wir Automaten reduzieren können. 03:49.540 --> 03:54.160 Und das hier war die letzte Folie beim letzten Mal und wird die erste 03:54.160 --> 04:01.260 Folie heute, die ich vollständig zeigen möchte, animieren möchte. 04:01.380 --> 04:03.460 Das war die Idee. 04:03.980 --> 04:10.480 Wir wollen jetzt nicht nur die deterministischen Automaten betrachten, 04:10.600 --> 04:13.560 bei denen der Folgezustand immer eindeutig festgelegt ist, sondern, 04:13.820 --> 04:16.360 wie in diesem Beispiel, das ich letztes Mal auch schon gezeigt habe, 04:17.180 --> 04:22.900 auf einfache Art und Weise Automaten spezifizieren, indem wir auf 04:22.900 --> 04:29.580 einmal nicht mehr einfach nur einen Folgezustand angeben für ein 04:29.580 --> 04:34.460 Eingabesymbol, in diesem Fall A oder auch B, sondern mehr als einen 04:34.460 --> 04:39.140 oder auch gar keinen, zum Beispiel hier bei Zustand S3, von dem aus 04:39.140 --> 04:40.460 gibt es überhaupt keinen Übergang. 04:40.460 --> 04:42.780 Also wenn wir da gelandet sind, können wir gar nicht weitermachen. 04:43.400 --> 04:47.520 Vorher bei den deterministischen Automaten musste es für jeden Zustand 04:47.520 --> 04:50.880 und jedes Eingabezeichen einen definierten Übergang geben. 04:51.280 --> 04:52.520 Darauf verzichten wir jetzt. 04:52.660 --> 04:56.740 Und die Frage ist eben, welche Sprache dann akzeptiert werden kann. 04:57.120 --> 05:00.020 Man sieht hier sofort, das ist die Sprache, bei der das letzte Zeichen 05:00.020 --> 05:02.100 vorher schon mal vorgekommen sein muss. 05:02.660 --> 05:05.080 Also das A muss vorher schon mal da gewesen sein. 05:05.360 --> 05:07.460 Das B muss auch vorher schon mal da gewesen sein. 05:07.460 --> 05:10.740 Und davor und dazwischen kann Beliebiges passieren. 05:11.920 --> 05:14.780 Und wenn wir das so machen, müssen wir uns auch wieder überlegen, wie 05:14.780 --> 05:19.080 wir jetzt damit umgehen, wenn wir Wörter eingeben und das Verhalten 05:19.080 --> 05:24.160 des Automaten für die Eingabe von Wörtern charakterisieren können. 05:24.600 --> 05:27.780 Jetzt wissen wir, wir können von einem Zustand, der Eingabe eines 05:27.780 --> 05:31.200 Symbols, in eine Menge von Folgezuständen kommen. 05:32.900 --> 05:35.360 Und das müssen wir jetzt entsprechend umsetzen. 05:35.920 --> 05:39.780 Also, Definition von Delta-Stern, wir hatten das schon mal, Delta 05:39.780 --> 05:44.920 -Stern definiert bei der Erweiterung der einfachen Übergangsfunktion 05:44.920 --> 05:48.600 mit deterministischen Automaten auf Wörter, wenn ich das leere Wort 05:48.600 --> 05:50.400 eingebe, tut sich ja gar nichts. 05:50.780 --> 05:54.620 In diesem Fall steht dann aber rechts nicht der Zustand, sondern die 05:54.620 --> 05:58.800 Menge, die diesen Zustand enthält, weil ja bei nicht deterministischen 05:58.800 --> 06:04.720 Automaten die Zustände und Eingabesymbole immer abgebildet werden auf 06:04.720 --> 06:05.860 Mengen von Zuständen. 06:05.960 --> 06:08.120 Deswegen ist das hier die Menge, die diesen Zustand enthält. 06:08.580 --> 06:12.740 Also, wenn wir nichts eingeben, wissen wir genau, was dieser Automat 06:12.740 --> 06:14.020 machen wird, nämlich gar nichts. 06:14.140 --> 06:15.480 Er bleibt in dem aktuellen Zustand. 06:16.500 --> 06:20.940 Wenn wir in einem Zustand sind und wir geben ein Wort EW ein, haben 06:20.940 --> 06:27.700 also als nächstes Zeichen das E zu bearbeiten und sind aktuell im 06:27.700 --> 06:33.080 Zustand E, dann gehen wir natürlich in eine Menge von Zuständen, die 06:33.080 --> 06:38.200 es hier angedeutet, das ist die gesamte Menge von Zuständen, die der 06:38.200 --> 06:39.700 Automat annehmen könnte. 06:40.600 --> 06:46.620 Das gibt praktisch eine Menge von Möglichkeiten, in die der Automat 06:46.620 --> 06:47.560 gehen könnte. 06:48.000 --> 06:49.700 Das sind mögliche Zustandsübergänge. 06:50.500 --> 06:52.400 Und dann müssen wir mit W weitermachen. 06:53.160 --> 06:57.740 Das heißt, da in jeden dieser Zustände in dieser schraffierten Menge 06:57.740 --> 07:03.540 gehen könnte, könnte er auch von jedem dieser Zustände S', in dieser 07:03.540 --> 07:09.300 Menge von Folgezuständen von S, in eine weitere Menge übergehen, in 07:09.300 --> 07:13.840 das Delta, und das wäre dann praktisch Delta-Stern von S' W, müsste 07:13.840 --> 07:16.120 entsprechend auch iterativ definiert werden. 07:16.120 --> 07:19.640 Die iterative oder die rekursive Definition ist hier gegeben, 07:20.520 --> 07:21.980 sukzessive immer weiter. 07:22.460 --> 07:27.160 Das heißt, das, was wir hier machen müssen, ist die Vereinigung aller 07:27.160 --> 07:35.780 Folgemengen von Zuständen, die wir von unserem Zustand S aus mit dem 07:35.780 --> 07:37.620 ersten Zeichen erreichen können. 07:38.580 --> 07:42.300 Insofern haben wir hier eventuell eine sehr große Menge von möglichen 07:42.300 --> 07:43.320 Folgezuständen. 07:44.660 --> 07:46.740 Nichtdeterminismus kann man auf verschiedene Art und Weise 07:46.740 --> 07:47.520 interpretieren. 07:47.680 --> 07:52.440 Es soll andeuten oder es soll bezeichnen eine Unsicherheit über den 07:52.440 --> 07:53.780 nächsten Folgezustand. 07:54.340 --> 07:57.400 Es kann sein, dass der Automat in irgendeinem dieser Zustände 07:57.400 --> 07:59.960 übergeht, wenn Sie in dem Buch das nachlesen. 08:00.960 --> 08:03.920 Theoretische Informatik ganz praktisch, da finden Sie im zweiten 08:03.920 --> 08:09.800 Kapitel eine Diskussion, dieses Begriff des Nichtdeterminismus, der 08:09.800 --> 08:12.540 genau das nochmal beschreibt an verschiedenen Beispielen. 08:12.540 --> 08:16.780 Wir machen das hier auch an diesem einfachen Beispiel des endlichen 08:16.780 --> 08:19.800 Automaten, der nichtdeterministisch jetzt arbeitet. 08:19.900 --> 08:22.720 Wir werden gleich sehen an einem Beispiel, wie das funktioniert. 08:23.300 --> 08:24.760 Hier ist nochmal ein Beispiel gegeben. 08:25.200 --> 08:29.220 Wenn wir also jetzt im Zustand S0 beginnen, bei dem Automaten, den wir 08:29.220 --> 08:33.560 gerade vorher gesehen hatten, bei dem das letzte Zeichen immer schon 08:33.560 --> 08:37.960 vorher irgendwann mal aufgetaucht sein muss, da hatten wir diese 08:37.960 --> 08:41.700 Zustandstafel, Übergangstafel. 08:42.360 --> 08:47.420 Das heißt, wenn wir im S0 beginnen und geben das Wort AB ein, zwei 08:47.420 --> 08:52.500 Zeichen nacheinander, dann ist das, behaupte ich jetzt einfach, die 08:52.500 --> 08:55.280 Menge, die aus den drei Zuständen S0, S1, S2 besteht. 08:55.400 --> 08:55.640 Warum? 08:56.380 --> 08:58.580 Weil wir zunächst mal das A eingeben. 08:58.580 --> 09:04.440 Wenn wir das A eingeben, kommen wir auf die Menge S0, S1 und dann 09:04.440 --> 09:09.500 müssen wir entsprechend der Definition, die hier steht, bei dem 09:09.500 --> 09:19.160 Folgezeichen natürlich jetzt das Delta von, da das hier die Menge der 09:19.160 --> 09:24.100 Folgezustände war, müssen wir also jetzt Delta von S0B vereinigt mit 09:24.100 --> 09:26.040 Delta von S1B betrachten. 09:26.040 --> 09:29.880 Das sind die beiden Zustände, die in der Folgemenge Delta von S0A 09:29.880 --> 09:30.760 enthalten sind. 09:31.540 --> 09:40.680 Delta von S0B ist diese Menge S0, S2 und Delta von S1B ist nur die 09:40.680 --> 09:44.220 Menge S1, also kommt da nochmal die Menge S1 dazu, wir haben also die 09:44.220 --> 09:47.820 Vereinigung der beiden Mengen zu betrachten, S0, S1 oder S2. 09:47.820 --> 09:52.200 Das heißt, nach Eingabe von A und B, nacheinander, könnte der Automat 09:52.200 --> 09:56.160 in irgendeinem dieser drei Zustände S0, S1 oder S2 sein. 09:57.580 --> 09:58.720 Das wissen wir jetzt. 09:59.100 --> 10:02.340 Das ist praktisch eine Unsicherheit über das, was der Automat macht. 10:03.080 --> 10:06.780 Und Sie haben gesehen auf der Folie, wo ich Ihnen das Beispiel von 10:06.780 --> 10:10.340 diesem Automaten gegeben habe, das kann ganz praktisch sein, man 10:10.340 --> 10:14.440 erkennt durchaus einfacher als bei anderen, bei dem deterministischen 10:14.440 --> 10:17.060 Automaten, was der eigentlich macht, obwohl das ein bisschen wie ein 10:17.060 --> 10:18.160 Widerspruch sich anhört. 10:18.800 --> 10:25.000 Wenn ich Unsicherheit habe in der Beschreibung des aktuellen Zustands, 10:25.340 --> 10:26.380 wieso wird das einfacher? 10:26.840 --> 10:29.440 Aber Sie sehen an dem Beispiel, dass das tatsächlich so ist. 10:30.980 --> 10:34.040 Also, jetzt wollen wir die Arbeitsweise auch wieder genauer 10:34.040 --> 10:34.560 beschreiben. 10:34.980 --> 10:38.180 Was müssen wir dann machen, um die Arbeitsweise zu beschreiben, auch 10:38.180 --> 10:40.920 das Akzeptierungsverhalten zu beschreiben, müssen wir wieder den 10:40.920 --> 10:43.080 Begriff der Konfiguration definieren. 10:44.080 --> 10:48.540 Konfiguration war, hatte ich Ihnen schon mal gesagt, so definiert, 10:48.700 --> 10:54.000 dass das die Information ist, die wir brauchen, um das weitere 10:54.000 --> 10:59.460 Verhalten dieses Automaten jetzt tatsächlich bestimmen zu können. 11:00.080 --> 11:01.620 Was sind das für Informationen? 11:02.260 --> 11:07.280 Genau wie vorher ist das, wie gesagt, oder wie vorher auch, einfach 11:07.280 --> 11:09.860 nur ein Zustand und ein Wort. 11:09.860 --> 11:12.380 Und zwar der aktuelle Zustand des Automaten. 11:12.900 --> 11:15.580 Der Automaten ist ja immer in irgendeinem Zustand. 11:16.400 --> 11:20.640 Und dann das Restwort auf dem Eingabeband. 11:20.960 --> 11:26.740 Also, wenn wir hier unseren Automaten haben, der irgendein Feld auf 11:26.740 --> 11:31.920 dem, hier ist also unser aktueller Zustand, und ab da der Inhalt des 11:31.920 --> 11:37.080 Bandes, hier dieses Wort W, das ist das, was die Konfiguration 11:37.080 --> 11:37.880 ausmacht. 11:37.880 --> 11:42.940 Der aktuelle Zustand und das Wort, das wir ab diesem Zeichen auf dem 11:42.940 --> 11:46.860 Eingabeband jetzt noch bearbeiten müssen, das bestimmt das weitere 11:46.860 --> 11:48.000 Verhalten dieses Automaten. 11:49.340 --> 11:54.800 Das Ganze muss dann entsprechend wieder angeguckt werden in Bezug auf, 11:54.860 --> 11:57.140 wie gehe ich von einer Konfiguration zur anderen über. 11:57.720 --> 12:00.880 Und jetzt haben wir bei den nichtdeterministischen Automaten natürlich 12:00.880 --> 12:09.800 eine etwas andere Situation, denn aus einer Konfiguration S, E, W, das 12:09.800 --> 12:15.280 heißt das Zeichen E ist auf dem Feld, auf dem der Lesekopf zeigt, 12:16.420 --> 12:22.220 gehen wir über in einen Zustand S' und müssen noch das W abarbeiten. 12:23.180 --> 12:28.080 Und zwar für jedes S' aus der Menge Delta von SE. 12:28.930 --> 12:33.940 Das heißt, wir haben jetzt nicht aus einer Konfiguration, ich sag mal 12:33.940 --> 12:41.140 Konfiguration C, machen wir das deutsche Abkürzung K, aus einer 12:41.140 --> 12:50.420 Konfiguration K haben wir nicht nur eine Folgeableitung K', sondern es 12:50.420 --> 12:56.640 kann sein, dass wir noch ein K2' kriegen, vielleicht noch ein K3', je 12:56.640 --> 13:02.320 nachdem, wie viele unterschiedliche Zustände in der Folgemenge drin 13:02.320 --> 13:06.720 sind, in die der Automat sich bewegen könnte. 13:07.140 --> 13:12.240 Das heißt, wir bekommen für jeden möglichen Folgezustand eine mögliche 13:12.240 --> 13:13.440 Folgekonfiguration. 13:14.460 --> 13:15.380 Eine Frage? 13:16.200 --> 13:17.560 Ja, tatsächlich ist das so. 13:18.560 --> 13:25.080 Also, wir haben also jetzt nicht mehr eine einfache Folge von 13:25.080 --> 13:29.080 Konfigurationen, eine lineare Folge, sondern wir haben einen Baum, 13:29.960 --> 13:33.120 weil sich das hier jeweils noch weiter verzweigen kann. 13:34.540 --> 13:39.980 Und das heißt, die Konfigurationsfolgen werden ein bisschen 13:39.980 --> 13:40.860 komplizierter. 13:40.860 --> 13:46.600 Wir bekommen eine Menge möglicher Zustandsfolgen, die ein solcher 13:46.600 --> 13:49.500 nicht deterministischer Automat durchlaufen kann. 13:50.680 --> 13:53.200 Das sind also die Konfigurationen, die er durchlaufen kann. 13:53.620 --> 13:57.120 Das heißt, für jeden möglichen Folgezustand haben wir hier jeweils 13:57.120 --> 14:00.820 einen Übergang in eine mögliche neue Folgekonfiguration. 14:01.120 --> 14:04.400 Und jede dieser Folgekonfigurationen ist eine mögliche 14:04.400 --> 14:07.100 Folgekonfiguration, kann also angenommen werden. 14:07.680 --> 14:10.560 Schauen wir uns das an bei unserem Beispiel wieder, das ich gegeben 14:10.560 --> 14:10.880 hatte. 14:11.560 --> 14:16.020 Wenn wir also das Wort BBAB eingeben, wir wissen, dieses Wort ist in 14:16.020 --> 14:19.460 der Sprache, weil ja das Zeichen B vorher schon mal auftaucht, dann 14:19.460 --> 14:25.100 fangen wir an mit S0 und wir müssen das gesamte Wort BBAB noch lesen. 14:25.860 --> 14:32.600 Jetzt können wir, da die Folgezustandsmenge von S0 S0 S1 ist, können 14:32.600 --> 14:36.780 wir auf die Konfiguration S0 BAB weitergehen. 14:37.660 --> 14:41.980 Mit einem B können wir in S0 bleiben und AB dahinschreiben und müssen 14:41.980 --> 14:43.080 noch AB bearbeiten. 14:43.820 --> 14:49.620 Mit A gehen wir nach S0 S1, können also wieder in S0 bleiben, müssen 14:49.620 --> 14:53.980 das B noch bearbeiten und sind immer noch im Zustand S0 und haben 14:53.980 --> 14:56.700 nichts mehr zu bearbeiten, wären also fertig. 14:59.040 --> 15:01.000 Okay, was hilft uns das jetzt? 15:01.040 --> 15:04.260 Wir wollten ja eigentlich wissen, ob dieses Wort tatsächlich 15:04.260 --> 15:07.600 akzeptiert werden kann von diesem Automaten, sollte es ja besser. 15:08.320 --> 15:12.700 Der Endzustand ist aber der Zustand S3 und nicht der Zustand S0. 15:12.820 --> 15:16.380 Also mit der Konfigurationsfolge könnten wir nicht feststellen, dass 15:16.380 --> 15:20.640 dieses Wort tatsächlich von dem Automaten akzeptiert werden kann. 15:22.420 --> 15:26.240 Also schauen wir uns eine andere Konfigurationsfolge an, diese hier, 15:26.440 --> 15:39.580 S0 BBAB, da könnten wir also mit dem B von S0 aus in S2 übergehen und 15:39.580 --> 15:47.080 von S2 mit einem B könnten wir in S3 übergehen, hätten S3 AB, von S3 15:47.080 --> 15:48.060 geht es aber nicht weiter. 15:48.600 --> 15:53.120 Jetzt sind wir zwar im Zustand S3, aber vom Zustand S3 aus gibt es 15:53.120 --> 15:56.840 keine Folgekonfiguration oder keine Folgezustände, das hilft uns also 15:56.840 --> 15:58.120 auch nicht, wir sind in der Sackgasse. 15:59.480 --> 16:05.220 Ich könnte aber auch von S0 aus zunächst mal in dem S0 bleiben, muss 16:05.220 --> 16:10.100 noch ein B bearbeiten, könnte dann mit dem B in den Zustand S2 gehen, 16:10.100 --> 16:15.880 könnte dann mit dem A, S2 und A, könnte ich in S2 bleiben oder muss 16:15.880 --> 16:20.700 ich in S2 bleiben, da ist nur eine Möglichkeit, dann bin ich in S2 und 16:20.700 --> 16:25.720 muss noch das Zeichen B abarbeiten und mit B kann ich in den Zustand 16:25.720 --> 16:28.280 S3 gehen, dann bin ich in S3 Lambda. 16:29.500 --> 16:32.600 Sie sehen, es hätte auch wieder andere Möglichkeiten gegeben, aber 16:32.600 --> 16:37.520 dieses hier ist eine Folge von Konfigurationen, bei der wir 16:37.520 --> 16:42.980 tatsächlich von der Anfangskonfiguration aus in eine Endkonfiguration 16:42.980 --> 16:47.520 kommen können, bei der dieser Zustand S3 ein Endzustand ist. 16:48.380 --> 16:53.720 Und das reicht uns, um zu sagen, dieses Wort kann von dem 16:53.720 --> 16:56.940 nichtdeterministischen Automaten akzeptiert werden, weil er die 16:56.940 --> 17:02.420 Möglichkeit hat, so einen Pfad durch diesen Konfigurationsbaum zu 17:02.420 --> 17:09.020 wählen, dass am Ende eine Konfiguration S Lambda dasteht und das F 17:09.020 --> 17:13.280 hier ist ein Element unserer Endzustandsmenge. 17:14.000 --> 17:18.700 Das heißt, so werden wir das definieren auf der nächsten Folie, dass 17:18.700 --> 17:22.920 wir sagen, ein nichtdeterministischer Automat kann ein Wort 17:22.920 --> 17:26.710 akzeptieren, wenn er die Möglichkeit hat, das zu tun. 17:27.110 --> 17:33.490 Das heißt nicht, dass jede Konfigurationsfolge tatsächlich zu diesem 17:33.490 --> 17:37.070 Endzustand führen muss, wie wir gerade gesehen haben. 17:37.570 --> 17:40.990 Die anderen beiden, die ich hier aufgemalt habe explizit, führten 17:40.990 --> 17:44.990 entweder nicht zum Endzustand oder zum Endzustand, aber wir konnten 17:44.990 --> 17:47.070 das Wort gar nicht vollständig bearbeiten. 17:47.610 --> 17:51.170 Das heißt, man muss genau anschauen, welche Möglichkeiten der Automat 17:51.170 --> 17:51.430 hat. 17:51.430 --> 17:54.570 Das sieht alles viel komplizierter aus zunächst mal, was wir jetzt 17:54.570 --> 17:56.630 gemacht haben, als beim deterministischen Automaten. 17:57.090 --> 18:00.190 Trotzdem hatten wir eigentlich, als wir den Automaten mit dem 18:00.190 --> 18:04.250 Zustandsdiagramm gesehen haben, sofort den Eindruck, wir sehen viel 18:04.250 --> 18:08.970 schneller, welche Eingaben der eigentlich akzeptieren kann. 18:09.050 --> 18:13.550 Das ist tatsächlich so, dass Sie mit nichtdeterministischen Automaten 18:13.550 --> 18:18.910 Sprachen wesentlich kompakter beschreiben können, als mit 18:18.910 --> 18:20.270 deterministischen Automaten. 18:21.270 --> 18:25.370 Also werden wir jetzt das, was ich Ihnen gerade versprochen habe, 18:25.810 --> 18:32.750 jetzt so definieren, dass der Automat ein Wort W akzeptiert, wenn in 18:32.750 --> 18:38.370 der Menge der aus S0 bei Eingabe von W erreichbaren Zustände 18:38.370 --> 18:41.390 mindestens ein Endzustand drin ist. 18:42.010 --> 18:46.650 Wenn also der Schnitt mit der Endzustandsmenge ungleich leer ist. 18:48.350 --> 18:52.490 Ich kann das auch so formulieren, wenn ich mir jetzt die Sprache 18:52.490 --> 18:53.550 dieses Automaten anschaue. 18:54.110 --> 18:56.350 Das sind also alle Wörter, die akzeptiert werden. 18:56.810 --> 18:59.250 Und das kann ich entweder genauso nochmal hinschreiben, wie das oben 18:59.250 --> 18:59.970 drüber stand. 19:00.570 --> 19:04.550 Der Schnitt mit der Endzustandsmenge ist nicht leer. 19:04.770 --> 19:08.290 Das heißt, ich kann einen Endzustand erreichen oder über die 19:08.290 --> 19:09.810 Konfigurationsschreibweise. 19:09.810 --> 19:15.250 Es gibt eine Konfigurationsfolge, sodass ich von der 19:15.250 --> 19:21.250 Anfangskonfiguration S0 W auf eine Endkonfiguration S Lambda komme, 19:21.670 --> 19:26.470 bei der das S ein Endzustand ist und ich das Wort natürlich 19:26.470 --> 19:27.910 vollständig abgearbeitet habe. 19:29.150 --> 19:32.970 So ist jetzt die Akzeptierungsweise von nicht deterministischen 19:32.970 --> 19:34.110 Automaten definiert. 19:34.110 --> 19:35.450 Ist gar nicht so schwer. 19:35.570 --> 19:39.630 Es muss einfach nur einen Weg geben und damit sind wir schon durch. 19:40.910 --> 19:43.710 Jetzt die Frage, was bringt uns das? 19:43.810 --> 19:46.930 Ich sagte schon, es gibt eine gewisse einfachere Art, Sprachen zu 19:46.930 --> 19:50.530 beschreiben, weil wir den Automat etwas knapper definieren können, 19:50.650 --> 19:52.210 etwas einfacher, übersichtlicher. 19:54.130 --> 19:58.170 Die Frage ist nur, wenn wir jetzt den endlichen Automaten haben, gibt 19:58.170 --> 20:00.930 es dazu einen äquivalenten nicht deterministischen endlichen 20:00.930 --> 20:01.590 Automaten? 20:01.590 --> 20:05.650 Das ist natürlich trivial, weil das, was wir deterministisch machen 20:05.650 --> 20:09.750 können, das ist natürlich ein spezieller nicht deterministischer 20:09.750 --> 20:10.370 Automat. 20:10.690 --> 20:14.890 Der deterministische hat halt immer genau einen Folgezustand und nicht 20:14.890 --> 20:19.450 eine eventuell leere oder größere Menge von Folgezuständen. 20:19.550 --> 20:20.710 Also das ist wirklich sehr einfach. 20:21.050 --> 20:22.570 Die andere Richtung ist interessanter. 20:23.390 --> 20:27.710 Kann ich zu einem nicht deterministischen endlichen Automaten einen 20:27.710 --> 20:30.670 deterministischen Automaten definieren, der die gleiche Sprache 20:30.670 --> 20:31.330 akzeptiert? 20:31.630 --> 20:33.470 Und wenn das so ist, wie sieht der denn aus? 20:33.510 --> 20:34.430 Wie kann ich den gewinnen? 20:35.550 --> 20:36.590 Und das werden wir jetzt gleich machen. 20:36.890 --> 20:40.410 Also es ist so, dass man tatsächlich dazu einen äquivalenten endlichen 20:40.410 --> 20:41.670 Automaten finden kann. 20:42.110 --> 20:44.290 Das geht bei diesem Automatentyp. 20:44.710 --> 20:49.350 Sie werden später Automatentypen kennenlernen, bei denen der Gang von 20:49.350 --> 20:53.110 einem deterministischen zu einem nicht deterministischen Automaten 20:53.110 --> 20:58.630 tatsächlich zu einer Erweiterung der Menge an Sprachen führt, die von 20:58.630 --> 21:00.930 dieser Automatenklasse akzeptiert werden kann. 21:01.690 --> 21:05.030 Hier bei den endlichen Automaten werden wir gleich sehen, können wir 21:05.030 --> 21:07.850 das tatsächlich zeigen, dass es einen äquivalenten deterministischen 21:07.850 --> 21:08.690 Automaten gibt. 21:09.150 --> 21:14.370 Das heißt, die Ausdrucksmächtigkeit oder die Spracherkennungsfähigkeit 21:14.370 --> 21:18.970 der endlichen Automaten ist unabhängig davon, ob sie deterministisch 21:18.970 --> 21:20.810 oder nicht deterministisch definiert werden. 21:21.330 --> 21:22.650 Also, wie können wir das einsehen? 21:23.390 --> 21:25.810 Schauen wir uns an, wie wir das machen würden. 21:26.470 --> 21:31.790 Also, wir betrachten jetzt einfach Mengen von Zuständen und sagen, das 21:31.790 --> 21:33.090 sind unsere neuen Zustände. 21:34.510 --> 21:38.810 Wir definieren also zu einem Automaten, der nicht deterministisch ist, 21:39.310 --> 21:44.330 einen neuen Automaten, bei dem das S-Strich, die neue Zustandsmenge, 21:44.830 --> 21:47.610 gerade die Menge aller Teilmengen von S ist. 21:47.710 --> 21:50.610 Dieses P von S steht für die Potenzmenge von S. 21:51.190 --> 21:54.230 Potenzmenge, Menge aller Teilmengen von S. 21:54.230 --> 21:56.990 Das ist jetzt unsere neue Zustandsmenge. 21:58.330 --> 22:03.090 Und der Anfangszustand S0-Strich ist einfach die Menge, die den 22:03.090 --> 22:04.650 Anfangszustand S0 enthält. 22:05.690 --> 22:11.190 Und unsere Endzustandsmenge, S-Strich, entsprechend der Definition, 22:11.350 --> 22:18.510 die wir vorher gesehen haben, muss das ja die Menge aller Teilmengen 22:18.510 --> 22:24.930 von S sein, die einen nicht leeren Schnitt mit... 22:24.930 --> 22:30.570 Ich muss aber diesen blöden senkrechten Strich da wieder rauslöschen. 22:34.110 --> 22:38.230 Also, das muss eine Menge sein, die mindestens einen Endzustand 22:38.230 --> 22:38.670 enthält. 22:38.890 --> 22:42.570 Weil es dann eine Möglichkeit gibt, zu einem Endzustand zu kommen. 22:43.570 --> 22:45.190 Und dann ist es ganz einfach. 22:45.710 --> 22:51.810 Die Definition von Delta-Strich auf diesen Mengen von Zuständen ist 22:51.810 --> 22:57.690 natürlich dann einfach so definiert, dass wir von einer Teilmenge T 22:57.690 --> 23:08.810 von S bei Eingabe eines Zeichens E einfach alle Folgezustände oder 23:08.810 --> 23:15.090 alle Folgemengen dazunehmen, die wir von dem Zustand S aus oder von 23:15.090 --> 23:19.450 jedem Zustand S in T aus bei Eingabe von E erreichen würden, in dem 23:19.450 --> 23:21.210 nicht deterministischen Automaten. 23:21.650 --> 23:25.350 Das hatten wir vorher auch so definiert bei der Erweiterung unserer 23:25.350 --> 23:29.070 Übergangsfunktion Delta zu dem Delta-Stern, Erweiterung auf Wörter. 23:29.550 --> 23:31.190 Jetzt machen wir eine Erweiterung auf Mengen. 23:31.190 --> 23:34.370 Aber es ist ja klar, wir müssen dann alles das, was wir von den 23:34.370 --> 23:37.810 Einzelzuständen aus erreichen können, vereinigen zu dem 23:37.810 --> 23:39.110 Gesamtergebnis. 23:39.490 --> 23:45.490 Wenn wir bei einer Menge von Zuständen ein Zeichen eingeben, muss das 23:45.490 --> 23:49.510 das Gleiche sein, als wenn wir für jeden Zustand in der Teilmenge 23:49.510 --> 23:54.130 dieses Zeichen eingeben und dann die Folgezustandsmenge betrachten. 23:55.210 --> 23:56.570 Also das ist das Delta-Strich. 23:56.570 --> 23:58.570 Jetzt ist das natürlich blöd. 24:00.550 --> 24:05.830 Wenn das der äquivalente deterministische Automat wird, dann haben wir 24:05.830 --> 24:06.650 natürlich ein Problem. 24:06.770 --> 24:08.270 Der hat auf einmal sehr viele Zustände. 24:09.330 --> 24:11.830 Also wie viele Zustände gibt das? 24:12.030 --> 24:19.310 Das S-Strich, die Anzahl der Elemente von S-Strich ist natürlich zwei 24:19.310 --> 24:20.930 Hochbetrag von S. 24:22.130 --> 24:27.090 Also exponentiell in der Anzahl der Zustände unseres 24:27.090 --> 24:28.330 Ausgangsautomaten. 24:29.070 --> 24:30.410 Das wäre sehr schlecht. 24:31.670 --> 24:36.830 Und leider ist das im schlimmsten Fall nicht vermeidbar, das so zu 24:36.830 --> 24:37.070 machen. 24:37.530 --> 24:39.850 Aber ich zeige Ihnen gleich, dass es in der Praxis häufig anders 24:39.850 --> 24:40.350 aussieht. 24:40.590 --> 24:42.950 Also die Zustandsmenge kann sehr groß werden. 24:44.230 --> 24:47.770 Und deswegen werden wir das versuchen, möglichst auf das, was 24:47.770 --> 24:49.690 erforderlich ist, zu beschränken. 24:49.690 --> 24:51.450 Was ist erforderlich? 24:51.970 --> 24:54.530 Erinnern Sie sich daran, was wir gemacht haben bei der Äquivalenz und 24:54.530 --> 24:55.750 Minimierung von Automaten? 24:56.130 --> 24:58.570 Da haben wir gesagt, wir brauchen eigentlich nur das zu betrachten, 24:58.970 --> 25:01.370 was wir vom Anfangszustand aus erreichen können. 25:03.290 --> 25:09.110 Also werden wir mit dem Anfangszustand unseres Automaten, den wir hier 25:09.110 --> 25:10.730 oben gerade definiert haben, beginnen. 25:10.990 --> 25:17.330 Das ist die Menge, die dann Anfangszustand S0 des Automaten A1 25:17.330 --> 25:17.770 enthält. 25:17.770 --> 25:22.370 Und werden sehen, welche Mengen von Zuständen wir daraus erreichen 25:22.370 --> 25:22.770 können. 25:23.270 --> 25:26.850 Und nur die brauchen wir als Zustände des äquivalenten 25:26.850 --> 25:28.810 deterministischen Automaten. 25:29.610 --> 25:30.170 Beispiel. 25:32.310 --> 25:37.430 Das im Prinzip hier ist schon der ganze Trick. 25:37.550 --> 25:41.230 Wir schauen uns nur diejenigen Zustände an, die wir erreichen können 25:41.230 --> 25:41.970 von dem S0. 25:42.610 --> 25:44.490 Da kann man sich einfach überlegen, wie man das macht. 25:44.610 --> 25:46.530 Da muss man sich einfach nur die Zustandstabelle anschauen. 25:46.530 --> 25:49.450 Und das machen wir hier an dem Beispiel unseres nicht 25:49.450 --> 25:53.070 deterministischen Automaten, der jetzt schon mehrfach hier als 25:53.070 --> 25:54.110 Beispiel dienen musste. 25:54.850 --> 25:58.470 Und wir wollen jetzt sehen, welche Folgezustände wir jetzt bekommen, 25:58.930 --> 26:01.730 wenn wir von dem S0 aus anfangen. 26:02.530 --> 26:07.170 Also, dieses hier ist auf jeden Fall ein erforderlicher Zustand 26:07.170 --> 26:09.730 unseres äquivalenten deterministischen Automaten. 26:10.710 --> 26:11.810 Welche brauchen wir noch? 26:11.810 --> 26:17.510 Geben wir da mal das A ein und das B, dann brauchen wir doch genau als 26:17.510 --> 26:21.230 nächste Zustände diese beiden Mengen, weil wir die von dem S0 aus 26:21.230 --> 26:22.030 erreichen können. 26:22.670 --> 26:29.390 Also sind dieses beides mögliche Folgezustände, die wir betrachten 26:29.390 --> 26:29.730 müssen. 26:30.110 --> 26:32.910 Das heißt, wir müssen diese beiden Mengen dazunehmen. 26:33.730 --> 26:34.710 Die können wir erreichen. 26:35.490 --> 26:39.530 Jetzt schauen wir uns an, welche Mengen wir von diesen beiden 26:39.530 --> 26:43.930 offensichtlich auch erforderlichen Zuständen des deterministischen 26:43.930 --> 26:45.930 Automaten erreichen können. 26:46.470 --> 26:53.010 Also, welche Menge können wir von S0, S1 aus erreichen? 26:54.090 --> 27:00.490 S0, S1, das ist dieses Paar hier, da haben wir S0, S1 von S0 aus und 27:00.490 --> 27:05.010 S1, S3 von S1 aus. 27:05.410 --> 27:09.930 Also haben wir hier im ersten Fall S0, S1, S3 und bei Eingabe von B 27:09.930 --> 27:13.930 haben wir S0, S2 und S1, also das sind die beiden Folgezustandsmengen. 27:14.970 --> 27:21.310 Das heißt, von diesem Zustand S0, S1 kommen wir auf S0, S1, S3 oder 27:21.310 --> 27:22.830 auf S0, S1, S2. 27:23.670 --> 27:26.790 Also zwei neue Zustände, die noch nicht drin standen in unserer 27:26.790 --> 27:28.830 Tabelle, müssen wir auch aufnehmen. 27:29.350 --> 27:31.590 Dann schauen wir uns S0, S2 an. 27:33.370 --> 27:36.950 Da kommen wir auf S0, S1 und auf S2. 27:37.810 --> 27:39.910 Das wäre also S0, S1, S2. 27:40.650 --> 27:42.170 Der steht hier unten schon. 27:42.850 --> 27:44.270 Und das andere wäre bei Eingabe von B. 27:44.370 --> 27:51.310 S0, S2 würde auf S0, S2 und S2, S3 gehen. 27:51.410 --> 27:52.910 Also S0, S2, S3. 27:53.710 --> 27:55.810 Das sind also die beiden Folgezustandsmengen. 27:55.810 --> 27:59.750 Da ist ein neuer Zustand dabei, den wir noch nicht betrachtet hatten. 28:00.950 --> 28:05.970 Schauen wir uns jetzt den Zustand S0, S1, S3 an. 28:06.910 --> 28:13.450 Von dem aus S0, S1, S3. 28:13.670 --> 28:15.790 Von S3 aus geht es ja gar nicht weiter. 28:16.750 --> 28:22.190 Also es ist das gleiche wie die Folgezustände von S0, S1. 28:22.190 --> 28:25.830 Den Eintrag kennen wir schon mit A und mit B. 28:26.110 --> 28:29.710 Das heißt, da haben wir die gleichen Einträge wie in der Zeile für S0, 28:29.770 --> 28:30.270 S1. 28:31.610 --> 28:37.370 Und hier unten drunter bei S0, S1, S2, wenn Sie sich das anschauen, da 28:37.370 --> 28:40.270 haben wir die gesamte Menge von Zuständen auf einmal. 28:41.910 --> 28:44.410 Das heißt, wir müssen noch einen Zustand aufnehmen. 28:44.650 --> 28:47.390 Die gesamte Menge an Zuständen. 28:47.390 --> 28:52.750 Und dann haben wir noch zu betrachten die Folgezustände von S0, S2, 28:52.850 --> 28:53.290 S3. 28:53.410 --> 28:55.450 Das sind die gleichen Einträge für S0, S2. 28:55.990 --> 28:56.930 Also das hatten wir schon. 28:57.730 --> 29:02.190 Und von der Menge S0, S1, S2, S3 kommen wir natürlich jedes Mal auf 29:02.190 --> 29:03.210 die gleiche Menge zurück. 29:05.650 --> 29:07.350 Und damit sind wir fertig. 29:07.910 --> 29:10.970 Wir haben alle Zustände, die wir als Folgezustände erreichen konnten, 29:11.090 --> 29:12.090 in die Tabelle aufgenommen. 29:12.090 --> 29:17.690 Und das ist offensichtlich ausreichend, um das Verhalten des nicht 29:17.690 --> 29:20.530 deterministischen Automaten, den wir hier angegeben hatten, 29:21.150 --> 29:22.910 deterministisch zu beschreiben. 29:23.750 --> 29:27.430 Wir hatten im nicht deterministischen Automaten vier Zustände, hier 29:27.430 --> 29:28.930 haben wir jetzt sieben Zustände. 29:30.170 --> 29:34.730 Theoretisch hätten wir bei vier Zuständen 2 hoch 4 gleich 16 29:34.730 --> 29:37.250 unterschiedliche Zustände betrachten müssen. 29:37.250 --> 29:42.810 Nach der einfachen Definition war der erste Versuch, das Äquivalent zu 29:42.810 --> 29:43.070 machen. 29:43.470 --> 29:47.270 Jetzt haben wir hier gesehen, wir kommen mit sieben Zuständen aus. 29:47.350 --> 29:49.330 Das sind genau die, die wir erreichen können. 29:50.690 --> 29:53.950 Das heißt, das wäre jetzt der Äquivalente, ein deterministischer 29:53.950 --> 29:59.170 Automat, der genau das gleiche macht, wie unser nicht 29:59.170 --> 30:02.570 deterministischer Automat, also insbesondere die gleiche Sprache 30:02.570 --> 30:03.390 akzeptiert. 30:03.390 --> 30:12.010 Weil ja, wir immer dann ein Wort akzeptieren, wenn in der erreichten 30:12.010 --> 30:14.770 Zustandsmenge ein Endzustand drin ist. 30:15.350 --> 30:19.170 Das heißt, es muss das S3 in der Endzustandsmenge drin sein. 30:19.230 --> 30:23.050 Das heißt, wir hätten hier auch Endzustände, das hier wäre ein 30:23.050 --> 30:26.810 Endzustand, das wäre ein Endzustand und natürlich ist das auch ein 30:26.810 --> 30:27.310 Endzustand. 30:27.430 --> 30:28.490 Wir hätten also drei Endzustände. 30:28.970 --> 30:29.550 Sie haben eine Frage? 30:29.550 --> 30:30.370 Okay, 30:35.650 --> 30:35.850 gut. 30:36.130 --> 30:38.290 Habe ich das praktisch geahnt, was Sie fragen wollen. 30:40.930 --> 30:43.810 Also, wir setzen praktisch jetzt die Zustandsmengen durch. 30:43.950 --> 30:45.170 Das sind also unsere neuen Zustände. 30:46.070 --> 30:48.670 Das ist jetzt Geschmackssache, ob Sie da die Mengen hinschreiben oder 30:48.670 --> 30:52.550 einen Zustand mit dem Index, wo die Zustände dran stehen oder die 30:52.550 --> 30:54.450 Zustandsindizes. 30:54.570 --> 30:56.370 Das können Sie machen, wie Sie wollen, das ist völlig egal. 30:56.890 --> 31:00.310 Sie müssen eben nur dafür sorgen, dass Sie zu jeder Menge, die hier 31:00.310 --> 31:05.690 identifiziert wurde, einen entsprechenden Zustand bezeichnen in dem 31:05.690 --> 31:07.210 neuen Automaten. 31:08.150 --> 31:11.130 Und hier haben wir also jetzt die Zustandstafel mit den 31:11.130 --> 31:16.370 entsprechenden, ups, ein bisschen verrutscht dort die Ovale, mit den 31:16.370 --> 31:22.310 Endzuständen, die jeweils gerade den Zustand 3 enthalten. 31:23.210 --> 31:26.470 Und das Zustandsdiagramm sieht jetzt so aus, wie hier angegeben. 31:26.470 --> 31:33.930 Wir haben drei Endzustände und die Übergänge sehen etwas komplizierter 31:33.930 --> 31:34.710 aus als vorher. 31:35.250 --> 31:38.150 Natürlich ist die Struktur, die wir in dem nicht-deterministischen 31:38.150 --> 31:41.270 Automaten so einfach gesehen hatten, hier auch drin. 31:42.350 --> 31:47.310 Ja, also wir haben gesagt, wenn wir in einen Endzustand kommen, muss 31:47.310 --> 31:50.910 das letzte Zeichen schon einmal vorgekommen sein. 31:51.410 --> 31:53.830 Das ist hier bei jedem Endzustand der Fall. 31:53.830 --> 31:58.030 Also hier ist das A schon einmal aufgetaucht. 31:58.870 --> 32:05.870 In dem Fall hier unten, bei dem S5-Strich, ist das B schon einmal 32:05.870 --> 32:06.710 aufgetaucht. 32:07.450 --> 32:12.850 Und bei dem S6-Strich hier unten, oder ganz rechts, da könnte ich mit 32:12.850 --> 32:20.790 A oder B hinkommen, weil A und B beide schon mindestens einmal 32:20.790 --> 32:22.010 aufgetaucht sein müssen. 32:22.010 --> 32:27.650 Sie sehen, jeder Pfad, der zu dem Zustand S3-Strich führt, hat 32:27.650 --> 32:32.610 mindestens einmal ein B oder ein A gesehen. 32:33.310 --> 32:37.570 Und deswegen kommt es dann nicht mehr darauf an, ob ich dort ein A 32:37.570 --> 32:39.990 oder ein B hinschreibe als letztes Zeichen. 32:40.670 --> 32:44.330 Das ist schon einmal vorgekommen und damit bin ich dann auch in einem 32:44.330 --> 32:48.610 Endzustand und was danach passiert, ist auch völlig egal, weil ja, 32:48.970 --> 32:55.550 egal ob A oder B am Ende steht, wir immer genau diese Bedingungen 32:55.550 --> 32:56.210 erfüllt haben. 32:56.770 --> 33:01.950 Aber Sie sehen bei diesem Automaten nicht sofort, wie bei dem nicht 33:01.950 --> 33:05.850 deterministischen Automaten, der ja der Ausgangspunkt war, dass das 33:05.850 --> 33:07.350 genau diese Sprache ist. 33:07.890 --> 33:12.190 Jedes Zeichen oder jedes Wort, das akzeptiert wird, hat als letztes 33:12.190 --> 33:15.930 Zeichen eines, das vorher schon einmal aufgetaucht war. 33:15.930 --> 33:18.590 Eine sehr einfache Beziehung, die wir in dem anderen nicht 33:18.590 --> 33:20.870 deterministischen Automaten sehr einfach gesehen haben. 33:21.390 --> 33:26.970 Also, das nur als Erläuterung, dass das vorteilhaft sein kann, diese 33:26.970 --> 33:28.970 Art von Automaten zu betrachten. 33:29.870 --> 33:32.550 Und die Endzustandsmenge, das ist klar, hatte ich schon gesagt, also 33:32.550 --> 33:35.970 alle, in denen der Endzustand des ursprünglichen Automaten enthalten 33:35.970 --> 33:36.330 ist. 33:36.890 --> 33:39.790 Und damit haben wir jetzt eine weitere Klasse von Automaten 33:39.790 --> 33:40.490 kennengelernt. 33:42.210 --> 33:49.250 Und jetzt kann es sein, dass die deterministische Übergangsfunktion 33:49.250 --> 33:50.970 nicht vollständig definiert ist. 33:51.010 --> 33:55.050 Es könnte sein, dass Sie von einer Zustandsmenge aus nicht 33:55.050 --> 34:02.830 weitergehend, also nicht in eine weitere Menge haben. 34:02.970 --> 34:08.130 Dann kann man einfach durch Einführung eines nicht in der Menge der 34:08.130 --> 34:10.970 Endzustände enthaltenen, des zusätzlichen Sackgassenzustands, das 34:10.970 --> 34:12.050 einfach vervollständigen. 34:12.670 --> 34:15.950 Und dann hat man auf jeden Fall einen vollständig definierten 34:15.950 --> 34:17.550 deterministischen Automaten. 34:17.630 --> 34:19.690 Sie werden solche Beispiele in den Übungen kennenlernen. 34:20.310 --> 34:23.230 Das ist dann sofort ersichtlich, wann man so etwas machen muss, dass 34:23.230 --> 34:26.910 man noch einen solchen Sackgassenzustand dazufügt, damit der Automat 34:26.910 --> 34:28.830 vollständig definiert ist. 34:29.830 --> 34:33.470 Und was wir damit mit diesem Beispiel gesehen haben, also den 34:33.470 --> 34:37.590 Algorithmus brauchte ich hier nicht algorithmisch aufzuschreiben, dass 34:37.590 --> 34:41.470 wir zu jedem nicht deterministischen endlichen Automaten einen 34:41.470 --> 34:44.670 endlichen Automaten, einen deterministischen endlichen Automaten 34:44.670 --> 34:47.670 finden können, der die gleiche Sprache akzeptiert, der also äquivalent 34:47.670 --> 34:49.570 ist und natürlich umgekehrt. 34:50.090 --> 34:51.890 Und die Umkehrung ist trivial. 34:54.210 --> 34:56.610 Der erste Teil zu dem nicht deterministischen gibt es einen 34:56.610 --> 34:59.410 deterministischen, das ist genau das, was ich Ihnen gerade eben 34:59.410 --> 35:00.570 gezeigt habe. 35:01.150 --> 35:04.570 Also, das haben wir damit eingesehen, dass wir durch die nicht 35:04.570 --> 35:09.230 deterministischen Automaten keine wirkliche Erweiterung der 35:09.230 --> 35:13.750 akzeptierten Menge von Sprachen bekommen. 35:14.690 --> 35:18.110 Also, diese Sprachklassen, die sind identisch. 35:18.850 --> 35:23.970 Das L-E-A von E, das sind gerade die Sprachen, die von endlichen 35:23.970 --> 35:26.490 Automaten akzeptiert werden, über dem Alphabet E. 35:27.050 --> 35:30.370 Und das L-N-E-A, das sind die, die von nicht deterministischen 35:30.370 --> 35:31.890 endlichen Automaten akzeptiert werden. 35:31.890 --> 35:33.250 Die gleiche Sprachklasse. 35:33.790 --> 35:38.590 Und das heißt, Sie können sich beliebig wählen, einen nicht 35:38.590 --> 35:42.050 deterministischen oder deterministischen Automaten, um eine Sprache zu 35:42.050 --> 35:45.130 charakterisieren, die in dieser Sprachklasse drin liegt. 35:46.590 --> 35:47.930 Was sind die Vorteile? 35:48.110 --> 35:51.810 Sie haben eine einfache Definition von Automaten, also zum Beispiel, 35:52.510 --> 35:57.330 wenn Sie sagen, es soll ein Wort E1 bis EK von dem Automaten 35:57.330 --> 35:58.270 akzeptiert werden. 35:58.270 --> 36:02.670 Sie suchen praktisch in einem Dokument, Sie haben hier ein Dokument 36:02.670 --> 36:06.030 und Sie suchen dort ein bestimmtes Wort, das jetzt hier als E1 bis EK 36:06.030 --> 36:07.010 dargestellt ist. 36:07.690 --> 36:11.050 Der Automat, den ich hier aufgeschrieben habe, macht genau das. 36:11.870 --> 36:14.310 Der akzeptiert beliebige Zeichen vorher. 36:15.190 --> 36:19.650 Und dann gibt es eine Folge E1, E2, E3 bis EK. 36:20.150 --> 36:21.490 Und dann komme ich in einen Endzustand. 36:21.690 --> 36:23.990 Dann ist nämlich genau dieses Wort hier aufgetaucht. 36:23.990 --> 36:26.670 Und danach kann irgendetwas Beliebiges noch passieren. 36:29.110 --> 36:33.670 Das heißt, das Wort könnte also auch mehrfach auftauchen hier, das ist 36:33.670 --> 36:34.030 egal. 36:34.170 --> 36:41.050 Ich würde hier also eine Eingabe, das heißt ein Dokument D in dem 36:41.050 --> 36:45.170 Fall, würde ich akzeptieren, wenn ich das Dokument hier eingebe, dann 36:45.170 --> 36:51.290 würde dieser Automat das Wort akzeptieren, weil dieses Dokument 36:51.290 --> 36:55.310 akzeptieren, weil das Wort E1 bis EK, das Wort W darin auftaucht. 36:55.550 --> 36:57.570 Ein einfacher, mustererkennender Automat. 36:57.970 --> 37:01.530 Der ist nicht sehr effizient, man kann bessere angeben, aber das ist 37:01.530 --> 37:04.730 eine Möglichkeit, so ein Verfahren zu beschreiben. 37:06.330 --> 37:10.090 Sie sehen, das hat durchaus einige einfache Vorteile. 37:11.170 --> 37:13.790 Wie der deterministische Automat dazu aussieht, können Sie sich leicht 37:13.790 --> 37:17.350 überlegen mit dem Verfahren, das ich Ihnen gerade vorgestellt habe. 37:18.020 --> 37:19.790 Es gibt weitere Vorteile. 37:20.410 --> 37:26.310 Manchmal möchte ich gewisse Operationen ausführen auf Sprachen. 37:27.310 --> 37:33.130 Beziehungsweise, ich interessiere mich dafür, was ist eigentlich, was 37:33.130 --> 37:36.890 passiert eigentlich, wenn ich die Sprachen von zwei endlichen 37:36.890 --> 37:38.270 Automaten vereinige. 37:38.890 --> 37:42.250 Ich habe zwei Automaten, die akzeptieren zwei Sprachen. 37:42.910 --> 37:46.070 Jetzt frage ich mich, kann ich einen Automaten angeben, der die 37:46.070 --> 37:48.310 Vereinigung der beiden Sprachen akzeptiert? 37:49.450 --> 37:53.090 Bleibe ich dann in der Menge der von endlichen Automaten erkennbaren 37:53.090 --> 37:53.690 Sprachen? 37:55.230 --> 37:57.430 Und das können wir uns mit einer einfachen Konstruktion jetzt 37:57.430 --> 38:01.070 überlegen, bei der wir genau die Möglichkeiten ausnutzen, etwas nicht 38:01.070 --> 38:02.550 deterministisch zu machen. 38:03.490 --> 38:07.250 Also, wir haben jetzt zwei Automaten, A und A'. 38:07.970 --> 38:12.710 Wir nehmen an, dass die Zustandsmengen disjunkt sind, sonst könnte es 38:12.710 --> 38:13.570 Verwechslungen geben. 38:14.330 --> 38:18.870 Und jetzt definieren wir uns einen Automaten, der nicht 38:18.870 --> 38:24.450 deterministisch ist, der jetzt die beiden Sprachen L und L'. 38:24.450 --> 38:29.830 akzeptieren soll, indem wir hier einfach eine disjunkte Vereinigung 38:29.830 --> 38:32.950 der beiden Sprachen bilden, mit einem gemeinsamen neuen 38:32.950 --> 38:33.670 Anfangszustand. 38:33.730 --> 38:34.730 Das sieht aus wie folgt. 38:34.810 --> 38:36.730 Wir haben also hier unsere beiden Automaten. 38:37.870 --> 38:42.850 Die haben beide irgendeinen Anfangszustand, hier S0 und S0'. 38:43.570 --> 38:46.830 Und gehen dann in irgendwelche Folgezustände über bei Eingabe von 38:46.830 --> 38:47.750 irgendwelchen Zeichen. 38:49.550 --> 38:54.890 Und kommen natürlich irgendwann auch hier zu irgendwelchen Zuständen S 38:54.890 --> 38:56.770 aus F. 38:57.650 --> 39:00.290 Hier wahrscheinlich auch zu irgendeinem S'. 39:02.170 --> 39:03.930 Da gibt es also auch Endzustände. 39:04.490 --> 39:06.750 Und jetzt machen wir daraus einen neuen Automaten. 39:07.570 --> 39:09.790 Ich sagte, wir nehmen einen neuen Anfangszustand. 39:11.550 --> 39:17.930 Also, einen neuen Anfangszustand, dem wir die Möglichkeit geben, mit 39:17.930 --> 39:23.810 einem Zeichen A das Gleiche zu machen wie der Automaten A, oder auch 39:23.810 --> 39:25.950 das Gleiche wie der Automaten A'. 39:26.610 --> 39:30.970 Das heißt, der kann mit dem A auf dieses S, ich habe das hier mit dem 39:30.970 --> 39:35.530 Index A versehen, der Folgezustand von S0 bei Eingabe von A, das ist 39:35.530 --> 39:36.710 die eine Möglichkeit. 39:36.970 --> 39:40.710 Und die andere Möglichkeit ist, auf das S A' zu gehen, der 39:40.710 --> 39:43.750 Folgezustand von S0' bei Eingabe von A. 39:44.030 --> 39:45.730 Die beiden Möglichkeiten hat er. 39:47.050 --> 39:47.890 Und das ist alles. 39:49.530 --> 39:50.930 Mehr verändern wir gar nicht. 39:50.990 --> 39:53.490 Natürlich müssen wir die beiden Endzustandsmengen vereinigen. 39:54.930 --> 39:55.890 Und was passiert dann? 39:56.370 --> 40:01.390 Wenn wir ein Wort eingeben, und dieses Wort ist meinetwegen in der 40:01.390 --> 40:07.450 Sprache des Automaten A, dann kann dieser Automat natürlich von dem 40:07.450 --> 40:13.790 S02' aus übergehen zu einem Zustand in dieser Folgezustandsmenge und 40:13.790 --> 40:18.010 von da aus entsprechend dem Automaten A weiterarbeiten und kommt dann 40:18.010 --> 40:21.630 zu einem Endzustand, wenn der Automat A zu einem Endzustand gekommen 40:21.630 --> 40:22.210 ist. 40:22.710 --> 40:28.230 Wenn wir ein Wort haben aus der Sprache L', dann gibt es ja hier die 40:28.230 --> 40:33.650 Möglichkeit, in einen Folgezustand des Anfangszustands des S0' 40:33.870 --> 40:39.790 überzugehen und von da aus immer weiter, bis wir in einen Endzustand 40:39.790 --> 40:40.430 von A'. 40:41.090 --> 40:45.510 Das heißt, wir können jedes Wort aus L und jedes Wort aus L' 40:45.870 --> 40:47.530 akzeptieren. 40:47.770 --> 40:49.190 Es gibt jeweils eine Folge. 40:50.130 --> 40:56.030 Und wenn wir ein Wort haben, das nicht in L und nicht in L' ist, dann 40:56.030 --> 41:03.270 gab es weder in A noch in A' eine Möglichkeit, von dem Anfangszustand 41:03.270 --> 41:05.850 aus dem jeweiligen zu einem Endzustand zu kommen. 41:06.530 --> 41:09.990 Und dann gibt es auch hier keine Möglichkeit, weil wir ja nur zu 41:09.990 --> 41:16.270 Beginn einmal auf die Folgezustände von S0' gegangen sind und danach 41:16.270 --> 41:21.990 konsequent so weitermachen, wie das in dem Automaten A oder B der Fall 41:21.990 --> 41:22.310 war. 41:22.310 --> 41:28.950 Das heißt, wir können keine neuen Folgen von Zuständen hier erreichen, 41:29.250 --> 41:33.830 die zu einem Endzustand führen für ein Wort, bei dem das vorher nicht 41:33.830 --> 41:34.450 der Fall war. 41:35.510 --> 41:37.490 Insofern ist das hier eine einfache Veränderung. 41:37.590 --> 41:43.010 Das heißt, wir haben einfach nur diesen neuen S0' dazugenommen. 41:43.690 --> 41:49.250 Wir haben die beiden Endzustandsmengen vereinigt und müssen allerdings 41:49.250 --> 41:57.670 das S02' dazunehmen, falls S0 oder S0' ein Endzustand gewesen ist. 41:58.630 --> 42:03.170 In dem Fall würde nämlich das leere Wort akzeptiert werden und das 42:03.170 --> 42:08.210 muss natürlich in dem Fall dann auch von dem S02' aus der Fall sein. 42:08.590 --> 42:11.590 Das heißt, das muss dann auch ein Endzustand sein, damit wir das Wort 42:11.590 --> 42:14.650 Lambda, das leere Wort akzeptieren können. 42:14.650 --> 42:17.870 Alles andere bleibt gleich. 42:18.610 --> 42:26.510 Das heißt, unser Delta-2' SE ist gleich dem Delta-SE, also dem 42:26.510 --> 42:32.070 Folgezustand von S bei Eingabe von E, sofern das S aus dem Automaten A 42:32.070 --> 42:39.570 ist, und gleich Delta' von SE, falls das S aus dem Automaten A' ist. 42:40.440 --> 42:47.230 Und ansonsten, wenn das S gleich S02' ist, dann ist es halt die 42:47.230 --> 42:52.990 Vereinigung der beiden Zustände, die wir von S0 und S0' erreichen 42:52.990 --> 42:53.450 würden. 42:54.310 --> 42:56.330 Also die Menge, die diese beiden Zustände enthält. 42:57.330 --> 43:00.770 Damit sehen wir, offensichtlich gibt es einen nicht deterministischen 43:00.770 --> 43:06.790 endlichen Automaten, der diese Sprache L' akzeptieren kann, also ist 43:06.790 --> 43:10.270 die Menge der Sprachen, die von endlichen Automaten akzeptiert werden, 43:10.810 --> 43:12.490 abgeschlossen gegenüber Vereinigung. 43:13.910 --> 43:16.650 Das ist eine Operation, die wir häufig gerne anwenden. 43:17.870 --> 43:19.790 Also das ist das, was hier unten... 43:19.790 --> 43:21.030 Ups, was habe ich denn jetzt gemacht? 43:22.690 --> 43:23.710 Das ist interessant. 43:24.170 --> 43:25.030 Wollte ich gar nicht. 43:26.810 --> 43:27.810 Wo bin ich wieder zurück? 43:28.030 --> 43:29.530 Da kann ich zoomen. 43:30.010 --> 43:33.390 Auch ganz nett, die Funktion nutze ich eigentlich kaum, aber ich kann 43:33.390 --> 43:35.330 also jetzt hier reinzoomen in meine Folien. 43:35.890 --> 43:37.090 Das ist eine ganz nette Funktion. 43:38.530 --> 43:42.430 Und hier unten steht also gerade jetzt, dass wir für alle W aus Estern 43:43.110 --> 43:48.950 also die Eigenschaft haben, dass wir von S02' bei Eingabe von W jetzt 43:48.950 --> 43:56.570 auf einen Endzustand kommen, genau dann, wenn wir von einem der beiden 43:56.570 --> 44:02.410 Anfangszustände S0 oder S0' auf den Endzustand gekommen wären. 44:03.530 --> 44:06.230 Also das ist jetzt die richtige Eigenschaft. 44:06.890 --> 44:10.530 Und jetzt schauen wir uns, dann wissen wir natürlich, dass die 44:10.530 --> 44:13.910 Vereinigungsmenge akzeptiert werden kann, das habe ich gerade eben 44:13.910 --> 44:14.530 schon gesagt. 44:14.970 --> 44:17.250 Und jetzt schauen wir uns noch eine weitere Operation an. 44:18.410 --> 44:19.830 Vereinigung haben wir gerade betrachtet. 44:20.910 --> 44:23.810 Wir schauen uns an das Produkt von zwei Sprachen. 44:24.590 --> 44:32.510 Also, wir haben irgendein Wort, das akzeptiert wurde von unserem 44:32.510 --> 44:36.350 Automaten oder in der Sprache L liegt. 44:36.850 --> 44:42.610 Wenn wir hier ein U haben und ein V, dann betrachten wir einfach das 44:42.610 --> 44:44.410 Hintereinanderschreiben von U und V. 44:45.410 --> 44:49.450 Und jedes Wort, das wir so durch Kombination von zwei Wörtern aus L 44:49.450 --> 44:54.910 und L' bekommen, ist in der Sprache L mal ein Strich drin, das Produkt 44:54.910 --> 44:55.930 von zwei Sprachen. 44:59.250 --> 45:05.770 Und tatsächlich ist es so, dass diese Menge der Sprachen, die von 45:05.770 --> 45:09.710 endlichen Automaten akzeptiert werden, abgeschlossen ist unter der 45:09.710 --> 45:10.470 Produktbildung. 45:11.950 --> 45:15.910 Das heißt, stellen Sie sich vor, Sie haben hier einen Automaten A und 45:15.910 --> 45:17.590 einen Automaten A'. 45:19.090 --> 45:22.570 So, das sind die beiden Automaten, die L und L' akzeptieren. 45:23.150 --> 45:26.670 Sie haben hier irgendwo Ihren Anfangszustand S0. 45:29.310 --> 45:35.950 Und jetzt wollen Sie zeigen, Sie können natürlich jedes Anfangsstück 45:35.950 --> 45:40.190 hier, U haben Sie da drin, wenn Sie also U vollständig eingelesen 45:40.190 --> 45:44.750 haben, sind Sie hier in irgendeinem Endzustand aus F. 45:45.700 --> 45:50.290 Dann müssen wir natürlich jetzt noch in der Lage sein, das V 45:50.290 --> 45:52.430 durchzulaufen. 45:52.950 --> 45:58.830 Wenn also hier ein Anfangszustand war bei dem A', müssten wir ähnlich 45:58.830 --> 46:04.230 wie vorher bei der Konstruktion jetzt von unserem Endzustand aus auf 46:04.230 --> 46:10.210 jeden Folgezustand des Anfangszustands laufen, um dann mit dem ersten 46:10.210 --> 46:15.530 Zeichen von dem V entsprechend in den Automaten A' hineinzukommen. 46:16.290 --> 46:20.170 Wir müssen also diese Verbindung schaffen und kommen dann hier am Ende 46:20.170 --> 46:22.650 wieder zu irgendwelchen Endzuständen, zum Beispiel zu einem 46:22.650 --> 46:26.190 Endzustand, bei dem das V akzeptiert worden wäre. 46:26.330 --> 46:31.110 Also mit U würden wir hier durchlaufen, mit V dadurch, da das erste 46:31.110 --> 46:35.230 Zeichen von dem V aber diesen Übergang hier bewirkt, müssen wir zu den 46:35.230 --> 46:40.110 Folgezuständen des Anfangszustands laufen, so wie wir das vorher bei 46:40.110 --> 46:41.970 der Vereinigung auch gemacht hatten. 46:43.110 --> 46:44.210 Pause kommt sofort. 46:44.830 --> 46:48.170 Sie haben recht, dreiviertel Stunde geht gleich los. 46:48.290 --> 46:50.490 Ich wollte diese eine Folie noch fertig machen, dann machen wir eine 46:50.490 --> 46:50.790 Pause. 46:51.410 --> 46:57.010 Also das ist das Produkt und Sie sehen, wir haben wieder einen nicht 46:57.010 --> 47:00.750 deterministischen Automaten, als Produktautomat, weil wir ja von 47:00.750 --> 47:07.670 diesem Zustand aus jetzt zu all diesen Folgezuständen laufen müssen. 47:08.730 --> 47:14.640 Und das wird dann ein nicht deterministischer Automat. 47:15.070 --> 47:20.230 Desjunkte Vereinigung der Zustandsmengen für Lambda aus L' kann 47:20.230 --> 47:24.030 natürlich auch sein, wenn das L' hier das leere Wort enthält, dann 47:24.030 --> 47:28.330 müsste natürlich die Endzustände des Automaten A, auch Endzustände des 47:28.330 --> 47:33.150 neuen Automaten sein, aber wir haben eben von den Endzuständen von A 47:33.150 --> 47:38.030 zusätzlich alle Übergänge zu Nachfolgern des Anfangszustands von A' 47:38.250 --> 47:42.330 und damit wieder etwas nicht deterministisches drin. 47:43.110 --> 47:47.850 Da wir wissen, dass nicht deterministische Automaten keine wesentliche 47:47.850 --> 47:52.090 Veränderung der Akzeptierungsqualität bringen, wissen wir, das ist 47:52.090 --> 47:57.010 wieder ein endlicher Automat und damit ist das Produkt auch wieder 47:57.010 --> 48:01.330 eine Sprache, die von endlichen Automaten akzeptiert werden kann. 48:02.670 --> 48:05.810 Und schließlich gibt es noch eine Operation, die auch häufig angewandt 48:05.810 --> 48:07.090 wird, das ist die Iteration. 48:07.920 --> 48:13.730 Das heißt, wir nehmen uns irgendein Wort, meinetwegen irgendein Wort W 48:13.730 --> 48:22.070 aus L' her und wollen jetzt zum Beispiel W, W hinschreiben oder wir 48:22.070 --> 48:27.690 können auch beliebig viele Ws hinschreiben oder wir können, wenn wir 48:27.690 --> 48:33.990 U, V, W haben, können wir auch U, V, W hinschreiben oder U, V, V, W 48:33.990 --> 48:34.930 oder und so weiter. 48:35.270 --> 48:40.330 Sie können also beliebige Folgen von Wörtern aus L' hinschreiben, auch 48:40.330 --> 48:45.490 eine leere Wiederholung von Wörtern aus L', das heißt, das leere Wort 48:45.490 --> 48:46.290 ist immer da drin. 48:47.330 --> 48:50.250 Und auch das müssten wir wieder entsprechend konstruieren, das ist 48:50.250 --> 48:56.590 unser Automat A, der also unsere Sprache L' akzeptiert. 48:56.590 --> 49:00.990 Auch da haben wir einen Anfangszustand, auch hier haben wir wieder 49:00.990 --> 49:02.730 irgendwelche Endzustände. 49:03.390 --> 49:08.950 Und von denen aus müssen wir jetzt nicht zu den Folgezuständen eines 49:08.950 --> 49:14.530 anderen Automaten springen, sondern zu den Folgezuständen unseres 49:14.530 --> 49:16.730 eigenen Automaten. 49:17.330 --> 49:22.490 Weil wir in der Lage sein müssen, jedes Wort, das von A akzeptiert 49:22.490 --> 49:27.210 wird, beliebig oft, beliebig dort hineinschreiben zu können. 49:27.570 --> 49:32.010 Das heißt, nachdem wir ein Wort akzeptiert haben, müssen wir in der 49:32.010 --> 49:36.510 Lage sein, auch noch ein weiteres Wort hier mit zu verarbeiten, das in 49:36.510 --> 49:37.890 der Sprache von A ist. 49:38.310 --> 49:41.730 Das heißt, wir müssen diese Konstruktion, alle Nachfolge des 49:41.730 --> 49:46.230 Anfangszustands werden zusätzlich dazu genommen, hier in dem Fall 49:46.230 --> 49:50.530 machen für die Endzustände unseres Automaten und verzweigen auf die 49:50.530 --> 49:53.830 Nachfolgezustände unseres Anfangszustands. 49:54.190 --> 49:57.890 Und natürlich muss der Anfangszustand auch ein Endzustand werden, weil 49:57.890 --> 50:02.310 wir ja das leere Wort, weil das L' ist, auch akzeptieren müssen. 50:02.310 --> 50:07.690 Also das ist eine weitere Konstruktion neuer Anfangszustand S-Stern, 50:07.830 --> 50:11.450 gleichzeitig neuer Endzustand und von S-Stern aus die gleichen 50:11.450 --> 50:16.270 Übergänge wie vom alten Anfangszustand und von jedem alten Endzustand 50:16.270 --> 50:21.490 zusätzlich alle Übergänge zu Nachfolgern des alten Anfangszustands. 50:21.790 --> 50:24.510 Also eine sehr kanonische Konstruktion. 50:24.510 --> 50:28.750 Und damit sehen Sie, dass diese Konstruktion der nicht 50:28.750 --> 50:32.390 deterministischen Automaten uns schon einen Vorteil gebracht hat. 50:32.730 --> 50:37.450 Wir haben hier eine relativ einfache, systematische Konstruktion von 50:37.450 --> 50:42.350 Automaten, um zu zeigen, dass wir die Vereinigung, das Produkt und die 50:42.350 --> 50:47.950 Iteration von Sprachen tatsächlich akzeptieren können mit endlichen 50:47.950 --> 50:48.550 Automaten. 50:48.550 --> 50:52.590 Und jetzt machen wir eine kurze Pause und machen danach dann weiter. 50:57.490 --> 50:58.170 So, 51:08.190 --> 51:08.970 wir machen weiter. 51:09.830 --> 51:14.070 Sie haben gesehen, ich habe hier mal wieder eine Frage Ihnen zur 51:14.070 --> 51:19.370 Verfügung gestellt, mit einer sehr eindeutigen Antwortstatistik im 51:19.370 --> 51:19.910 Augenblick. 51:20.410 --> 51:24.390 Die Frage ist, welche Informationen stehen in der Konfiguration eines 51:24.390 --> 51:31.050 endlichen Automaten und das haben Sie überwiegend richtig hier 51:31.050 --> 51:35.150 aufgeschrieben, der aktuelle Zustand und das restliche Eingabewort. 51:35.770 --> 51:39.030 Die Position des Lesekopfes auf dem Band ist eigentlich völlig 51:39.030 --> 51:39.870 uninteressant. 51:40.810 --> 51:44.650 Es interessiert nur, was muss der Automat noch machen ab der aktuellen 51:44.650 --> 51:50.530 Position und der Inhalt des gesamten Eingabebandes ist auch nicht 51:50.530 --> 51:54.350 interessant, weil der Teil, den wir schon gelesen haben, natürlich 51:54.350 --> 51:55.370 nicht mehr relevant ist. 51:55.430 --> 51:58.810 Man könnte es auch so machen, dass man einen Zustand angibt, Position 51:58.810 --> 52:01.950 des Lesekopfes und den gesamten Inhalt des Bandes, aber das wäre zu 52:01.950 --> 52:02.610 viel Information. 52:03.530 --> 52:07.570 Im Hinblick auf Datensparsamkeit braucht man ja nur das, was man noch 52:07.570 --> 52:12.530 anschauen muss, um das restliche oder das folgende Verhalten des 52:12.530 --> 52:14.550 Automaten tatsächlich zu beschreiben. 52:15.390 --> 52:18.710 Und das haben Sie auch hier überwiegend richtig gesehen. 52:18.850 --> 52:21.710 Einer hat sich vertippt, das kann ja auch vorkommen. 52:21.950 --> 52:25.610 Also vielen Dank für die gute Antwort, die korrekt ist. 52:27.170 --> 52:30.650 Kommen wir weiter zu der Vorlesung. 52:31.110 --> 52:37.250 Das waren jetzt diese Operationen und ein weiterer Punkt, den wir uns 52:37.250 --> 52:48.450 anschauen, ist natürlich der Aufwand, den wir treiben müssen, um das 52:48.450 --> 52:50.710 Wortproblem zu entscheiden. 52:51.310 --> 52:53.170 Das hatte ich ja gesagt, das ist ein ganz wichtiger Punkt. 52:53.330 --> 52:57.250 Das war die Effizienz einer Sprachbeschreibung, das andere war die 52:57.250 --> 52:58.450 Ausdrucksfähigkeit. 52:59.250 --> 53:03.270 Bei der Ausdrucksfähigkeit wissen wir schon, diese Sprachen sind 53:03.270 --> 53:06.530 offensichtlich nicht ausreichend für das, was wir in 53:06.530 --> 53:07.730 Programmiersprachen brauchen. 53:08.270 --> 53:10.930 Denn in Programmiersprachen brauchen wir auf jeden Fall die 53:10.930 --> 53:13.350 Möglichkeit, Klammerschachtelungen vorzunehmen. 53:13.870 --> 53:16.570 Und wenn wir eine Sprache wie A auch in B hochendlich akzeptieren 53:16.570 --> 53:19.350 können, können wir auch keine Klammerschachtelungen ausdrücken. 53:19.810 --> 53:22.050 Das heißt, einfache Dinge, die zum Beispiel in arithmetischen 53:22.050 --> 53:26.410 Ausdrücken vorkommen oder in irgendwelchen Schachtelungen innerhalb 53:26.410 --> 53:29.610 eines Programms, können wir hier gar nicht darstellen. 53:29.610 --> 53:33.610 Das heißt, die endlichen Automaten sind sicherlich nicht ausreichend, 53:33.870 --> 53:35.390 um Programmiersprachen zu beschreiben. 53:36.250 --> 53:37.770 Und wie sieht das mit der Effizienz aus? 53:37.890 --> 53:40.590 Wie viel Aufwand haben wir, um zu entscheiden, ob ein Wort in der 53:40.590 --> 53:41.370 Sprache ist? 53:41.950 --> 53:45.050 Naja, wir müssen ja nur das Wort abarbeiten. 53:45.630 --> 53:48.910 Für jedes Zeichen müssen wir einmal in unserer Zustandstabelle 53:48.910 --> 53:51.650 nachschauen, was ist der nächste Zustand. 53:52.670 --> 53:55.790 Je nachdem, wie Sie es aufgebaut haben, ist es also kein großer 53:55.790 --> 53:57.510 Aufwand, das ist ein linearer Aufwand. 53:57.510 --> 54:03.430 Das heißt, Sie haben einen Aufwand, der linear in der Wortlänge ist. 54:04.210 --> 54:05.610 Besser geht es natürlich gar nicht. 54:06.570 --> 54:09.090 Und wenn Sie nicht die terministischen Automaten haben, dann haben Sie 54:09.090 --> 54:09.510 natürlich... 54:10.070 --> 54:12.250 Zunächst mal sieht das so aus, als könnte das schwierig werden. 54:13.430 --> 54:18.550 Da haben wir ja die Konfigurationen, von denen aus sich das so sehr 54:18.550 --> 54:19.530 verzweigen kann. 54:20.070 --> 54:24.470 Und wir suchen ja nur irgendeinen Pfad, der tatsächlich dann zu einem 54:24.470 --> 54:25.430 Endzustand führt. 54:26.130 --> 54:29.050 Da könnte ja sein, dass man alle diese Möglichkeiten erstmal 54:29.050 --> 54:30.070 durchprobieren muss. 54:30.910 --> 54:32.330 Und das ist natürlich ziemlich viel. 54:34.910 --> 54:37.370 Aber was muss ich denn alles durchschauen? 54:37.990 --> 54:45.090 Also, ich habe ja maximal in der Menge von Zuständen drin, habe ich 54:45.090 --> 54:46.090 alle Zustände. 54:47.870 --> 54:52.570 Das ist eine feste Zahl von Zuständen, das heißt, die Menge an 54:52.570 --> 54:55.310 möglichen Zuständen, die ich erreichen kann, die ist gar nicht so 54:55.310 --> 54:55.750 groß. 54:56.670 --> 54:59.830 Und ich muss nur für jedes Zeichen schauen, wie laufe ich hier weiter. 55:00.210 --> 55:06.190 Kann ich dabei irgendwann in eine Menge kommen, in der ein Endzustand 55:06.190 --> 55:06.550 ist? 55:07.790 --> 55:12.130 Und das heißt, ich muss jedes Mal nur so oft reinschauen in meine 55:12.130 --> 55:17.730 Übergangstabelle, wie ich Zustände gerade habe in der möglichen Menge 55:17.730 --> 55:20.070 von Zuständen, in der der Automat sein könnte. 55:20.070 --> 55:26.370 Das ist eine Konstante, die Anzahl der Zustände ist eine Konstante für 55:26.370 --> 55:31.110 den Automaten, unabhängig von der Wortlänge, das heißt, wir haben hier 55:31.110 --> 55:35.570 ebenfalls eine Linearität in der Wortlänge, der Aufwand ist allerdings 55:35.570 --> 55:37.870 etwas höher, theoretisch. 55:39.390 --> 55:42.190 Praktisch hatten wir gesehen, bei den Automaten, die wir betrachtet 55:42.190 --> 55:46.230 hatten, konnte er auch niedriger sein, weil wir gar nicht alle 55:46.230 --> 55:49.930 Übergänge tatsächlich für jedes Zeichen dort drin haben, für einige 55:49.930 --> 55:51.370 Zeichen steht dort gar kein Übergang. 55:51.470 --> 55:52.090 Sie haben eine Frage? 56:12.500 --> 56:15.260 Na ja, also die Frage ist, was passiert, wenn ich zwischendurch schon 56:15.260 --> 56:16.760 mal zum Endzustand gekommen bin? 56:17.360 --> 56:20.720 Wir wissen ja, dass die Akzeptierungsentscheidung erst getroffen 56:20.720 --> 56:24.660 werden kann, wenn wir das Wort vollständig abgearbeitet haben. 56:25.240 --> 56:30.080 Das heißt, wir müssen so lange eine Menge von möglichen Zuständen 56:30.080 --> 56:35.600 unseres Automaten betrachten, bis wir alle Zeichen abgearbeitet haben. 56:35.600 --> 56:39.960 Und diese Menge von Folgezuständen, die kann wachsen, kann auch wieder 56:39.960 --> 56:44.780 kleiner werden, wenn wir also von einigen Zuständen, die wir schon mal 56:44.780 --> 56:47.140 erreicht hatten, vielleicht gar nicht weiterlaufen können, dann wird 56:47.140 --> 56:50.600 die wieder kleiner, aber sie kann nie größer werden als die 56:50.600 --> 56:51.960 Gesamtmenge aller Zustände. 56:52.960 --> 56:59.140 Wir müssen also so lange diese aktuelle mögliche Anzahl von, oder die 56:59.140 --> 57:02.840 aktuell möglichen Zustände, in denen der Automat sein kann, betrachten 57:02.840 --> 57:07.960 und deren Folgezustände bei Eingabe eines weiteren Zeichens, bis wir 57:07.960 --> 57:11.560 alle Zeichen abgearbeitet haben und dann schauen wir uns an, ist in 57:11.560 --> 57:14.100 der Menge, die wir dann haben, ein Endzustand drin. 57:15.500 --> 57:18.860 Also das ist eine ganz einfache, systematische Vorgehensweise. 57:19.400 --> 57:23.420 Und diese Menge an Zuständen, die wir betrachten müssen, die kann 57:23.420 --> 57:25.500 natürlich nicht größer werden als die Menge aller Zustände. 57:25.700 --> 57:28.840 Und das ist eine Konstante, deswegen ist es insgesamt linear an der 57:28.840 --> 57:36.500 Wortlänge, weil wir für jedes Zeichen maximal für jeden Zustand des 57:36.500 --> 57:38.900 Automaten die Folgezustandsmenge betrachten müssen. 57:39.020 --> 57:39.840 Also das ist immer noch linear. 57:40.440 --> 57:41.460 Da gibt es noch eine Frage. 57:43.300 --> 57:45.180 Muss das alles immer so formal sein? 57:45.340 --> 57:46.400 Ist ziemlich trocken so? 57:47.040 --> 57:49.020 Das ist leider so. 57:49.200 --> 57:49.900 Tut mir leid. 57:50.540 --> 57:53.000 Ich versuche immer, Ihnen auch praktische Beispiele zu geben. 57:53.100 --> 57:56.000 Ich habe Ihnen gerade das praktische Beispiel gegeben auf der einen 57:56.000 --> 57:59.800 Folie, wo ich sagte, wenn wir in einem Dokument ein Muster suchen, ein 57:59.800 --> 58:02.240 Wort suchen, können wir einfach einen endlichen Automaten 58:02.240 --> 58:02.760 aufschreiben. 58:03.740 --> 58:05.360 Das ist ein praktisches Beispiel. 58:05.780 --> 58:09.000 Sie können sagen, da stand jetzt nur E1 bis EK und da stand nicht 58:09.000 --> 58:09.560 irgendein Wort. 58:09.620 --> 58:12.080 Ich hätte Ihnen irgendein Wort hinschreiben können und hätte dann 58:12.080 --> 58:15.680 dieses Wort dort, ich hätte also hinschreiben können, wenn wir hier 58:15.680 --> 58:18.340 irgendein Wort akzeptieren wollen. 58:21.420 --> 58:24.540 So, meinetwegen dieses Wort AH. 58:25.900 --> 58:29.840 So, dann können wir hier sagen, das ist also jetzt hier unser Automat, 58:30.020 --> 58:33.700 der zunächst mal das Zeichen A, dann das H, dann das A akzeptiert, 58:33.980 --> 58:36.640 davor irgendetwas macht und hinterher irgendetwas macht. 58:36.940 --> 58:38.360 Und dann kann er das Wort AH akzeptieren. 58:38.700 --> 58:39.700 Ist das jetzt praktischer? 58:40.640 --> 58:42.420 Ist auch nicht viel praktischer, dieses Beispiel. 58:42.940 --> 58:44.500 Aber das ist halt leider das Problem. 58:44.600 --> 58:45.540 Es ist nun mal Theorie. 58:45.540 --> 58:48.000 Es sind theoretische formale Grundlagen. 58:48.880 --> 58:52.060 Und da muss man sehen, dass man das dann eben auch so formal 58:52.060 --> 58:52.700 aufschreibt. 58:53.740 --> 58:58.300 Und ich versuche immer, Ihnen dabei wieder klarzumachen, was sind die 58:58.300 --> 59:02.380 praktischen Fragestellungen, die uns treiben bei dem, was wir hier 59:02.380 --> 59:02.640 machen. 59:03.000 --> 59:07.300 Und die eine Fragestellung war, wie aufwendig ist das, zu entscheiden, 59:07.440 --> 59:10.760 ob ein Programm korrekt ist oder nicht, oder ein Wort in der Sprache 59:10.760 --> 59:11.220 ist oder nicht. 59:11.260 --> 59:12.580 Das haben wir gerade hier beantwortet. 59:12.580 --> 59:16.720 Die andere Frage war, reicht die Ausdrucksfähigkeit aus, um alles das 59:16.720 --> 59:19.020 zu beschreiben, was wir in Programmen aufschreiben wollen. 59:19.460 --> 59:23.260 Das war das Pumping Lemma, das uns gezeigt hat, die Sprachen von 59:23.260 --> 59:25.140 endlichen Automaten reichen nicht aus. 59:25.920 --> 59:28.680 Damit haben wir diese zwei Fragen schon mal beantwortet. 59:29.420 --> 59:36.040 Und wir hatten gesucht nach den Möglichkeiten, Sprachen formal, also 59:36.040 --> 59:40.820 nach klaren Regeln, auf einem endlichen Stück Papier tatsächlich zu 59:40.820 --> 59:41.340 beschreiben. 59:41.340 --> 59:43.840 Und haben jetzt also die Automaten kennengelernt. 59:43.960 --> 59:46.480 Ich hatte Ihnen zu Anfang auch kurz die Grammatiken vorgestellt. 59:47.520 --> 59:50.560 Und jetzt können wir als nächstes die dritte Art anschauen. 59:51.140 --> 59:54.000 Es gab noch eine dritte Art, neben der erzeugenden Art und der 59:54.000 --> 59:58.500 akzeptierenden Art, gab es auch noch die operationelle Art, um 59:58.500 --> 59:59.540 Sprachen zu beschreiben. 01:00:00.200 --> 01:00:01.480 Und das müssen wir uns auch noch anschauen. 01:00:01.620 --> 01:00:05.480 Wir kommen dann auch gleich noch zu der Grammatikklasse danach. 01:00:06.480 --> 01:00:10.640 Es hilft nichts, es ist etwas trocken. 01:00:11.640 --> 01:00:14.000 Aber was sind reguläre Ausdrücke? 01:00:14.080 --> 01:00:18.980 Reguläre Ausdrücke sind zum Beispiel die Art, wie Sie Anfragen an 01:00:18.980 --> 01:00:21.900 etwas komplexere Suchmaschinen beschreiben können. 01:00:23.440 --> 01:00:24.960 Das sind reguläre Ausdrücke. 01:00:26.320 --> 01:00:27.740 Also was ist ein regulärer Ausdruck? 01:00:28.720 --> 01:00:30.880 Das ist eine Anwendung der operationellen Methode zur 01:00:30.880 --> 01:00:31.820 Sprachdefinition. 01:00:32.820 --> 01:00:38.860 Und wir brauchen da zunächst einmal eine Menge von Basismengen, von 01:00:38.860 --> 01:00:40.320 einfachen Mengen. 01:00:40.920 --> 01:00:43.320 Betrachtende Reihe von Operationen. 01:00:45.040 --> 01:00:50.800 Also irgendwie haben wir dann irgendeinen B, irgendeine Operation und 01:00:50.800 --> 01:00:51.620 einen B-Strich. 01:00:52.980 --> 01:00:57.500 Und diese Sprache oder diese Menge, die dann daraus kommt, soll wieder 01:00:57.500 --> 01:00:59.800 eine Sprache sein. 01:01:00.680 --> 01:01:04.700 Und wir bekommen dann eine sogenannte Theorie der abstrakten 01:01:04.700 --> 01:01:09.420 Sprachfamilien, bei denen ich eine Klasse von Sprachen beschreiben 01:01:09.420 --> 01:01:12.420 kann, über die Anwendung von Operationen. 01:01:13.480 --> 01:01:21.360 Und wir nehmen jetzt sehr einfache solche Operationen uns her. 01:01:21.640 --> 01:01:24.400 Steht auf dieser Folie noch nicht drauf, kommt gleich dazu. 01:01:25.840 --> 01:01:31.840 Wir werden betrachten Sprachen, die wir bekommen, wenn wir einzelne 01:01:31.840 --> 01:01:35.200 Zeichen uns hernehmen oder Mengen, die einzelne Zeichen enthalten. 01:01:36.400 --> 01:01:37.980 Oder auch die leere Menge. 01:01:38.520 --> 01:01:41.720 Und darauf Vereinigung, Produkt und Iteration anwenden. 01:01:42.460 --> 01:01:45.040 Deswegen hatte ich Ihnen gerade diese drei Operationen dargestellt. 01:01:47.140 --> 01:01:50.860 Und das sind dann die regulären Sprachen. 01:01:50.940 --> 01:01:55.080 Die regulären Sprachen gehen von der Basismenge aus. 01:01:57.200 --> 01:02:00.320 Das ist die Sprache, die leer ist, die leere Menge. 01:02:01.120 --> 01:02:04.180 Und die Sprachen, die nur einzelne Zeichen enthalten. 01:02:05.080 --> 01:02:07.080 Und dann haben wir hier diese drei Operationen. 01:02:08.620 --> 01:02:09.740 Vereinigung ist klar. 01:02:11.220 --> 01:02:14.680 Das Produkt oder auch Komplexprodukt von zwei Sprachen hatte ich Ihnen 01:02:14.680 --> 01:02:15.560 gerade vorgestellt. 01:02:16.220 --> 01:02:18.280 So geschrieben als A-Kringel-B. 01:02:18.400 --> 01:02:19.640 Den Kringel lässt man meistens weg. 01:02:21.800 --> 01:02:27.200 Also das Hineinander-Schreiben der Wörter aus dem A und aus dem B. 01:02:27.920 --> 01:02:33.300 Und das A-Stern ist dann gerade die Menge der endlichen Produkte von 01:02:33.300 --> 01:02:33.600 A. 01:02:36.700 --> 01:02:38.340 Oder auch die Iteration. 01:02:39.580 --> 01:02:43.240 Also kann man das so hinschreiben, dass das A hoch 0, die Menge, die 01:02:43.240 --> 01:02:44.320 das leere Wort enthält. 01:02:44.320 --> 01:02:46.400 Dann ist natürlich das A selber drin. 01:02:46.540 --> 01:02:49.360 Das A mal A, das A mal A mal A und so weiter. 01:02:49.660 --> 01:02:52.940 Also alle Produkte von A mit sich selbst. 01:02:54.440 --> 01:02:58.880 Und dann habe ich neue Mengen. 01:03:00.900 --> 01:03:03.760 Und jetzt definiere ich die Menge der regulären Sprachen. 01:03:04.540 --> 01:03:08.520 Das ist die Menge aller Sprachen über dem Alphabet E, die man aus den 01:03:08.520 --> 01:03:14.080 ein -elementigen Teilmengen von E und der leeren Menge als Basismengen 01:03:14.080 --> 01:03:18.180 durch endlich häufiges Anwenden von Vereinigung, Produkt und Iteration 01:03:18.180 --> 01:03:18.560 erhält. 01:03:20.160 --> 01:03:24.080 Ich hatte gerade gezeigt mit diesen drei Konstruktionen, dass die 01:03:24.080 --> 01:03:27.960 Menge der Sprachen, die von endlichen Automaten akzeptiert werden 01:03:27.960 --> 01:03:31.560 können, abgeschlossen ist gegenüber Vereinigung, Produkt und 01:03:31.560 --> 01:03:32.200 Iteration. 01:03:33.000 --> 01:03:38.620 Und wir werden gleich einsehen, dass man durch diese drei Operationen, 01:03:38.800 --> 01:03:43.340 ausgehend von diesen Basismengen, genau die Menge der Sprachen 01:03:43.340 --> 01:03:47.080 definieren kann, die wir von endlichen Automaten akzeptieren können. 01:03:48.640 --> 01:03:51.000 Das heißt, das gibt die gleiche Sprachklasse. 01:03:52.580 --> 01:03:56.500 Und das ist ganz wichtig, weil wir damit nämlich eine Möglichkeit 01:03:56.500 --> 01:04:00.980 haben, die Sprachen auf eine ganz andere Art und Weise wiederum zu 01:04:00.980 --> 01:04:01.500 beschreiben. 01:04:01.500 --> 01:04:03.460 Nämlich durch solche Ausdrücke. 01:04:04.040 --> 01:04:06.660 Durch Ausdrücke, hier steht etwas von Sprachen, was ist jetzt ein 01:04:06.660 --> 01:04:07.400 Ausdruck? 01:04:08.140 --> 01:04:17.900 Also ein regulärer Ausdruck ist dann einfach eine Beschreibung dieser 01:04:17.900 --> 01:04:23.300 Anwendung von Operationen auf diese Basismengen. 01:04:23.300 --> 01:04:28.280 Und das heißt, in den regulären Ausdrücken, Sie erinnern sich an die 01:04:28.280 --> 01:04:33.540 logischen Systeme, die in Grundlagen der Informatik I Ihnen 01:04:33.540 --> 01:04:34.460 vorgestellt wurden. 01:04:35.040 --> 01:04:38.100 Einfache Aussagenlogik und so weiter, Prädikatenlogik. 01:04:38.700 --> 01:04:39.960 Da haben Sie eine Basismenge. 01:04:41.180 --> 01:04:44.580 Hier haben wir als Basismenge ein Zeichen für die leere Menge. 01:04:45.460 --> 01:04:48.140 Und wir haben die Zeichen des Alphabets. 01:04:49.820 --> 01:04:51.880 Und das sind schon mal alles reguläre Ausdrücke. 01:04:51.880 --> 01:04:57.620 Das Zeichen, das die leere Menge hier bezeichnet oder die einzelnen 01:04:57.620 --> 01:04:59.140 Zeichen des Alphabets. 01:04:59.920 --> 01:05:02.320 Und wenn Sie zwei reguläre Ausdrücke haben, dann ist das 01:05:02.320 --> 01:05:04.340 hintereinander schreiben einer Klammer auf. 01:05:05.040 --> 01:05:08.620 Das ist der Ausdruck, ein Plus, der zweite Ausdruck und der Klammer 01:05:08.620 --> 01:05:08.940 zu. 01:05:09.560 --> 01:05:15.000 Ein regulärer Ausdruck, genauso mit einem Punkt in der Mitte und mit 01:05:15.000 --> 01:05:16.980 einem Stern in Klammern. 01:05:18.300 --> 01:05:22.620 Das sind alles reguläre Ausdrücke. 01:05:23.660 --> 01:05:24.880 Es kommen gleich Beispiele. 01:05:25.740 --> 01:05:28.720 Gleich, gleich, da sind die Beispiele. 01:05:32.040 --> 01:05:35.280 Also, das ist noch kein Beispiel, das ist die Definition, die nächste 01:05:35.280 --> 01:05:36.340 Folie hat Beispiele. 01:05:37.120 --> 01:05:42.420 Also, jeder reguläre Ausdruck ist also ein wohlgeformter Term über der 01:05:42.420 --> 01:05:49.540 variablen Menge E sowie der Funktionssymbolmenge Plus, Mal, Stern und 01:05:49.540 --> 01:05:53.580 dieses nullstellige Zeichen für die leere Menge. 01:05:55.640 --> 01:06:00.000 Terme haben Sie kennengelernt in Aussagenlogik, Grundlageninformatik 01:06:00.000 --> 01:06:00.400 1. 01:06:00.760 --> 01:06:02.480 Da haben Sie logische Kalküle kennengelernt. 01:06:03.720 --> 01:06:06.240 Das ist genau das Gleiche, wir bilden Terme über diese drei 01:06:06.240 --> 01:06:07.020 Operationen. 01:06:08.280 --> 01:06:12.180 Wir haben also Plus und Mal als zweistellige Operationen, Stern ist 01:06:12.180 --> 01:06:13.140 eine einstellige Operation. 01:06:14.060 --> 01:06:17.560 Dieses Zeichen hier könnte man als nullstellige Operation auffassen. 01:06:19.060 --> 01:06:21.820 Und wenn ich jetzt einen solchen Ausdruck habe, möchte ich von dem 01:06:21.820 --> 01:06:23.420 Ausdruck zu Sprachen kommen. 01:06:24.140 --> 01:06:27.140 Und dazu komme ich, das sieht etwas seltsam aus hier, das ist genau 01:06:27.140 --> 01:06:28.760 das Gleiche, ist aber nicht ganz. 01:06:29.340 --> 01:06:34.340 Das Zeichen für die leere Menge wird hier interpretiert als die leere 01:06:34.340 --> 01:06:34.600 Menge. 01:06:35.800 --> 01:06:39.740 Also ich könnte auch schreiben hier die Menge, die nichts enthält, 01:06:40.000 --> 01:06:40.820 also die leere Menge. 01:06:42.140 --> 01:06:47.340 Jedes Zeichen aus E wird als Menge interpretiert, die dieses Zeichen 01:06:47.340 --> 01:06:47.800 enthält. 01:06:48.740 --> 01:06:53.080 Und wenn ich zwei reguläre Ausdrücke Alpha und Alpha Strich habe, dann 01:06:53.080 --> 01:06:58.720 wird dieser Ausdruck Alpha plus Alpha Strich interpretiert als die 01:06:58.720 --> 01:07:02.300 Vereinigung der beiden Sprachen, die ich bekomme, wenn ich den 01:07:02.300 --> 01:07:04.080 Ausdruck Alpha bzw. 01:07:04.300 --> 01:07:07.320 den Ausdruck Alpha Strich interpretiere als Sprache. 01:07:07.940 --> 01:07:12.180 Oder dieser Ausdruck mit dem Punkt in der Mitte ist dann das Produkt 01:07:12.180 --> 01:07:13.200 der beiden Sprachen. 01:07:13.640 --> 01:07:18.220 Oder wenn hier der Ausdruck mit dem Stern dahinter steht, dann ist das 01:07:18.220 --> 01:07:19.580 die Iteration der Sprache. 01:07:21.260 --> 01:07:24.580 Ich habe jetzt also Terme abgebildet auf Sprachen. 01:07:25.440 --> 01:07:28.780 Und das machen wir auf der nächsten Folie an Beispielen. 01:07:28.780 --> 01:07:35.200 Also wir werden den Punkt meist weglassen und werden Klammerregeln 01:07:35.200 --> 01:07:40.820 einführen, dass ein Klammer vor Iteration, vor Produkt und vor Summe 01:07:40.820 --> 01:07:40.940 gilt. 01:07:41.040 --> 01:07:44.680 Das ist die übliche Klammerregel, die wir ansonsten auch kennen. 01:07:45.220 --> 01:07:46.500 Das wird Sie nicht weiter wundern. 01:07:47.200 --> 01:07:48.100 Jetzt kommen Beispiele. 01:07:49.020 --> 01:07:54.500 Also, wenn wir den einfachen regulären Ausdruck, das Zeichen für die 01:07:54.500 --> 01:07:57.900 leere Menge, iteriert betrachten, was ist da drin, was ist das für 01:07:57.900 --> 01:07:58.480 eine Sprache? 01:08:00.200 --> 01:08:03.720 Diese Sprache ist genau die Sprache, die das leere Wort enthält. 01:08:04.180 --> 01:08:10.320 Weil nämlich dieses Zeichen für leere Menge Stern, das steht hier gar 01:08:10.320 --> 01:08:11.860 nicht dahinter, kommt gleich. 01:08:12.920 --> 01:08:20.980 Also, das ist ja das L von Alpha, ist ja gleich L von leere Menge und 01:08:20.980 --> 01:08:22.560 das Ganze iteriert. 01:08:23.820 --> 01:08:28.340 Und das ist gleich, könnte ich auch hinschreiben, leere Menge, 01:08:28.940 --> 01:08:29.600 iteriert. 01:08:30.620 --> 01:08:35.080 Diese Menge hoch Null ist das leere Wort, vereinigt mit der leeren 01:08:35.080 --> 01:08:38.360 Menge, vereinigt mit Produkt der leeren Menge, mit sich selbst, das 01:08:38.360 --> 01:08:39.240 sind alles leere Mengen. 01:08:39.380 --> 01:08:44.980 Das heißt, die einzige interessante Sprache, die hier rauskommt, ist 01:08:44.980 --> 01:08:49.580 diese leere Menge hoch Null, nämlich die Menge, die das leere Wort 01:08:49.580 --> 01:08:49.940 enthält. 01:08:50.800 --> 01:08:54.100 Das heißt, diese Menge ist eine reguläre Sprache. 01:08:55.720 --> 01:09:00.660 Und dann haben wir hier ein anderes Beispiel, A plus BC in Klammern. 01:09:02.400 --> 01:09:03.940 So, was ist das für eine Sprache? 01:09:05.020 --> 01:09:08.080 Das L von Alpha steht hier, ist das A, BC. 01:09:08.280 --> 01:09:09.120 Warum ist das so? 01:09:10.300 --> 01:09:14.900 Das L von Alpha ist doch nach Definition die Sprache, die wir 01:09:14.900 --> 01:09:19.140 bekommen, wenn wir das A interpretieren, vereinigt mit der Sprache, 01:09:19.320 --> 01:09:21.220 die wir aus dem Ausdruck BC bekommen. 01:09:22.660 --> 01:09:26.600 Das L von BC ist aber gerade das Produkt der beiden Sprachen, die wir 01:09:26.600 --> 01:09:28.720 durch Interpretation von B und C bekommen. 01:09:30.040 --> 01:09:36.260 Und das ist jeweils die Sprache B bzw. 01:09:36.520 --> 01:09:36.940 C. 01:09:37.140 --> 01:09:40.320 Wenn wir die beiden Sprachen B und C miteinander multiplizieren, 01:09:40.400 --> 01:09:41.580 bekommen wir das Wort BC. 01:09:41.580 --> 01:09:46.800 Und wenn wir die beiden vereinigen, haben wir das Wort A und das Wort 01:09:46.800 --> 01:09:48.260 BC in dieser Sprache drin. 01:09:49.000 --> 01:09:52.600 Das ist also sehr einfach, denke ich, und naheliegend, dass das so 01:09:52.600 --> 01:09:53.160 aussieht. 01:09:53.740 --> 01:09:58.460 Und so können Sie also jetzt, also hier A plus B mal C, so geklammert, 01:09:58.860 --> 01:10:04.460 ist klar, da haben Sie also hier vorne, dass A plus B werden die 01:10:04.460 --> 01:10:06.660 beiden Sprachen A und B vereinigt. 01:10:06.660 --> 01:10:10.740 Ich habe hier gar nicht mehr hingeschrieben, aber es ist klar, das 01:10:10.740 --> 01:10:16.380 hier ist natürlich gleich L von A plus B 01:10:20.560 --> 01:10:29.400 mal L von C und das hier ist gerade gleich die Menge, die das C 01:10:29.400 --> 01:10:29.940 enthält. 01:10:29.940 --> 01:10:37.320 Dieses hier ist L von A vereinigt L von B und das Ganze in Klammern. 01:10:37.480 --> 01:10:43.020 Und entsprechend haben Sie dann A, C und BC in dieser Sprache drin. 01:10:43.900 --> 01:10:49.040 Oder wenn Sie hier hinschreiben A-Stern B, dann müssen Sie also das A 01:10:49.040 --> 01:10:53.400 -Stern interpretieren und multiplizieren und das Produkt bilden mit 01:10:53.400 --> 01:10:54.860 der Sprache, die nun das B enthält. 01:10:54.860 --> 01:10:58.880 Das heißt, Sie haben beliebigen Folgen von A's gefolgt von dem B. 01:10:59.900 --> 01:11:03.940 Also das ist diese etwas umständliche formale Interpretation. 01:11:04.480 --> 01:11:08.880 Man sieht eigentlich diesen Ausdrücken sofort an, wie die Struktur der 01:11:08.880 --> 01:11:11.380 Wörter ist, die in dieser Sprache drin liegen. 01:11:12.380 --> 01:11:15.720 Und wir hatten das gleich zu Anfang, als ich Ihnen die formalen 01:11:15.720 --> 01:11:18.760 Modelle beschrieben habe, hatte ich Ihnen schon einen solchen Ausdruck 01:11:18.760 --> 01:11:22.080 damals hingemalt, aus dem man auch sofort sah, wie die Struktur der 01:11:22.080 --> 01:11:22.540 Wörter sind. 01:11:22.540 --> 01:11:23.760 Das heißt, was sehen wir hier? 01:11:24.660 --> 01:11:29.340 Wir sehen bei den regulären Ausdrücken auf sehr einfache Art und Weise 01:11:29.340 --> 01:11:33.400 die Struktur der Wörter, die in der Sprache sind. 01:11:34.180 --> 01:11:38.140 Das ist das Wesentliche, was wir hier drüber erkennen können. 01:11:40.140 --> 01:11:50.900 Und natürlich gilt dann, dass die Menge der regulären Sprachen, das 01:11:50.900 --> 01:11:53.840 war die Menge der Sprachen, die ich aus den Basismengen durch endlich 01:11:53.840 --> 01:11:59.320 häufiges Anwenden von Vereinigung, Produkt und Iteration bekomme, dann 01:11:59.320 --> 01:12:03.160 ist natürlich diese Menge von Sprachen gerade gleich der Menge von 01:12:03.160 --> 01:12:07.280 Sprachen, die ich als Interpretation von regulären Ausdrücken bekomme, 01:12:08.060 --> 01:12:12.180 weil die regulären Ausdrücken ja gerade Terme bildeten, die ich 01:12:12.180 --> 01:12:18.020 bekomme im Prinzip durch Anwenden von Plus, Mal und Stern, also 01:12:18.020 --> 01:12:20.020 Vereinigung, Produkt und Iteration. 01:12:20.440 --> 01:12:25.140 Das heißt, das ist offensichtlich genau so, dass wir mit regulären 01:12:25.140 --> 01:12:28.900 Ausdrücken genau die regulären Sprachen beschreiben können. 01:12:29.880 --> 01:12:33.940 Und jetzt ist eben eines schon klar, dadurch, dass wir uns vorhin 01:12:33.940 --> 01:12:38.900 überlegt haben, dass die Sprachen, die von endlichen Automaten 01:12:38.900 --> 01:12:44.220 akzeptiert werden, abgeschlossen sind unter Vereinigung, Produkt und 01:12:44.220 --> 01:12:49.860 Iteration und weil wir wissen, dass jede endliche Sprache auch die 01:12:49.860 --> 01:12:54.460 Sprache eines endlichen Automaten ist, insbesondere also die Sprachen, 01:12:54.640 --> 01:12:59.040 die jetzt nur aus den einzelnen Zeichen des Alphabets bestehen, ist es 01:12:59.040 --> 01:13:06.340 offensichtlich so, dass die Menge der regulären Sprachen eine 01:13:06.340 --> 01:13:10.520 Teilmenge ist der Sprachen, die von endlichen Automaten akzeptiert 01:13:10.520 --> 01:13:11.140 werden können. 01:13:11.800 --> 01:13:17.680 Also diese Inklusion ist offensichtlich, weil wir wissen, unsere 01:13:17.680 --> 01:13:20.860 Sprachklasse der Sprachen, die von endlichen Automaten akzeptiert 01:13:20.860 --> 01:13:25.100 werden können, ist abgeschlossen gegenüber diesen drei Operationen. 01:13:25.100 --> 01:13:28.580 Interessant ist die andere Seite, also zunächst einmal müsste man 01:13:28.580 --> 01:13:33.800 natürlich sich überlegen, wie ich zu einem regulären Ausdruck einen 01:13:33.800 --> 01:13:35.600 Automaten bauen kann. 01:13:36.460 --> 01:13:41.180 Und was dann interessanter wird, ist, wie ich aus einem Automaten 01:13:41.180 --> 01:13:44.540 einen regulären Ausdruck ableiten kann. 01:13:44.600 --> 01:13:50.000 Und das möchte ich zeigen, dass dann tatsächlich jede Sprache, die von 01:13:50.000 --> 01:13:52.880 einem endlichen Automaten akzeptiert werden kann, auch durch einen 01:13:52.880 --> 01:13:54.740 regulären Ausdruck beschrieben werden kann. 01:13:57.380 --> 01:14:00.620 Also, wie ich den Automaten konstruiere, das geht in der Regel 01:14:00.620 --> 01:14:01.780 ziemlich einfach. 01:14:03.480 --> 01:14:07.980 Wir hatten diesen, nehmen wir nur hier als einfaches Beispiel A plus B 01:14:07.980 --> 01:14:09.920 mal C. 01:14:09.920 --> 01:14:17.040 Wenn Sie diese Sprache haben, dann wissen Sie, Sie haben einen 01:14:17.040 --> 01:14:25.740 Anfangszustand und mit A oder B gehen Sie hier in einen Folgezustand 01:14:25.740 --> 01:14:32.080 über und danach muss noch ein C kommen und dann sind Sie fertig. 01:14:32.700 --> 01:14:33.480 Das ist der Automat. 01:14:33.900 --> 01:14:34.940 Ganz einfach. 01:14:35.600 --> 01:14:39.040 Wenn Sie natürlich da eine Iteration drin haben, dann kriegen Sie in 01:14:39.040 --> 01:14:40.500 dem Automaten auch eine Schleife. 01:14:43.820 --> 01:14:48.380 Aber man kann in der Regel sehr einfach aus dem regulären Ausdruck 01:14:48.380 --> 01:14:52.760 einen Automaten konstruieren, der genau diese Sprache akzeptiert. 01:14:55.840 --> 01:14:58.000 Man kann das sogar ganz allgemein machen. 01:14:58.140 --> 01:15:02.120 Ich kann also sagen, ich mache das systematisch und zeige, wie ich zu 01:15:02.120 --> 01:15:06.440 den Basisausdrücken meiner regulären Mengen Basisautomaten 01:15:06.440 --> 01:15:07.220 konstruiere. 01:15:08.260 --> 01:15:11.420 Also zu diesem Zeichen, dass die leere Menge darstellt, 01:15:12.120 --> 01:15:15.740 Bauchenautomaten, der kein einziges Wort akzeptiert. 01:15:16.380 --> 01:15:19.020 Das heißt, der Endzustand ist nie erreichbar. 01:15:20.340 --> 01:15:25.060 Jetzt sehen Sie, da ist eine kleine formale Ungenauigkeit drin. 01:15:25.060 --> 01:15:30.300 Ich hatte gesagt, die Endzustandsmenge ist immer nicht leer. 01:15:31.020 --> 01:15:33.820 Deswegen muss ich eine nicht leere Endzustandsmenge angeben. 01:15:34.180 --> 01:15:36.200 Die ist aber in diesem Fall gar nicht erreichbar. 01:15:36.320 --> 01:15:39.400 Ich gebe also hier einen Automaten an, der einen nicht erreichbaren 01:15:39.400 --> 01:15:40.240 Endzustand hat. 01:15:40.540 --> 01:15:41.800 Könnte ich im Prinzip auch weglassen. 01:15:42.640 --> 01:15:44.360 Ist nicht ganz so relevant. 01:15:45.620 --> 01:15:49.340 Was ich aber auf jeden Fall brauche ist, wenn ich einen solchen 01:15:49.340 --> 01:15:54.140 Zeichen E akzeptieren möchte, dann gebe ich einfach diesen Automaten 01:15:54.140 --> 01:15:59.780 an, der von dem Anfangszustand aus bei dem Zeichen E in einen Zustand 01:15:59.780 --> 01:16:00.720 S1 übergeht. 01:16:00.960 --> 01:16:02.200 Und das ist alles, was ich brauche. 01:16:02.520 --> 01:16:05.740 Das sind insbesondere natürlich nicht deterministische Automaten, die 01:16:05.740 --> 01:16:09.220 halt nur für die Zeichen, die relevant sind, etwas tun und für die 01:16:09.220 --> 01:16:10.540 anderen einfach nicht definiert sind. 01:16:11.520 --> 01:16:18.700 Und jetzt brauche ich nur aus diesen Automaten die weiteren zu bauen, 01:16:18.700 --> 01:16:21.500 entsprechend der Konstruktion, die ich Ihnen vorher vorgestellt habe. 01:16:21.980 --> 01:16:28.100 Wir wissen jetzt ja, wie wir aus Automaten die Vereinigungsautomaten, 01:16:28.220 --> 01:16:31.380 die Produktautomaten und die Iterationsautomaten bauen können. 01:16:31.940 --> 01:16:36.480 Und genau mit diesen Operationen bilden wir ja aus diesen Zeichen hier 01:16:36.480 --> 01:16:38.800 die komplizierteren Sprachen. 01:16:39.420 --> 01:16:43.520 Das heißt, wenn wir also zum Beispiel hier dieses A-Stern plus AB als 01:16:43.520 --> 01:16:47.280 Ausdruck haben, dann brauchen wir erstmal das A-Stern, das ist ein 01:16:47.280 --> 01:16:52.100 solcher Automat, Iteration unseres einfachen Automaten, der das 01:16:52.100 --> 01:16:55.220 Zeichen A akzeptiert, das ist ein bisschen vereinfacht hier. 01:16:56.060 --> 01:17:00.440 Das AB zu akzeptieren wäre dieser Automat, das wäre schon der 01:17:00.440 --> 01:17:02.660 Produktautomat von A und B. 01:17:03.560 --> 01:17:07.260 Und dann muss ich die beiden nur noch zusammenbauen und dann bekomme 01:17:07.260 --> 01:17:12.000 ich hier den Automaten, der sowohl in der Lage ist, das AB zu 01:17:12.000 --> 01:17:15.380 akzeptieren, als auch eine beliebige Folge von A. 01:17:17.320 --> 01:17:21.340 Also Sie können wirklich solche Automaten sehr einfach bauen. 01:17:21.780 --> 01:17:25.360 Das wäre hier die ganz systematische Vorgehensweise ausgehend von 01:17:25.360 --> 01:17:29.160 Basisautomaten, dann die Vereinigungsprodukt- und Iterationsautomaten 01:17:29.160 --> 01:17:30.360 zu bauen, dann sind Sie fertig. 01:17:31.360 --> 01:17:38.240 Okay, und jetzt ist das Interessante, wie kann ich aus einem endlichen 01:17:38.240 --> 01:17:42.640 Automaten einen regulären auskonstruieren, das ist hier etwas 01:17:42.640 --> 01:17:46.980 komplizierter und deswegen werde ich das nicht mit einem Verfahren 01:17:46.980 --> 01:17:48.100 Ihnen konkret vorstellen. 01:17:48.920 --> 01:17:57.680 Tatsächlich ist es so, wir haben das in X-Wizard drin, wir haben es 01:17:57.680 --> 01:18:02.180 aber hier in der Vorlesung nicht als Verfahren Ihnen vorgestellt. 01:18:03.540 --> 01:18:08.480 Man kann den regulären Ausdruck natürlich bestimmen, man sieht das 01:18:08.480 --> 01:18:12.260 häufig einfach, oder bei vielen Automaten sieht man sehr schnell, 01:18:12.440 --> 01:18:14.240 welcher regulärer Ausdruck dazugehört. 01:18:14.840 --> 01:18:18.940 Und wenn dieser Satz also gilt, was ich Sie bitte zu glauben, und wir 01:18:18.940 --> 01:18:23.760 werden gleich noch Beispiele betrachten, dann ist es halt so, dass wir 01:18:23.760 --> 01:18:28.440 durch die regulären Ausdrücke nichts Neues bekommen, sondern die 01:18:28.440 --> 01:18:33.020 gleichen Sprachen akzeptieren oder beschreiben, die wir durch endliche 01:18:33.020 --> 01:18:36.400 Automaten deterministisch oder nicht deterministisch akzeptieren 01:18:36.400 --> 01:18:36.760 können. 01:18:38.360 --> 01:18:42.460 Und natürlich gibt es dann auch Sprachen, die nicht regulär sind, weil 01:18:42.460 --> 01:18:47.520 wir ja wissen, es gibt Sprachen, die nicht von endlichen Automaten 01:18:47.520 --> 01:18:49.800 akzeptiert werden können, die sind dann insbesondere auch nicht 01:18:49.800 --> 01:18:50.240 regulär. 01:18:51.240 --> 01:18:54.780 Damit haben wir jetzt schon drei Sprachklassen charakterisiert, die 01:18:54.780 --> 01:18:57.900 von deterministischen endlichen Automaten akzeptiert werden, von nicht 01:18:57.900 --> 01:19:00.580 deterministischen und von regulären Ausdrücken. 01:19:01.520 --> 01:19:03.560 Und wir wissen, das ist die gleiche Sprachklasse. 01:19:04.300 --> 01:19:09.800 Und jetzt kommt hier ein Beispiel, wir haben diesen Automaten, jetzt 01:19:09.800 --> 01:19:12.680 lassen wir uns mal anschauen, wie man dazu einen regulären Ausdruck 01:19:12.680 --> 01:19:13.440 finden kann. 01:19:15.920 --> 01:19:20.460 Also, im Exquisite können Sie sich das genauer anschauen, da können 01:19:20.460 --> 01:19:23.820 Sie den Ausdruck dann betrachten. 01:19:25.300 --> 01:19:28.480 Der Zustand S3 ist der Endzustand, wie kann ich den erreichen? 01:19:30.360 --> 01:19:33.680 Da schaue ich mir an, wie sehen also die Strukturen aus, die ich hier 01:19:33.680 --> 01:19:41.740 habe, von dem Zustand S0 aus kann ich zu dem S3 kommen mit einem A. 01:19:44.620 --> 01:19:48.640 Das letzte Zeichen muss ein A gewesen sein von S0 aus. 01:19:49.860 --> 01:19:56.580 Und zu dem S0 kann ich kommen, entweder habe ich da gestartet, oder 01:19:56.580 --> 01:20:03.560 ich bin über B und dann beliebig viele weitere Bs und ein A und 01:20:03.560 --> 01:20:08.640 beliebig viele weitere As und ein weiteres B wieder zurückgekommen zu 01:20:08.640 --> 01:20:09.240 dem S0. 01:20:11.620 --> 01:20:22.100 Also, ich habe ein B, danach beliebig viele Bs, danach ein A, danach 01:20:22.100 --> 01:20:24.080 beliebig viele weitere... 01:20:26.300 --> 01:20:29.140 Ein Schwert haben wir hier eigentlich nicht drin als Zeichen. 01:20:32.040 --> 01:20:37.980 Also, das war hier ein Stern, dann ein B. 01:20:39.460 --> 01:20:44.760 Und das hier können wir durchlaufen, müssen es aber nicht. 01:20:45.620 --> 01:20:51.000 Das können wir beliebig oft durchlaufen und dann muss ein A folgen. 01:20:53.020 --> 01:20:54.800 Das wären schon mal Wörter, die da drin sind. 01:20:57.620 --> 01:21:04.880 Jetzt können wir aber von dem S3 aus natürlich auch weiterlaufen mit A 01:21:04.880 --> 01:21:05.500 oder B 01:21:08.990 --> 01:21:15.350 und können dann, das war dieses A, dann kann hier noch ein A oder B 01:21:15.350 --> 01:21:19.290 drin vorkommen und dann könnten wir wieder hier durchlaufen durch die 01:21:19.290 --> 01:21:22.210 Schleife und wir könnten auch hierhin laufen. 01:21:22.330 --> 01:21:34.210 Wir können also zu dem S0 natürlich auch kommen, indem wir ein A 01:21:34.210 --> 01:21:47.950 durchlaufen, danach ein A oder B und das hier können wir beliebig oft 01:21:47.950 --> 01:21:51.870 machen und danach noch ein A schreiben. 01:21:53.890 --> 01:21:56.910 Und das müssen wir noch kombinieren, das sind ja nur einige, nicht 01:21:56.910 --> 01:21:57.330 alle. 01:21:57.750 --> 01:22:00.990 Wir können ja entweder hier durchlaufen, durch diese Schleife da oben 01:22:00.990 --> 01:22:05.490 oder da unten durchlaufen und dann das A hintendran machen. 01:22:08.550 --> 01:22:20.370 Das heißt, wir haben also hier das B, B-Stern, A, A-Stern, B und das 01:22:20.370 --> 01:22:35.190 Ganze beliebig oft oder unser A und dann A plus B und das hier 01:22:35.190 --> 01:22:40.010 beliebig oft und danach kommt noch ein A. 01:22:41.190 --> 01:22:42.870 Und das müsste der gesamte Ausdruck sein. 01:22:44.210 --> 01:22:47.870 Und da sehen Sie, da steht es hier unten drunter, da haben wir also 01:22:47.870 --> 01:22:50.250 genau diese B, B-Stern, A, A-Stern, B. 01:22:50.250 --> 01:22:55.730 Das ist die eine Schleife, S0, S3, S0 ist das A mal A plus B. 01:22:56.310 --> 01:22:59.370 Das können wir beliebig oft machen und danach noch ein A. 01:22:59.490 --> 01:23:01.190 Und dann haben wir das Wort, das akzeptiert wird. 01:23:02.050 --> 01:23:06.030 Und da steht also genau dieser Ausdruck nochmal drin, deswegen kann 01:23:06.030 --> 01:23:10.910 ich den jetzt auch zur besseren Lesbarkeit hier wieder wegwischen, 01:23:11.410 --> 01:23:13.650 damit das auch besser zu sehen ist. 01:23:15.130 --> 01:23:18.310 Also, das ist dann dieser Ausdruck, den wir uns gerade eben überlegt 01:23:18.310 --> 01:23:18.610 haben. 01:23:19.670 --> 01:23:22.290 Und wenn Sie sich das im X-Wizard anschauen wollen, sind Sie dazu 01:23:22.290 --> 01:23:26.530 herzlich eingeladen, kann man dann auch oben und unten immer 01:23:26.530 --> 01:23:27.530 abwechselnd durchlaufen. 01:23:27.730 --> 01:23:29.490 Ganz genau, das kann man genauso machen. 01:23:29.970 --> 01:23:31.010 Und genau das steht hier ja. 01:23:31.670 --> 01:23:36.690 Sie können also entweder die obere Schleife nehmen, entweder die 01:23:36.690 --> 01:23:40.010 untere Schleife oder die obere Schleife und danach machen Sie noch ein 01:23:40.010 --> 01:23:40.170 A. 01:23:40.490 --> 01:23:42.710 Und das Ganze beliebig oft, deswegen steht da ein Stern. 01:23:44.070 --> 01:23:45.570 Jetzt muss ich zurück zum Stift. 01:23:45.570 --> 01:23:48.250 So, ja. 01:23:54.190 --> 01:23:57.770 Naja, Sie können natürlich, es ist so, ich hatte hier jeweils einen 01:23:57.770 --> 01:24:00.570 Stern dran geschrieben, der Stern war eigentlich überflüssig. 01:24:01.290 --> 01:24:05.050 Denn ich kann ja die eine Schleife durchlaufen oder die andere und das 01:24:05.050 --> 01:24:05.750 beliebig oft. 01:24:06.710 --> 01:24:08.930 Ich habe einen Stern zu viel gemacht bei dem, was ich Ihnen gerade 01:24:08.930 --> 01:24:09.890 eben vorgestellt habe. 01:24:10.890 --> 01:24:12.890 Ja, gute Frage, danke. 01:24:14.130 --> 01:24:16.710 Ja, also mein Ausdruck war ein bisschen komplizierter. 01:24:16.710 --> 01:24:22.710 Diese Iteration hier an diesem Teil und an dem Teil, die hatte ich 01:24:22.710 --> 01:24:25.910 dann nochmal reingeschrieben, die war nicht erforderlich, weil ich 01:24:25.910 --> 01:24:30.850 halt, wie Sie hier sehen, entweder die eine Schleife oder die andere 01:24:30.850 --> 01:24:33.130 Schleife und das beliebig oft mache. 01:24:34.510 --> 01:24:35.230 Oder machen kann. 01:24:35.390 --> 01:24:36.530 Und dann kommt das A noch dahinter. 01:24:36.910 --> 01:24:40.510 Dann haben Sie den Ausdruck für die Wörter, die von dem Automaten 01:24:40.510 --> 01:24:41.350 akzeptiert werden. 01:24:42.050 --> 01:24:46.610 Und in dieser Beschreibung sehen Sie sofort, wie die Wörter aussehen. 01:24:46.710 --> 01:24:47.990 Das gibt Ihnen die Struktur. 01:24:49.250 --> 01:24:51.750 Das sind also drei Arten, wie wir das beschreiben können. 01:24:52.590 --> 01:24:56.010 Durch, ja eigentlich nur zwei, durch einen ähnlichen Automaten, 01:24:56.470 --> 01:24:57.730 deterministisch oder nicht deterministisch. 01:24:58.730 --> 01:25:01.730 Und das andere ist der reguläre Ausdruck, gibt uns die Struktur. 01:25:02.450 --> 01:25:09.070 Und wir werden dann beim nächsten Mal uns noch kurz die rechtslinearen 01:25:09.070 --> 01:25:10.010 Sprachen anschauen. 01:25:10.110 --> 01:25:11.610 Das war die Beschreibung durch Grammatiken. 01:25:12.250 --> 01:25:15.170 Also das machen wir am Mittwoch früh und dann sind wir mit dem Teil 01:25:15.170 --> 01:25:18.630 schon fertig mit der nächsten Sprachklasse in den kontextfreien 01:25:18.630 --> 01:25:18.970 Sprachen. 01:25:19.070 --> 01:25:20.410 Ich danke Ihnen für die Aufmerksamkeit. 01:25:21.030 --> 01:25:22.110 Wir sehen uns am Mittwoch wieder.