WEBVTT 00:00.000 --> 00:04.560 Ich begrüße Sie zur Vorlesung Grundlagen der Informatik 2. 00:05.800 --> 00:10.280 Eine kurze Wiederholung, was Sie letzte Woche hatten. 00:11.020 --> 00:16.060 Sie haben sich natürlich mit ähnlichen Automaten beschäftigt und 00:16.060 --> 00:22.000 danach haben Sie die Minimierung von ähnlichen Automaten. 00:22.040 --> 00:24.000 Ich glaube, das war vielleicht dann vorher. 00:25.220 --> 00:26.340 Das ist hier so. 00:26.480 --> 00:30.380 Sie hatten ähnliche Automaten, dann Minimierung von ähnlichen 00:30.380 --> 00:31.160 Automaten. 00:31.940 --> 00:35.720 Dann haben Sie nicht-deterministische ähnliche Automaten gehabt. 00:35.840 --> 00:40.280 Hier zeige ich mit dem Stift hier. 00:41.040 --> 00:44.200 Und Vorurteile von nicht-deterministischen Automaten. 00:44.280 --> 00:47.320 Heute werden wir auch nochmal sehen, dass wir nicht-deterministische 00:47.320 --> 00:49.640 Kellerautomaten haben können. 00:51.080 --> 00:57.260 Dann hatten Sie reguläre Ausdrücke und auch die Verbindung von 00:57.260 --> 01:01.080 regulären Ausdrücken mit ähnlichen Automaten. 01:01.520 --> 01:07.700 Hier sehen Sie, hier unten ist ein regulärer Ausdruck und dann ein 01:07.700 --> 01:10.140 nicht -deterministischer, ähnlicher Automat. 01:10.220 --> 01:13.860 Hier sehen Sie auch unten, wie ich hier mit meinem Stift zeige. 01:15.180 --> 01:15.480 Gut. 01:17.080 --> 01:21.860 Dann haben Sie in der Vorlesung, ich glaube, es war in den letzten 01:21.860 --> 01:26.900 Minuten in der Vorlesung, sich mit Typ-3-Sprachen beschäftigt. 01:27.740 --> 01:29.640 Und ab dieser Folie werde ich weitermachen. 01:29.760 --> 01:33.820 Herr Schmeck hat schon drei Folien jetzt hier letzte Woche erklärt. 01:34.780 --> 01:38.460 Diese ersten drei Folien werde ich schneller erklären und dann komme 01:38.460 --> 01:43.140 ich zur Folie, wo die eigentliche Vorlesung von heute ist. 01:43.600 --> 01:47.540 So, Typ-3-Sprachen sind die sogenannten rechtslinearen Sprachen. 01:49.160 --> 01:50.900 Und warum rechtslinear? 01:53.820 --> 01:57.820 Weil die so eine Form haben, wie Herr Schmeck hier unten gezeigt hat. 01:57.940 --> 02:05.520 So eine Regel haben, so wie von einem Non-Terminal-Symbol haben wir so 02:05.520 --> 02:11.600 eine Produktion auf so etwas wie AB, das ist ein Terminal-Symbol und 02:11.600 --> 02:12.700 ein Non-Terminal-Symbol. 02:13.300 --> 02:17.940 Und wie sieht ein Wort dann aus, wenn wir diese Regel in dieser 02:17.940 --> 02:20.000 Grammatik oder Sprache verwenden? 02:20.320 --> 02:25.400 Das sieht immer so aus, dass wir zum Beispiel die Worte, die haben 02:25.400 --> 02:30.540 immer auf dieser rechten Seite hier, die können wir erweitern. 02:30.840 --> 02:35.220 Zum Beispiel, wenn wir dieses Beispiel haben, da können wir Worte 02:35.220 --> 02:41.440 haben, die zum Beispiel A, B, B, B und so weiter haben. 02:41.520 --> 02:44.900 Das heißt, wir können immer die rechte Seite so hier erweitern. 02:45.000 --> 02:48.540 Deswegen heißen die rechtslinearen Sprachen. 02:48.960 --> 02:50.700 Gut, das hat Herr Schmeck schon erklärt. 02:50.840 --> 02:55.940 Hier gibt es auch nochmal auf dieser Folie oben diese Ableitung eines 02:55.940 --> 02:56.460 Wortes. 02:57.720 --> 03:02.020 Okay, und dann haben Sie hier ein Beispiel gehabt, hat er hier 03:02.020 --> 03:04.820 erklärt, wie dann das gemacht wird. 03:05.560 --> 03:10.200 So, und dann gibt es eine Verbindung zwischen diesen rechtslinearen 03:10.200 --> 03:13.000 Sprachen und endlichen Automaten. 03:13.880 --> 03:18.060 Und hier hat er mit einem Beispiel gezeigt, zum Beispiel, wenn wir 03:18.060 --> 03:23.240 hier eine Grammatik haben, die über diese Wörter so besteht aus Null 03:23.240 --> 03:29.460 und Eins, und die Wörter sollen ungerade Anzahl von Einsen haben. 03:29.600 --> 03:34.660 Wenn wir dann diese Grammatik dann schreiben, dann haben wir so 03:34.660 --> 03:40.440 Grammatik, Terminalsymbolen, Non-Terminalsymbolen und die Regeln, die 03:40.440 --> 03:41.140 so aussehen. 03:42.280 --> 03:46.520 Und das Gleiche haben wir eigentlich, das war Teil von der Vorlesung, 03:46.560 --> 03:49.940 die ich persönlich gehalten habe hier, da haben wir auch endliche 03:49.940 --> 03:54.740 Automaten dazu erzeugt, so zu dieser Sprache erzeugt und endliche 03:54.740 --> 04:00.380 Automaten unten sieht so aus, wie Sie hier mit diesem Diagramm sehen. 04:02.100 --> 04:07.380 Und dann können wir beobachten, dass es genau, wenn wir in der 04:07.380 --> 04:11.720 Automaten zwei Zustände haben, in der Grammatik haben wir auch zwei 04:11.720 --> 04:12.960 Non -Terminal-Symbole. 04:14.140 --> 04:18.800 Wenn wir Anfangszustand in Automaten haben, S0 ist, dann haben wir 04:18.800 --> 04:23.800 auch in unserer Grammatik ein Start-Symbol, das ist S und das zeigen 04:23.800 --> 04:29.240 wir immer hier oben bei der Grammatik in dieser Tupel. 04:29.920 --> 04:32.840 Dann haben wir bei unserem Automaten Endzustand. 04:32.920 --> 04:34.200 Wie sieht Endzustand aus? 04:34.440 --> 04:38.880 Jeder weiß hier, dass da hier S1 ist Endzustand, haben wir hier eine 04:38.880 --> 04:40.740 Menge von Endzuständen gezeigt. 04:41.960 --> 04:47.060 Und dann haben wir Übergangsfunktionen und wir wissen, dass von S0, 04:47.260 --> 04:53.180 wenn wir Eingabealphabet 1 haben, gehen wir zu S1 und das Gleiche ist 04:53.180 --> 04:54.420 es auch in unserer Grammatik. 04:54.480 --> 04:59.780 Wenn Sie die Grammatik oben sehen, wir haben hier S und wenn ein 1 04:59.780 --> 05:02.900 kommt, dann haben wir 1A. 05:04.280 --> 05:09.620 Das heißt, das sind irgendwie Analogien zwischen Grammatiken, diese 05:09.620 --> 05:12.040 rechtlineare Grammatik und ähnliche Automaten. 05:13.120 --> 05:17.260 Und auf dieser Folie, auf der nächsten Folie, das ist die erste Folie 05:17.260 --> 05:24.500 von der Vorlesung heute, es gibt einen Algorithmus, mit diesem 05:24.500 --> 05:29.000 Algorithmus können wir eine rechtlineare Grammatik aus 05:29.000 --> 05:31.800 deterministischen, ähnlichen Automaten erzeugen. 05:33.400 --> 05:39.980 So, Idee ist es dann, die Menge der Non-Terminal-Symbole sind genau 05:39.980 --> 05:42.960 gleiche Menge wie Zustandsmenge. 05:43.240 --> 05:46.540 Das heißt, für unser Beispiel, ich bringe das Beispiel nochmal hier 05:46.540 --> 05:51.840 vorne, ich habe es hier irgendwo, genau hier. 05:52.460 --> 05:57.080 So, wir haben so einfach als Beispiel, wir wollen eine rechtlineare 05:57.080 --> 06:03.400 Grammatik aus diesen Automaten, das ist einfach ein Beispiel, aus der 06:03.400 --> 06:04.280 letzten Folie. 06:04.840 --> 06:07.820 Ich möchte es aber hier haben, dass Sie sehen, wie ich dann einfach 06:07.820 --> 06:08.960 das erzeuge. 06:09.580 --> 06:14.160 So, 1 kommt, kommen wir hier, für 1 hier und dann 0 bleiben wir hier. 06:15.640 --> 06:19.280 So, Menge der Non-Terminal-Symbole simuliert die Zustandsmenge. 06:19.440 --> 06:26.880 So, Non-Terminal-Symbole, das heißt, wir können dann schreiben, N ist 06:26.880 --> 06:32.980 gleich Zustandsmenge, S0 und S1. 06:34.680 --> 06:40.200 Dann haben wir Menge der Terminal-Symbolen entspricht dem 06:40.200 --> 06:41.120 Eingabealphabet. 06:41.480 --> 06:45.720 Okay, der Eingabealphabet wüssten wir für das Beispiel hier oben, dass 06:45.720 --> 06:47.240 es 0 und 1 ist. 06:47.440 --> 06:50.820 Das heißt, dann T ist es für uns 0 und 1. 06:52.920 --> 06:54.960 Gut, und dann, was kommt noch? 06:55.380 --> 07:00.060 Für jede mögliche Anwendung der Überführungsfunktion wird eine Regel 07:00.060 --> 07:04.020 erzeugt, die mit dem damit verbundenen Zustandswechsel entspricht. 07:04.340 --> 07:05.320 Was bedeutet das? 07:05.400 --> 07:11.900 Das heißt, jedes Mal, wenn ich in S0 bin, da in den Automaten, und 0 07:11.900 --> 07:13.780 kommt, bleibe ich in S0. 07:14.380 --> 07:19.060 Dann kann ich gleich diese Übergangsfunktion nehmen und dann eine 07:19.060 --> 07:19.980 Regel daraus machen. 07:20.100 --> 07:25.300 Das heißt, ich sage, okay, S0, dann habe ich, wenn 0 kommt, bleibe ich 07:25.300 --> 07:25.940 in S0. 07:28.480 --> 07:31.140 Das werden Sie genauer in diesem Algorithmus unten sehen. 07:31.620 --> 07:37.100 Okay, und dann für N-Zustand erzeugen wir auch eine Regel, so diese 07:37.100 --> 07:40.000 Produktion, N-Zustand S1. 07:40.240 --> 07:44.720 Für jeden N-Zustand gehen wir auf Lambda. 07:46.200 --> 07:48.240 Und dann haben wir eine Grammatik erzeugt. 07:48.280 --> 07:50.680 Das ist nicht vollständig hier, ich werde es dann gleich nochmal 07:50.680 --> 07:51.960 vervollständigen. 07:52.260 --> 07:54.120 So, Algorithmus. 07:54.520 --> 07:58.240 Sie kennen alle Algorithmus aus Grundlageninformatik 1, denke ich, wie 07:58.240 --> 07:59.680 man Algorithmen schreibt und so. 07:59.780 --> 08:00.860 Da haben wir einen Input. 08:01.300 --> 08:05.600 Input ist ein ähnlicher Automaten, wie in dem Beispiel hier, den ich 08:05.600 --> 08:07.300 an der rechten Seite oben zeige. 08:07.800 --> 08:10.600 Dann wollen wir eine Grammatik haben. 08:11.080 --> 08:14.620 Das heißt, wir müssen dann diese Grammatik genau definieren. 08:15.340 --> 08:20.700 So, wie ich oben gemacht habe, im Beispiel, Menge des Terminalsymbolen 08:20.700 --> 08:24.480 sind Eingabealphabet, das haben wir hier oben gemacht. 08:25.140 --> 08:28.160 Hier ist eine nicht so schöne Annotation, aber sehen Sie hier. 08:28.680 --> 08:31.440 Dann haben wir im Non-Terminal-Symbolen gleiche Menge wie 08:31.440 --> 08:32.320 Zustandsmenge. 08:32.920 --> 08:33.780 Dann haben wir hier. 08:35.040 --> 08:37.940 Gut, und dann müssen wir diese Delta, also diese 08:37.940 --> 08:40.300 Überführungsfunktionen zu Regeln wechseln. 08:40.440 --> 08:44.240 Und das ist, was ich hier gemacht habe, machen wir dann hier weiter. 08:44.680 --> 08:49.260 Für jede Überführungsfunktion von irgendeinem Zustand S und einem 08:49.260 --> 08:52.440 Eingabealphabet wechseln wir zu irgendeinem anderen Zustand. 08:52.540 --> 08:54.440 Das sehen wir in dem Diagramm oben. 08:55.280 --> 08:57.520 Dann erzeugen wir Regeln, die so aussehen. 08:57.880 --> 09:04.440 S auf E und S-Strich haben wir so, jetzt kann ich dann vollständig 09:04.440 --> 09:05.440 schreiben, S0. 09:06.560 --> 09:08.980 Dann, wenn 0 kommt, bleibe ich in S0. 09:09.740 --> 09:13.760 In S0, wenn 1 kommt, gehe ich auf S1. 09:16.060 --> 09:20.340 Dann S1, wenn 0 kommt, bleibe ich auf S1. 09:21.060 --> 09:26.740 Und S1, wenn 1 kommt, gehe ich auf S0. 09:27.920 --> 09:31.020 Gut, das heißt, diese Schleife hier haben wir auch erzeugt. 09:31.360 --> 09:34.800 Und dann bleibt Endzustand, wir haben nur einen Endzustand, das ist in 09:34.800 --> 09:37.000 dem Beispiel hier ein S1. 09:37.280 --> 09:42.120 Und dann erzeugen wir eine Regel, das sagt uns S1 auf Lambda. 09:44.120 --> 09:50.540 Und so haben wir diese Grammatik, so rechtlineare Grammatik, ich 09:50.540 --> 09:54.580 lösche hier die Sachen, die ich hier oben gemalt habe, so hier in 09:54.580 --> 09:59.200 diesem Beispiel erzeugt und das war es. 10:00.800 --> 10:03.500 Haben Sie verstanden mit dem Beispiel? 10:03.500 --> 10:07.260 Okay, gut, ich werde es auch sehr häufig fragen, ob Sie verstanden 10:07.260 --> 10:09.720 haben, ob ich wiederholen soll, weil ich diese Nukid jetzt nicht 10:09.720 --> 10:13.680 verwende und ich möchte ein bisschen Feedback von Ihrer Seite 10:13.680 --> 10:14.100 bekommen. 10:14.380 --> 10:20.340 Okay, gut, wenn Sie das verstanden haben, wir können auch umgekehrt 10:20.340 --> 10:24.140 das machen, aber nicht mit ähnlichen, so deterministisch ähnlichen 10:24.140 --> 10:27.360 Automaten, aber nicht deterministisch ähnlichen Automaten. 10:27.500 --> 10:30.840 Das heißt, das Gleiche, was wir jetzt gemacht haben, wir wollen 10:30.840 --> 10:34.360 umgekehrt das machen und einen nicht deterministischen, ähnlichen 10:34.360 --> 10:38.060 Automaten aus einer rechtlinearen Grammatik erzeugen. 10:39.240 --> 10:42.120 Sie wissen jetzt mit dem Beispiel, wie eine rechtlineare Grammatik, so 10:42.120 --> 10:43.680 ein Beispiel, davon wissen Sie jetzt. 10:44.760 --> 10:50.160 So, wir wissen, dass rechtlineare Grammatik, wir haben diese Regeln 10:50.160 --> 10:51.780 für eine rechtlineare Grammatik. 10:51.880 --> 10:56.640 Erstmal sieht es so aus, dass wir hier ein Non-Terminal-Symbol haben, 10:56.740 --> 11:00.500 dann hier haben wir ein Terminal-Symbol und hier kann ein Non-Terminal 11:00.500 --> 11:01.100 -Symbol kommen. 11:01.160 --> 11:02.820 Die sehen so aus. 11:03.760 --> 11:10.900 Und wie sieht es aus, wenn wir diese Regeln nehmen und jetzt 11:10.900 --> 11:16.520 entsprechend Überführungsfunktionen für Automaten bauen wollen, 11:16.840 --> 11:17.680 konstruieren wollen? 11:18.020 --> 11:21.300 Das ist nichts anderes, als dass wir sagen, okay, wir haben ein Wort. 11:22.840 --> 11:27.480 So, mit ähnlichen Automaten lesen wir Wörter und das Wort, was wir 11:27.480 --> 11:31.640 hier haben, hat halt hier so eine Form. 11:31.900 --> 11:37.540 Wir lesen erstmal A und dann ändern wir unseren Zustand und lesen wir 11:37.540 --> 11:40.180 dann Restwort B, was auch immer da bleibt. 11:41.400 --> 11:43.980 Und dadurch wechseln wir unseren Zustand. 11:44.120 --> 11:49.500 Wenn wir in A sind, lesen wir die Eingabe Alphabet A und wechseln 11:49.500 --> 11:51.560 unseren Zustand auf B. 11:52.880 --> 11:55.860 Und dann erzeugen wir so eine Überführungsfunktion. 11:56.760 --> 12:01.080 Das heißt, diese Regel, was Sie hier gesehen haben, wird dann zu 12:01.080 --> 12:05.760 dieser Überführungsfunktion gewechselt, so konstruiert. 12:06.280 --> 12:10.520 Dann haben wir Zustand, so einen Zustand wollen wir auch noch haben 12:10.520 --> 12:11.680 bei unseren Automaten. 12:12.160 --> 12:15.240 Wir wissen, dass diese Regel, Sie wissen auch von der letzten Folie, 12:15.300 --> 12:18.520 wenn wir so eine Regel haben, das ist ähnlich wie ein Endzustand, so 12:18.520 --> 12:20.300 dann haben wir hier einen Endzustand. 12:20.980 --> 12:24.060 Und dann kommt etwas noch, das wir bis jetzt nicht hatten. 12:24.980 --> 12:30.120 Bei rechtlinearen Grammatiken kann es sein, dass wir solche Regeln 12:30.120 --> 12:34.900 haben, so ein Non-Terminal-Symbol a und geht auf ein Terminal-Symbol 12:34.900 --> 12:36.600 a, so klein a. 12:38.680 --> 12:44.480 Und hier das genau so konstruieren in ähnlichen Automaten oder nicht 12:44.480 --> 12:47.820 -deterministischen ähnlichen Automaten, das können wir mit einem 12:47.820 --> 12:53.380 speziellen Endzustand, Sigma 0, konstruieren. 12:53.740 --> 12:59.960 Und dann haben wir so einen speziellen Endzustand, das genau so Sigma 12:59.960 --> 13:00.500 0 ist. 13:00.700 --> 13:04.860 Das heißt, für alle Regeln, die wir haben, die so aussehen, a nach b 13:04.860 --> 13:10.220 oder a nach a, dann haben wir irgendeinen speziellen Endzustand. 13:11.220 --> 13:14.340 Gut, jetzt kommen wir zum Algorithmus und dann auf der nächsten Seite 13:14.340 --> 13:17.020 haben wir ein Beispiel, dann das Beispiel werde ich in der nächsten 13:17.020 --> 13:20.100 Folie zeigen, werde ich hier nicht so malen. 13:21.580 --> 13:23.340 Gut, was ist Input? 13:23.560 --> 13:29.180 Input ist rechtlineare Grammatik und wir wollen einen nicht 13:29.180 --> 13:32.220 -deterministischen Automaten daraus erzeugen. 13:34.180 --> 13:38.720 Und das ist ein Tuple, wir müssen Eingabealphabet definieren, Menge, 13:38.800 --> 13:42.320 Zustände, Überführungsfunktion, das ist da, was sehr schwierig ist, 13:42.660 --> 13:44.960 diese Delta, dann S0 und F. 13:47.320 --> 13:51.640 So, e, jeder weiß hier, okay, das ist gleich wie vorhin, wie wir 13:51.640 --> 13:57.380 hatten, e ist gleich wie Menge von Terminal-Symbolen, der 13:57.380 --> 14:04.720 Anfangszustand, S0 ist das Start-Symbol in unserer Grammatik und Menge 14:04.720 --> 14:09.060 des Zustandes, es ist jetzt nicht gleich mit Non-Terminal-Symbolen, 14:09.080 --> 14:10.600 was wir auf der letzten Folie hatten. 14:11.120 --> 14:18.180 Auf der letzten Folie hatten wir, dass n und s gleich waren hier, das 14:18.180 --> 14:25.640 ist nicht so jetzt hier, sondern wir haben hier diese Menge auch, die 14:25.640 --> 14:28.000 von dieser Regel konstruiert werden. 14:28.400 --> 14:32.540 Diese Regel ist a nach klein a, also ein Non-Terminal-Symbol auf 14:32.540 --> 14:33.260 Terminal -Symbol. 14:34.120 --> 14:41.860 Gut, dann haben wir s auch definiert, m-Zustand ist natürlich auch 14:41.860 --> 14:52.440 gleich wie so Menge a, die nach Lambda gehen, so diese Regel, und auch 14:52.440 --> 14:53.320 diese Sigma 0. 14:55.020 --> 14:58.740 So, wie machen wir dann die Überführungsfunktionen? 14:58.760 --> 15:02.300 So ähnlich, wie oben wir gemacht haben. 15:02.740 --> 15:13.040 Für alle Regeln, die so aussehen, a auf ab, erzeugen wir eine 15:13.040 --> 15:19.180 Überführungsfunktion, Delta a und a gleich b. 15:21.260 --> 15:27.300 Das heißt, von Zustand a, Eingabealphabet klein a, landen wir auf 15:27.300 --> 15:34.380 Zustand b und dann müssen wir für alle Regeln, die so aussehen, auch 15:34.380 --> 15:36.580 ein Sigma 0 erzeugen. 15:38.080 --> 15:42.960 So sagen wir, für alle, die so aussehen, die Regeln, dann 15:42.960 --> 15:49.080 Überführungsfunktion a und a ist gleich Sigma 0 und das machen wir für 15:49.080 --> 15:50.500 alle Regeln, die wir haben. 15:57.140 --> 16:01.280 Danach müssen wir auch noch was anderes erzeugen und das ist dann hier 16:01.840 --> 16:05.840 der Wert für diese Sigma 0 hier definieren. 16:07.180 --> 16:09.740 Wo landen wir mit diesem Sigma 0? 16:09.840 --> 16:12.020 Wenn wir in Sigma 0 sind, was passiert danach? 16:12.520 --> 16:16.440 Und das ist hier, wir bleiben einfach so in der Sackkasse. 16:17.860 --> 16:18.900 Es wird nicht weitergehen. 16:19.420 --> 16:22.220 So, Beispiel jetzt, dass Sie genauer sehen, das kann ich hier im 16:22.220 --> 16:23.880 Beispiel besser erklären. 16:24.680 --> 16:28.080 Genau gleiche Grammatik, wie wir hatten, jetzt machen wir umgekehrt. 16:28.160 --> 16:31.420 Das heißt, hier ist Grammatik und wir wollen einen nicht 16:31.420 --> 16:34.020 -deterministischen, ähnlichen Automaten davon erzeugen. 16:34.820 --> 16:35.120 Gut. 16:37.980 --> 16:42.320 Sofort, wenn Sie so eine Aufgabe bekommen, sollen Sie erstmal, okay, 16:42.500 --> 16:46.000 Eingabealphabet definieren, Menge, Zustände. 16:46.460 --> 16:51.460 Jetzt wissen Sie, ah, okay, Zustände sind, die Menge ist gleich wie 16:51.460 --> 16:58.120 Non -Terminal-Symbole und plus dieses Sigma 0, das wir haben. 16:59.500 --> 17:03.440 Und dann Endzustände sind, es ist dann Endzustand. 17:03.500 --> 17:04.560 Wo ist Endzustand? 17:04.840 --> 17:10.320 So, Endzustand, dann ist es das, was hier gezeigt wird, A. 17:10.840 --> 17:12.840 So, hier schreiben wir S A, ist egal. 17:12.980 --> 17:14.000 Sie können auch A schreiben. 17:14.360 --> 17:17.100 Sie können zum Beispiel hier S so schreiben. 17:17.260 --> 17:21.620 So, wenn ich die Aufgabe zu lösen hätte, dann würde ich dann nicht S 0 17:21.620 --> 17:25.660 und S A schreiben, sondern ich würde dann auch tatsächlich so 17:25.660 --> 17:28.120 schreiben, A und S. 17:28.880 --> 17:32.360 Dann weiß ich, okay, was da passiert. 17:33.640 --> 17:39.840 Und dann Endzustände, es ist dann das hier, kommt von diesen Regeln 17:39.840 --> 17:44.620 und Sigma 0, das ist dieser spezielle Endzustand, den wir haben. 17:45.700 --> 17:49.380 Gut, hier rechte Seite sehen Sie den gleichen Algorithmus, den wir bis 17:49.380 --> 17:49.920 jetzt hatten. 17:50.160 --> 17:51.620 Das werde ich nicht jetzt wiederholen. 17:52.000 --> 17:55.900 Aber was passiert, wenn wir, so, wir müssen dann Regeln nach dem 17:55.900 --> 18:02.440 anderen nehmen aus unserer Regelmenge und dann diese Tafel erzeugen. 18:02.960 --> 18:03.720 Gut, machen wir. 18:04.720 --> 18:10.120 Wir haben Zustände hier, S 0, S A und Sigma 0 und dann haben wir ein 18:10.120 --> 18:11.000 Gabalphabet 0. 18:11.180 --> 18:15.880 So, jetzt sehen wir, was passiert, wenn wir in S 0 sind und 0 kommt. 18:16.440 --> 18:24.780 S 0 war für uns wie diese A und, nee, nee, sorry, nicht A, jetzt muss 18:24.780 --> 18:30.840 ich nochmal, genau, so Startsymbol, so hier S war unser 18:30.840 --> 18:31.860 Anfangszustand. 18:32.180 --> 18:37.020 Deswegen S 0 ist es dann gleich wie S oben. 18:37.540 --> 18:47.820 So, wenn S und 0 kommt, S, das ist diese Regel, wenn 0 kommt, bleibe 18:47.820 --> 18:51.460 ich in S und S haben wir gesagt, dass es gleich S 0 ist, das heißt, 18:51.560 --> 18:52.560 hier schreiben wir S 0. 18:53.440 --> 18:59.700 Was passiert, wenn ich in S bin und eine 1 kommt, S hier, eine 1 18:59.700 --> 19:01.380 kommt, dann bin ich bei A. 19:02.280 --> 19:06.760 Das heißt, ich bin, wenn eine 1 kommt in der S A. 19:08.660 --> 19:13.540 Gut, dann machen wir das Gleiche für den zweiten Zustand, S A, was wir 19:13.540 --> 19:14.400 definiert haben. 19:15.720 --> 19:23.480 S A war hier oben bei Regelmenge A haben wir genommen, weil wenn A 0 19:23.480 --> 19:27.140 kommt, was für eine Regel ist es, das ist hier diese Regel, hier oben, 19:27.380 --> 19:30.700 ich male es, dass Sie es besser sehen, das ist 0 A. 19:31.380 --> 19:36.120 Das heißt, hier in Zustandstafel, wenn wir S A sind und 19:36.120 --> 19:43.700 Eingabealphabet 0 kommt, bleiben wir in S A und dann nochmal A und 1 19:43.700 --> 19:48.660 kommt, das ist diese Regel hier, 1 S, das heißt, enden wir und gehen 19:48.660 --> 19:49.600 wir auf S 0. 19:51.380 --> 19:56.560 Endzustand ist gleich S A, haben wir auch hier unten geschrieben und 19:56.560 --> 20:01.920 bei diesem Beispiel haben wir keine Regel, die so aussieht wie S nach 20:01.920 --> 20:05.020 1 oder A nach 0. 20:05.700 --> 20:09.540 Wenn wir das hätten, dann hätten wir auch diese Sigma 0 auch hier 20:09.540 --> 20:13.360 gefühlt und wenn wir es nicht haben, dann bleibt es einfach so und das 20:13.360 --> 20:14.480 bleibt einfach leer. 20:20.350 --> 20:25.070 Das ist das Problem, wenn man mit Folien arbeitet, die man nicht 20:25.070 --> 20:25.950 selber gemacht hat. 20:26.090 --> 20:29.490 Das Gleiche, was ich hier oben mit A und S versucht haben zu zeigen, 20:29.610 --> 20:33.430 hat Herr Schmeck mit Animation hier gezeigt. 20:33.710 --> 20:35.050 Das ist das Gleiche wie oben. 20:35.930 --> 20:39.130 Ich habe versucht, hier mit S 0 und S A dann alles zu erklären mit dem 20:39.130 --> 20:43.490 Beispiel, aber das hat er nochmal in der Tabelle hier unten gezeigt. 20:43.970 --> 20:51.590 So, hier haben Sie S und A, das sind equivalent zu S 0 und S A und so 20:51.590 --> 20:52.970 weiter, was wir bis jetzt hatten. 20:53.630 --> 21:00.070 Gut, in diesem Fall, Sigma 0 ist leer, es gibt keine Regel, die so 21:00.070 --> 21:03.290 aussieht, wie ich vorhin gesagt habe, das A nach irgendwie 0. 21:03.770 --> 21:07.650 Wenn wir das hätten, dann müssten wir hier auch nochmal so genau 21:07.650 --> 21:10.290 sehen, wie diese Sigma 0 definiert wird. 21:10.510 --> 21:12.850 Das ist dann vielleicht für Sie eine interessante Übung. 21:13.210 --> 21:16.610 Vielleicht haben Sie auch eine Übung dazu im Übungsbuch, wie Sie dann 21:16.610 --> 21:17.250 das machen. 21:18.030 --> 21:22.270 So, auf jeden Fall, Sie können eine recht lineare Grammatik nehmen und 21:22.270 --> 21:26.610 einen nicht deterministisch ähnlichen Automaten davon konstruieren 21:26.610 --> 21:28.390 oder umgekehrt. 21:28.770 --> 21:32.010 Es sind viele Beispiele, nehmen Sie einfach Beispiele aus der 21:32.010 --> 21:38.030 Vorlesung oder Übungen und machen Sie das, üben Sie das und dann 21:38.030 --> 21:44.510 schauen Sie, was für so interessante Aufgaben daraus gemacht werden 21:44.510 --> 21:44.730 kann. 21:45.190 --> 21:50.370 So, eine Bemerkung gibt es hier, dass wir hier gerade einen nicht 21:50.370 --> 21:55.130 deterministisch ähnlichen Automaten erzeugt haben, aber Sie wissen 21:55.130 --> 21:57.750 auch von der Vorlesung, ich glaube, letzte Woche haben Sie 21:57.750 --> 22:02.430 wahrscheinlich in der Vorlesung gehabt, dass von einem nicht 22:02.430 --> 22:05.170 deterministisch ähnlichen Automaten können Sie einen deterministisch 22:05.170 --> 22:08.070 ähnlichen Automaten erzeugen, konstruieren. 22:08.330 --> 22:14.010 Das Gleiche können Sie dann hier so machen, Sie erzeugen einen nicht 22:14.010 --> 22:17.610 deterministisch ähnlichen Automaten und daraus machen Sie einen 22:17.610 --> 22:18.970 deterministischen Automaten. 22:20.690 --> 22:26.110 Und es gibt einen Satz und das ist auch klar, zu jedem deterministisch 22:26.110 --> 22:30.390 ähnlichen Automaten gibt es eine rechtlineare Grammatik und das haben 22:30.390 --> 22:35.170 wir gerade gesehen in diesem Algorithmus und auch umgekehrt haben wir 22:35.170 --> 22:39.590 auch gesehen und Beweis, das müssen wir nicht jetzt hier beweisen 22:39.590 --> 22:43.490 durch diesen Algorithmus, wenn Sie verifizieren, können Sie dann 22:43.490 --> 22:46.770 sehen, dass es dann tatsächlich so einen Satz gibt. 22:48.350 --> 22:54.210 Und für jedes Alphabet, die wir haben, da können Sie so etwas 22:54.210 --> 22:59.490 schreiben und ich weiß es, wenn Sie Interesse haben zu sehen, manchmal 22:59.490 --> 23:03.430 bei Multiple-Choice-Fragen, ich weiß nicht, ob wir eine Klausur haben, 23:03.570 --> 23:08.550 aber damals, als wir Multiple-Choice-Fragen hatten, wir haben immer so 23:08.550 --> 23:09.270 etwas gefragt. 23:10.070 --> 23:11.210 So, wie ist es? 23:11.650 --> 23:13.830 So, also eine Ein-Punkt-Frage. 23:14.590 --> 23:17.450 So, was sagt hier diese Folgerung sagt? 23:18.030 --> 23:24.490 Das heißt, Sprache von ähnlichen Automaten, diese Typ-3-Sprachen sind 23:24.490 --> 23:29.030 gleich wie Sprachen von nicht deterministischen ähnlichen Automaten, 23:30.030 --> 23:32.150 reguläre Ausdrücke und so weiter. 23:32.230 --> 23:35.870 Das heißt, die sind alle hier äquivalent, gleiche Sprachen, 23:36.830 --> 23:40.770 rechtslinear oder Typ-3-ähnliche Automaten, nicht-ähnliche Automaten 23:40.770 --> 23:41.310 und so weiter. 23:42.410 --> 23:46.430 Und Sie können, das ist auch interessant, für jede Anwendung, die Sie 23:46.430 --> 23:50.410 haben, Sie können dann das nehmen, was es dann genau passt für die 23:50.410 --> 23:50.850 Anwendung. 23:50.910 --> 23:53.770 Sie müssen nicht sagen, Sie müssen immer rechtslineare Grammatik 23:53.770 --> 23:58.810 nehmen, um ein Wort zu verifizieren oder so akzeptieren, sondern Sie 23:58.810 --> 24:01.890 können sagen, okay, wenn ich ein Wort akzeptieren möchte, dann nehme 24:01.890 --> 24:07.110 ich dann halt einen ähnlichen Automaten und für jede Anwendung und so 24:07.110 --> 24:11.470 können Sie dann selber frei wählen, welche von diesen Varianten Sie 24:11.470 --> 24:13.310 nehmen wollen, weil die alle gleich sind. 24:15.570 --> 24:19.950 Gut, und dieser Kapitel wollen wir mit dieser Zusammenfassung beenden. 24:20.810 --> 24:25.470 Sie hatten hier ähnliche Automaten, deterministisch und nicht 24:25.470 --> 24:29.370 -deterministisch und erste Aussage hier sagt, dass die beide gleich 24:29.370 --> 24:35.790 mächtig sind und Sie können beide sehr gut verwenden. 24:35.950 --> 24:41.230 Nicht-deterministische Automaten, die sind kleiner und haben eine 24:41.230 --> 24:45.910 kürzere Darstellung und haben dann wesentliche Eigenschaften der 24:45.910 --> 24:46.430 Automaten. 24:46.590 --> 24:51.610 Ähnliche deterministische, die haben dann halt genaue Spezifikationen 24:51.610 --> 24:53.790 und können auch ein bisschen größer sein. 24:54.230 --> 24:57.910 Dann haben Sie Pumping Glamour und die Pumping Glamour habe ich hier 24:57.910 --> 24:58.350 bewiesen. 24:58.910 --> 25:04.270 Das ist auch ein Thema, das Sie bis Ende dieser Vorlesung immer wieder 25:04.270 --> 25:05.830 brauchen, auch bei den Übungen. 25:06.530 --> 25:08.070 Was macht Pumping Glamour? 25:08.310 --> 25:12.770 Mit Pumping Glamour können wir zeigen, ob ein Wort von ähnlichen 25:12.770 --> 25:17.010 Automaten akzeptiert wird oder nicht, oder dass eine Sprache nicht von 25:17.010 --> 25:19.770 ähnlichen Automaten akzeptiert werden kann oder nicht. 25:19.990 --> 25:24.810 Und das ist dann sehr wichtig und ein Beispiel, ein Beispiel, das 25:24.810 --> 25:30.950 jeder sofort wissen muss, ist es die Worte, die so sind. 25:31.050 --> 25:32.550 A hoch N, B hoch N. 25:33.810 --> 25:37.210 Und das haben wir in der Vorlesung gezeigt mit Pumping Glamour, dass 25:37.210 --> 25:41.230 solche Worte können von ähnlichen Automaten nicht akzeptiert werden. 25:42.290 --> 25:43.450 Jetzt habe ich eine Frage. 25:45.730 --> 25:51.930 Warum kann ein ähnlicher Automat so ein Wort nicht akzeptieren? 25:52.330 --> 25:53.170 Irgendeine Antwort. 26:02.390 --> 26:07.830 Die Antwort ist, weil ähnliche Automaten keinen Speicher haben. 26:07.890 --> 26:12.010 Die können nicht zählen, weil bei A hoch N, B hoch N, Sie müssen 26:12.010 --> 26:20.390 erstmal N mal A schreiben und dann auch genauso viel N mal B und das 26:20.390 --> 26:22.090 können wir mit ähnlichen Automaten nicht. 26:22.170 --> 26:23.930 Ähnliche Automaten können nicht zählen. 26:24.550 --> 26:28.150 Deswegen, ähnliche Automaten können Sie auch nicht für 26:28.150 --> 26:30.030 Programmiersprachen verwenden. 26:30.130 --> 26:32.670 Zum Beispiel, wenn Sie Klammerausdrücke schreiben wollen. 26:33.150 --> 26:35.690 Klammer offen, Klammer offen zu und so weiter. 26:36.990 --> 26:40.110 Und mit Pumping Glamour können Sie das zeigen. 26:41.330 --> 26:45.250 Und es kann sein, wie gesagt, in der Klausur oder so irgendeine 26:45.250 --> 26:52.730 Sprache kommt und dann wird gefragt, ob das Sprache ein ähnlicher 26:52.730 --> 26:54.190 Automaten ist oder nicht. 26:54.510 --> 26:56.730 Und da können Sie mit Pumping Glamour das zeigen. 26:58.630 --> 27:02.470 Gut, dann haben Sie die rechtlineare Grammatik gehabt und heute haben 27:02.470 --> 27:08.470 wir auch ein bisschen noch darüber gesprochen und reguläre Ausdrücke, 27:08.930 --> 27:14.010 die gleiche Sprachen wie ähnliche Automaten sind. 27:15.070 --> 27:20.290 Und dann, was Sie auch noch haben, ich glaube, Herr Schmeck hier hat 27:20.290 --> 27:23.190 alle Punkte, die in die Klausur kommen, hier nochmal wesentliche 27:23.190 --> 27:23.930 Kenntnisse geschrieben. 27:24.490 --> 27:26.910 So und dann Minimierung von ähnlichen Automaten. 27:28.690 --> 27:32.430 Herr König zum Beispiel in seiner Forschung, er hat die Sparmrobotik 27:32.430 --> 27:37.770 und jeder Roboter hat einen ähnlichen Automaten und gemeinsam ähnliche 27:37.770 --> 27:42.390 Automaten erzeugen und es kann sein, dass die Roboter riesige ähnliche 27:42.390 --> 27:43.770 Automaten erzeugen. 27:44.430 --> 27:47.690 Und da müssen wir schauen, wie wir diese riesige ähnliche Automaten 27:47.690 --> 27:48.430 kleiner machen. 27:48.570 --> 27:52.150 Ob es einen minimal ähnlichen Automaten gibt und wie kann man das 27:52.150 --> 27:53.410 kleiner machen, minimieren. 27:53.730 --> 27:55.990 Und Sie haben dafür auch die Vorlesung. 27:56.030 --> 27:58.610 Ich weiß nicht, ob es letzte Vorlesung war oder Vorvorletzte 27:58.610 --> 27:59.090 Vorlesung. 27:59.390 --> 28:00.450 Das war hier. 28:01.770 --> 28:06.210 Gut, dann haben wir dann diese Kapitel zu Ende. 28:06.310 --> 28:10.850 Haben Sie Fragen über ähnliche Automaten, deterministisch, nicht 28:10.850 --> 28:13.790 -deterministisch und rechtslinearen Grammatiken? 28:15.350 --> 28:18.750 Okay, wenn nicht der Fall ist, dann werde ich die Vorlesung 28:18.750 --> 28:25.530 weitermachen mit neue Kapitel. 28:28.630 --> 28:30.990 Die Folien sind schon eigentlich online. 28:33.390 --> 28:38.950 Und hier reden wir über etwas, das heißt Kellerautomaten. 28:41.370 --> 28:44.890 Und Herr Schmeck hat hier einen kleinen Scherz auf dieser Folie. 28:45.170 --> 28:46.510 Was ist ein Kellerautomat? 28:48.190 --> 28:51.650 Hier hatte er zwei Werbungen aus Zeichnungen. 28:52.510 --> 28:55.070 Kellerautomat ist nicht ein Automat, der im Keller ist. 28:57.330 --> 29:03.010 Oder hier, gut erhaltener Kellerautomat, Farbe hellblau und so weiter. 29:03.630 --> 29:08.290 Das ist nicht, was Sie denken, dass wir irgendeinen Automaten haben, 29:08.370 --> 29:11.530 so wie Warenautomaten im Keller sind. 29:12.050 --> 29:13.550 Aber das hat mit Keller zu tun. 29:13.890 --> 29:18.370 Und ich kann auch sagen, als nicht-Native-Speaker, wir nennen das 29:18.370 --> 29:23.270 Kellerautomat oder Basementautomat in Englisch, sondern die heißen Pop 29:23.270 --> 29:25.030 -and -Push-Automater. 29:25.930 --> 29:31.090 Okay, aber es ist jetzt hier Vorlesung auf Deutsch und da reden wir 29:31.090 --> 29:32.050 über Kellerautomaten. 29:33.910 --> 29:35.550 So, wie sieht ein Kellerautomat aus? 29:35.770 --> 29:41.470 Und Kellerautomat ist auch diese, was ich am Anfang gesagt habe, 29:42.950 --> 29:46.230 Automaten, das kommt in die Klausur, das ist das Thema. 29:46.390 --> 29:51.330 Deswegen machen Sie alle Beispiele mit mir jetzt mit und dann haben 29:51.330 --> 29:54.950 Sie das für die Klausur oder Bonusklausur oder was. 29:55.130 --> 29:57.730 Okay, wie ist, was ist ein Kellerautomat? 29:59.210 --> 30:04.890 Kellerautomat ist im Prinzip das Gleiche wie bei ähnlichen Automaten. 30:05.090 --> 30:08.710 So, wir haben hier ein Eingabeband, wie bei ähnlichen Automaten. 30:09.210 --> 30:13.590 Da lesen wir ein Wort, so hier E1, E3, E4 und so weiter. 30:14.570 --> 30:18.470 Und dann haben wir Zustände, das heißt, es ist im Prinzip so Zustände, 30:18.650 --> 30:20.510 die wir auch bei ähnlichen Automaten haben. 30:21.110 --> 30:24.890 Und dann haben wir was Zusätzliches und das ist ein Keller, deswegen 30:24.890 --> 30:26.290 heißen Kellerautomaten. 30:26.690 --> 30:28.790 Und diese Keller sieht so aus. 30:30.770 --> 30:35.930 Und Kellerautomaten können Sie verwenden, um genau Wörter wie A hoch 30:35.930 --> 30:40.890 N, B hoch N, das heißt, wenn Sie zählen wollen, egal was für Aufgaben 30:40.890 --> 30:45.810 Sie bekommen, aber Sie wollen zählen, Klammeraufgaben, so Klammer 30:45.810 --> 30:50.150 offen, Klammer zu programmieren, Sprachen zu verifizieren, alle diese 30:50.150 --> 30:52.550 Sachen können Sie mit Kellerautomaten machen. 30:53.690 --> 30:54.770 Und wie funktioniert das? 30:54.910 --> 30:58.630 So jetzt einfach ein kleines Beispiel und das Beispiel werden wir 30:58.630 --> 31:00.550 vielleicht dreimal, viermal noch weiter haben. 31:00.850 --> 31:02.190 Aber wie funktioniert das? 31:02.590 --> 31:06.670 Es funktioniert so, dass wir einen Keller haben, sieht so aus, wie 31:06.670 --> 31:07.550 hier unten auch. 31:08.090 --> 31:12.850 Und dann gibt es ein Kellerzeichen K0 und sagt uns, dass es dann ganz 31:12.850 --> 31:14.630 unten im Keller K0 ist. 31:14.730 --> 31:18.750 Das heißt, wenn wir irgendwann bei K0 sind, dann ist es Ende von 31:18.750 --> 31:20.390 Kellerautomaten, es geht nicht mehr runter. 31:20.930 --> 31:25.710 Dann, wenn wir ein Wort haben, zum Beispiel A, A, A, B, B, B. 31:27.370 --> 31:27.970 Was machen wir? 31:28.070 --> 31:31.910 Das ist A hoch N, B hoch N oder genauer gesagt A hoch 3, B hoch 3. 31:32.770 --> 31:37.630 So, jedes Mal, dass wir ein A lesen mit unseren Automaten, dann 31:37.630 --> 31:39.410 schreiben wir ein A hier rein. 31:40.270 --> 31:44.710 Einmal A, dann zweimal A und dreimal A. 31:46.450 --> 31:49.010 Das ist die sogenannte Push, auf Englisch gesagt. 31:49.310 --> 31:53.370 So, jedes Mal, dass Sie ein A lesen, schreiben Sie in Speicher oder im 31:53.370 --> 31:59.370 Keller ein A und wenn Sie dann ein Eingabealphabet haben, das B ist, 32:00.730 --> 32:04.490 Sie löschen für jedes B, das Sie lesen, Sie löschen ein A. 32:05.210 --> 32:10.470 So, hier, ich lese das erste B, hier ein A wird gelöscht und Lesekopf, 32:10.630 --> 32:14.710 das sieht auch hier so aus, der Lesekopf kommt eins runter, dann kommt 32:14.710 --> 32:22.270 das zweite B, dann lösche ich ein A, Lesekopf kommt runter und hier B 32:22.270 --> 32:22.990 gelesen. 32:23.330 --> 32:26.610 Jedes Mal, dass wir B lesen, ein A löschen wir und so haben wir einen 32:26.610 --> 32:27.110 Speicher. 32:28.110 --> 32:33.570 So können wir A hoch N, B hoch N zum Beispiel akzeptieren. 32:35.570 --> 32:38.730 So, und was auch noch für Eigenschaften hier gibt, jeder, der hier 32:38.730 --> 32:41.550 jetzt gerade das Beispiel gehört hat, der kann auch sagen, ja, ja, 32:41.630 --> 32:43.750 klar, das ist dann das LIFO-Prinzip. 32:44.090 --> 32:46.770 LIFO-Prinzip heißt Last In, First Out. 32:47.710 --> 32:54.790 Und Last In, First Out heißt, dass, so nochmal hier, K0, wir haben es 32:54.790 --> 33:01.390 gemacht, A, A, A und das Letzte, das wir geschrieben haben, Last In, 33:01.710 --> 33:04.750 das war dieser A, wird als erstes gelöscht. 33:05.910 --> 33:09.090 Und nochmal das und das A, das wir am Anfang geschrieben haben, wird 33:09.090 --> 33:10.450 als erstes gelöscht. 33:10.530 --> 33:11.970 Deswegen ist es das LIFO-Prinzip. 33:14.150 --> 33:21.010 Gut, jetzt definieren wir dann genauer, wir haben Zustände, das wissen 33:21.010 --> 33:26.650 wir, genau wie ähnliche Automaten, wir haben Zustände S0 bis Sn, das 33:26.650 --> 33:33.290 heißt, wir haben Menge von Zuständen und jedes Mal, dass wir einen 33:33.290 --> 33:40.670 Übergang machen wollen, dann haben wir nicht nur jetzigen aktuellen 33:40.670 --> 33:44.910 Zustand und aktuelle Eingabe, die wir bei ähnlichen Automaten haben, 33:45.530 --> 33:48.430 sondern haben wir auch Kellerautomat. 33:48.550 --> 33:55.070 Wir müssen schauen, Zustand S, Eingabealphabet E und was das 33:55.070 --> 33:56.270 Kellerzeichen ist. 33:58.150 --> 34:04.070 Das sind die drei Elemente, die wir für jeden Übergang brauchen und 34:04.070 --> 34:12.090 Operation auf dem Keller, der oberste Kellerzeichen, K, wird durch U 34:12.090 --> 34:19.190 ersetzt und dann haben Sie hier diese Push-and-Pop, was ich gerade 34:19.190 --> 34:21.990 erzählt habe, diese Kellerautomaten, auf Englisch heißen Push-and-Pop. 34:22.310 --> 34:28.450 Push heißt, dass Sie ein Alphabet, da Eingabe, ein Alphabet dann 34:28.450 --> 34:34.450 schreiben, pushen und das sehen Sie hier, wenn Sie ein Push-V sagen, 34:34.610 --> 34:40.170 das heißt, wird im Keller so hier irgendwie K0 und dann so, so, so und 34:40.170 --> 34:43.910 da haben Sie K und dann V wird hier geschrieben, wenn Sie ein V lesen, 34:44.230 --> 34:48.910 V wird hier geschrieben und Pop ist es und das ist auch wichtig jetzt 34:48.910 --> 34:54.030 für Sie, jedes Mal, dass wir lesen, werden wir auch genau später 34:54.030 --> 34:55.830 haben, aber dann haben wir ein Lambda. 34:58.210 --> 35:01.690 Das ist wichtig, wenn wir dann später formale Beschreibungen haben, 35:01.690 --> 35:06.010 aber erst mal sehen Sie, wenn wir schreiben, dann werden wir dann, was 35:06.010 --> 35:10.370 auch immer im Keller ist und dann V wird vorne geschrieben, so das 35:10.370 --> 35:15.950 heißt ganz oben, VK, V wird hier und K und so weiter und wenn wir 35:15.950 --> 35:20.950 lesen, dieses Pop-Operation, dann haben wir Lambda, zeigen wir mit 35:20.950 --> 35:21.270 Lambda. 35:22.170 --> 35:24.350 Und wie wir mit Lambda zeigen, dann sehen wir gleich. 35:28.390 --> 35:33.630 Und der Lesekopf von unserem Kellerautomaten steht immer im obersten 35:33.630 --> 35:35.690 Kellerzeichen. 35:36.370 --> 35:39.190 Das heißt, es kann nicht sein, dass wir Kellerzeichen so irgendwo 35:39.190 --> 35:43.610 beliebig haben, sondern das ist immer oben und da müssen wir immer das 35:43.610 --> 35:46.510 entweder löschen, lesen oder was auch immer, aber das Kellerzeichen 35:46.510 --> 35:47.330 ist immer oben. 35:47.670 --> 35:51.390 Der Lesekopf ist immer oben und da müssen wir von oben nach unten 35:51.390 --> 35:54.250 lesen oder auch nach oben schreiben. 35:55.370 --> 35:59.330 Gut, formale Definition, das ist wichtig für Sie, wenn jemand sagt, 35:59.470 --> 36:02.550 okay, konstruieren Sie einen Kellerautomaten, da sollen Sie dann 36:02.550 --> 36:04.070 formal alles schreiben. 36:05.470 --> 36:06.050 Definition. 36:06.950 --> 36:11.850 Kellerautomat, Sie haben hier ein Tupel und Sie sehen jetzt gleich, 36:12.570 --> 36:16.590 gerade eben, dass Sie hier mehr Elementen in diesem Tupel haben als 36:16.590 --> 36:17.750 bei ähnlichen Automaten. 36:18.310 --> 36:20.910 Wir reden von deterministischen Kellerautomaten. 36:21.350 --> 36:23.170 Okay, was sind diese Elemente? 36:23.310 --> 36:27.170 E, es ist dann genauso wie vorher Eingabealphabet. 36:28.550 --> 36:33.150 Dann haben Sie S, Zustandsmenge, genauso wie bei ähnlichen Automaten. 36:34.650 --> 36:39.910 Und dann haben Sie diese zwei Definitionen, Kelleralphabet, das heißt 36:39.910 --> 36:44.690 Kelleralphabet muss nicht unbedingt das Gleiche sein wie bei 36:44.690 --> 36:45.650 Eingabealphabet. 36:46.390 --> 36:49.650 Sie können zum Beispiel zählen, zum Beispiel eine Zahl schreiben. 36:50.510 --> 36:54.290 Jedes Mal, dass Sie ein A lesen, ein 1 im Keller schreiben. 36:56.150 --> 37:00.710 Oder jedes Mal, dass Sie ein B lesen, ein 0 im Keller schreiben. 37:00.890 --> 37:06.430 Für viele Beispiele ist es so, dass wir immer das, was wir lesen, hier 37:06.430 --> 37:10.570 A lesen, A im Keller schreiben, aber Sie werden auch in Beispielen, in 37:10.570 --> 37:14.210 Übungen sehen, Sie können ein Eingabealphabet haben und etwas anderes 37:14.210 --> 37:15.010 im Keller schreiben. 37:15.110 --> 37:19.990 Deswegen haben wir eine Menge von Kelleralphabeten, so K. 37:20.930 --> 37:26.530 Und dann Kellerstartzeichen ist immer K0, wie S0, die wir immer nehmen 37:26.530 --> 37:28.850 für Anfangszustand, das ist auch K0. 37:29.850 --> 37:36.270 Menge und hier nicht leere Menge, die Endzustände, das darf nicht leer 37:36.270 --> 37:41.610 sein, wie bei ähnlichen Automaten, so Endzustände. 37:42.450 --> 37:45.990 Und die Überführungsfunktion ist ein bisschen jetzt hier anders, weil 37:45.990 --> 37:47.150 wir auch Keller haben. 37:48.970 --> 37:51.850 Okay, wie funktioniert, wie war es das eigentlich bei ähnlichen 37:51.850 --> 37:52.570 Automaten? 37:54.010 --> 37:56.130 Bei ähnlichen Automaten sah es so aus. 37:56.810 --> 38:02.230 So, das haben wir Delta und dann S mal so E, das war eine Produktion 38:02.230 --> 38:04.950 und haben wir ein S. 38:05.070 --> 38:11.170 Das heißt, für einen Zustand S, was weiß ich, S0, Eingabealphabet 0, 38:12.030 --> 38:15.050 dann landen wir in Zustand S1 zum Beispiel. 38:16.550 --> 38:18.550 Und hier, was passiert hier? 38:18.730 --> 38:24.550 Hier haben wir ein S, das Gleiche wie bei ähnlichen Automaten und hier 38:24.550 --> 38:26.110 E oder Lambda. 38:27.530 --> 38:30.990 Das heißt, hier können wir auch ein leeres Wort lesen und da sehen 38:30.990 --> 38:35.090 Sie, warum wir das machen wollen und können mit Kellerautomaten. 38:35.530 --> 38:39.030 Aber erst mal einfach notieren, wir können Eingabealphabet oder ein 38:39.030 --> 38:43.470 leeres Wort lesen und dann haben wir auch Kellerzeichen, 38:43.730 --> 38:44.330 Kelleralphabet. 38:45.610 --> 38:49.030 Und dann, was passiert, ist es, dass wir nicht nur in einen neuen 38:49.030 --> 38:53.770 Zustand landen, sondern Kellerzeichen, diese Lesekopf vom 38:53.770 --> 38:55.750 Kellerautomat auch sich ändert. 38:56.470 --> 39:01.050 Das heißt, jeder Übergang, es ist eine Änderung im Zustand und 39:01.050 --> 39:03.070 Kellerzeichen, Kellerlesekopf. 39:05.290 --> 39:06.630 Und das ist partiell. 39:06.750 --> 39:08.090 Warum das ist partiell? 39:08.710 --> 39:13.590 Wir haben hier geschrieben partielle Überführungsfunktion, weil wir 39:13.590 --> 39:19.970 entweder können wir sowas definieren, Delta, S, E und K. 39:22.830 --> 39:26.150 Und dann, wenn wir so definieren, das heißt eine Überführungsfunktion 39:26.150 --> 39:29.910 haben, das vom jetzigen Zustand Eingabealphabet und Kellerzeichen 39:29.910 --> 39:35.850 irgendeine Überführung gibt, wenn wir das so definieren, können wir 39:35.850 --> 39:40.530 das so nicht definieren und umgekehrt. 39:40.570 --> 39:42.930 Und deswegen, das heißt partielle Überführung. 39:44.230 --> 39:46.370 Das hier werden wir in mehreren Beispielen sehen. 39:47.890 --> 39:51.770 Einfach im Kopf halten, lassen Sie mich bis zur nächsten Folie kommen, 39:51.910 --> 39:54.630 dann werde ich das genauer auf dem Beispiel erklären. 39:57.070 --> 40:03.690 Und das hier, so kurz, dass ich dann auch das erkläre, das hier heißt, 40:03.690 --> 40:08.330 dass wir in irgendeinem Zustand sehen, zum Beispiel S0 hier oben und 40:08.330 --> 40:13.010 wir hier nichts mehr lesen, das heißt wir bleiben im gleichen 40:13.010 --> 40:17.450 Alphabet, aber Kellerzeichen ändern. 40:19.110 --> 40:22.470 Und das brauchen wir, wenn wir im Keller hoch und runter gehen wollen 40:22.470 --> 40:26.070 oder etwas lesen wollen, aber da oben nichts ändern wollen. 40:29.460 --> 40:34.220 Ohne letzte Bedienung wäre der Automat nicht deterministisch, aber wir 40:34.220 --> 40:37.040 reden jetzt hier über deterministischen Kellerautomaten. 40:39.060 --> 40:42.300 Und auch noch eine Bemerkung, ich glaube, jeder hier weiß, dass wir 40:42.300 --> 40:46.060 über Akzeptoren reden, das heißt, wir haben keine Ausgabe wie bei 40:46.060 --> 40:49.740 ähnlichen Automaten und deterministisch und nicht-deterministisch, so 40:49.740 --> 40:53.140 bei Millie- und More-Automaten haben Sie immer eine Ausgabe bei jedem 40:53.140 --> 40:54.740 Zustand oder jede Überführung. 40:55.080 --> 40:58.460 Und hier ist es auch so, wie bei ähnlichen Automaten, wir haben 40:58.460 --> 40:59.140 Akzeptoren. 40:59.220 --> 41:02.400 Das heißt, entweder der Kellerautomat akzeptiert ein Wort oder nicht 41:02.400 --> 41:04.660 und das wollen wir feststellen. 41:06.240 --> 41:07.640 Gut, Arbeitsweise. 41:08.460 --> 41:13.940 Und jetzt kommen wir genauer zu, wie wir wirklich ein Wort lesen. 41:14.440 --> 41:17.940 So, wir haben ein Wort und wir wollen ein Wort lesen, so ein Wort W, 41:18.180 --> 41:22.940 genauso war bei ähnlichen Automaten, so irgendein Wort W und dann so W 41:22.940 --> 41:28.300 zum Beispiel A, A, B, B, B und wir fangen natürlich mit dem linken 41:28.300 --> 41:34.740 Eingabezeichen, das heißt, wir fangen mit dem kleinen A hier an und 41:34.740 --> 41:40.640 Keller ist im Zeichen K0, das heißt, Keller ist ganz unten, es ist 41:40.640 --> 41:41.580 noch nichts im Keller. 41:44.080 --> 41:53.480 Und dann, wenn wir im Zustand S sind, Lesekopf von Automaten ist jetzt 41:53.480 --> 41:57.400 hier über zum Beispiel erstes Zeichen A oder so können wir E nennen, 41:59.780 --> 42:06.460 dann haben wir einen Fall, dass wir anhalten und Kellerautomat das 42:06.460 --> 42:13.680 Wort nicht akzeptiert, wenn Delta für bestimmte Eingabeworte nicht 42:13.680 --> 42:14.660 definiert ist. 42:14.860 --> 42:18.540 Zum Beispiel, wenn wir im Zustand S sind und irgendein Eingabealphabet 42:18.540 --> 42:22.340 haben und K ist irgendwo, Lesekopf ist irgendwo im Zeichen, 42:22.640 --> 42:26.720 Kellerzeichen ist K und das hier nicht in Überführungsfunktion 42:26.720 --> 42:33.020 definiert ist oder S und Lambda und K nicht definiert ist, dann 42:33.020 --> 42:38.120 Kellerautomat hält an, weil wir es halt nicht definiert haben und das 42:38.120 --> 42:39.140 Wort wird nicht akzeptiert. 42:39.220 --> 42:40.000 Tschüss, nach Hause. 42:42.020 --> 42:46.280 Dann, interessant ist es, wann wir was akzeptieren und da sind diese 42:46.280 --> 42:50.700 zwei Punkte hier. 42:51.620 --> 42:57.560 So, wenn wir im Zustand S sind, Eingabealphabet E lesen, K-Zeichen ist 42:57.560 --> 43:02.520 irgendein Zeichen im Keller, dann was passiert? 43:02.940 --> 43:12.220 Wir wechseln auf Zustand S Strich, das zeigen wir so, und K wird durch 43:12.220 --> 43:13.280 V ersetzt. 43:16.640 --> 43:21.380 Das heißt, Zustand wechselt und auch K hat ein V. 43:21.640 --> 43:26.760 So schreiben wir immer, so bei ähnlichen Automaten weiß nur Delta S 43:26.760 --> 43:31.760 und E gibt uns ein S Strich und hier müssen wir das für natürlich 43:32.520 --> 43:33.780 Kellerautomat auch definieren. 43:34.160 --> 43:39.440 Das heißt, hier haben wir auch ein K, ein Kellerzeichen und dann haben 43:39.440 --> 43:40.920 wir S Strich und V. 43:44.580 --> 43:51.960 Und wenn wir das hier haben, was ich auch vorhin gezeigt habe, was 43:51.960 --> 43:57.700 passiert, dass von Lesekopf von ähnlichen Automaten, so das Wort, was 43:57.700 --> 44:04.200 wir lesen, hier zum Beispiel, wir sind in E gewesen und S zeigt hier, 44:04.380 --> 44:09.720 so Zustand, so Lesekopf von Kellerautomat für Zustände ist es hier, 44:09.840 --> 44:15.880 zeigt E und Keller waren wir irgendwo hier K, so hier. 44:17.340 --> 44:22.380 Und wenn wir Delta S, Lambda und K haben, dann werden wir hier ein V 44:22.380 --> 44:28.400 schreiben, Lesezeichen von Keller, geht eins höher, Zustand wechselt 44:28.400 --> 44:35.700 von S nach S Strich, aber Lesekopf von Leseautomat, wie auf dem 44:35.700 --> 44:43.280 Eingabeband, bleibt da gleich, ändert sich nicht, weil wir leeres Wort 44:43.280 --> 44:46.040 lesen und das können wir bei ähnlichen Automaten machen. 44:46.780 --> 44:48.600 Wie war es beim Fall 2? 44:48.860 --> 44:53.620 Bei Fall 2 ist es so, dass das Gleiche passiert, beim Kellerautomat K, 44:53.680 --> 44:58.440 hier V, wenn wir im Keller schreiben, ändern wir dann die Position von 44:58.440 --> 45:04.980 Lesezeichen Keller, Lesekopf eins nach oben und dann auch E haben wir 45:04.980 --> 45:08.820 gelesen, dann lesen wir ein anderes Alphabet, das heißt, das ändert 45:08.820 --> 45:09.340 sich hier. 45:13.980 --> 45:17.340 Okay, und wann wird ein Wort akzeptiert? 45:17.420 --> 45:24.800 Genauso wie bei ähnlichen Automaten, wenn wir das Wort lesen und 45:24.800 --> 45:26.840 Kellerautomat in N-Zustand ist. 45:28.040 --> 45:32.840 Aber das sagt nicht etwas, dass Keller ganz unten sein muss. 45:33.300 --> 45:38.700 Keller, Lesekopf kann irgendwo bleiben, nur müssen wir in N-Zustand 45:38.700 --> 45:38.940 landen. 45:39.000 --> 45:41.000 Das ist genauso bei ähnlichen Automaten. 45:41.260 --> 45:44.820 Wenn ein ähnlicher Automat am Ende ist und wir das Wort bis Ende 45:44.820 --> 45:48.120 gelesen haben und nichts übrig ist, das Wort wird akzeptiert. 45:48.320 --> 45:50.600 Hat mit Keller nicht mehr zu tun. 45:51.440 --> 45:55.880 Nur Keller benutzen wir als Speicher, aber nicht, um festzustellen, 45:56.220 --> 45:58.260 dass wir ein Wort akzeptiert haben oder nicht. 45:59.500 --> 46:03.520 Gut, jetzt Konfiguration. 46:04.160 --> 46:07.200 Sie können jetzt das eigentlich selber machen. 46:07.280 --> 46:10.680 Die Konfiguration ist es so, dass wir immer in irgendeinem Zustand 46:10.680 --> 46:12.720 sind, ein Wort zu bearbeiten haben. 46:12.840 --> 46:17.140 Aktuelle Kellereinheit, das ist schon klar von der letzten Folie. 46:19.300 --> 46:22.860 Und dann Übergangsrelation, das ist auch eigentlich klar von der 46:22.860 --> 46:26.320 letzten Folie, aber hier ist es halt formal und das ist die Definition 46:26.320 --> 46:26.680 dazu. 46:27.960 --> 46:32.500 So, das ist das Gleiche wie bei ähnlichen Automaten, hatten wir immer 46:32.500 --> 46:36.120 Übergangsrelation von ähnlichen Automaten, die hatten wir so gezeigt 46:36.120 --> 46:39.500 und jetzt haben wir Kellerautomaten, wir zeigen so. 46:41.100 --> 46:46.620 Und von einer Konfiguration, so irgendeine Konfiguration, wir sind in 46:46.620 --> 46:50.080 irgendeinem Zustand, wir haben ein Wort zu lesen und wir haben 46:50.080 --> 46:58.380 Kellerzeichen V, dann gehen wir auf nächste Konfiguration mit diesem 46:58.380 --> 46:58.880 Zeichen. 47:00.960 --> 47:03.640 Und das ist auch nächste Konfiguration heißt, das ist, dass wir dann 47:03.640 --> 47:08.440 irgendwie ein Strich sein, hier V Strich sein und dann hier W Strich 47:08.440 --> 47:09.180 und V Strich. 47:09.880 --> 47:14.280 Genauer gesagt, unten wird so genauer gezeigt, so wenn wir ein Wort 47:14.280 --> 47:20.340 haben, dass es nicht nur W ist, sondern das ist dann hier EW und wir 47:20.340 --> 47:22.160 wissen, dass wir erstmal E lesen. 47:23.120 --> 47:32.860 Wir sind in Zustand S, wir lesen E, im Keller haben wir KV und dann 47:32.860 --> 47:35.760 was passiert, ist es dann, nächste Konfiguration ist es, dass wir 47:35.760 --> 47:37.120 unseren Zustand ändern müssen. 47:38.240 --> 47:42.500 E gelesen haben wir, jetzt bleibt nur W zu lesen, so E haben wir 47:42.500 --> 47:46.760 gelesen, dann bleibt Restwort W und im Keller kommt dann ein neues 47:46.760 --> 47:49.100 Zeichen im Keller, das heißt, Keller wird gerutscht. 47:49.340 --> 47:58.140 So, da waren wir hier K0 und dann hier K und dann KV war schon im 47:58.140 --> 48:00.140 Zustand, so was wir im Keller hatten. 48:01.280 --> 48:06.920 Und dann kommt jetzt ein V Strich und dann schreiben wir hier V Strich 48:06.920 --> 48:07.180 V. 48:07.840 --> 48:10.560 Das ist immer die zwei, die da hier sind. 48:10.840 --> 48:16.000 Und das ist äquivalent, wie ich vorhin gezeigt habe, Übergang von S, 48:16.100 --> 48:21.600 lesen wir E und Kellerzeichen ist K, dann sind wir bei S Strich und V 48:21.600 --> 48:22.460 Strich. 48:25.100 --> 48:28.460 Und was passiert, wenn wir das leere Wort lesen, das heißt, das Wort 48:28.460 --> 48:34.140 EW gar nicht lesen, das E gar nicht lesen, das heißt, hier bleibt das 48:34.140 --> 48:37.360 Gleiche, das Wort haben wir gar nicht gelesen, aber wir haben eine 48:37.360 --> 48:38.280 Operation im Keller. 48:39.260 --> 48:43.720 Das heißt, hier wird nur im Keller die Operation gemacht, im Keller, 48:43.940 --> 48:47.000 wenn wir was schreiben und das können wir mit diesem Lambda zeigen. 48:48.780 --> 48:53.000 Ist das jetzt mit Lambda für alle klar, wie wir, wenn wir das Wort 48:53.000 --> 48:57.360 nicht lesen, aber im Keller Kellerzeichen ändern, schreiben wir so, 48:57.700 --> 48:59.440 wie Sie hier sehen. 48:59.680 --> 49:00.960 Ist das klar für alle hier? 49:01.860 --> 49:02.260 Gut. 49:04.680 --> 49:08.680 Und Sie können diese Zeichen, was wir hier hatten für 49:08.680 --> 49:14.220 Übergangsrelation, Sie können mit einem Stern verwenden, um ein ganzes 49:14.220 --> 49:14.940 Wort zu lesen. 49:15.040 --> 49:19.960 Bis jetzt haben wir nur E gelesen, so ein Eingabealphabet E gelesen 49:19.960 --> 49:23.500 und wenn wir sagen, okay, wenn wir bis ein Wort W lesen, das heißt, 49:23.580 --> 49:26.920 wir nicht genau sagen, was für Elementen in dem Wort gelesen haben, 49:26.980 --> 49:30.280 sondern einfach zeigen wollen, dass wir ein Wort gelesen haben. 49:30.520 --> 49:34.980 Da können wir mit Stern das zeigen und steht für diese reflexiv 49:34.980 --> 49:38.860 -transitive Hülle, das wir auch damals bei ähnlichen Automaten hatten. 49:39.880 --> 49:46.700 Das heißt, K-A, dieser Kellerautomat akzeptiert ein Wort W, wenn wir 49:46.700 --> 49:52.080 von Anfangszustand S0 anfangen, W komplett lesen und Kellerautomat ist 49:52.080 --> 49:59.220 auch K0 und das komplette Wort lesen und am Ende sind wir bei Lambda, 49:59.720 --> 50:03.860 irgendein Zeichen im Keller und S muss in N-Zustand sein. 50:05.320 --> 50:09.200 Das heißt, was ich auch in letzter Folie gesagt habe, wenn wir in N 50:09.200 --> 50:13.320 -Zustand in Automaten sind, das reicht, dass wir das Wort bis Ende 50:13.320 --> 50:15.920 gelesen haben, dann heißt das Wort haben wir akzeptiert. 50:20.140 --> 50:24.200 Und dann können wir Sprache definieren, wir sagen, wenn dieser 50:24.200 --> 50:30.640 Kellerautomaten solche Worte akzeptiert, dann ist dann diese Sprache 50:30.640 --> 50:34.300 von Kellerautomaten. 50:34.580 --> 50:38.000 Das heißt, Sprache von Kellerautomaten ist die Menge von Worten, die 50:38.000 --> 50:40.160 von diesen Kellerautomaten akzeptiert werden. 50:42.200 --> 50:43.400 Beispiel jetzt. 50:45.940 --> 50:50.000 So, Kellerautomat definieren wir so mit einem Tuple. 50:50.620 --> 50:53.320 Menge A und B für Eingabealphabet. 50:54.240 --> 50:57.200 Zustände S0, S1, S2. 50:58.160 --> 51:01.440 Kelleralphabet, es ist nur K0 und A. 51:02.560 --> 51:05.760 Sehen Sie, Kelleralphabet, es ist nicht das Gleiche wie 51:05.760 --> 51:08.500 Eingabealphabet, mindestens nicht vollständig. 51:10.040 --> 51:14.060 Und dann haben wir Delta, S0, K0 und N-Zustand ist S2. 51:14.820 --> 51:21.700 Und dann definieren wir die, so bei ähnlichen Automaten war es 51:21.700 --> 51:24.760 einfacher, weil wir immer ein Diagramm gezeigt haben und jetzt müssen 51:24.760 --> 51:26.980 wir so arbeiten bei Kellerautomaten. 51:27.720 --> 51:28.860 Okay, was passiert? 51:28.960 --> 51:36.180 Wir sind in S0, wir lesen A und wenn Sie es dann bei Übungen oder 51:36.180 --> 51:39.800 Klausuren oder so, Sie können auch für sich einen Keller hier malen, 51:40.120 --> 51:41.300 dass Sie sehen, was passiert. 51:43.020 --> 51:52.140 Gut, ich bin in S0, lese A und bin in K0 und dann bleibe ich in S0 und 51:52.140 --> 51:53.540 A wird im Keller geschrieben. 51:54.720 --> 51:55.340 Das sagt hier. 51:56.640 --> 51:56.960 Richtig? 51:57.460 --> 51:57.700 Gut. 51:58.740 --> 52:05.380 Dann, wenn ich in S0 bin, das bin ich gerade, und ein A im Keller 52:05.380 --> 52:10.560 steht, Keller ist nicht mehr leer, im Keller habe ich jetzt ein A und 52:10.560 --> 52:12.860 ein A kommt als Eingabealphabet. 52:13.880 --> 52:15.900 Dann, was zeigt das hier? 52:16.680 --> 52:24.200 Das heißt, ich in S0 bleibe und ein A im Keller schreibe. 52:26.360 --> 52:27.040 Gut. 52:27.720 --> 52:30.440 Dann, wenn ich in S0 bin, 52:37.140 --> 52:40.820 das bin ich in S0 und ich schreibe A, was mache ich? 52:41.480 --> 52:49.740 Ich ändere meinen Zustand auf S1 und mit diesem Lambda haben wir 52:49.740 --> 52:53.280 gesagt, wenn wir im Keller Lambda schreiben, heißt es, dass wir 52:53.280 --> 52:53.700 löschen. 52:55.560 --> 53:01.300 Das heißt, ich habe ein B in Eingabealphabet, ein A im Kellerautomat 53:01.300 --> 53:06.400 und bei diesem B, ich lösche ein A. 53:07.120 --> 53:09.000 So, hier gelöscht. 53:09.240 --> 53:11.260 Und ändere meinen Zustand auf S1. 53:11.400 --> 53:13.520 Das heißt, ich bin gerade auf S1. 53:14.280 --> 53:14.520 Gut. 53:15.120 --> 53:21.820 Dann, wenn ich in S1 bin und noch ein B kommt und im Keller immer ein 53:21.820 --> 53:24.260 A gibt, dann, was mache ich? 53:25.860 --> 53:28.440 Lösche nochmal ein Element aus dem Keller. 53:29.700 --> 53:31.840 So, hier nochmal, hier wird gelöscht. 53:33.700 --> 53:43.060 Und wenn ich in S1 bin und das bin ich auch gerade und hier, ich bin 53:43.060 --> 53:47.660 in S1, K ist es, K0, im Keller habe ich nur K0. 53:48.540 --> 53:50.140 Ich lese nichts mehr. 53:51.420 --> 53:57.140 Mein Lesekopf bleibt stehen und ich mache nur einen Übergang auf den 53:57.140 --> 53:58.440 nächsten Zustand. 53:58.800 --> 54:02.840 Das heißt, was hier passiert, ist, in K0 bleibt K0, wird nichts 54:02.840 --> 54:03.300 geschrieben. 54:04.400 --> 54:07.760 Und was ich hier nur mache, ist es, ich gehe auf S2. 54:08.900 --> 54:12.300 Das heißt, mit diesem Lambda, das heißt, dieser Lesekopf bleibt stehen 54:12.300 --> 54:16.320 und was ich mache, ist es nur einen Zustandwechsel. 54:16.920 --> 54:19.080 Das Wort wird nicht weitergelesen oder sowas. 54:20.220 --> 54:20.280 Gut. 54:21.260 --> 54:23.880 Und dann S2, was war S2? 54:24.020 --> 54:25.780 S2 war mein Endzustand. 54:29.710 --> 54:34.190 Und wir behaupten, dass mit diesen Kellerautomaten können wir A hoch 54:34.190 --> 54:36.250 N, B hoch N lesen. 54:36.950 --> 54:37.350 Stimmt? 54:37.710 --> 54:37.910 Ja. 54:38.830 --> 54:42.670 Sie können, jetzt gerade das Beispiel ist es für zweimal A, zweimal B, 54:43.130 --> 54:46.770 aber wir können das zum Beispiel für fünfmal A und fünfmal B machen. 54:47.710 --> 54:51.430 Das Beispiel kommt gleich, das werde ich hier nicht schreiben. 54:51.950 --> 54:57.990 Aber dass hier diese Konfigurationen reichen, um diese A hoch N, B 54:57.990 --> 55:02.770 hoch N mit diesen Kellerautomaten zu akzeptieren. 55:03.430 --> 55:07.350 Und hier haben wir ein Beispiel für A hoch 3, B hoch 3. 55:07.850 --> 55:11.090 Was Sie machen müssen immer bei Aufgaben, die Sie bekommen. 55:11.730 --> 55:16.010 Sie schreiben einfach für den Kellerautomaten diese Konfigurationen 55:16.010 --> 55:18.370 und dann testen Sie das. 55:18.790 --> 55:23.030 Nehmen Sie zum Beispiel fünf verschiedene Beispiele aus der Sprache, 55:23.150 --> 55:25.390 die Sie dann die Worte davon akzeptieren müssen. 55:26.230 --> 55:29.950 Machen Sie drei, vier, fünf und mehr aus zehn Beispielen und schauen 55:29.950 --> 55:33.530 Sie, ob mit dieser Konfiguration Sie diese Worte akzeptieren. 55:34.010 --> 55:36.890 Wenn dann, dann ist es gute Verifikation, dass Sie gute 55:36.890 --> 55:39.210 Konfigurationen für Kellerautomaten geschrieben haben. 55:39.650 --> 55:43.310 Hier ist es so, wir machen das hier für A hoch 3, B hoch 3. 55:44.170 --> 55:48.730 Gut, wir fangen mit S0 an, A hoch 3, B hoch 3 ist das Wort, das wir 55:48.730 --> 55:51.250 lesen wollen und wir sind im K0. 55:52.990 --> 56:01.530 So, mit einmal so lesen, das heißt, ich lese einmal ein A, hier habe 56:01.530 --> 56:08.030 ich A hoch 2 und A schreibe ich im Keller, wie, mit dem ich dann diese 56:08.030 --> 56:10.330 Nummer eins hier benutze. 56:10.830 --> 56:11.110 Warum? 56:11.450 --> 56:16.090 Weil im Keller ist K0, ich bin in S0, das ist genau diese Nummer eins. 56:16.610 --> 56:21.810 So, hier Keller, K0 steht immer ganz unten, A wird hier geschrieben 56:21.810 --> 56:23.950 und ich bin immer noch in S0. 56:25.170 --> 56:28.970 Gut, dann habe ich noch ein A zu lesen. 56:30.010 --> 56:33.210 So, ich lese noch ein A, was für Regel ist es dann? 56:33.530 --> 56:37.510 Das ist diese Nummer zwei, Konfiguration Nummer zwei, ich bin in S0, 56:37.810 --> 56:42.330 im Keller steht ein A, ich lese ein A und ich schreibe im Keller AA 56:42.330 --> 56:45.270 und ich bleibe immer noch in S0. 56:46.790 --> 56:50.430 Dann mache ich auch noch einmal, ich lese noch ein A und ich bleibe 56:50.430 --> 56:52.910 noch einmal hier und ich bin immer noch in S0. 56:54.390 --> 57:01.210 Gut, dann kommt ein B, wenn ein B kommt, dann muss ich diese dritte 57:01.790 --> 57:07.170 Konfiguration hier nehmen, das ist diese, ändere ich meinen Zustand, 57:07.250 --> 57:11.210 da bin ich bei Zustand S1 und lösche ein A. 57:13.010 --> 57:22.550 Und dann nochmal hier S1, das ist nochmal in gleicher, genau, da 57:22.550 --> 57:29.770 bleibe ich nochmal bei S1 und lösche ich noch ein A, das ist dann 57:29.770 --> 57:31.590 jetzt hier diese Konfiguration. 57:33.730 --> 57:41.330 Und dann lese ich noch allerletzte B und bin immer noch in Zustand S1 57:41.330 --> 57:42.310 und lösche ein A. 57:43.830 --> 57:48.470 Und dann hier, genau hier, das ist, was Sie bei Kellerautomaten machen 57:48.470 --> 57:52.790 müssen immer, dass Sie dann irgendwann in N-Zustand kommen. 57:53.850 --> 57:55.030 Und wie machen wir das? 57:55.810 --> 57:57.510 Das ist diese Regel mit Lambda. 57:58.090 --> 58:03.050 Das heißt, Sie sind in irgendeinem Zustand S1 und Sie wollen zu S2 58:03.050 --> 58:06.110 kommen, dass es N-Zustand ist, weil wir es so definiert haben. 58:07.830 --> 58:13.350 Und Sie machen diese Konfiguration, das, was jetzt hier kommt, wird 58:13.350 --> 58:18.630 nichts gelesen und werden wir in N-Zustand wechseln und dann haben wir 58:18.630 --> 58:21.850 auch das Wort bis Ende gelesen, N-Zustand, das Wort haben wir 58:21.850 --> 58:22.470 akzeptiert. 58:23.790 --> 58:26.990 Sie können zum Beispiel, wenn Sie sowas in die Konfiguration 58:26.990 --> 58:30.750 schreiben, dann versuchen Sie zum Beispiel für ein Beispiel A hoch 4, 58:31.150 --> 58:31.890 B hoch 3. 58:34.010 --> 58:35.370 Das wird nicht akzeptiert. 58:35.470 --> 58:35.670 Warum? 58:36.050 --> 58:39.570 Weil wir am Ende das Wort gelesen haben und nicht in N-Zustand sind. 58:39.830 --> 58:43.590 Das heißt, der N-Zustand wäre wahrscheinlich, also der Zustand, den 58:43.590 --> 58:49.370 wir am Ende haben, ist S0 oder S1 und es ist nicht dann S2 und da 58:49.370 --> 58:50.930 können wir nicht das Wort akzeptieren. 58:53.730 --> 59:00.950 Gut, Kellerautomat akzeptiert alle Wörter der Form A hoch N, B hoch N. 59:01.170 --> 59:02.430 Das ist diese allgemeine Form. 59:03.230 --> 59:06.730 Und das können Sie auch so zeigen, wenn Sie dann in irgendeiner 59:06.730 --> 59:11.770 Aufgabe zeigen wollen, dass Sie dann allgemein N akzeptieren wollen, A 59:11.770 --> 59:12.810 hoch N, B hoch N. 59:13.130 --> 59:18.470 Sie können dann genau diese Art von Konfiguration nehmen, so N mal A 59:18.470 --> 59:25.070 lesen, diese Sternzeichen oder hier genau N mal A lesen, das heißt, 59:25.170 --> 59:35.110 mit dieser Stern lesen Sie Wörter, so N mal und dann haben Sie hier N 59:35.110 --> 59:42.930 mal auch B und können Sie dann mit diesen Zeichen die Konfigurationen 59:42.930 --> 59:43.470 noch zeigen. 59:47.910 --> 59:51.970 So, was wir jetzt hier gemacht haben, ist es so, dass wir Wörter 59:51.970 --> 59:53.670 akzeptieren können, die mit A anfangen. 59:54.090 --> 59:55.150 Sie können nicht mit B anfangen. 59:55.230 --> 59:58.370 Das heißt, wir können nicht B hoch N, A hoch N akzeptieren mit diesen 59:58.370 --> 01:00:00.030 Kellerautomaten, die wir bis jetzt hatten. 01:00:00.330 --> 01:00:04.130 Aber Sie können üben, wie können Sie einen Kellerautomaten haben, die 01:00:04.130 --> 01:00:08.550 A hoch N, B hoch N und A hoch N akzeptiert, zum Beispiel. 01:00:10.690 --> 01:00:16.150 Und das ist dann die Eingabe, man darf nicht mit B beginnen, weil das 01:00:16.150 --> 01:00:17.670 hier ist halt nicht definiert. 01:00:19.870 --> 01:00:26.870 Oder auf erstes B darf kein A mehr folgen, weil das hier ist nicht 01:00:26.870 --> 01:00:27.450 definiert. 01:00:27.570 --> 01:00:28.830 Von Zustand erst eins. 01:00:30.410 --> 01:00:36.090 Wir haben es so programmiert, dass es danach einmal nach B, ein B 01:00:36.090 --> 01:00:38.450 kommt und kein A und das ist halt nicht definiert. 01:00:42.520 --> 01:00:47.740 Gut, das war's und dann gibt es hier einen Satz und das ist jetzt für 01:00:47.740 --> 01:00:53.540 alle, ich glaube, klar, dass für jeden ähnlichen Automaten existiert 01:00:53.540 --> 01:00:57.680 ein deterministischen Kellerautomaten, K.A., das gleiche Sprache 01:00:57.680 --> 01:00:58.360 akzeptiert. 01:01:04.260 --> 01:01:07.120 Kellerautomat kann im Prinzip ein ähnlicher Automat sein, dass wir den 01:01:07.120 --> 01:01:08.000 Keller nicht benutzen. 01:01:08.960 --> 01:01:11.200 Wenn wir den Keller nicht benutzen, dann haben wir einen ähnlichen 01:01:11.200 --> 01:01:11.860 Automaten. 01:01:12.460 --> 01:01:14.820 Und das ist auch ein trivialer Beweis. 01:01:15.560 --> 01:01:18.940 Genau hier hat Herr Schmeck auch noch geschrieben, ein ähnlicher 01:01:18.940 --> 01:01:21.440 Automat ist ein Kellerautomat, der den Keller nicht nutzt. 01:01:21.980 --> 01:01:25.860 So, das kann auch eine Multiple-Choice-Frage sein. 01:01:25.920 --> 01:01:29.800 Das ist nur ein Tipp von mir für Sie, wenn Sie das haben. 01:01:30.160 --> 01:01:34.160 Okay, das heißt, die Sprachen, die ähnliche Automaten akzeptieren, 01:01:34.840 --> 01:01:39.140 sind eine Submenge von Sprachen, die von Kellerautomaten akzeptiert 01:01:39.140 --> 01:01:39.360 werden. 01:01:39.620 --> 01:01:42.420 Wir wissen zum Beispiel, ähnliche Automaten A-Hochren, B-Hochren nicht 01:01:42.420 --> 01:01:45.660 akzeptieren, aber Kellerautomaten, die akzeptieren können. 01:01:47.060 --> 01:01:53.920 Gut, dann das Beispiel, das Lieblingsbeispiel, das sind arithmetische 01:01:53.920 --> 01:01:56.080 Ausdrücke oder Klammerstrukturen. 01:01:58.720 --> 01:02:04.340 Wir wollen Worte akzeptieren, die so aussehen. 01:02:11.720 --> 01:02:16.220 Hier müssen wir auch zählen, das heißt, mit ähnlichen Automaten können 01:02:16.220 --> 01:02:18.220 wir solche Worte nicht akzeptieren. 01:02:19.220 --> 01:02:21.760 Aber wie ist es mit ähnlichen Automaten? 01:02:22.980 --> 01:02:24.940 So, erstmal mit Kellerautomaten. 01:02:25.280 --> 01:02:31.380 Erstmal, wir definieren das sogenannte wohlgeformter Klammerausdruck. 01:02:33.340 --> 01:02:35.680 Was ist wohlgeformter Klammerausdruck? 01:02:35.840 --> 01:02:37.120 Das heißt, das ist nicht so. 01:02:38.440 --> 01:02:39.240 So ist es nicht. 01:02:40.960 --> 01:02:46.620 Okay, wohlgeformter ist das, was wir oben haben oder so, aber es kann 01:02:46.620 --> 01:02:47.500 nicht so sein. 01:02:47.880 --> 01:02:48.700 So ist es nicht. 01:02:49.020 --> 01:02:50.500 Und wie können wir es definieren? 01:02:50.980 --> 01:02:54.940 Die Anzahl der öffnenden Klammern in W gleich der Anzahl der 01:02:54.940 --> 01:02:56.560 geschlossenen Klammern in W ist. 01:02:57.300 --> 01:03:00.940 Okay, zum Beispiel, das trifft eigentlich für diesen Beispiel zu. 01:03:01.770 --> 01:03:03.600 Aber dann kommt der zweite Punkt. 01:03:04.400 --> 01:03:11.160 Für jede Zerlegung W auf UV, die Anzahl der schließenden Klammern in U 01:03:11.160 --> 01:03:14.160 nicht größer als die Anzahl der öffnenden Klammern in U ist. 01:03:14.740 --> 01:03:20.600 Und das ist dann hier, wenn wir so etwas haben, dann hier schließende 01:03:20.600 --> 01:03:24.280 Klammern, es ist mehr als was wir aufmachen. 01:03:24.280 --> 01:03:27.240 Aber auch sowas wird nicht akzeptiert. 01:03:28.680 --> 01:03:31.940 So, das ist wohlgeformter Klammerausdruck. 01:03:34.180 --> 01:03:35.800 Hier auch, okay, Beispiele. 01:03:36.740 --> 01:03:40.260 Hier, das ist ein Beispiel, das wir wollen, aber das hier stimmt nicht 01:03:40.260 --> 01:03:42.180 und das ist kein WKA. 01:03:44.620 --> 01:03:49.520 So, wie können wir einen ähnlichen Kellerautomaten erzeugen, der das 01:03:49.520 --> 01:03:50.120 akzeptiert? 01:03:50.120 --> 01:03:52.100 Klar, das ist wie A hoch N, B hoch N. 01:03:53.500 --> 01:03:56.160 Und wie definieren wir unsere Kellerautomaten? 01:03:56.600 --> 01:04:00.160 KA, Eingabealphabet, steht aus diese Klammern. 01:04:00.620 --> 01:04:05.920 Wir haben zwei Zustände, hier Kellerzeichen und so weiter. 01:04:06.340 --> 01:04:11.240 Eigentlich, Sie können das jetzt basieren auf was wir vorhin hatten, 01:04:11.720 --> 01:04:13.120 sofort lösen. 01:04:13.120 --> 01:04:17.800 Das ist, nur statt A müssen Sie Klammern schreiben, statt B Klammern 01:04:17.800 --> 01:04:19.880 aufschreiben, statt B Klammern zuschreiben. 01:04:21.400 --> 01:04:24.060 So, das ist im Prinzip das Gleiche. 01:04:24.200 --> 01:04:25.820 Ich kann es nochmal dann genau erklären. 01:04:26.160 --> 01:04:30.760 Wenn wir in S0 sind und Eingabealphabet so eine Klammer kommt, dann 01:04:30.760 --> 01:04:36.020 wird dann in den Keller geschrieben, ändern wir Zustand und dann sind 01:04:36.020 --> 01:04:39.880 wir in einem neuen Zustand und dann haben wir das schon im Keller, 01:04:39.880 --> 01:04:44.280 lesen wir Eingabealphabet und dann schreiben wir das nochmal im 01:04:44.280 --> 01:04:44.560 Keller. 01:04:45.200 --> 01:04:51.980 Das heißt, im Keller haben wir jetzt K0 hier so und hier so und dann, 01:04:52.400 --> 01:04:55.700 wir können auch beliebig haben, so wir können zum Beispiel zehnmal das 01:04:55.700 --> 01:04:59.520 Gleiche machen, das heißt, wir bleiben zehnmal in diesem Loop und dann 01:04:59.520 --> 01:05:04.320 jedes Mal, dass Klammer zukommt, dann lesen wir eins, so das ist hier, 01:05:04.560 --> 01:05:10.280 es ist einmal löschen vom Keller und kommen wir dann, also wenn wir 01:05:10.280 --> 01:05:14.160 nochmal so, wie wir bis jetzt so hatten und dann jetzt so eins kommt, 01:05:14.260 --> 01:05:18.360 dann wird gelöscht und nochmal so eins kommt, wird gelöscht und dann 01:05:18.360 --> 01:05:20.420 sind wir in N-Zustand. 01:05:22.740 --> 01:05:26.760 Gut, das ist dann die Bearbeitung für das Beispiel. 01:05:27.320 --> 01:05:31.260 Ich glaube, ich werde es nicht genauer jetzt hier erklären, aber das 01:05:31.260 --> 01:05:34.120 Beispiel mit A hoch N, B hoch N, das habe ich schon erklärt. 01:05:34.440 --> 01:05:39.500 Sie können zum Beispiel andere Beispiele nehmen, zum Null hoch N, Eins 01:05:39.500 --> 01:05:40.080 hoch N. 01:05:42.140 --> 01:05:44.880 Das ist auch die gleiche Sprache, die Sie verwenden können. 01:05:45.140 --> 01:05:51.820 Statt Null kann man Klammer nehmen, Klammer offen, Klammer zu oder A 01:05:51.820 --> 01:05:53.200 hoch N, B hoch N. 01:05:53.200 --> 01:05:56.620 Das sind im Prinzip alle gleiche Sprachen. 01:05:59.640 --> 01:06:03.620 Und jetzt kommt eine sehr interessante Sprache. 01:06:04.740 --> 01:06:05.900 Kennen Sie Palindrome? 01:06:07.840 --> 01:06:08.680 Sehr gut. 01:06:10.220 --> 01:06:13.640 Es ist ähnlich wie Palindrome, wir werden Palindrome in fünf Minuten 01:06:13.640 --> 01:06:17.380 haben, aber was es hier gibt, ist es so, dass wir ein Eingabealphabet 01:06:17.380 --> 01:06:23.200 haben, das aus Null und Eins und C besteht und dann wir wollen Worte 01:06:23.200 --> 01:06:24.800 akzeptieren, die so aussehen. 01:06:26.580 --> 01:06:30.460 Und das ist ähnlich wie Palindrome, aber es ist hier ein C in der 01:06:30.460 --> 01:06:33.540 Mitte, dass wir es nicht genau wie Palindrome nennen können. 01:06:34.440 --> 01:06:38.520 Zum Beispiel, das Wort kann aus Null und Eins und C bestehen, zum 01:06:38.520 --> 01:06:45.440 Beispiel Null, Null, Eins, Null und dann ein C und was nach C kommt, 01:06:45.540 --> 01:06:50.120 das ist diese V, was wir hier haben, diese Bezeichnung hier und dann 01:06:50.120 --> 01:06:54.180 kommt ein C und was nach C kommt, muss eine Spiegelung von V sein. 01:06:55.180 --> 01:06:58.180 Das heißt hier Null, Eins, Null, Null. 01:06:59.540 --> 01:07:03.800 Und solche Worte können wir von Kellerautomaten akzeptieren. 01:07:04.540 --> 01:07:05.880 Wie funktioniert das? 01:07:09.540 --> 01:07:15.620 Wir lesen V und speichern das im Keller ab. 01:07:16.820 --> 01:07:23.560 Das heißt, ich speichere das hier K0, Null, Null, Eins, Null. 01:07:25.660 --> 01:07:31.780 Sobald das erste und einzige C erscheint, okay, das heißt ich bin dann 01:07:31.780 --> 01:07:41.280 hier, Lesekopf von Automaten ist bei C, ich lese dann U, das heißt 01:07:41.280 --> 01:07:47.880 diese Teil U und dann, wenn es gleich ist, wenn genau was ich lese 01:07:47.880 --> 01:07:52.660 gerade, also danach C lese, gleich ist wie im Keller, lösche ich das. 01:07:52.960 --> 01:07:56.700 Wenn es nicht gleich ist, höre ich auf und das Wort akzeptiere ich 01:07:56.700 --> 01:07:56.940 nicht. 01:07:58.060 --> 01:08:02.940 Jetzt müssen wir den Automaten diese Gleichheit auch noch bringen. 01:08:03.900 --> 01:08:09.400 Das ist nicht nur so A hoch N, B hoch N, sondern ob das Wort, das 01:08:09.400 --> 01:08:13.180 Alphabet, das wir gerade lesen, das Gleiche ist, dass es was in dem 01:08:13.180 --> 01:08:13.880 Keller ist. 01:08:13.880 --> 01:08:17.900 Und das ist was Interessantes bei Kellerautomaten. 01:08:18.920 --> 01:08:20.060 Wie funktioniert das? 01:08:20.800 --> 01:08:27.640 Wir definieren die Zustände, Endzustand und Kelleralphabet Null und 01:08:27.640 --> 01:08:28.040 Eins. 01:08:30.400 --> 01:08:36.920 Kelleralphabet beinhaltet C nicht, C ist das Eingabealphabet, aber es 01:08:36.920 --> 01:08:38.660 ist nicht im Kelleralphabet. 01:08:39.380 --> 01:08:45.880 Okay, wir sind in Zustand Null, lesen wir ein E, E aus Eingabealphabet 01:08:45.880 --> 01:08:47.940 und schreiben wir das im Keller. 01:08:49.100 --> 01:08:51.260 Das ist schon bis jetzt soweit klar. 01:08:51.800 --> 01:08:52.040 Gut. 01:08:56.060 --> 01:08:59.960 Und wenn Keller leer ist, dann schreiben wir es im Keller und wenn 01:08:59.960 --> 01:09:05.780 Keller nicht leer ist, das heißt irgendein Wort K drin hat, dann lesen 01:09:05.780 --> 01:09:08.920 wir so E und schreiben wir das dann im Keller. 01:09:09.140 --> 01:09:12.800 Das heißt, hier habe ich E1, E2, E3. 01:09:13.400 --> 01:09:13.580 Gut. 01:09:14.100 --> 01:09:18.200 Das heißt, hier können wir beliebig lange bleiben, bis wir das gelesen 01:09:18.200 --> 01:09:21.080 haben, bis wir eigentlich ein C haben. 01:09:21.830 --> 01:09:31.680 Wenn ein C kommt, dann, und Keller hat irgendein Zeichen K, statt E3 01:09:31.680 --> 01:09:32.940 kann ich hier K schreiben. 01:09:35.160 --> 01:09:36.260 Was passiert? 01:09:36.900 --> 01:09:39.680 Ändere ich meinen Zustand auf S1? 01:09:40.160 --> 01:09:44.540 Das heißt, ändere ich Keller nicht, sondern einfach Keller bleibt da 01:09:44.540 --> 01:09:49.900 auf K und nur mein Zustand auf S0 werde ich auf S1 gehen. 01:09:51.340 --> 01:09:58.440 Wenn S1, dann lese ich ein E, das heißt, wie weit sind wir, so 0, 0, 01:09:58.560 --> 01:10:02.980 1, 0, C haben wir gelesen und jetzt lese ich ein 0. 01:10:05.200 --> 01:10:10.680 Wenn E und E gibt, das ist das gleiche, E muss das sein. 01:10:11.300 --> 01:10:17.140 Wenn zum Beispiel hier 0 wäre im Keller, dann lösche ich das und gehe 01:10:17.140 --> 01:10:17.860 1 weiter. 01:10:19.700 --> 01:10:23.460 Wenn es nicht der Fall wäre, wenn E ist nicht gleich E, was in dem 01:10:23.460 --> 01:10:28.120 Keller ist, eigentlich hier höre ich auf und Kellerautomat ist 01:10:28.120 --> 01:10:31.300 irgendwo in der Mitte, in der Luft und akzeptiert das Wort halt nicht, 01:10:31.380 --> 01:10:32.200 kommt nie zu Ende. 01:10:34.360 --> 01:10:38.140 Und wenn das das gleiche ist, dann lese ich bis Ende und lösche ich 01:10:38.140 --> 01:10:42.100 immer ein Element nach dem anderen aus dem Keller und dann ändere ich 01:10:42.100 --> 01:10:47.640 meinen Zustand auf den Endzustand und dann akzeptiere ich das Wort. 01:10:49.080 --> 01:10:54.100 Gut, das ist keine Palindrome bis jetzt gewesen, weil ein C dazwischen 01:10:54.100 --> 01:10:54.260 ist. 01:10:54.340 --> 01:11:04.100 Palindrome sind die Worte, die so aussehen, so wie Otto. 01:11:05.460 --> 01:11:08.300 Von hier lesen und von hier lesen, das ist das Gleiche. 01:11:08.620 --> 01:11:11.200 Es ist nichts dazwischen, denke ich. 01:11:15.680 --> 01:11:19.100 Aber was passiert, wenn wir diese C nicht hätten? 01:11:21.120 --> 01:11:23.140 Woher weiß ich, wann ich umkehren muss? 01:11:24.360 --> 01:11:30.140 So, wenn ich so ein Wort hätte, 0, 0, 0, 1, 1, 0, 0, 0. 01:11:30.480 --> 01:11:34.520 Woher soll ich wissen, dass ich hier nicht umkehren muss oder genau 01:11:34.520 --> 01:11:35.860 hier umkehren muss? 01:11:35.860 --> 01:11:37.900 Wie kann ich das programmieren? 01:11:38.140 --> 01:11:40.020 Ich weiß nicht, wie lang das Wort ist. 01:11:40.080 --> 01:11:43.680 Kann auch belebig lang sein, kann 20 Elemente haben. 01:11:43.860 --> 01:11:47.460 Woher soll ich wissen, wie viele Worte, wie viele Alphabeten drin sind 01:11:47.460 --> 01:11:48.640 und wann ich umkehren muss? 01:11:52.140 --> 01:11:57.660 Und das ist dann das Problem, das heißt, Umkehrpunkt zu finden ist 01:11:57.660 --> 01:12:03.100 nicht möglich, mit deterministischen Kellerautomaten zu haben. 01:12:03.100 --> 01:12:07.980 Das ist nicht die Sprache von deterministischen Kellerautomaten, aber 01:12:07.980 --> 01:12:12.080 es kann die Sprache von nicht-deterministischen Kellerautomaten sein. 01:12:12.460 --> 01:12:17.860 Und hier ist die Definition, nicht ein deterministischer Kellerautomat 01:12:17.860 --> 01:12:20.820 ist auch ein Tuple, wie vorhin bei Kellerautomaten. 01:12:22.420 --> 01:12:28.040 Die Komponenten alle sind gleich wie bei deterministischen 01:12:28.040 --> 01:12:30.740 Kellerautomaten, außer Delta. 01:12:31.480 --> 01:12:37.500 Und Delta ist im Prinzip, was wir vorhin hatten, wir hatten diese C 01:12:37.500 --> 01:12:41.660 nicht, diese C-Funktion, aber bei nicht-deterministischen ähnlichen 01:12:41.660 --> 01:12:46.200 Automaten können wir mehrere, so einen Übergang auf mehrere 01:12:46.200 --> 01:12:47.640 Konfigurationen haben. 01:12:48.820 --> 01:12:52.000 Und das sagt uns, dass wir nicht-deterministische Kellerautomaten 01:12:52.000 --> 01:12:52.280 haben. 01:12:54.420 --> 01:12:58.680 Und akzeptiert so ein Kellerautomat Wort, wenn eine 01:12:58.680 --> 01:13:02.440 Konfigurationsfolge gibt, wo ein Zustand kommt und ein Zustand von 01:13:02.440 --> 01:13:03.880 Zustände und nicht von Keller. 01:13:04.840 --> 01:13:07.180 So, hier denke ich, wir haben ein Beispiel. 01:13:07.300 --> 01:13:09.600 Ich zeige erst mal, wie das Beispiel aussieht. 01:13:09.900 --> 01:13:15.180 Bei nicht-deterministischen ähnlichen Automaten gibt es mehrere 01:13:15.180 --> 01:13:17.080 Konfigurationen für einen Übergang. 01:13:17.740 --> 01:13:20.480 Und da sehen Sie hier, was da grün gezeigt ist. 01:13:21.280 --> 01:13:27.520 Da hier bei einem Übergang von einer Konfiguration haben wir dann zwei 01:13:27.520 --> 01:13:31.460 andere Konfigurationen, die in grüner Farbe gezeigt worden sind. 01:13:31.600 --> 01:13:35.040 Und das ist genau das, was wir brauchen, um diesen Umkehrpunkt so 01:13:35.040 --> 01:13:36.040 irgendwann zu finden. 01:13:37.080 --> 01:13:38.340 So, wie funktioniert das? 01:13:39.300 --> 01:13:46.680 Wir wollen Sprache, eine Palindrome, also Kellerautomaten haben, die 01:13:46.680 --> 01:13:47.860 diese Sprache akzeptieren. 01:13:49.260 --> 01:13:50.880 Wir definieren diese Zustände. 01:13:50.880 --> 01:13:56.180 Also erst mal kurz, vielleicht haben Sie eine Frage und sagen, woher 01:13:56.180 --> 01:14:02.560 weiß ich, dass wir von S0 so viele Zustände brauchen, wenn ich den 01:14:02.560 --> 01:14:04.000 Kellerautomaten erzeugen möchte. 01:14:05.020 --> 01:14:10.800 Eigentlich diese Mengen füllen wir aus, wenn wir diese Regelmenge, 01:14:11.080 --> 01:14:15.800 nicht Regelmenge, diese Konfigurationen und diese Übergangfunktionen 01:14:15.800 --> 01:14:16.500 gefunden haben. 01:14:16.500 --> 01:14:16.620 Warum? 01:14:16.960 --> 01:14:22.120 Wenn Sie irgendein Beispiel bekommen, in Klausur oder Übungen, was Sie 01:14:22.120 --> 01:14:26.680 als erstes machen, das ist ein Tipp von mir, Sie machen erst mal diese 01:14:26.680 --> 01:14:35.660 Übergangfunktionen und dann können Sie beliebig mehr Zustände haben. 01:14:36.260 --> 01:14:38.300 Und wenn Sie dann alles gefunden haben und alle Beispiele 01:14:38.300 --> 01:14:41.660 funktionieren, dann schreiben Sie oben, okay, jetzt brauche ich S0 bis 01:14:41.660 --> 01:14:42.180 S3. 01:14:42.800 --> 01:14:45.440 Sonst vorher weiß man nicht, wie viele Zustände wir brauchen. 01:14:46.640 --> 01:14:49.980 So, das ist nur ein Tipp von mir, wie Sie dann das machen, auch bei 01:14:49.980 --> 01:14:50.700 Endzuständen. 01:14:50.780 --> 01:14:53.120 So sehen Sie hier, wir haben zwei Endzustände. 01:14:53.820 --> 01:14:54.780 Woher weiß ich vorher? 01:14:54.880 --> 01:14:55.640 Ich weiß es nicht vorher. 01:14:55.820 --> 01:14:59.480 Ich schreibe diese Übergangfunktionen und danach schaue ich, okay, wo 01:14:59.480 --> 01:15:02.140 habe ich einen Endzustand definiert und wie viele Zustände ich 01:15:02.140 --> 01:15:02.800 überhaupt habe. 01:15:04.920 --> 01:15:08.920 Gut, Kellerautomat hat das gleiche Alphabet, nur mit einem neuen 01:15:08.920 --> 01:15:14.780 Anfangsalphabet extra und sonst ist es das gleiche wie unser 01:15:14.780 --> 01:15:16.880 Eingabealphabet. 01:15:19.690 --> 01:15:24.010 Wir modellieren immer einen möglichen Umkehrpunkt, wenn das 01:15:24.010 --> 01:15:27.230 Eingabezeichen gleich das oberste Kellerzeichen ist. 01:15:27.670 --> 01:15:37.190 Das heißt, wir definieren immer bei allen möglichen Umkehrpunkten, die 01:15:37.190 --> 01:15:37.830 wir haben. 01:15:39.150 --> 01:15:44.050 Für das Wort Auto gibt es immer interessante... 01:15:45.210 --> 01:15:50.310 So, ob ich hier umkehren muss oder hier umkehren muss, weiß ich nicht. 01:15:50.370 --> 01:15:54.050 Aber für alle diese Fälle mache ich dann... 01:15:55.030 --> 01:16:00.350 So, wir haben da mögliche Umkehr mit dieser Konfiguration erstmal in 01:16:00.350 --> 01:16:02.330 den nicht deterministischen Kellerautomaten. 01:16:02.330 --> 01:16:03.530 So, wir definieren das. 01:16:04.010 --> 01:16:04.990 Wie funktioniert das? 01:16:05.090 --> 01:16:11.990 Wir haben Anfangszustand 0, wir haben Eingabealphabet E, K0, wir 01:16:11.990 --> 01:16:13.270 schreiben E in Keller. 01:16:16.830 --> 01:16:22.250 Dann, wir lesen das Wort, so zum Beispiel das Auto, bis zu einem 01:16:22.250 --> 01:16:24.730 bestimmten Punkt, so dann noch ein E kommt hier rein. 01:16:25.970 --> 01:16:30.330 Und dann, wenn das, was wir lesen, das Gleiche ist, was wir in dem 01:16:30.330 --> 01:16:33.750 Keller haben, dann habe ich zwei Optionen. 01:16:34.390 --> 01:16:42.250 Entweder kann ich das löschen und dann runterkommen oder kann ich das 01:16:42.250 --> 01:16:43.590 schreiben und weitergehen. 01:16:45.030 --> 01:16:47.870 Und das ist dieser Nicht-Determinismus, den wir definieren. 01:16:48.290 --> 01:16:51.530 Bei deterministischen Kellerautomaten ist es immer klar, wann was 01:16:51.530 --> 01:16:53.510 passiert ist, geben wir immer vor. 01:16:54.110 --> 01:16:57.830 Aber bei Nicht-Deterministischen, da sagen wir so oder so. 01:16:58.290 --> 01:17:02.470 Und dann müssen wir schauen, wie wir bei Nicht-Deterministischen und 01:17:02.470 --> 01:17:07.430 ähnlichen Automaten, wie das am Ende für uns und für das Beispiel, das 01:17:07.430 --> 01:17:10.550 Wort, die wir lesen wollen, die Worte, die wir lesen wollen, welche 01:17:10.550 --> 01:17:12.770 geeignet ist und wann. 01:17:14.010 --> 01:17:21.450 Und genau so hier an dieser Stelle wird dann das Programm, diese 01:17:21.450 --> 01:17:24.230 Kellerautomaten definiert. 01:17:25.870 --> 01:17:26.650 Gut, 01:17:30.810 --> 01:17:35.550 ja, und offensichtlich gilt bei Nicht-Deterministischen Automaten, sie 01:17:35.550 --> 01:17:38.610 müssen immer am Ende, was passiert ist, am Ende, wenn sie ein Wort 01:17:38.610 --> 01:17:41.130 lesen, müssen sie irgendwann in einen Zustand kommen. 01:17:42.030 --> 01:17:42.510 Irgendwie. 01:17:42.990 --> 01:17:47.210 Und wenn sie es irgendwie zeigen können, dann haben sie die Aufgabe 01:17:47.210 --> 01:17:50.430 eigentlich gelöst und das ist auch hier der Fall. 01:17:51.290 --> 01:17:55.550 Wir kommen zu irgendeinem Endzustand und das ist das, was wir wollen 01:17:55.550 --> 01:17:58.510 und das Wort können wir von Kellerautomaten akzeptieren. 01:17:59.030 --> 01:18:01.530 So, ich werde hier mit der Vorlesung aufhören. 01:18:02.330 --> 01:18:07.490 Vielen Dank für Ihre Aufmerksamkeit und nächste Woche oder Mittwoch, 01:18:07.550 --> 01:18:09.030 Lukas, ist Herr Schmeck Mittwoch da? 01:18:11.750 --> 01:18:14.710 Okay, dann, ich bin auf jeden Fall nicht da. 01:18:16.010 --> 01:18:18.810 Ja, ich glaube, er ist da, wenn er nicht da wäre, dann würde Herr 01:18:18.810 --> 01:18:19.470 König wissen. 01:18:19.930 --> 01:18:23.510 Dann Herr Schmeck wird Mittwoch in Audimax dann die Vorlesung an 01:18:23.510 --> 01:18:25.290 dieser Stelle weiterhalten. 01:18:26.810 --> 01:18:27.250 Danke.