WEBVTT 00:07.030 --> 00:10.540 Gut, dann begrüße ich alle recht herzlich zur dritten Übung von TGI. 00:11.640 --> 00:15.480 Heute werden wir natürlich wieder Übungsblätter besprechen, also das 00:15.480 --> 00:17.280 zweite Übungsblatt. 00:21.550 --> 00:25.980 Was die Idee heute ist, ist, dass wir einmal Minimierung von Automaten 00:25.980 --> 00:29.980 durchsprechen, dann eine Rohde-Relation, aber auch Touring-Maschinen, 00:30.820 --> 00:35.000 erweiterte Touring-Maschinen und wenn die Zeit noch reicht, auch 00:35.000 --> 00:38.560 universelle Touring-Maschinen und Entscheidbarkeit. 00:38.680 --> 00:42.060 Das hängt so ein bisschen davon ab, wie schnell wir heute vorankommen. 00:43.160 --> 00:45.360 Aber erstmal ein bisschen was zum Organisatorischen. 00:45.640 --> 00:48.940 Einmal Tutorium 19 gehalten von Simon Sudrich. 00:49.140 --> 00:55.560 Falls ihr in dem Tutorium drin seid, das wird verlegt am 4.12. 00:55.920 --> 00:57.580 in den Raum 010. 00:57.580 --> 00:59.360 Das ist eine einmalige Verlegung. 01:00.080 --> 01:01.160 Bitte denkt daran, am 4. 01:01.720 --> 01:04.980 Dezember auch in den entsprechenden Raum zu gehen. 01:05.860 --> 01:12.560 Außerdem entfallen die Tutorien 18 und 20 an den Terminen am 27.11. 01:12.820 --> 01:13.700 und am 4.12. 01:14.000 --> 01:15.740 von Tobias Stolzmann. 01:16.920 --> 01:21.840 Da ist die Regelung, das sucht euch einfach ein anderes Tutorium und 01:21.840 --> 01:24.100 setzt euch in ein anderes Tutorium rein. 01:24.100 --> 01:28.220 Die Übungsblätter von euch werden von anderen Tutoren korrigiert. 01:28.380 --> 01:32.140 Also Tobias ist gerade krank und kann deswegen seine Tutorien nicht 01:32.140 --> 01:32.480 halten. 01:33.080 --> 01:38.020 Die Übungsblätter bekommt ihr dann von uns, also sprich kommt dann 01:38.020 --> 01:40.960 einfach zu uns nach so ein bis zwei Wochen. 01:42.020 --> 01:45.100 Wir werden es aber auch nochmal bekannt geben, wann die Übungsblätter 01:45.100 --> 01:46.740 da sind, wann ihr die abholen könnt. 01:46.820 --> 01:49.580 Aber das betrifft nur Tutorium 18 und 20. 01:55.220 --> 01:58.500 Dann würde ich direkt mit dem Inhalt anfangen. 01:58.680 --> 02:00.260 Es geht los mit Aufgabe 1. 02:00.420 --> 02:03.600 Aufgabe 1 sollte auch nochmal so ein bisschen den Stoff wiederholen, 02:03.660 --> 02:05.120 was wir auch schon zuvor gemacht haben. 02:05.220 --> 02:07.420 Da ging es nochmal ein bisschen um endliche Automaten, um 02:07.420 --> 02:08.880 Potenzmengenkonstruktion. 02:09.660 --> 02:12.300 Und der Hauptteil war dann eigentlich die Minimierung von dem 02:12.300 --> 02:12.900 Automaten. 02:14.620 --> 02:16.760 Die erste Aufgabe war relativ einfach. 02:16.860 --> 02:18.940 Das war so eine typische Einstiegsaufgabe. 02:18.940 --> 02:20.820 Natürlich auch gut zum Punkte sammeln. 02:21.460 --> 02:24.640 Man sollte einmal das Alphabet bestimmen und die Start- und 02:24.640 --> 02:25.380 Endzustände. 02:26.040 --> 02:28.760 Das Alphabet ist offensichtlich 0 und 1. 02:29.780 --> 02:32.280 Andere Zeichen werden nicht verwendet. 02:32.920 --> 02:35.680 Also es enthält mindestens die 0 und die 1, das Alphabet. 02:36.340 --> 02:40.060 Dann gibt es den Startzustand Q0, hier eben markiert durch diesen 02:40.060 --> 02:43.780 eingehenden Pfeil, der keinen ausgehenden Zustand hat. 02:43.780 --> 02:50.160 Außerdem haben wir hier die Endzustände F gleich Q5 und Q7, also hier 02:50.160 --> 02:54.520 einmal durch diese Doppelkreise markiert. 02:56.360 --> 02:59.440 Das war die Aufgabe A, also nicht sehr schwierig. 02:59.660 --> 03:03.960 Die Aufgabe B ging dann darum, wie kann ich eigentlich unerreichbare 03:03.960 --> 03:05.380 Zustände finden. 03:06.720 --> 03:08.420 Hat da jemand eine Idee, wie man das macht? 03:15.270 --> 03:17.070 Die Antwort war Tiefensuche. 03:17.830 --> 03:21.550 Was man macht, ist man startet die Tiefensuche von Q0 aus, also von 03:21.550 --> 03:24.430 dem Zustand, der auf alle Fälle erreichbar ist, weil Q0 der 03:24.430 --> 03:25.330 Startzustand ist. 03:25.750 --> 03:29.830 Und was man dann macht, ist durch eine Tiefensuche alle Zustände 03:29.830 --> 03:31.770 abzuklappern, die man erreichen kann. 03:32.110 --> 03:36.530 Und am Ende wirft man eben alle anderen Zustände raus, die nicht 03:36.530 --> 03:37.270 erreichbar sind. 03:37.350 --> 03:39.290 In dem Fall ist es Q6 und Q7. 03:40.150 --> 03:43.470 Also eine relativ einfache Geschichte, wie man das machen kann. 03:45.230 --> 03:47.610 Was ist die Laufzeit der Tiefensuche? 03:48.950 --> 03:50.330 Wie schnell kann man das machen? 04:08.320 --> 04:09.240 Hat jemand eine Idee? 04:14.520 --> 04:16.320 Also in O-Notation angegeben. 04:21.240 --> 04:25.260 Also im Prinzip in linearer Laufzeit, nämlich linear in der Anzahl der 04:25.260 --> 04:29.520 Kanten und in der Anzahl der Knoten, kann ich einmal die Tiefensuche 04:29.520 --> 04:35.700 anwenden und habe dann alle Knoten abgeklappert, die erreichbar sind. 04:38.280 --> 04:43.660 Die nächste Aufgabe war dann, den Automaten zu minimieren. 04:43.800 --> 04:47.000 Und was man dazu erstmal machen muss, ist den Automaten von einem 04:47.000 --> 04:50.260 nicht -deterministischen endlichen Automaten in einen deterministisch 04:50.260 --> 04:51.940 endlichen Automaten umzuwandeln. 04:52.740 --> 04:55.680 Dazu habt ihr die Potenzmengen-Konstruktion kennengelernt. 04:55.680 --> 04:59.560 Möchte vielleicht jemand nochmal wiederholen, was so grob die Idee war 04:59.560 --> 05:01.100 bei der Potenzmengen-Konstruktion? 05:02.420 --> 05:03.760 Ist nicht sehr schwierig. 05:03.940 --> 05:08.960 Im Prinzip was man macht, ist man klappert oder man sucht systematisch 05:08.960 --> 05:13.580 die Zustände, die erreichbar sind von dem Startzustand aus und geht 05:13.580 --> 05:18.060 davon aus, in einem nicht-deterministischen Automaten kann ich mit dem 05:18.060 --> 05:23.520 selben Zeichen in verschiedene Zustände gelangen und in meinem 05:23.520 --> 05:26.560 deterministischen bilde ich das dann ab, indem ich so einen 05:26.560 --> 05:30.380 Metazustand einfüge, der dann so zu interpretieren ist, dass man sagt, 05:30.500 --> 05:35.260 in dem Fall bin ich in einem dieser Zustände, die erreichbar sind von 05:35.260 --> 05:35.660 Q0. 05:36.060 --> 05:39.500 Und so geht man das dann sukzessive für alle Zustände durch, die man 05:39.500 --> 05:41.680 dann noch zusätzlich bekommt. 05:41.680 --> 05:47.620 Also hier am Beispiel, wir starten mit dem Zustand Q0 und was 05:47.620 --> 05:53.040 erreichbar ist, von 0 aus ist der Zustand Q1 und Q2, das sieht man 05:53.040 --> 05:53.320 hier. 05:54.920 --> 05:58.660 Und dann mit der 1 erreiche ich noch den Zustand Q3. 05:59.100 --> 06:04.440 Also zu lesen ist das, mit einer 0 schaffe ich es in einem nicht 06:04.440 --> 06:07.620 -deterministischen Automaten, der gegeben ist, komme ich mit einer 0 06:07.620 --> 06:10.600 von Q0 entweder nach Q1 oder nach Q2. 06:10.600 --> 06:14.120 Also befinde ich mich in meinem deterministischen Automaten jetzt in 06:14.120 --> 06:19.480 so einem Metazustand, der sagt, ich bin entweder in Q1 oder Q2 und für 06:19.480 --> 06:21.980 1 ist es dann eben Q3. 06:23.120 --> 06:26.220 Dadurch kriege ich jetzt neue Zustände in meinem deterministischen 06:26.220 --> 06:30.440 Automaten und die muss ich jetzt auch behandeln und die sind jetzt 06:30.440 --> 06:31.260 wieder erreichbar. 06:31.260 --> 06:34.180 Das heißt, ich schaue mir jetzt Q1, Q2 an. 06:35.500 --> 06:42.400 Von Q1 aus kann ich Q5 erreichen und von Q2 aus kann ich F erreichen 06:42.400 --> 06:43.880 mit der 0. 06:44.520 --> 06:46.940 Das heißt, ich kriege hier Q5, F raus. 06:48.000 --> 06:52.380 Mit der 1 kann ich dasselbe Spiel machen und kriege dann Q3, F raus. 06:53.460 --> 06:54.780 Das müsste stimmen. 06:54.860 --> 07:03.780 Genau von Q2 schaffe ich es nach Q3 und von Q1 mit einer 0 schaffe ich 07:03.780 --> 07:05.800 es nach Q5 und nach F. 07:06.240 --> 07:07.360 Also das passt auch wieder. 07:07.420 --> 07:11.860 Ich kriege wieder zwei neue Zustände, die ich mir einfach hier 07:11.860 --> 07:15.720 aufschreibe und sage, die sind jetzt auch erreichbar und gehe dann 07:15.720 --> 07:18.120 wieder so weiter voran. 07:18.120 --> 07:21.520 Dasselbe mache ich dann für Q3 und kriege dann Q4 und Q3. 07:22.960 --> 07:26.440 Und das ganze Spiel kann ich natürlich jetzt komplett fortsetzen, bis 07:26.440 --> 07:28.760 ich irgendwann keine Zustände mehr hier bekomme. 07:29.500 --> 07:30.420 Keine zusätzlichen. 07:31.160 --> 07:35.540 Im Forum gab es die Frage, ob man jetzt wirklich alle Zustände 07:35.540 --> 07:36.220 anschauen muss. 07:36.400 --> 07:40.180 Also das ganz naive Vorgehen ist, dass man erstmal sich alle möglichen 07:40.180 --> 07:44.000 Kombinationen hier hinschreibt an Zuständen oder Zustandsmengen, die 07:44.000 --> 07:44.360 es gibt. 07:44.360 --> 07:47.220 Was natürlich sehr viele sein können. 07:48.280 --> 07:49.620 Und das muss man eben nicht machen. 07:49.720 --> 07:53.560 Es reicht aus, wenn ich von Q0 ausgehe und hier immer direkt die 07:53.560 --> 07:56.800 Erreichbarkeit, also nur die erreichbaren Zustände anschaue. 07:57.160 --> 08:01.400 Und dadurch werden diese Tabellen deutlich kleiner, als man erwarten 08:01.400 --> 08:01.720 würde. 08:02.980 --> 08:06.140 Also es kann natürlich passieren, das haben wir in der ersten Übung 08:06.140 --> 08:10.800 gesehen, dass man tatsächlich exponentiell viele Zustände bekommt, 08:10.900 --> 08:14.040 indem man nicht-deterministischen Automaten in den deterministischen 08:14.040 --> 08:14.600 umwandelt. 08:14.860 --> 08:18.440 Das kann passieren, aber im Normalfall, wenn wir eine Aufgabe euch 08:18.440 --> 08:19.580 geben, wird das nicht so sein. 08:24.050 --> 08:29.370 Und was man dann noch machen kann, ist natürlich diese Zustandstabelle 08:29.370 --> 08:30.690 auch einfach mal aufzuzeichnen. 08:31.010 --> 08:34.950 Und was wir dann hier bekommen, ist diesen etwas großen Automaten und 08:34.950 --> 08:37.050 die Frage ist, ist der minimal oder nicht. 08:37.050 --> 08:41.670 Und der ist nicht minimal und die Idee war dann auf dem Übungsblatt, 08:41.850 --> 08:44.050 dass ihr den auch minimieren sollt. 08:48.360 --> 08:51.860 Die Idee beim Minimieren ist im Prinzip, dass man sich Zustände 08:51.860 --> 08:55.440 anschaut, die ein selbes Akzeptanzverhalten haben. 08:55.900 --> 09:02.640 Also die Idee ist, dass man versucht herauszufinden, welche Zustände 09:02.640 --> 09:03.600 äquivalent sind. 09:03.600 --> 09:08.880 Und äquivalent nennen wir zwei Zustände, also P und Q, wenn für alle 09:08.880 --> 09:13.320 Wörter W gilt, dass wenn wir dieses Wort W abarbeiten von P oder von Q 09:13.320 --> 09:18.860 aus, dass wir entweder für beide Abarbeitungen in einem Endzustand 09:18.860 --> 09:22.360 landen oder für beide Abarbeitungen eben nicht in einem Endzustand 09:22.360 --> 09:22.780 landen. 09:23.260 --> 09:26.640 Und dann nennen wir zwei Zustände eben äquivalent. 09:27.510 --> 09:30.960 Und dementsprechend kriegen wir natürlich, weil das eine 09:30.960 --> 09:33.880 Äquivalenzrelation ist, Äquivalenzklassen. 09:35.420 --> 09:38.500 Diese ganze Relation ist eine Äquivalenzrelation. 09:38.820 --> 09:43.180 Wir kriegen Äquivalenzklassen und später können wir zeigen, okay, 09:43.560 --> 09:47.480 diese Äquivalenzklassen geben uns einen Automaten, der dieselbe 09:47.480 --> 09:50.240 Sprache akzeptiert wie der ursprüngliche Automat. 09:50.240 --> 09:54.520 Und wir können sogar zeigen, dass wenn wir diese Äquivalenzklassen als 09:54.520 --> 09:58.400 Zustände verwenden, dass wir einen minimalen Automaten bekommen. 10:02.040 --> 10:04.200 So, als kleine Zwischenfrage. 10:04.620 --> 10:07.260 Hier ist ein ganz einfacher Automat gegeben. 10:08.080 --> 10:09.640 Welche Zustände sind äquivalent? 10:12.780 --> 10:14.300 Q2 und Q4, genau. 10:14.980 --> 10:18.080 Warum sind Q1 und Q3 nicht äquivalent? 10:19.180 --> 10:25.920 Ja genau, also es gibt einen Zeugen, der uns sagt, dass Q1 und Q3 10:25.920 --> 10:27.580 nicht äquivalent sein können. 10:28.080 --> 10:30.960 Also zum Beispiel kann ich hier den Zeugen 1,0 nehmen. 10:31.880 --> 10:36.080 Mit dem Wort 1,0 komme ich von Q1 in den Endzustand. 10:36.540 --> 10:41.260 Aber von Q3 aus bleibe ich einmal, wenn ich die 1 abarbeite, in Q3 und 10:41.260 --> 10:44.300 gehe dann noch zu Q4 rüber und bin nicht in dem Endzustand. 10:44.300 --> 10:48.480 Und dementsprechend sind diese zwei Zustände nicht äquivalent. 10:48.560 --> 10:50.400 Wir haben dafür jetzt einen Zeugen gefunden. 10:55.340 --> 10:58.780 Basierend auf diesen Äquivalenzklassen können wir jetzt einen 10:58.780 --> 11:01.300 Äquivalenzklassenautomaten definieren. 11:03.380 --> 11:07.900 Die Idee ist, dass man im Prinzip diese Äquivalenzklassen als Zustände 11:07.900 --> 11:08.520 betrachtet. 11:08.520 --> 11:13.520 Das Alphabet belassen wir einfach so, wie es ist. 11:14.700 --> 11:17.840 Und außerdem haben wir jetzt für die Zustände, für die Übergänge, dass 11:17.840 --> 11:21.240 wir immer den Übergang nehmen für eine Äquivalenzklasse zu einer 11:21.240 --> 11:25.780 anderen Äquivalenzklasse, also zu den entsprechenden Zuständen, indem 11:25.780 --> 11:28.240 wir einfach die Zustände der Repräsentanten nehmen. 11:28.640 --> 11:33.160 Also im Prinzip hier so eine Äquivalenzklasse, wenn P, dann steht 11:33.160 --> 11:36.880 dieses P für einen Repräsentanten aus dieser Äquivalenzklasse. 11:39.760 --> 11:44.160 Und was wir dann machen, ist natürlich noch den Startzustand zu wählen 11:44.160 --> 11:46.760 und dann nehmen wir die Äquivalenzklasse, wo S drin ist. 11:47.600 --> 11:51.220 Und außerdem nehmen wir für die Endzustände all die Zustände oder 11:51.220 --> 11:57.340 Äquivalenzklassen, für die ebenfalls die Endzustände enthalten sind. 11:58.320 --> 12:00.600 Und dementsprechend kriegt man dann so einen 12:00.600 --> 12:01.980 Äquivalenzklassenautomaten. 12:01.980 --> 12:04.980 Und in der Vorlesung habt ihr eben gelernt, dass so ein 12:04.980 --> 12:10.040 Äquivalenzklassenautomat dieselbe Sprache akzeptiert, wie der 12:10.040 --> 12:11.720 ursprünglich gegebene Automat. 12:12.640 --> 12:15.860 Und außerdem ist dieser Äquivalenzklassenautomat auch noch minimal. 12:16.420 --> 12:18.900 Und das ist im Prinzip das Ziel, das wir erreichen wollen. 12:22.180 --> 12:26.900 Zwei Minuten braucht man vielleicht nicht unbedingt zu sehen, was der 12:26.900 --> 12:28.800 Äquivalenzklassenautomat hiervon ist. 12:42.610 --> 12:45.470 Also du sagst Q1, Q3, neuer Zustand? 12:53.960 --> 12:57.580 Ah ok, genau und dieser neue Zustand ist ein Zustand. 12:59.660 --> 13:05.720 Das ist die Idee, was wir machen ist, wir legen im Prinzip Q2 und Q4 13:05.720 --> 13:06.120 zusammen. 13:06.340 --> 13:09.720 Wir sehen, dass die äquivalent sind oder das sehen wir jetzt durch 13:09.720 --> 13:13.420 draufschauen und wir sehen, die anderen sind nicht äquivalent. 13:13.420 --> 13:16.640 Was wir jetzt machen ist, wir legen diese zwei Zustände zusammen zu 13:16.640 --> 13:17.520 einem Zustand. 13:17.920 --> 13:22.940 Der Repräsentant ist Q2 und die restlichen Zustände bleiben gleich und 13:22.940 --> 13:24.660 dann haben wir das, der minimal ist. 13:25.560 --> 13:28.520 Hier müsste eigentlich auch noch eine eckige Klammer um das F 13:28.520 --> 13:29.020 rumstehen. 13:29.640 --> 13:32.060 Aber das ist im Prinzip der Äquivalenzklassenautomat. 13:33.240 --> 13:36.400 Die Frage ist, kann man das auch irgendwie systematisch machen und das 13:36.400 --> 13:39.300 war im Prinzip das, was auf dem Übungsblatt gefragt war. 13:40.240 --> 13:44.480 Nämlich, was man machen kann ist, das Ganze systematisch über Zeugen 13:44.480 --> 13:44.940 zu machen. 13:45.480 --> 13:48.840 Und diese Zeugen sagen einem immer, dass zwei Zustände nicht 13:48.840 --> 13:50.040 äquivalent sind. 13:50.200 --> 13:54.860 Ein Zeuge ist einfach ein Wort aus unserem Alphabet und dieser Zeuge 13:54.860 --> 13:59.640 zeigt uns, dass diese zwei Zustände nicht dasselbe Akzeptanzverhalten 13:59.640 --> 13:59.920 haben. 14:02.200 --> 14:05.740 Und die Idee ist also, was man machen kann bei diesem Verfahren ist, 14:05.840 --> 14:10.840 dass man systematisch die Zeugen durchprobiert, die es gibt. 14:11.080 --> 14:14.080 Und was man macht, man fängt erst an mit dem Wort der Länge 0, 14:14.220 --> 14:15.000 probiert es damit. 14:15.340 --> 14:19.620 Dann mit den Worten der Länge 1, dann mit den Worten der Länge 2 und 14:19.620 --> 14:20.060 so weiter. 14:21.100 --> 14:25.920 Bis man für eine bestimmte Wortlänge keine Zeugen findet und dann kann 14:25.920 --> 14:26.580 man abbrechen. 14:26.580 --> 14:29.900 Und das ist die Idee, wie man im Prinzip diese Minimierung macht. 14:30.480 --> 14:35.300 Das ist der Zustandsautomat aus der Aufgabe zuvor. 14:35.380 --> 14:38.580 Was ich gemacht habe ist, ich habe hier noch diese Namen geändert. 14:38.780 --> 14:43.720 Also davor waren das solche Metazustände mit Klammern. 14:43.800 --> 14:45.380 Das war ein bisschen unschön dann zum Lesen. 14:45.720 --> 14:49.000 Deswegen habe ich sie hier durch S0 bis S9 ersetzt. 14:49.700 --> 14:52.680 Und was man jetzt macht ist folgendes. 14:53.740 --> 15:01.020 Man fragt sich jetzt, wenn ich mir das Wort Epsilon anschaue, welche 15:01.020 --> 15:04.240 Zustände werden dadurch aufgetrennt. 15:04.380 --> 15:09.700 Also sprich, von welchen Zuständen aus komme ich dadurch in den 15:09.700 --> 15:13.580 Endzustand und von welchen Zuständen aus komme ich in keinen 15:13.580 --> 15:14.300 Endzustand. 15:14.300 --> 15:17.040 Und bei Epsilon ist die Antwort was? 15:28.580 --> 15:28.760 Hier. 15:31.640 --> 15:34.460 Genau, also da wir einen deterministischen Automaten haben und wir 15:34.460 --> 15:37.660 führen die Minimierung immer auf deterministischen Automaten aus, ist 15:37.660 --> 15:41.540 es immer so, dass Epsilon immer die Endzustände von den Nicht 15:41.540 --> 15:42.720 -Endzuständen trennt. 15:43.260 --> 15:46.580 Weil das das Wort der Länge 0 ist, also wir gehen keinen echten 15:46.580 --> 15:48.480 Übergang hier entlang. 15:49.120 --> 15:54.720 Das heißt, S3 und S9 sind die Endzustände, also im Prinzip über unser 15:54.720 --> 15:58.080 Wort erreichbar, hier orange markiert. 15:58.580 --> 16:03.580 Und die restlichen Zustände führen nicht in den Endzustand, wenn wir 16:03.580 --> 16:06.180 hier dieses entsprechende Wort anschauen, blau markiert. 16:08.880 --> 16:13.380 Dann die Frage für das nächste Wort, das wir anschauen, ist 0. 16:14.180 --> 16:16.420 Trennt das Zustände auf oder nicht? 16:17.600 --> 16:25.100 Ja genau, S8 geht in den Endzustand, dann hier die S6 und auch die S4, 16:26.160 --> 16:27.740 außerdem noch die S2. 16:30.660 --> 16:35.100 Das heißt, die Zustände führen alle irgendwie in den Endzustand, auch 16:35.100 --> 16:40.540 S9 führt wieder selber in den Endzustand, weil ich hier diese Schleife 16:40.540 --> 16:41.460 habe, S3 auch. 16:41.460 --> 16:46.400 Allerdings heißt das dementsprechend, dass die nicht aufgetrennt 16:46.400 --> 16:46.560 werden. 16:46.680 --> 16:50.740 Also die haben immer noch dasselbe Akzeptanzverhalten und nur hier 16:50.740 --> 16:53.500 diese Zustände werden aufgetrennt. 16:56.960 --> 17:00.420 Die nächste Frage ist natürlich die 1. 17:01.020 --> 17:02.280 Die 1 trennt nichts. 17:02.280 --> 17:07.400 Hier entsprechend sieht man, dass die alle in Nicht-Endzustände 17:07.400 --> 17:07.760 führen. 17:07.960 --> 17:11.980 Diese Zustände, die jetzt blau markiert sind und orange oder gelblich, 17:12.340 --> 17:13.780 führen in den Endzustand. 17:15.720 --> 17:18.200 Was ist das nächste Wort, das wir anschauen? 17:29.720 --> 17:34.300 Als nächstes müssen wir 00 anschauen oder zumindest Wort der Länge 2, 17:34.500 --> 17:35.580 so funktioniert das Verfahren. 17:35.580 --> 17:40.740 Wir schauen 00 an und 00 trennt auch nichts, weil 00 führt für alle 17:40.740 --> 17:42.420 Zustände in den Endzustände. 17:43.480 --> 17:46.460 Das heißt, 00 kann auch kein Zeuge sein. 17:47.880 --> 17:54.940 01 kann auch kein Zeuge sein, weil hier entsprechend wieder die 17:54.940 --> 18:00.260 Zustände, die wir eh hier schon aufgetrennt haben, auch aufgetrennt 18:00.260 --> 18:04.040 sind, aber keine zusätzlichen Zustände aufgetrennt oder Zustandsmengen 18:04.040 --> 18:04.860 aufgetrennt werden. 18:08.140 --> 18:10.820 Hier für 10 ist es dasselbe Spiel. 18:11.620 --> 18:17.680 Mit 10 komme ich zum Beispiel von S8 in S5 und dann nach S6. 18:17.820 --> 18:21.720 Also ich bleibe in einem Nicht-Endzustand und so kann ich dieses Spiel 18:21.720 --> 18:24.360 für alle Zustände durchgehen, die nicht Endzustände sind. 18:24.800 --> 18:27.740 Und die Endzustände selber sind aber so gewählt, dass man da nicht 18:27.740 --> 18:28.400 mehr rauskommt. 18:28.620 --> 18:30.280 Also passiert da auch nichts. 18:33.180 --> 18:38.640 Und dann 01 trennt auch nichts, da ist im Prinzip dasselbe Spiel. 18:39.600 --> 18:43.680 Von S8 komme ich nach S5 und dann bleibe ich in S5 und so kann ich das 18:43.680 --> 18:47.260 für jeden Zustand durchmachen, der kein Endzustand ist und alle 18:47.260 --> 18:52.420 Endzustände bleiben natürlich, wenn ich von da aus starte, bleibe ich 18:52.420 --> 18:53.640 wieder in den Endzuständen. 18:54.680 --> 18:56.740 Also nicht so schwierig in dem Fall. 18:57.440 --> 18:59.000 Was machen wir als nächstes? 19:19.330 --> 19:21.750 Keiner eine Idee oder ist es zu einfach? 19:24.230 --> 19:25.850 Man macht nichts mehr. 19:26.670 --> 19:30.830 Wir haben jetzt alle Worte der Länge 2 durchgearbeitet und es ist 19:30.830 --> 19:31.730 nichts mehr passiert. 19:31.870 --> 19:33.770 Deswegen können wir das Verfahren abbrechen. 19:34.290 --> 19:37.390 In der Vorlesung wurde dann auch die Korrektheit von dem Verfahren 19:37.390 --> 19:37.890 gezeigt. 19:37.890 --> 19:40.230 Damit haben wir es dann geschafft. 19:40.370 --> 19:45.570 Und was wir dann erhalten, sind drei Äquivalenzklassen. 19:45.730 --> 19:47.810 Diese hier, diese hier und diese hier. 19:50.730 --> 19:55.730 Und dann kriegen wir, wenn wir daraus den Äquivalenzklassenautomaten 19:55.730 --> 19:58.170 formen, diesen Automaten. 19:58.250 --> 20:02.870 Im Prinzip haben wir die Äquivalenzklasse S0 als Startzustand, die 20:02.870 --> 20:08.470 Äquivalenzklasse mit Repräsentant S2 und dann noch diese 20:08.470 --> 20:10.150 Äquivalenzklasse mit S9. 20:10.750 --> 20:18.730 Und dann ist dieser Automat deutlich einfacher geworden und akzeptiert 20:18.730 --> 20:24.690 alle Worte, die mindestens zwei Nullen enthalten, wenn ich es richtig 20:24.690 --> 20:25.410 sehe. 20:28.730 --> 20:30.370 Ja, ist da eine Frage? 20:35.310 --> 20:40.050 Also im Prinzip, wir haben hier diese drei Klassen und ich gehe noch 20:40.050 --> 20:44.030 einmal ganz kurz zurück zum Äquivalenzklassenautomaten. 20:44.570 --> 20:48.950 Der hat gesagt, wir nehmen von jeder Äquivalenzklasse einen 20:48.950 --> 20:50.030 Repräsentanten her. 20:50.030 --> 20:56.490 Und nehmen diese Äquivalenzklasse als Zustand. 20:58.430 --> 21:04.030 Und dann nehmen wir als Übergänge immer die Übergänge der 21:04.030 --> 21:07.830 Repräsentanten, die wir gewählt haben, um in den nächsten Zustand zu 21:07.830 --> 21:08.190 kommen. 21:08.590 --> 21:11.510 Und dann muss man eben noch den Startzustand wählen, das ist im 21:11.510 --> 21:14.310 Prinzip die Äquivalenzklasse, die den Startzustand enthält. 21:14.690 --> 21:18.490 Und die Endzustände sind die Äquivalenzklassen, die Endzustände 21:18.490 --> 21:18.930 enthalten. 21:18.930 --> 21:27.770 Wenn wir uns das Ganze nochmal anschauen, dann ist es so, dass S0 ist 21:27.770 --> 21:35.390 hier unser Startzustand, das heißt die Äquivalenzklasse hier wird 21:35.390 --> 21:37.790 unser Startzustand in unserem neuen Automaten. 21:39.210 --> 21:43.610 Von S0 aus komme ich mit der 1 nach S1. 21:44.070 --> 21:46.090 S1 ist aber in derselben Klasse drin. 21:46.090 --> 21:48.250 Das heißt, ich kriege hier eine Schleife rein. 21:49.070 --> 21:52.450 Von S0 aus komme ich mit der 0 nach S4. 21:53.250 --> 21:56.330 Und S4 ist aber in der zweiten Äquivalenzklasse drin. 21:56.410 --> 21:59.710 Das heißt, ich komme jetzt hier zu dieser zweiten Äquivalenzklasse und 21:59.710 --> 22:00.090 so weiter. 22:00.810 --> 22:01.950 Ist das klar geworden? 22:06.840 --> 22:09.900 Genau, und dann haben wir diesen Automaten und wir wissen, dass der 22:09.900 --> 22:11.300 tatsächlich minimal ist. 22:12.300 --> 22:15.840 Es gibt keinen kleinen Automaten, der dieselbe Sprache akzeptiert. 22:17.060 --> 22:20.520 Die zweite Aufgabe war dann auf dem Übungsblatt, dass man zeigen 22:20.520 --> 22:23.260 sollte, dass der Automat minimal ist. 22:23.620 --> 22:24.380 Wie geht man vor? 22:24.900 --> 22:25.420 Nicht schwierig. 22:41.280 --> 22:44.160 Ja, das reicht noch nicht aus. 22:44.940 --> 22:47.040 Ah ok, jetzt weiß ich, wie du es meinst. 22:47.100 --> 22:48.400 Also du versuchst... 22:49.400 --> 22:53.020 Ja genau, also was du machst, ist auch wieder systematisch 22:53.020 --> 22:56.880 durchzuprobieren, ob es äquivalente Zustände gibt und dadurch, ob ich 22:56.880 --> 22:59.120 ihn minimieren kann, also noch kleiner machen kann. 23:00.420 --> 23:04.220 Genau, das ist im Prinzip die Idee und was man macht, ist, man wendet 23:04.220 --> 23:05.600 einfach nochmal das Verfahren an. 23:06.080 --> 23:09.440 Das wir bereits gesehen haben, das mache ich jetzt so ein bisschen 23:09.440 --> 23:12.940 schneller durch, weil das kennt ihr auch schon von dem Automaten 23:12.940 --> 23:13.340 zuvor. 23:13.720 --> 23:17.460 Was man macht, man fängt an und sagt, naja, am Anfang gehe ich davon 23:17.460 --> 23:19.460 aus, dass alle Zustände äquivalent sind. 23:20.280 --> 23:23.780 Und dann schaue ich mir die einzelnen Zeugen an und Epsilon trennt 23:23.780 --> 23:26.660 natürlich wieder die Endzustände von den restlichen Zuständen. 23:27.760 --> 23:31.520 Dann schaue ich mir das nächste Wort an, das ist die Null. 23:32.200 --> 23:38.980 Die Null trennt Q3, Q3 geht nach Q4, von den restlichen Zuständen, Q1 23:38.980 --> 23:39.640 und Q2. 23:40.500 --> 23:46.760 Dementsprechend trennt jetzt die Null Q1, Q2, Q3 in die Mengen auf Q1, 23:46.860 --> 23:47.920 Q2 und Q3. 23:49.180 --> 23:52.480 Und dann schaue ich mir die Eins an, die Eins macht nichts. 23:53.360 --> 23:58.780 Ich bleibe hier in den Nicht-Endzuständen, mit den Nicht-Endzuständen. 23:59.480 --> 24:04.720 Null Eins trennt wieder nichts, zum Beispiel Q3 geht in den Endzustand 24:04.720 --> 24:07.400 zuerst, aber weil ich noch eine Eins habe, die ich abarbeiten muss, 24:07.800 --> 24:10.540 geht es dann weiter in Q1 zurück. 24:10.540 --> 24:13.320 Das heißt, so kann ich weitermachen. 24:14.780 --> 24:19.200 Und dann habe ich hier im Prinzip die Eins Null, die trennt jetzt Q1 24:19.200 --> 24:19.960 und Q2. 24:21.560 --> 24:26.760 Mit der Eins bleibe ich in Q1, dann nach Q2 und von Q2 gehe ich nach 24:26.760 --> 24:30.080 Q3 und dann in Q4. 24:30.800 --> 24:34.100 Und dann habe ich jetzt hier im Prinzip diese vier Mengen, die jeweils 24:34.100 --> 24:37.100 nur einen Zustand enthalten und jetzt muss ich natürlich auch nicht 24:37.100 --> 24:40.240 mehr weitermachen, weil ich nichts mehr auftrennen kann und ich habe 24:40.240 --> 24:41.240 es im Prinzip gezeigt. 24:41.540 --> 24:44.100 Also hier kann ich das Verfahren früher abbrechen. 24:47.730 --> 24:51.670 Soviel zur Minimierung von endlichen Automaten. 24:51.770 --> 24:52.670 Gibt es Fragen dazu? 24:58.400 --> 25:04.060 Dann geht es weiter zur Nerode-Relation, die eine relativ interessante 25:04.060 --> 25:08.000 Relation auf Sprachen ist oder eine Relation zwischen zwei Wörtern in 25:08.000 --> 25:12.480 Sprachen ist und uns hilft, endliche Automaten oder reguläre Sprachen 25:12.480 --> 25:18.600 besser gesagt nochmal anders zu sehen und zum Beispiel auch zu 25:18.600 --> 25:21.520 beweisen, dass eine Sprache nicht regulär ist. 25:21.840 --> 25:25.920 Dafür ist die Nerode-Relation sehr gut oder um zu beweisen, dass eine 25:25.920 --> 25:27.900 Sprache regulär ist, können wir es auch verwenden. 25:28.160 --> 25:30.200 Als Erinnerung das Pumping Lemma zum Beispiel. 25:30.360 --> 25:33.300 Damit konnten wir nur zeigen, dass eine Sprache nicht regulär ist. 25:33.300 --> 25:36.400 Mit der Nerode-Relation können wir zeigen, dass eine Sprache auch 25:36.400 --> 25:37.000 regulär ist. 25:37.620 --> 25:40.860 Also Nicht-Regularität und Regularität können wir beweisen. 25:42.660 --> 25:46.060 Dazu haben wir uns rechtsinvariante Relationen angeschaut. 25:46.420 --> 25:48.300 Kann jemand wiederholen, was das war? 25:49.160 --> 25:54.660 Eine rechtsinvariante Relation ist eine Äquivalenzrelation über Sigma 25:54.660 --> 26:03.280 -Stern und man nennt sie eben rechtsinvariant, wenn für alle Wörter 26:03.280 --> 26:11.800 aus Sigma-Stern gilt, dass wenn diese zwei Wörter x und y in dieser 26:11.800 --> 26:16.460 Relation stehen, dann müssen auch xz und yz für alle weiteren Wörter 26:16.460 --> 26:18.840 in derselben Relation stehen. 26:20.180 --> 26:24.580 Sprich, ich darf beliebige Wörter dranhängen an diese zwei Wörter x 26:24.580 --> 26:30.780 und y und sie bleiben immer noch in derselben Relation, die neu 26:30.780 --> 26:31.660 entstehenden Wörter. 26:32.580 --> 26:36.480 Also es macht nichts aus im Prinzip, was für Wörter ich noch an x und 26:36.480 --> 26:37.620 y hänge. 26:37.880 --> 26:42.580 Und das ist nachher wichtig bei der Nerode-Relation, die uns im 26:42.580 --> 26:48.040 Prinzip so ein Akzeptanzverhalten, wie bei Automaten gibt, nur eben, 26:48.160 --> 26:50.580 dass wir das ein bisschen verallgemeinern, dieses Konzept. 26:52.160 --> 26:57.800 Eine Relation gibt uns eben auch Äquivalenzklassen, weil das im 26:57.800 --> 27:01.440 Prinzip eine Äquivalenzrelation ist, so eine rechtsinvariante. 27:02.200 --> 27:07.080 Und wenn wir eine endliche Anzahl haben an Äquivalenzklassen, dann 27:07.080 --> 27:10.780 sagen wir, dass der Index von dieser Relation endlich ist und 27:10.780 --> 27:13.200 ansonsten eben nicht endlich. 27:14.860 --> 27:18.800 Und dann kommen wir zu der Nerode-Relation, die wie folgt definiert 27:18.800 --> 27:24.300 war, dass wir uns eine beliebige Sprache anschauen von Sigma Stern und 27:24.300 --> 27:27.240 die Nerode-Relation arbeitet dann auf dieser Sprache. 27:27.700 --> 27:31.240 Und was wir machen ist, wir schauen uns zwei Wörter x und y an und 27:31.240 --> 27:37.300 sagen, dass diese zwei Wörter in dieser Nerode-Relation in Beziehung 27:37.300 --> 27:47.960 stehen, genau dann, wenn für alle Wörter aus Sigma Stern gilt, xz ist 27:47.960 --> 27:51.760 in der Sprache genau dann, wenn yz in der Sprache ist. 27:53.260 --> 27:54.800 Wie kann man das genauer verstehen? 27:54.920 --> 27:56.920 Nehmen wir nochmal an, die Sprache ist regulär. 27:56.920 --> 27:59.900 Also die Sprache muss nicht unbedingt nach dieser Definition regulär 27:59.900 --> 28:01.920 sein, aber nehmen wir mal an, die ist regulär. 28:02.780 --> 28:06.980 Und nehmen wir an, wir haben zwei Wörter aus dieser Sprache oder aus 28:06.980 --> 28:11.960 Sigma Stern besser gesagt und diese zwei Wörter stehen in dieser 28:11.960 --> 28:13.860 Relation bezüglich der Sprache L. 28:14.700 --> 28:18.600 Was wir wissen ist, dass es dann deterministischen Automaten gibt, der 28:18.600 --> 28:21.640 nicht unbedingt minimal ist, der diese Sprache akzeptiert. 28:22.620 --> 28:25.960 Und wenn wir uns überlegen, was passiert, wenn wir x abarbeiten, 28:26.420 --> 28:27.680 kommen wir in den Zustand p. 28:28.020 --> 28:30.820 Und wenn wir y abarbeiten, kommen wir in den Zustand q. 28:32.700 --> 28:35.640 Und was wir jetzt wissen, dadurch, dass die in der Relation hier in 28:35.640 --> 28:39.380 der Nerode-Relation bezüglich dieser Sprache stehen, ist es egal, 28:39.500 --> 28:40.700 welches Wort ich dran hänge. 28:41.080 --> 28:45.180 Wenn ich hier zum Beispiel das Wort z dran hänge an x, dann komme ich 28:45.180 --> 28:50.200 in den Endzustand und dann komme ich aber auch unten hier mit y, z 28:50.200 --> 28:51.500 auch in den Endzustand. 28:51.900 --> 28:57.780 Wenn z' dafür zu führt, dass x, z' nicht in den Endzustand führt, dann 28:57.780 --> 29:01.120 eben auch y, z' führt nicht in den Endzustand. 29:01.940 --> 29:08.400 Was im Prinzip damit gleichzusetzen ist, dass p und q Äquivalent sind. 29:08.400 --> 29:13.360 Sprich, die Nerode-Relation schafft uns wieder eine Beziehung zwischen 29:13.360 --> 29:15.720 endlichen Automaten und Sprachen. 29:16.140 --> 29:20.420 Allerdings mit diesem Unterschied, dass wir hier auch andere Sprachen 29:20.420 --> 29:23.800 anschauen können, nämlich nicht reguläre Sprachen. 29:24.380 --> 29:27.260 Und da gibt es dann eben einen sehr netten Zusammenhang und das ist 29:27.260 --> 29:28.240 der Satz von Nerode. 29:28.240 --> 29:35.220 Er sagt, dass wenn so eine Sprache regulär ist, dann ist der Nerode 29:35.220 --> 29:40.380 -Index, also die Anzahl der Äquivalenzklassen endlich und die 29:40.380 --> 29:41.320 Umkehrung gilt auch. 29:41.380 --> 29:44.300 Wenn die Anzahl der Äquivalenzklassen dieser Relation endlich ist, 29:44.800 --> 29:46.740 dann ist die Sprache auch regulär. 29:46.920 --> 29:49.380 Also es gibt einen deterministischen endlichen Automaten. 29:49.380 --> 29:56.080 Und dann sagt noch hier im Prinzip diese zweite Aussage, dann können 29:56.080 --> 30:00.380 wir L im Prinzip zusammensetzen aus Äquivalenzklassen von der 30:00.380 --> 30:04.520 rechtsinvarianten Äquivalenzrelation mit endlichem Index. 30:05.220 --> 30:09.720 Und das ist ein relativ starker Satz, den man sehr gut verwenden kann, 30:10.120 --> 30:13.860 zum Beispiel zu zeigen, dass eine Sprache regulär ist, aber auch um zu 30:13.860 --> 30:15.820 zeigen, dass eine Sprache nicht regulär ist. 30:16.780 --> 30:19.440 Und das solltet ihr dann auch auf dem Übungsblatt machen. 30:23.120 --> 30:27.340 Die Aufgabe hieß dann, dass man für eine gegebene Sprache jeweils die 30:27.340 --> 30:32.760 Äquivalenzklassen angeben sollte bezüglich der Nerode-Relation und 30:32.760 --> 30:38.400 dann sollte man noch den minimalen Automaten angeben. 30:39.840 --> 30:44.320 Die erste Sprache war die Sprache, die alle Wörter über 0 und 1 30:44.320 --> 30:50.440 enthält, die nur eine gerade Anzahl an Einsen enthalten, die Wörter. 30:51.220 --> 30:57.000 Und die Frage war, was sind die Äquivalenzklassen bezüglich der Nerode 30:57.000 --> 30:57.500 -Relation? 30:59.020 --> 31:01.460 Ja genau, das sind die zwei Äquivalenzklassen. 31:01.780 --> 31:03.000 Ich wiederhole es einfach nochmal. 31:04.420 --> 31:10.160 Die erste Äquivalenzklasse sagt, alle Wörter, die im Prinzip eine 31:10.160 --> 31:13.560 gerade Anzahl an Einsen enthalten und alle Wörter. 31:14.060 --> 31:18.720 Die zweite Äquivalenzklasse ist dann die, die alle Wörter enthält, die 31:18.720 --> 31:20.780 eine ungerade Anzahl an Einsen enthalten. 31:21.610 --> 31:25.220 Und der minimale Automat dazu ist nicht sehr schwierig. 31:25.980 --> 31:28.080 Besteht natürlich aus zwei Zuständen. 31:28.200 --> 31:32.720 Wir haben zwei Äquivalenzklassen und offensichtlich akzeptiert er 31:32.720 --> 31:34.360 genau eben diese Wörter. 31:36.020 --> 31:37.840 Ich glaube nicht so schwierig zu sehen. 31:38.020 --> 31:41.240 Ich habe hier als Darzustand auch den Endzustand. 31:41.700 --> 31:43.280 Ich kann beliebig viele Nullen machen. 31:43.620 --> 31:47.780 Sobald ich eine Eins habe, bin ich ungerade in der Anzahl Einsen. 31:47.780 --> 31:50.700 Das heißt, es dürfen noch zwei Nullen kommen, aber ich darf nicht 31:50.700 --> 31:51.200 enden. 31:51.640 --> 31:53.880 Aber irgendwann kommt vielleicht wieder eine Eins und dann komme ich 31:53.880 --> 31:56.460 wieder zurück in Q0 als Endzustand. 32:00.110 --> 32:03.350 Hier bei der Sprache war es ein bisschen schwieriger. 32:04.490 --> 32:05.830 Was war da die Antwort? 32:26.160 --> 32:29.980 Nein, also was du machen kannst, ist zu sagen, was zum Beispiel nicht 32:29.980 --> 32:34.560 in den Worten enthalten ist und wie die Worte einfach aufgebaut sein 32:34.560 --> 32:34.780 müssen. 32:48.040 --> 32:51.200 Ja genau, das sind im Prinzip die Äquivalenzklassen. 32:52.100 --> 32:53.500 Hier nochmal zur Wiederholung. 32:55.760 --> 32:58.940 Fangen wir erstmal mit der einfachsten Äquivalenzklasse an, das ist 32:58.940 --> 33:01.580 die mit dem Repräsentanten ABC. 33:02.800 --> 33:09.000 B enthält im Prinzip dieses Wort ABC, also dieses nicht gewollte Wort 33:09.000 --> 33:11.140 oder dieses Teilwort, das nicht enthalten sein darf. 33:11.140 --> 33:15.080 Und dann haben wir noch hier im Prinzip diese drei Äquivalenzklassen, 33:16.140 --> 33:19.860 die es jeweils sagen, dass ABC nicht in den Worten enthalten ist. 33:20.240 --> 33:23.580 Und dann unterscheiden sie sich darin, wie diese Worte enden. 33:24.060 --> 33:29.260 In der ersten Äquivalenzklasse endet das Wort weder mit A noch AB. 33:29.780 --> 33:33.200 Das heißt, ich brauche noch mindestens drei Zeichen, um dieses 33:33.200 --> 33:35.560 Teilwort tatsächlich zu erzeugen. 33:35.560 --> 33:39.380 Bei der zweiten Äquivalenzklasse brauche ich noch mindestens zwei 33:39.380 --> 33:43.760 Zeichen, um dieses Teilwort, das nicht enthalten sein soll, zu 33:43.760 --> 33:44.280 erzeugen. 33:44.420 --> 33:47.880 Und bei der dritten Äquivalenzklasse ist es dann nur noch ein Zeichen, 33:47.980 --> 33:48.680 nämlich das C. 33:50.600 --> 33:53.560 Und das sind dann im Prinzip diese vier Äquivalenzklassen. 33:54.300 --> 33:58.060 Und dementsprechend kriegt man dann auch hier einen Zustandsautomaten 33:58.060 --> 34:03.720 mit vier Äquivalenzklassen, wobei eben diese eine Äquivalenzklasse 34:03.720 --> 34:04.960 dieser Fehlerzustand ist. 34:08.270 --> 34:12.030 Also im Prinzip, am Anfang kann ich ganz viele BCs haben. 34:12.190 --> 34:13.150 Irgendwann kommt ein A. 34:13.730 --> 34:16.370 Und jetzt habe ich natürlich das Problem, wenn jetzt noch ein B und 34:16.370 --> 34:18.490 ein C kommt, dann komme ich in den Fehlerzustand. 34:19.630 --> 34:21.550 Deswegen brauche ich hier einen neuen Zustand. 34:22.070 --> 34:24.990 Und dann gehe ich noch eins weiter mit einem B zum Beispiel. 34:25.150 --> 34:27.710 Dann bin ich im Prinzip hier in dieser Äquivalenzklasse. 34:28.430 --> 34:31.610 Jetzt brauche ich nur noch ein Zeichen, um in den Fehlerzustand zu 34:31.610 --> 34:31.790 kommen. 34:31.790 --> 34:35.450 Und so erhalte ich diesen Äquivalenzklassenautomaten. 34:39.520 --> 34:40.580 Sind Fragen dazu? 34:48.060 --> 34:53.120 Die nächste Aufgabe war dann eben zu zeigen, dass eine Sprache nicht 34:53.120 --> 34:56.720 regulär ist, was man eben auch mit der Nerode-Relation machen kann. 34:57.180 --> 35:00.520 Und hier hat man die Sprache A hoch N, B hoch N². 35:02.600 --> 35:06.240 Und jetzt soll man zeigen, dass es nicht regulär ist. 35:06.240 --> 35:11.280 Was man also macht, ist zu zeigen, dass diese Sprache bezüglich der 35:11.280 --> 35:14.520 Nerode -Relation unendlich viele Äquivalenzklassen besitzt. 35:16.060 --> 35:20.840 Was man machen kann oder was man dann macht, ist, man sucht sich zwei 35:20.840 --> 35:24.680 geeignete Worte raus, die allgemein gehalten sind. 35:24.880 --> 35:30.040 Also zum Beispiel BI ist gleich A hoch I, also das Wort, das IAs 35:30.040 --> 35:30.520 enthält. 35:31.100 --> 35:35.720 Und dann im Prinzip das Wort, das JAs enthält. 35:35.720 --> 35:38.040 Mit der Bedingung, dass I kleiner J ist. 35:38.820 --> 35:43.560 Und was man jetzt zeigt, ist, dass diese zwei Worte in 35:43.560 --> 35:45.780 unterschiedlichen Äquivalenzklassen liegen. 35:46.160 --> 35:49.420 Dadurch, dass ich das I und J allgemein halte, weiß ich, dass das für 35:49.420 --> 35:51.220 jede Paarung von I und J gilt. 35:51.640 --> 35:54.420 Dementsprechend bekomme ich unendlich viele Äquivalenzklassen. 35:55.420 --> 36:01.340 Und dann wissen wir vom Satz von Nerode, dass diese Sprache nicht 36:01.340 --> 36:03.500 regulär sein kann. 36:04.620 --> 36:08.080 Was wir also machen, ist genau das, was ich hier gerade gesagt habe. 36:08.440 --> 36:13.720 Wir zeigen, dass diese zwei Worte in unterschiedlichen 36:13.720 --> 36:14.920 Äquivalenzklassen liegen. 36:17.980 --> 36:20.420 Was wir machen, ist einfach ein Widerspruchsbeweis. 36:20.540 --> 36:23.600 Wir nehmen jetzt einfach mal an, sie liegen in derselben 36:23.600 --> 36:27.920 Äquivalenzklasse und überlegen uns jetzt, was daraus folgt. 36:29.800 --> 36:34.220 Naja, wir wissen von der Nerode-Relation selber, von der Definition, 36:34.900 --> 36:38.980 dass wir jetzt jedes beliebige Wort dranhängen können an diese zwei 36:38.980 --> 36:39.320 Worte. 36:39.740 --> 36:44.480 Und es gilt, wenn das eine neu erzeugte Wort in der Sprache liegt, 36:44.640 --> 36:46.380 dann muss auch das andere in der Sprache liegen. 36:46.720 --> 36:48.960 Oder eben beide liegen nicht in der Sprache. 36:50.160 --> 36:55.280 Und jetzt muss man eben dieses Z geschickt wählen. 36:55.280 --> 37:00.800 Und was man macht, ist, man wählt zum Beispiel als B hoch I hoch 2. 37:03.160 --> 37:07.420 Wir wissen, dass da das für alle Worte gilt, muss das auch für dieses 37:07.420 --> 37:08.160 Wort gelten. 37:08.920 --> 37:15.960 Dann hat man entsprechend B hoch I hoch 2 ist in der Sprache genau 37:15.960 --> 37:20.100 dann, wenn BJB hoch I hoch 2 auch in der Sprache ist. 37:20.420 --> 37:22.920 Also hier muss natürlich auch das I stehen. 37:23.960 --> 37:28.040 Aber das führt uns eigentlich direkt zu einem Widerspruch, weil was 37:28.040 --> 37:33.860 wir jetzt haben ist, naja, dieses Wort gilt offensichtlich, also das 37:33.860 --> 37:35.400 Wort ist offensichtlich in der Sprache. 37:35.740 --> 37:37.780 Das ist im Prinzip genau die Definition. 37:39.580 --> 37:44.080 Aber wir wissen jetzt, dass J größer als I ist und dementsprechend 37:44.080 --> 37:46.540 kann dieses Wort nicht in der Sprache drin liegen. 37:46.780 --> 37:49.580 Weil das widerspricht natürlich hier genau diesem Zusammenhang. 37:49.580 --> 37:53.780 Und dementsprechend kriegen wir hier den Widerspruch, dieses Wort 37:53.780 --> 37:57.080 liegt nicht in der Sprache. 37:57.440 --> 38:01.040 Und das Wort liegt in der Sprache, das widerspricht genau der 38:01.040 --> 38:03.460 Definition von der Relation von Nerode. 38:08.290 --> 38:09.570 Gibt es Fragen dazu? 38:18.140 --> 38:23.040 Das ganze Spiel kann man dann auch für Fibonacci-Zahlen machen, für 38:23.040 --> 38:25.760 die Sprache, die hier über diese Fibonacci-Zahlen definiert ist. 38:25.760 --> 38:31.980 Die Idee ist, dass wir Worte enthalten, die immer die Länge einer 38:31.980 --> 38:33.200 Fibonacci -Zahl haben. 38:33.400 --> 38:36.600 Und Fibonacci-Zahlen, kennt ihr vielleicht aus anderen Vorlesungen, 38:36.920 --> 38:41.900 ist einfach eine Zahlenfolge, sodass die erste Fibonacci-Zahl die 1 38:41.900 --> 38:43.980 ist, die zweite auch eine 1. 38:44.380 --> 38:48.840 Und die ende Fibonacci-Zahl ist immer definiert, basierend auf den 38:48.840 --> 38:53.660 zwei vorherigen, nämlich die ist nur die Summe der zwei vorherigen. 38:53.660 --> 38:58.920 Also zum Beispiel hier die 5 erhalte ich, indem ich die 2 plus die 3 38:58.920 --> 38:59.340 rechne. 38:59.800 --> 39:03.140 Und erhalte dadurch die 5, die 8 ist dann 3 plus 5 und so weiter. 39:03.600 --> 39:06.060 Das ist die Fibonacci-Folge. 39:07.420 --> 39:11.220 Und was wir jetzt zeigen sollen ist, dass diese Sprache nicht regulär 39:11.220 --> 39:11.480 ist. 39:14.660 --> 39:18.520 Was wir machen, ist im Prinzip genau das gleiche Vorgehen wieder. 39:20.220 --> 39:24.620 Wir sagen, wir schauen uns ein Wort an, das die Länge der n-ten 39:24.620 --> 39:28.660 Fibonacci -Zahl hat und ein Wort, das die Länge der m-ten Fibonacci 39:28.660 --> 39:30.680 -Zahl hat, sodass m größer n ist. 39:32.540 --> 39:35.760 Und wir zeigen, dass jetzt diese zwei Worte in unterschiedlichen 39:35.760 --> 39:37.000 Äquivalenzklassen liegen. 39:40.290 --> 39:43.390 Wir machen wieder einen Widerspruchsbeweis und sagen, naja, nehmen wir 39:43.390 --> 39:45.690 an, die liegen in derselben Äquivalenzklasse. 39:45.690 --> 39:51.590 Dann gilt nach Satz von der Rode eben genau diese Genau-dann-wenn 39:51.590 --> 39:57.310 -Aussage, dass wenn wir noch ein Z an dieses eine Wort hängen und das 39:57.310 --> 40:00.630 Z an das andere Wort, dann sind entweder beide in der Sprache oder 40:00.630 --> 40:01.230 beide nicht. 40:03.430 --> 40:06.150 Und jetzt müssen wir uns eben wieder überlegen, wie wir das Z 40:06.150 --> 40:07.070 geschickt wählen. 40:10.180 --> 40:17.360 Das Z wählen wir so, dass wir sagen, das ist das Wort mit der Länge 40:17.360 --> 40:23.960 der n-1-ten Fibonacci-Zahl und was wir daraus folgern können, dass 40:23.960 --> 40:28.040 eben genau diese Genau-dann-wenn-Beziehung gilt für diese zwei Wörter. 40:28.740 --> 40:32.540 Sprich, entweder beide sind in der Sprache oder keins von beiden ist 40:32.540 --> 40:33.160 in der Sprache. 40:38.480 --> 40:42.820 Jetzt wissen wir natürlich, dass dieses Wort hier in der Sprache drin 40:42.820 --> 40:47.620 liegen muss, weil das hier hat genau die Länge der n-1-ten Fibonacci 40:47.620 --> 40:47.940 -Zahl. 40:48.040 --> 40:52.740 Das ist hier n-te Fibonacci-Zahl und die n-1-te Fibonacci-Zahl gibt 40:52.740 --> 40:54.380 die n-1-te Fibonacci-Zahl. 40:55.380 --> 41:02.620 Dementsprechend wissen wir durch diese Aussage hier, dass dieses Wort 41:02.620 --> 41:04.160 auch in der Sprache drin liegen muss. 41:04.160 --> 41:05.900 Und das führen wir jetzt zum Widerspruch. 41:06.080 --> 41:10.180 Wir zeigen jetzt, dass dieses Wort gerade eben nicht in der Sprache 41:10.180 --> 41:10.440 liegt. 41:11.320 --> 41:15.860 Was wir machen ist, dass wir sagen, naja, wir schätzen das jetzt 41:15.860 --> 41:22.800 einfach ab und zeigen, dass die Summe aus der m-ten Fibonacci-Zahl und 41:22.800 --> 41:26.360 der n-1-ten Fibonacci-Zahl eben keine Fibonacci-Zahl ist. 41:26.980 --> 41:28.600 Dazu machen wir ein paar Abschätzungen. 41:29.080 --> 41:32.860 Was wir wissen ist, dass m größer n ist und dementsprechend wissen 41:32.860 --> 41:36.540 wir, dass die m-te Fibonacci-Zahl größer als die n-te Fibonacci-Zahl 41:36.540 --> 41:42.460 ist, weil wir wissen nach Definition, dass hier im Prinzip die Folge 41:42.460 --> 41:44.240 streng monoton steigend ist. 41:46.440 --> 41:50.980 Und somit wissen wir auch, dass die m-1-te Fibonacci-Zahl größer 41:50.980 --> 41:53.320 gleich der n-ten Fibonacci-Zahl sein muss. 41:54.860 --> 41:59.200 Und die ist natürlich größer als die n-1-te Fibonacci-Zahl und 41:59.200 --> 42:01.760 dementsprechend haben wir hier diese Abschätzung. 42:01.920 --> 42:04.960 Also wir brauchen jetzt die Abschätzung vom roten zum blauen. 42:07.300 --> 42:13.120 Und was wir jetzt wissen ist, dass die m-te Fibonacci-Zahl kleiner ist 42:13.120 --> 42:16.700 als die m-te plus die n-1-te. 42:18.180 --> 42:22.580 Und die wiederum ist kleiner als die m-te plus die m-1-te. 42:22.700 --> 42:24.880 Das ist im Prinzip genau diese Abschätzung. 42:25.660 --> 42:28.100 Diese Abschätzung kriege ich dadurch, dass ich hier einfach was 42:28.100 --> 42:29.360 Positives drauf addiere. 42:30.760 --> 42:35.120 Und dann weiß ich, naja das hier ist nichts anderes als die m-1-te 42:35.120 --> 42:36.060 Fibonacci -Zahl. 42:37.520 --> 42:42.820 Dementsprechend weiß ich, okay, dieser gelbe Ausdruck, das entspricht 42:42.820 --> 42:46.920 gerade hier diesem Ausdruck, der liegt zwischen zwei Fibonacci-Zahlen, 42:47.020 --> 42:48.200 die aufeinanderfolgend sind. 42:48.780 --> 42:53.180 Und weil eben die Fibonacci-Folge streng monoton steigend ist, wissen 42:53.180 --> 42:57.980 wir, okay, dann kann es aber nicht so sein, dass das noch eine 42:57.980 --> 42:59.020 Fibonacci -Zahl ist. 43:00.020 --> 43:04.780 Und dementsprechend erhalten wir hier einen Widerspruch und haben 43:04.780 --> 43:11.300 gezeigt, die können nicht in derselben Äquivalenzklasse liegen. 43:19.340 --> 43:20.460 Soweit verstanden? 43:21.200 --> 43:25.180 Im Prinzip, wie man zeigt, dass eine Sprache nicht regulär ist, mit 43:25.180 --> 43:29.240 der Nerode-Relation ist immer im Prinzip dasselbe Vorgehen. 43:29.840 --> 43:35.140 Ich suche mir zwei Wörter raus, hänge dann noch ein zusätzliches Wort 43:35.140 --> 43:40.060 dran und weiß von diesen zwei neu erzeugten Worten, dass genau diese 43:40.060 --> 43:42.940 Beziehung gilt, entweder beide in der Sprache oder keins von beiden. 43:42.940 --> 43:50.280 Und dann muss ich eben dieses Z entsprechend gut wählen, sodass ich 43:50.280 --> 43:52.400 dann eben zeigen kann, dass das einen Widerspruch gibt. 43:53.060 --> 43:54.440 Und dann hat man das. 43:56.400 --> 43:59.480 Also Z als Epsilon zu wählen wäre zum Beispiel nicht geschickt 43:59.480 --> 44:02.720 gewesen, weil dann diese Beziehung gegolten hätte. 44:07.060 --> 44:09.480 Sind Fragen zur Nerode-Relation? 44:16.830 --> 44:19.870 Dann gehe ich über zu Turing-Maschinen, also ein bisschen anderes 44:19.870 --> 44:23.770 Thema, ein bisschen allgemeiner als endliche Automaten. 44:24.310 --> 44:25.950 Da kann man nettere Sachen mitmachen. 44:27.590 --> 44:31.190 Turing-Maschinen habt ihr in der Vorlesung schon ausreichend 44:31.190 --> 44:31.810 kennengelernt. 44:31.910 --> 44:35.370 Die Definition war die, dass man jetzt nicht nur einen endlichen 44:35.370 --> 44:37.410 Speicher hat, wie bei einem endlichen Automaten. 44:37.530 --> 44:40.590 Also wir haben hier zwar immer noch so einen Zustandsautomaten, der im 44:40.590 --> 44:43.950 Prinzip endlich ist, aber was wir jetzt noch zusätzlich haben ist 44:43.950 --> 44:48.630 einen nicht-endlichen Speicher, sodass wir im Prinzip hier auf diesem 44:48.630 --> 44:51.370 Speicher noch Dinge abspeichern können. 44:51.550 --> 44:54.630 Also wir können jetzt zum Beispiel so Dinge tun wie zählen und 44:54.630 --> 44:59.030 ähnliche Dinge tun, was wir bisher nicht konnten mit den endlichen 44:59.030 --> 44:59.650 Automaten. 45:00.070 --> 45:04.650 Und was wir tun ist, wir sagen, naja, diese endliche Kontrolle ist 45:04.650 --> 45:06.450 definiert durch eine Zustandsmenge. 45:06.450 --> 45:11.710 Wir haben dann außerdem wieder Übergänge und diese Übergänge sind aber 45:11.710 --> 45:12.450 anders definiert. 45:12.590 --> 45:15.730 Also im Prinzip, was wir haben, ist auf diesem Eingabeband Zeichen, 45:15.810 --> 45:21.710 die wir bearbeiten können, mit dem Prinzip so einem Lese-Schreibe 45:21.710 --> 45:21.970 -Kopf. 45:22.850 --> 45:26.070 Und jetzt ist immer die Frage, wo geht der Lese-Schreibe-Kopf hin? 45:26.170 --> 45:28.590 Entweder er bleibt an derselben Stelle oder er geht nach links oder 45:28.590 --> 45:33.970 nach rechts eine Einheit und er setzt dann im Prinzip noch die 45:33.970 --> 45:34.350 Zeichen. 45:34.350 --> 45:38.350 Und dieser Zustandsautomat beschreibt dann, wie wir die Zeichen 45:38.350 --> 45:38.670 ändern. 45:39.210 --> 45:42.550 Und wir lesen das so zum Beispiel, wenn wir in Q0 sind und dieses 45:42.550 --> 45:46.710 Blank -Symbol lesen, dann ersetzen wir das durch ein Blank-Symbol und 45:46.710 --> 45:48.110 gehen noch eins nach links. 45:53.030 --> 45:58.470 Also die erste Aufgabe war, dass man erstmal die formale Definition 45:58.470 --> 46:03.630 von dieser Turing-Maschine hinschreiben soll, was noch relativ einfach 46:03.630 --> 46:04.710 ist. 46:05.150 --> 46:07.690 Was man hat, ist natürlich hier einfach diese Zustände. 46:08.310 --> 46:12.330 Was man noch hat, ist dieses Alphabet. 46:12.630 --> 46:15.850 Das Eingabe-Alphabet daraus darf diese Eingabe bestehen. 46:16.410 --> 46:18.510 Und was man noch hat, ist dieses Band-Alphabet. 46:18.990 --> 46:22.950 Und das Band-Alphabet ist immer das Eingabe-Alphabet plus zusätzliche 46:22.950 --> 46:25.770 Zeichen, die man auch noch haben darf zum Bearbeiten. 46:25.770 --> 46:30.450 Und dann hat man noch den Start-Zustand, dann noch eine Übergangs 46:30.450 --> 46:32.490 -Funktion und dann noch einen End-Zustand. 46:33.150 --> 46:40.890 Und was man nicht rauslesen kann aus so einem Zustandsautomaten, ist 46:40.890 --> 46:44.570 zu welchem Alphabet jetzt die einzelnen Zeichen gehören. 46:45.010 --> 46:49.590 Also im Prinzip, was sein kann, und so habe ich es jetzt gewählt, ist, 46:49.750 --> 46:54.310 dass eben 0,1 und die Raute zum Eingabe-Alphabet gehören und das 46:54.310 --> 46:57.630 Hilfszeichen sind, die ich einfach nachher verwende für meine 46:57.630 --> 47:00.130 Berechnung, aber die erlaube ich nicht als Eingabe. 47:01.110 --> 47:04.650 Aber da gibt es unterschiedliche Möglichkeiten, was man dann angibt. 47:06.230 --> 47:08.270 Sollte einigermaßen Sinn natürlich machen. 47:12.470 --> 47:16.150 Wichtiger war im Prinzip so hier zu sagen, was die End-Zustände sind 47:16.150 --> 47:19.310 und was die Start-Zustände sind oder der Start-Zustand. 47:21.730 --> 47:24.190 Und genau, das war so die erste Aufgabe. 47:24.810 --> 47:28.290 Die zweite Aufgabe war, dass man das durchrechnen soll. 47:29.750 --> 47:33.470 Das war so ein bisschen aufwendiger, aber ich sollte euch einfach mal 47:33.470 --> 47:37.550 zeigen, wie so eine Turing-Maschine abläuft und dass ihr die auch mal 47:37.550 --> 47:41.310 selber durchrechnet und auch einfach mal die Konfiguration anschaut. 47:41.310 --> 47:45.210 Und die Turing-Maschine, was die macht, ist, sie startet hier in 47:45.210 --> 47:50.350 diesem Zustand Q0 und ihr solltet das auf der Eingabe 1.1.1 Raute 1.1 47:50.350 --> 47:51.670 .1 ausführen. 47:52.470 --> 47:57.510 Und was jetzt passiert ist, dass dieser Zustand Q0 immer eine 1 liest 47:57.510 --> 47:58.850 und nach rechts geht. 47:59.370 --> 48:02.910 Das macht ihr mit allen Zeichen, sprich Q0 läuft einfach einmal von 48:02.910 --> 48:04.070 links nach rechts durch. 48:05.370 --> 48:07.990 Das sieht dann so aus, kann man auch abkürzen. 48:10.270 --> 48:13.870 Und dann komme ich in den Zustand Q1, weil ich auf einmal ein 48:13.870 --> 48:14.990 Blankzeichen lese. 48:15.090 --> 48:16.670 Ich bin also ganz rechts angekommen. 48:17.910 --> 48:19.910 Und jetzt ist die Frage, was ich lese. 48:20.070 --> 48:23.070 Also entweder ich lese eine 1 oder ich lese eine 0 und gehe wieder 48:23.070 --> 48:23.450 zurück. 48:24.090 --> 48:28.770 Wenn ich eine 1 lese, was hier der Fall ist, dann lösche ich diese 1 48:28.770 --> 48:33.230 und laufe jetzt wieder nach links, bis ich wieder zurückkomme. 48:37.750 --> 48:40.610 Und dann komme ich irgendwann über die Raute rüber. 48:40.990 --> 48:45.670 Und dieser Zustand Q3 beschreibt jetzt im Prinzip dieses Verhalten, 48:45.750 --> 48:49.090 was passiert, wenn ich von links wieder zurücklaufe über eine Raute. 48:49.610 --> 48:53.390 Und das heißt einfach, ich muss jetzt dieses zweite Wort anschauen. 48:55.070 --> 48:58.810 Und jetzt geht es eben von Q4, jetzt geht es in Q4 rein. 48:58.810 --> 49:03.150 Und was jetzt passiert, ist, wenn ich eine 1 finde, dann wird sie 49:03.150 --> 49:09.570 durch eine 0 ersetzt, die ich speziell markiere und laufe nochmal 49:09.570 --> 49:10.430 weiter nach links. 49:10.910 --> 49:14.350 Und dann heißt es einfach, naja, dann laufe ich weiter nach links, 49:14.410 --> 49:16.790 solange ich 1 lese und ersetze die immer durch Nullen. 49:17.270 --> 49:21.190 Bis ich irgendwann eine 1, ein Blankzeichen finde oder eine 0, dann 49:21.190 --> 49:24.510 ersetze ich das jeweils durch eine 1 und komme dann wieder in den 49:24.510 --> 49:25.370 Startzustand. 49:25.990 --> 49:28.090 Da laufe ich dann wieder einfach nach rechts. 49:28.670 --> 49:29.650 Also das sieht dann so aus. 49:30.290 --> 49:34.050 Ich laufe hier einmal noch nach links, finde jetzt hier diese letzte 49:34.050 --> 49:37.630 1, ersetze jeweils die 0, 1 durch die Nullen. 49:38.510 --> 49:42.670 Und da ist, glaube ich, ein Fehler reingekommen. 49:50.720 --> 49:54.700 Das sollte einfach draußen sein, wenn ich es richtig sehe. 50:01.310 --> 50:06.090 Genau, also im Prinzip, was passiert, ich schreibe jetzt hier mit 50:06.090 --> 50:09.290 diesem Q4 eine 1, also hier dieses Blankzeichen macht irgendwie keinen 50:09.290 --> 50:09.510 Sinn. 50:12.370 --> 50:15.390 Und schreibe hier diese zusätzliche 1 und laufe jetzt wieder nach 50:15.390 --> 50:15.710 rechts. 50:16.630 --> 50:18.970 Und jetzt geht dieses Spiel wieder von vorne los. 50:20.250 --> 50:22.570 Was macht die Turingmaschine mit der Eingabe? 50:29.100 --> 50:30.040 Jemand eine Idee? 50:47.650 --> 50:53.090 Ja, also im Prinzip, es addiert beide Zahlen und du liest die Zahlen 50:53.090 --> 50:55.330 immer von rechts nach links. 50:55.650 --> 50:59.490 Also im Prinzip, die kleinste, also die Stelle mit der kleinsten 50:59.490 --> 51:03.050 Wertigkeit steht rechts, also immer rechts und dann nach links. 51:03.970 --> 51:09.750 Genau, das Ding ist, genau, das macht es jetzt mit der Eingabe. 51:09.750 --> 51:13.110 Wie ist das, funktioniert das mit jeder binären Zahl? 51:14.170 --> 51:17.770 Also nehme ich an, ich habe andere binären Zahlen getrennt von der 51:17.770 --> 51:18.050 Raute. 51:41.560 --> 51:46.580 Die Antwort ist nein, es funktioniert nicht mit allen binären Zahlen. 51:46.720 --> 51:52.840 Dafür ist dieser Automat oder die Turingmaschine noch nicht komplett 51:52.840 --> 51:53.480 definiert. 51:55.320 --> 51:58.220 Als Einschub der Aufgabe habe ich vergessen, was man noch machen 51:58.220 --> 51:58.580 sollte. 51:58.780 --> 52:02.200 Man sollte die Turingmaschine vervollständigen, da fügt man einfach 52:02.200 --> 52:05.600 noch einen Fehlerzustand ein und fügt dann entsprechend diese 52:05.600 --> 52:07.260 zusätzlichen Übergänge ein. 52:08.060 --> 52:09.220 Aber das ist hier mal übersprungen. 52:10.960 --> 52:13.900 Was mich eher interessiert ist, was passiert z.B. 52:14.060 --> 52:17.940 wenn hier so eine Eingabe passiert, dass wir hier eine 1 0 0 Raute 1 1 52:17.940 --> 52:18.480 0 haben. 52:20.280 --> 52:21.460 Funktioniert das dann immer noch? 52:22.260 --> 52:23.940 Oder was macht die Turingmaschine? 52:32.560 --> 52:37.620 Was passiert ist, dass die Nuller einfach weggekürzt werden. 52:37.800 --> 52:39.700 Also da macht die Turingmaschine irgendwie noch keinen Sinn. 52:41.120 --> 52:44.540 Auf dem Übungsblatt haben wir leider relativ undeutlich geschrieben, 52:44.820 --> 52:49.420 dass man beschreiben soll, was die Turingmaschine auf der Eingabe 52:49.420 --> 52:49.660 macht. 52:49.660 --> 52:54.620 Und eigentlich war die Eingabe, also die, die ihr hier durchgerechnet 52:54.620 --> 52:55.380 habt, gemeint. 52:56.520 --> 53:01.140 Die Frage ist, was passiert, wenn wir eine andere Eingabe reinnehmen. 53:01.300 --> 53:05.500 Also im Prinzip können wir eine Eingabe auch bekommen, wo wir hier die 53:05.500 --> 53:06.040 Nullen haben. 53:06.200 --> 53:08.180 Also wie können wir die Turingmaschine ändern? 53:08.740 --> 53:12.540 Also im Prinzip, wenn ihr die Turingmaschine jetzt anders beschrieben 53:12.540 --> 53:16.820 habt oder gesagt habt, naja, ich habe die Aufgabe eben so verstanden, 53:16.940 --> 53:20.180 dass man allgemein beschreiben soll, was die Turingmaschine macht für 53:20.180 --> 53:23.040 eine allgemeine Eingabe, dann werden die Tutoren das auch entsprechend 53:23.040 --> 53:25.300 werten und richtig werten. 53:26.180 --> 53:29.580 Das war einfach eine Ungenauigkeit auf dem Übungsblatt, das soll euch 53:29.580 --> 53:31.000 nicht irgendwie zum Schaden sein. 53:34.220 --> 53:37.540 Und die Frage ist aber, wie kriege ich jetzt zum Beispiel die 53:37.540 --> 53:42.260 Turingmaschine dazu, dass sie tatsächlich zwei beliebige Binärzahlen 53:42.260 --> 53:42.660 addiert. 53:43.360 --> 53:44.480 Sieht das jemand? 53:44.840 --> 53:48.140 Also ihr habt jetzt mal drei Minuten Zeit, einfach euch zu überlegen, 53:48.500 --> 53:51.420 wie ihr die Turingmaschine erweitert, sodass ihr tatsächlich binäre 53:51.420 --> 53:52.500 Zahlen addiert. 53:53.920 --> 53:57.500 Und nicht nur binäre Zahlen, die hier nur Einsen enthalten. 55:27.740 --> 55:35.900 Was wir machen ist folgendes, wir gehen von Q1 aus nicht einfach 55:35.900 --> 55:39.920 wieder zurück nach Q0 und ignorieren die Null, sondern was wir machen 55:39.920 --> 55:45.660 ist, wir laufen einfach hier rüber und markieren dann entsprechend das 55:45.660 --> 55:48.780 Zeichen, also wir laufen hier über die Raute, schauen uns alle 55:48.780 --> 55:52.860 markierten Zeichen noch an, die es gibt, und gehen noch eins weiter 55:52.860 --> 55:56.220 und markieren dann das darauf folgende Zeichen auch noch als markiert, 55:56.460 --> 55:59.480 weil wir wissen, dass auf diese Stelle nichts mehr drauf addiert wird. 55:59.980 --> 56:01.600 Und das ist dann die Idee dahinter. 56:02.300 --> 56:04.620 Ich hoffe, man kann es lesen mit dem Gelb. 56:04.620 --> 56:08.180 Was wir machen ist, wir fügen hier folgende Zustände ein. 56:08.280 --> 56:12.040 Wenn wir eine Null lesen in Q1, dann laufen wir nach links, irgendwann 56:12.040 --> 56:13.040 finden wir die Raute. 56:13.460 --> 56:16.780 Das heißt, wir kommen wieder in den neuen Zustand, der sagt, wir sind 56:16.780 --> 56:17.980 jetzt links von der Raute. 56:19.260 --> 56:23.400 Da lesen wir alle Zustandsmarkierungen, bis wir mal ein Zeichen 56:23.400 --> 56:25.760 finden, dass es keine Zustandsmarkierung mehr gibt. 56:27.020 --> 56:29.620 Das kann eine Null, eine Eins oder ein Plank-Symbol sein. 56:29.620 --> 56:35.680 Und schreiben jetzt entsprechend die Null, die Eins oder eben eine 56:35.680 --> 56:37.080 Null, falls es ein Plank-Symbol ist. 56:37.200 --> 56:38.040 Aber jetzt markiert. 56:38.540 --> 56:42.040 Die Markierung heißt im Prinzip, wir dürfen es nicht mehr abändern. 56:45.240 --> 56:50.680 Und hier haben wir nochmal einen zusätzlichen Übergang eingefügt. 56:51.120 --> 56:52.120 Für was braucht man den? 57:07.980 --> 57:09.160 Der hat auch noch gefehlt. 57:18.630 --> 57:25.450 Wir sind jetzt im Prinzip ganz links und wollen jetzt noch eine Eins 57:25.450 --> 57:25.950 schreiben. 57:26.750 --> 57:28.590 Und wir tun es bisher nur, wenn eine Null da ist. 57:28.730 --> 57:32.470 Das war noch so ein kleiner Fehler in der Automatenbeschreibung. 57:32.890 --> 57:37.090 Aber auch da werden dann im Prinzip die Korrekturen entsprechend sein, 57:37.190 --> 57:41.130 dass die Tutoren einfach schauen, was ihr geschrieben habt und 57:41.130 --> 57:44.870 dementsprechend die Aufgabe bewerten. 57:44.870 --> 57:47.930 Hier ist uns einfach dieser Fehler passiert, dass wir diesen Übergang 57:47.930 --> 57:48.590 vergessen haben. 57:54.600 --> 57:56.460 Sind Fragen zu der Aufgabe noch? 58:02.940 --> 58:04.720 Dann zur Aufgabe 6. 58:04.900 --> 58:09.040 Da war die Idee, man hat ein Wort gegeben, ein binäres Wort. 58:10.120 --> 58:13.560 Und man soll jetzt entscheiden, ob die Null genauso häufig vorkommt 58:13.560 --> 58:14.180 wie die Eins. 58:15.880 --> 58:18.080 Dazu sollte man eine Turing-Maschine entwerfen. 58:18.900 --> 58:19.980 Was ist so die grobe Idee? 58:20.100 --> 58:21.720 Kann es jemand erklären, was man machen muss? 58:44.380 --> 58:46.180 Genau, also das ist die Idee. 58:46.500 --> 58:47.420 Also zur Wiederholung. 58:48.680 --> 58:53.800 Was man macht ist, man durchläuft das Wort von links nach rechts. 58:54.680 --> 58:57.380 Schaut, was man zuerst liest, eine Null oder eine Eins. 58:57.900 --> 59:01.020 In beiden Fällen ersetze ich die durch ein Sonderzeichen, zum Beispiel 59:01.020 --> 59:01.620 durch ein X. 59:02.740 --> 59:06.300 Damit ich es markiere, dass es schon gelesen ist. 59:06.820 --> 59:08.900 Nehmen wir an, ich habe eine Null gelesen am Anfang. 59:08.900 --> 59:12.020 Dann gehe ich jetzt weiter bis zur nächsten Stelle, an der eine Eins 59:12.020 --> 59:13.000 oder eine Null kommt. 59:13.480 --> 59:16.240 Und ersetze die, oder an der eine Eins steht. 59:16.380 --> 59:17.620 Also wir haben jetzt eine Null gelesen. 59:17.740 --> 59:19.800 Ich laufe bis zu der Stelle, wo ich eine Eins lese. 59:20.320 --> 59:22.440 Und ersetze die dann auch durch X. 59:23.160 --> 59:24.820 Und dann gehe ich wieder zurück zum Anfang. 59:26.520 --> 59:31.520 Und das Ganze mache ich dann eben so lange, bis nur noch Xen auf dem 59:31.520 --> 59:32.000 Band stehen. 59:32.820 --> 59:34.500 In dem Fall akzeptiere ich. 59:34.500 --> 59:37.640 Was aber auch passieren kann, dass bei der Suche nach dem zweiten 59:37.640 --> 59:40.500 Zeichen, ich das rechte Ende erreiche. 59:40.900 --> 59:44.820 Und in dem Fall ist die Anzahl ungleich. 59:45.240 --> 59:47.380 Und dementsprechend breche ich dann einfach ab. 59:47.700 --> 59:53.860 Und das ist hier im Prinzip durch diesen Zustandsgrafen dargestellt. 59:59.660 --> 01:00:02.700 Das Ganze kann man dann auch an der Konfiguration durchrechnen. 01:00:02.800 --> 01:00:03.760 Das solltet ihr auch machen. 01:00:03.760 --> 01:00:06.020 Hier nur kurz im Detail. 01:00:06.900 --> 01:00:08.900 Das werde ich nicht im Detail erklären. 01:00:09.340 --> 01:00:11.540 Ich laufe von links nach rechts durch. 01:00:11.660 --> 01:00:12.720 Ich lese zuerst eine Null. 01:00:13.260 --> 01:00:17.180 Markiere die als X, lese eine Eins, markiere die als X, laufe zurück. 01:00:18.040 --> 01:00:21.300 Laufe wieder nach rechts, bis ich das erste Zeichen gefunden habe. 01:00:21.420 --> 01:00:24.760 Markiere das als X, laufe zu... 01:00:26.160 --> 01:00:28.780 Ah ja genau, dann laufe ich noch eins weiter. 01:00:30.100 --> 01:00:33.340 Markiere die auch als X und laufe wieder zurück und so weiter. 01:00:35.800 --> 01:00:38.200 Und dementsprechend kriege ich hier diese Übergänge. 01:00:39.940 --> 01:00:42.500 Und so funktioniert dann die Turing-Maschine. 01:00:43.860 --> 01:00:45.120 Von der Idee klar. 01:00:45.980 --> 01:00:49.240 Es ist prinzipiell, wenn man die Idee mal hat, nicht so schwierig. 01:00:49.540 --> 01:00:51.060 Man muss nur drauf kommen, wie man es macht. 01:00:55.050 --> 01:00:57.830 Das waren die Aufgaben. 01:00:58.510 --> 01:01:02.610 Was jetzt noch kommt, sind zusätzliche Informationen zu erweiterten 01:01:02.610 --> 01:01:03.330 Turing -Maschinen. 01:01:03.450 --> 01:01:06.150 Und wenn noch die Zeit reicht, auch zur Entscheidbarkeit von Sprachen. 01:01:08.170 --> 01:01:12.170 Turing-Maschinen zu bauen, das ist eine relativ aufwendige Sache. 01:01:12.690 --> 01:01:14.970 Man muss ständig hin und her laufen auf dem Band. 01:01:15.690 --> 01:01:21.150 Man muss ständig schauen, dass man die Zustände richtig schreibt. 01:01:21.290 --> 01:01:24.710 Es wäre nett, ein paar Hilfen zu haben, um Turing-Maschinen zu bauen. 01:01:24.710 --> 01:01:29.090 Um die ein bisschen leichter zu konstruieren. 01:01:29.350 --> 01:01:31.150 Und darum geht es jetzt in dem Kapitel. 01:01:33.790 --> 01:01:37.890 Die erste Idee, die man machen kann, um es ein bisschen leichter zu 01:01:37.890 --> 01:01:40.010 machen, um Turing-Maschinen zu konstruieren. 01:01:40.730 --> 01:01:43.750 Man kann Spuren einführen für eine Turing-Maschine. 01:01:44.110 --> 01:01:47.630 Die Idee ist einfach, dass man sagt, dieses Band hat jetzt mehrere 01:01:47.630 --> 01:01:48.070 Spuren. 01:01:48.190 --> 01:01:49.590 Hier in dem Fall drei Spuren. 01:01:49.590 --> 01:01:54.590 Wenn ich jetzt hier mit dem Lese- und Schreibkopf über dieses Band 01:01:54.590 --> 01:01:58.030 rüberlaufe, dann lese ich immer drei Zeichen gleichzeitig, aber kann 01:01:58.030 --> 01:02:00.150 auch drei Zeichen gleichzeitig schreiben. 01:02:00.650 --> 01:02:04.310 Formal heißt das einfach, dass ich das Bandalphabet ende. 01:02:04.910 --> 01:02:10.090 Das Bandalphabet ist einfach jetzt ein Tupel aus K-Zeichen oder ein 01:02:10.090 --> 01:02:13.690 Vektor aus K-Zeichen, die jetzt eben entsprechend hier diesen Spuren 01:02:13.690 --> 01:02:14.210 entsprechen. 01:02:14.210 --> 01:02:18.790 Und die Frage ist jetzt natürlich, was bringt mir das? 01:02:19.230 --> 01:02:22.690 Für die binäre Addition, die wir jetzt vorhin auf dem Übungsblatt 01:02:22.690 --> 01:02:26.210 gesehen haben, ist das deutlich einfacher umzusetzen. 01:02:26.910 --> 01:02:31.670 Was wir jetzt machen, ist, wir laufen mit dem Lese-Kopf von rechts 01:02:31.670 --> 01:02:32.150 nach links 01:02:35.170 --> 01:02:40.970 und dann verwenden wir einfach die Additionsmethode, die jeder in der 01:02:40.970 --> 01:02:44.570 Schule gelernt hat, um schriftlich zu addieren mit Übertrag. 01:02:44.750 --> 01:02:48.810 Also sprich, ich merke mir hier jetzt, dass es hier einen Übertrag 01:02:48.810 --> 01:02:51.530 gibt und ich gehe in den nächsten Zustand und schreibe jetzt hier auf 01:02:51.530 --> 01:02:53.450 die dritte Spur noch das Ergebnis. 01:02:54.130 --> 01:02:57.810 Also was ich mache ist, ich verwende die erste Spur als ersten 01:02:57.810 --> 01:03:01.670 Summand, die zweite Spur als zweiten Summand und die dritte Spur 01:03:01.670 --> 01:03:06.410 verwende ich jetzt, um das Ergebnis aufzuschreiben. 01:03:06.410 --> 01:03:10.470 Das heißt, ich muss jetzt nicht ständig hin und her laufen, um im 01:03:10.470 --> 01:03:13.390 Prinzip diese Eingabe zu bearbeiten. 01:03:15.010 --> 01:03:19.690 Die Frage ist, ist das in irgendeiner Weise mächtiger als eine normale 01:03:19.690 --> 01:03:20.430 Turingmaschine? 01:03:20.550 --> 01:03:24.270 Kann ich mehr machen als mit einer Turingmaschine mit nur einer Spur? 01:03:26.610 --> 01:03:29.150 Das war im Prinzip das, was ich gesagt habe. 01:03:32.070 --> 01:03:36.170 Ja genau, es ist im Prinzip eine Einband-Turingmaschine mit einer 01:03:36.170 --> 01:03:37.510 Spur, mit einem größeren Alphabet. 01:03:37.710 --> 01:03:42.050 Also das Einzige, was wir geändert haben, ist das Alphabet und das 01:03:42.050 --> 01:03:42.930 auch nicht sehr. 01:03:43.390 --> 01:03:46.150 Also im Prinzip haben wir nicht wirklich was groß an der 01:03:46.150 --> 01:03:48.310 Turingmaschine geändert, wir haben es nur so ein bisschen an der 01:03:48.310 --> 01:03:53.650 Interpretation geändert und haben dadurch deutlich mehr Möglichkeiten, 01:03:54.190 --> 01:03:57.950 ein bisschen auf abstrakter Ebene zu arbeiten. 01:03:59.310 --> 01:04:03.110 Was man auch machen kann, ist Turingmaschinen mit mehreren Bändern zu 01:04:03.110 --> 01:04:03.710 betrachten. 01:04:04.130 --> 01:04:08.810 Hier ist die Idee, im Vergleich zu Spuren, dass man sagt, man hat 01:04:08.810 --> 01:04:13.120 jetzt mehrere Bänder, auf denen jeweils ein eigener Kopf liest. 01:04:13.650 --> 01:04:16.370 Also sprich, jeder Schreib- und Lesekopf kann eine unterschiedliche 01:04:16.370 --> 01:04:17.570 Position haben. 01:04:18.990 --> 01:04:23.050 Formal kann man das jetzt so fassen, dass man sagt, man ändert dieses 01:04:23.050 --> 01:04:28.930 Bandalphabet oder die Übergangsfunktion, sodass man sagt, okay, ich 01:04:28.930 --> 01:04:34.390 lese einen Zustand und mehrere Zeichen, zum Beispiel 1, 1, 0 und 01:04:34.390 --> 01:04:37.430 bestimme jetzt den nächsten Zustand, die nächsten Zeichen, also 01:04:37.430 --> 01:04:40.950 sprich, was ich hier hinschreibe, plus in welche Richtung meine 01:04:40.950 --> 01:04:41.830 Leseköpfe gehen. 01:04:42.510 --> 01:04:45.930 Die Frage ist wieder, ist das in irgendeiner Weise mächtiger? 01:05:02.380 --> 01:05:03.240 Jemand eine Idee? 01:05:12.820 --> 01:05:16.360 Also es ist nicht mächtiger, es ist sogar so, dass man zeigen kann, 01:05:16.500 --> 01:05:22.460 dass es vom Zeitaufwand, um so eine Turingmaschine zu simulieren mit 01:05:22.460 --> 01:05:27.240 mehreren Bändern, dass man da immer noch in polynomialer Zeit bleibt. 01:05:27.460 --> 01:05:31.540 Also man braucht maximal quadratisch so viel Zeit wie die 01:05:31.540 --> 01:05:35.540 Mehrbandmaschine und vom Speicherplatz bleiben wir immer noch in 01:05:35.540 --> 01:05:36.700 derselben Größenordnung. 01:05:36.700 --> 01:05:41.180 Was natürlich ganz nett ist, weil uns so Mehrband-Turingmaschinen 01:05:41.180 --> 01:05:45.400 einfach ein starkes Werkzeug liefern, um Turingmaschinen leicht zu 01:05:45.400 --> 01:05:45.880 modellieren. 01:05:47.200 --> 01:05:48.960 Der Beweis ist nicht allzu schwierig. 01:05:49.620 --> 01:05:53.480 Was man macht, ist folgendes, ich habe da mal zwei Minuten Zeit, 01:05:53.520 --> 01:05:56.460 darüber nachzudenken, wie man es machen würde. 01:05:57.860 --> 01:06:01.220 Es ist nicht so schwierig, was man macht, man schaut sich eine 01:06:01.220 --> 01:06:03.560 Turingmaschine mit 2K-Spuren an. 01:06:03.560 --> 01:06:08.240 Was wir machen ist, wir haben jetzt so eine Mehrband-Turingmaschine 01:06:08.240 --> 01:06:10.360 mit K-Bändern gegeben, M. 01:06:10.840 --> 01:06:13.400 Und was wir jetzt machen ist, wir schauen uns eine Turingmaschine M' 01:06:13.600 --> 01:06:16.380 an, die 2K-Spuren hat, aber nur ein Band. 01:06:17.220 --> 01:06:20.800 Und was wir jetzt machen ist, wir simulieren diese Turingmaschine M 01:06:20.800 --> 01:06:22.320 mit M'. 01:06:23.700 --> 01:06:27.660 Und dann müssen wir uns natürlich überlegen, wie sieht eigentlich so 01:06:27.660 --> 01:06:28.700 eine Turingmaschine aus? 01:06:28.760 --> 01:06:31.280 Und was wir machen ist folgende Transformation. 01:06:32.140 --> 01:06:35.320 Wir übersetzen jedes Band in eine eigene Spur. 01:06:36.320 --> 01:06:39.860 Und da wir jetzt 2K-Spuren haben, haben wir noch jeweils für jedes 01:06:39.860 --> 01:06:41.600 Band eine zusätzliche Spur übrig. 01:06:41.920 --> 01:06:46.000 Und auf dieser zusätzlichen Spur speichern wir uns immer die Position 01:06:46.000 --> 01:06:48.020 von dem Lesekopf. 01:06:51.880 --> 01:06:55.460 Also zum Beispiel die Position von diesem Lese-Schreibkopf und dann 01:06:55.460 --> 01:06:57.540 die Position von diesem Lese-Schreibkopf. 01:06:58.620 --> 01:07:02.500 Die müssen natürlich nicht übereinstimmen mit dem Lese-Schreibkopf von 01:07:02.500 --> 01:07:06.200 der Turingmaschine M'. 01:07:06.880 --> 01:07:09.880 Und jetzt müssen wir uns noch überlegen, wie wir im Prinzip die 01:07:09.880 --> 01:07:11.600 einzelnen Rechenschritte abarbeiten. 01:07:13.820 --> 01:07:16.020 Und was wir machen ist folgendes. 01:07:17.440 --> 01:07:23.060 Wir nehmen an, dass der Kopf von M' auf der linksten Raute startet. 01:07:23.060 --> 01:07:28.140 Und arbeiten jetzt im Prinzip das Verhalten von M wie folgt ab. 01:07:28.620 --> 01:07:32.540 Der Kopf von M' läuft jetzt erstmal nach rechts zur rechtesten Raute 01:07:32.540 --> 01:07:35.480 und merkt sich jedes Mal, wenn eine Raute kommt, auf irgendeiner 01:07:35.480 --> 01:07:40.580 dieser Spuren in dem endlichen Speicher, was die K-Köpfe von M lesen 01:07:40.580 --> 01:07:40.860 würden. 01:07:41.180 --> 01:07:42.940 Das wird darin abgespeichert. 01:07:44.740 --> 01:07:49.680 Dann in dem zweiten Schritt läuft der Kopf von M' wieder von rechts 01:07:49.680 --> 01:07:54.360 nach links zurück und macht genau das, was M tun würde mit der 01:07:54.360 --> 01:07:54.900 Eingabe. 01:07:55.080 --> 01:07:59.140 Das heißt, einmal wird es den Bandinhalt, also den Inhalt der 01:07:59.140 --> 01:08:01.600 einzelnen Spuren entsprechend ändern, wo die Rauten sind. 01:08:02.220 --> 01:08:05.840 Wird aber auch gegebenenfalls die Positionsmarkierungen, also diese 01:08:05.840 --> 01:08:09.040 Rauten, nach links oder nach rechts verschieben. 01:08:09.140 --> 01:08:16.380 Und dann merkt sich natürlich noch M' in welchem Zustand sich M gerade 01:08:16.380 --> 01:08:16.820 befindet. 01:08:16.820 --> 01:08:22.200 Und dann im dritten Schritt läuft M' einfach wieder komplett nach 01:08:22.200 --> 01:08:27.040 links zur linkesten Raute und geht somit in die Ausgangsposition für 01:08:27.040 --> 01:08:29.180 den nächsten Berechnungsschritt. 01:08:30.120 --> 01:08:32.700 Und dementsprechend hat man T plus 1. 01:08:33.700 --> 01:08:38.620 Die Frage ist natürlich, ist das alles... also die Transformation 01:08:38.620 --> 01:08:42.500 selber, also so können wir M simulieren mit M'. 01:08:42.500 --> 01:08:45.420 Aber die Frage ist natürlich, halten wir auch die Schranken ein, die 01:08:45.420 --> 01:08:46.360 wir versprochen haben. 01:08:46.880 --> 01:08:49.540 Und die Antwort ist ja, die halten wir ein. 01:08:51.300 --> 01:08:55.040 Was wir wissen ist, dass T von N beschränkt die Breite des 01:08:55.040 --> 01:08:56.860 betrachteten Bandes von M'. 01:08:56.860 --> 01:09:02.200 Also die Spuren sind immer nur so breit, wie entsprechend die Bänder 01:09:02.200 --> 01:09:04.500 breit sind von M'. 01:09:05.320 --> 01:09:11.480 Das heißt, in jedem Rechenschritt können wir M simulieren in O von T 01:09:11.480 --> 01:09:12.320 von N Zeit. 01:09:13.280 --> 01:09:18.060 Und da wir T von N viele Rechenschritte haben, bekommen wir jetzt eben 01:09:18.060 --> 01:09:20.260 eine quadratische Laufzeit für M'. 01:09:22.960 --> 01:09:26.640 Für den Speicherverbrauch gilt im Prinzip das gleiche. 01:09:26.740 --> 01:09:29.100 Wir werden nicht breiter als die einzelnen Bänder. 01:09:30.680 --> 01:09:34.380 Dementsprechend kriegen wir nun im konstanten Faktor mehr Speicher. 01:09:34.640 --> 01:09:38.680 Also der Speicher wächst nicht mit der Eingabe, sondern einfach mit 01:09:38.680 --> 01:09:39.540 der Anzahl der Bänder. 01:09:39.720 --> 01:09:41.340 Aber dies ist fest vorgegeben. 01:09:43.140 --> 01:09:47.340 Und dementsprechend haben wir im Prinzip nicht mehr Speicher in der 01:09:47.340 --> 01:09:47.840 Unutation. 01:09:49.100 --> 01:09:50.880 Also asymptotisch haben wir nicht mehr Speicher. 01:09:52.820 --> 01:09:55.140 So können wir im Prinzip weiter vorgehen. 01:09:55.140 --> 01:09:58.920 Die Frage ist, können wir noch andere Hilfsmittel uns konstruieren, 01:09:59.000 --> 01:10:00.140 zum Beispiel Unterprogramme. 01:10:01.660 --> 01:10:06.020 Wie würdet ihr Unterprogramme konstruieren mit einer Turing-Maschine? 01:10:07.540 --> 01:10:10.680 Also wenn ich es richtig verstanden habe, möchtest du im Prinzip eine 01:10:10.680 --> 01:10:13.900 Zwei -Band-Turing-Maschine aufbauen und dann wie einen Stack drauf. 01:10:14.780 --> 01:10:18.120 Also im Prinzip so ein Verhalten nachbauen, wie man es im Prinzip auch 01:10:18.120 --> 01:10:20.760 normalerweise kennt von Rechner-Modellen. 01:10:21.420 --> 01:10:23.260 Das ist im Prinzip das, was man machen kann. 01:10:27.380 --> 01:10:30.180 Also Unterprogramme werden natürlich in einem bestimmten Zustand 01:10:30.180 --> 01:10:30.820 aufgerufen. 01:10:31.000 --> 01:10:34.680 Und was man dann macht, ist, dass man zum Beispiel Daten übergibt als 01:10:34.680 --> 01:10:35.260 Eingabe. 01:10:35.440 --> 01:10:38.620 Das sind die Parameter, wie man es auch von Unterprogrammen kennt. 01:10:38.960 --> 01:10:42.180 Man kopiert dann entsprechend die Daten in den freien Bereich oder 01:10:42.180 --> 01:10:43.380 eben auf ein extra Band. 01:10:44.160 --> 01:10:45.580 Das ist im Prinzip egal. 01:10:46.360 --> 01:10:48.800 Und das begrenzt man vielleicht noch. 01:10:49.120 --> 01:10:53.020 Und was man dann noch macht, ist, man hat dann noch eine Teilmenge an 01:10:53.020 --> 01:10:54.580 Zuständen für dieses Unterprogramm. 01:10:54.580 --> 01:10:57.420 Und dann arbeitet die Turing-Maschine erstmal nur auf diesem einen 01:10:57.420 --> 01:10:58.020 Bereich. 01:10:58.280 --> 01:11:00.200 Arbeitet dieses Unterprogramm ab. 01:11:00.880 --> 01:11:05.140 Und danach gibt es einfach das Ergebnis zurück, in dem das Ergebnis in 01:11:05.140 --> 01:11:07.160 den reservierten Bereich reingeschrieben wird. 01:11:07.620 --> 01:11:12.240 Von der aufrufenden Turing-Maschine. 01:11:12.940 --> 01:11:18.240 Und dementsprechend kann dann der aufrufende Zustand darauf 01:11:18.240 --> 01:11:19.460 weiterarbeiten. 01:11:19.460 --> 01:11:22.440 Also es funktioniert wirklich jetzt im Prinzip wie in normalen 01:11:22.440 --> 01:11:23.400 Rechenarchitekturen. 01:11:23.520 --> 01:11:27.920 Da kann man sich jetzt so Konzepte überlegen, um im Prinzip Methoden 01:11:27.920 --> 01:11:30.260 zu haben, mit denen man leichter Turing-Maschinen bauen kann. 01:11:30.580 --> 01:11:32.620 Was man natürlich auch bauen kann, sind Schleifen. 01:11:33.520 --> 01:11:34.920 Wie würdet ihr Schleifen aufbauen? 01:11:50.260 --> 01:11:53.940 Schleifen sind nichts anderes als Unterprogramme, nur spezielle 01:11:53.940 --> 01:11:54.780 Unterprogramme. 01:11:56.360 --> 01:11:58.700 Nämlich mit bestimmten Abbruchkriterien. 01:11:58.700 --> 01:12:02.400 Also man hat dann so typische Aufgaben, die halt noch erledigt werden 01:12:02.400 --> 01:12:02.640 müssen. 01:12:02.820 --> 01:12:05.480 Es müssen entsprechende Zähler vergrößert werden, wenn es zum Beispiel 01:12:05.480 --> 01:12:06.580 eine Vorschleife ist. 01:12:06.940 --> 01:12:08.100 Oder verkleinert werden. 01:12:08.180 --> 01:12:10.680 Es müssen Abbruchbedingungen überprüft werden. 01:12:10.760 --> 01:12:13.260 Und es muss dann halt noch ein anderes Unterprogramm aufgerufen 01:12:13.260 --> 01:12:15.080 werden, das die eigentliche Arbeit macht. 01:12:15.400 --> 01:12:19.600 Aber im Prinzip kann ich dadurch auch das Ganze wieder mit 01:12:19.600 --> 01:12:20.720 Unterprogrammen erledigen. 01:12:20.920 --> 01:12:24.440 Und ich kriege dann dadurch wieder ein Werkzeug für Turing-Maschinen, 01:12:24.540 --> 01:12:26.600 mit denen ich weiterarbeiten kann. 01:12:28.700 --> 01:12:32.860 Dann würde ich noch in den letzten 10 Minuten so einen Grobüberflug 01:12:32.860 --> 01:12:34.280 über Entscheidbarkeit machen. 01:12:35.160 --> 01:12:37.260 Und universelle Turing-Maschinen. 01:12:38.760 --> 01:12:43.400 Was ihr kennengelernt habt, ist die Definition für entscheidbare 01:12:43.400 --> 01:12:45.640 Sprachen und semi-entscheidbare Sprachen. 01:12:46.100 --> 01:12:49.740 Bei semi-entscheidbaren Sprachen ist die Idee, dass es eine Turing 01:12:49.740 --> 01:12:54.440 -Maschine gibt, die, wenn ich dir ein Wort aus der Sprache gebe, dann 01:12:54.440 --> 01:12:57.680 wird die irgendwann enden und sagen, ja dieses Wort gehört zu der 01:12:57.680 --> 01:12:58.120 Sprache. 01:12:59.200 --> 01:13:04.020 Aber es kann sein, dass wenn ich ein Wort eingebe, das nicht zu der 01:13:04.020 --> 01:13:07.740 Sprache gehört, dann wird es passieren, dass entweder die Turing 01:13:07.740 --> 01:13:11.520 -Maschine unendlich lang läuft oder ein Fehlerzustand geht. 01:13:13.520 --> 01:13:18.060 Und bei der Entscheidbarkeit versteht man es darunter, dass man sagt, 01:13:18.180 --> 01:13:22.880 eine Sprache ist entscheidbar, wenn es eine Turing-Maschine gibt, die 01:13:22.880 --> 01:13:27.960 auf allen Eingaben zumindest stoppt und dann sagt, das Wort ist in der 01:13:27.960 --> 01:13:29.640 Sprache oder ist es nicht in der Sprache. 01:13:29.740 --> 01:13:31.560 Also eine wirklich klare Entscheidung liefert. 01:13:31.900 --> 01:13:35.760 Während semi-Entscheidbarkeit einfach bedeutet, wenn das Wort in der 01:13:35.760 --> 01:13:38.020 Sprache ist, kriege ich eine klare Entscheidung, nämlich ja. 01:13:38.020 --> 01:13:41.920 Und ansonsten läuft es zum Beispiel unendlich weiter. 01:13:42.240 --> 01:13:45.760 Aber es wird natürlich nicht fehlerhaft ja sagen, das passiert nicht. 01:13:48.340 --> 01:13:51.300 Was ihr auch noch kennengelernt habt, ist die Gödel-Nummer. 01:13:52.020 --> 01:13:56.420 Das ist im Prinzip eine Kodierung von Turing-Maschinen. 01:13:56.520 --> 01:13:59.460 Was man macht, ist man bildet im Prinzip eine Turing-Maschine auf 01:13:59.460 --> 01:14:00.580 Einsen und Nullen ab. 01:14:01.340 --> 01:14:04.920 Wie man das sehen kann, ist im Prinzip eine Kodierung von Turing 01:14:04.920 --> 01:14:06.840 -Maschinen als ein Binärwort. 01:14:06.840 --> 01:14:10.560 Sprich, das ist der binäre Programm-Code einer Turing-Maschine. 01:14:10.720 --> 01:14:15.340 Also das, was sehr ähnlich zu dem, was man hat, wenn man im Prinzip 01:14:15.340 --> 01:14:17.640 ein Programm schreibt, dann wird das auch in einen Binär-Code 01:14:17.640 --> 01:14:18.440 umgewandelt. 01:14:18.700 --> 01:14:19.860 Das entspricht ungefähr dem. 01:14:20.880 --> 01:14:25.200 Und die Idee ist jetzt, dass man eine universelle Turing-Maschine 01:14:25.200 --> 01:14:29.820 ausführt und diese universelle Turing-Maschine simuliert eine gegebene 01:14:29.820 --> 01:14:32.140 Turing -Maschine, die ich als Programm-Code habe. 01:14:32.140 --> 01:14:38.560 Sprich, ich habe eine universelle Turing-Maschine als Interpret für 01:14:38.560 --> 01:14:39.740 andere Turing-Maschinen. 01:14:40.520 --> 01:14:45.320 Wenn ich mir das bildlich vorstelle, kann man das vielleicht so sagen, 01:14:45.400 --> 01:14:48.980 dass man sagt, ich habe eine spezielle Turing-Maschine M, die macht 01:14:48.980 --> 01:14:52.360 zum Beispiel die Addition zweier Zahlen, die kann ich umwandeln in 01:14:52.360 --> 01:14:53.180 einen Binär-Code. 01:14:53.580 --> 01:14:56.300 Ich habe jetzt noch diese universelle Turing-Maschine, die simuliert 01:14:56.300 --> 01:14:56.560 M. 01:14:59.020 --> 01:15:04.060 Und der gebe ich im Prinzip diese spezielle Turing-Maschine und dann 01:15:04.060 --> 01:15:06.820 aber auch noch die Eingabe für diese spezielle Turing-Maschine, 01:15:07.040 --> 01:15:10.880 nämlich 5 und 5 zum Beispiel und kriege dann am Schluss das Ergebnis 01:15:10.880 --> 01:15:11.280 raus. 01:15:12.280 --> 01:15:16.120 Und das war ein relativ starkes Hilfsmittel, um nachher Beweise zu 01:15:16.120 --> 01:15:16.360 führen. 01:15:16.760 --> 01:15:21.600 Das werdet ihr auch auf dem Übungsblatt brauchen, um entsprechend die 01:15:21.600 --> 01:15:26.680 Beweise führen zu können, weil man einfach immer so diesen Trick hat 01:15:26.680 --> 01:15:29.760 in dem Beweis, man simuliert eine Turing-Maschine oder man simuliert 01:15:29.760 --> 01:15:33.580 mehrere Turing-Maschinen und versucht dann daraus eine Aussage zu 01:15:33.580 --> 01:15:33.880 treffen. 01:15:35.660 --> 01:15:40.840 Eine sehr schöne Aussage ist im Prinzip der Satz von Weiss. 01:15:41.580 --> 01:15:46.760 Zum Beispiel nehmen wir an, wir haben Verifikationsprogramm M und wir 01:15:46.760 --> 01:15:50.260 haben noch ein beliebiges Programm M' als Eingabe und noch die 01:15:50.260 --> 01:15:53.380 Bedingungen für die Korrektheit von M'. 01:15:53.380 --> 01:15:57.920 Und was wir jetzt machen ist, die universelle Turing-Maschine nimmt 01:15:57.920 --> 01:16:04.120 eben diese zwei Programme, simuliert im Prinzip M auf M', also M 01:16:04.120 --> 01:16:09.280 überprüft, ob M' korrekt ist und sagt dann ja oder nein. 01:16:09.500 --> 01:16:11.980 Also entweder das Programm ist korrekt oder nicht korrekt. 01:16:12.520 --> 01:16:16.880 Und die Frage ist, kann es so eine Turing-Maschine wirklich geben, die 01:16:16.880 --> 01:16:18.200 das auf jeder Eingabe macht? 01:16:21.100 --> 01:16:22.680 Und was ist die Antwort? 01:16:39.140 --> 01:16:41.360 Ja genau, also das ist irgendwie so ein Widerspruch. 01:16:41.520 --> 01:16:45.320 Man im Prinzip M müsste zum Beispiel es schaffen können, von sich 01:16:45.320 --> 01:16:47.840 selbst die Korrektheit zu zeigen, was ja irgendwie blöd ist, wenn es 01:16:47.840 --> 01:16:48.480 nicht korrekt ist. 01:16:50.100 --> 01:16:54.660 Es führt zu einem Widerspruch und das ist dann im Prinzip das, was ihr 01:16:54.660 --> 01:16:58.200 auch über Diagonalsprachen gemacht habt, da im Prinzip das Ganze 01:16:58.200 --> 01:16:58.680 formal. 01:16:59.240 --> 01:17:03.260 Aber was man im Prinzip insgesamt zeigen kann, ist dann der Satz von 01:17:03.260 --> 01:17:06.100 Weiss, der das im Prinzip zusammenfasst. 01:17:08.020 --> 01:17:12.440 Und der sagt jetzt im Prinzip, wenn wir die Menge der berechenbaren 01:17:12.440 --> 01:17:15.400 Funktionen anschauen, also von Turing-Maschinen berechenbaren 01:17:15.400 --> 01:17:18.380 Funktionen anschauen, und da irgendwie eine nicht-triviale Menge 01:17:18.380 --> 01:17:22.400 rauswählen, also zum Beispiel sagen, naja, wie ist das eigentlich? 01:17:22.500 --> 01:17:26.680 Gibt es ein Programm, das die Korrektheit von einem beliebigen 01:17:26.680 --> 01:17:27.860 Programm berechnen kann? 01:17:28.620 --> 01:17:33.240 Dann sagt der Satz von Reiss, das geht eben nicht. 01:17:33.660 --> 01:17:37.820 Wenn wir uns dann die entsprechende Sprache anschauen, also sprich 01:17:37.820 --> 01:17:43.640 alle Programme, die zum Beispiel korrekt sind, dann kann es keine 01:17:43.640 --> 01:17:49.640 Turing -Maschine geben, die entscheidet, ob ein anderes Programm in 01:17:49.640 --> 01:17:51.120 dieser Sprache liegt oder nicht. 01:17:52.000 --> 01:17:56.500 Und das ist ein relativ starker Satz, weil man so Sachen machen kann, 01:17:56.640 --> 01:18:01.400 wie oder sagen kann, dass es kein Programm geben kann, das die 01:18:01.400 --> 01:18:05.560 Terminierung für alle Programme beweist oder eben beweist, dass es 01:18:05.560 --> 01:18:08.420 nicht terminiert oder terminiert, dieses gegebene Programm. 01:18:10.060 --> 01:18:12.880 Man muss natürlich so ein bisschen aufpassen, das ist eine sehr 01:18:12.880 --> 01:18:13.960 allgemeine Aussage. 01:18:15.320 --> 01:18:19.640 Was man immer als Eingabe zum Beispiel hat, ist, man schaut sich ein 01:18:19.640 --> 01:18:22.820 Programm an, das Korrektheit von einem anderen Programm beweisen kann 01:18:22.820 --> 01:18:28.820 und das gilt jetzt für jedes beliebige, also die Aussage ist, es gibt 01:18:28.820 --> 01:18:34.360 kein Programm M, das für jedes beliebige Programm M' entscheiden kann, 01:18:34.460 --> 01:18:35.480 ob es korrekt ist oder nicht. 01:18:35.480 --> 01:18:40.780 Aber natürlich kann es sein, dass das Programm so speziell ist, dass 01:18:40.780 --> 01:18:43.740 man auf Korrektheit prüfen will, dass es da schon noch geht. 01:18:43.840 --> 01:18:47.300 Aber im Allgemeinen geht es eben nicht, nur manchmal im Speziellen. 01:18:48.460 --> 01:18:54.360 Das heißt, das ist eine sehr allgemeine Aussage erstmal, die man dann 01:18:54.360 --> 01:18:56.680 entsprechend interpretieren muss. 01:18:59.440 --> 01:19:05.360 Der letzte Beweis ist der Hinweis auf dem Übungsblatt, den ihr am 01:19:05.360 --> 01:19:06.340 Montag abgeben müsst. 01:19:08.900 --> 01:19:13.400 Der Satz sagt, dass eine Sprache L genau dann entscheidbar ist, wenn L 01:19:13.400 --> 01:19:16.440 und deren Kompliment LC semi-entscheidbar ist. 01:19:17.880 --> 01:19:20.600 Der wird häufiger auf dem Übungsblatt gebraucht. 01:19:21.080 --> 01:19:22.820 Weiß jemand, wie man den Satz beweist? 01:19:42.330 --> 01:19:46.970 Der Beweis ist an sich nicht schwierig und liefert einem auch schon 01:19:46.970 --> 01:19:49.870 einen Hinweis, wie man das auch für andere Aufgaben machen kann. 01:19:50.290 --> 01:19:52.870 Was man nämlich macht, ist, man schaut sich einfach... 01:19:52.870 --> 01:19:57.630 Dadurch, dass beide Sprachen L und LC semi-entscheidbar sind, weiß 01:19:57.630 --> 01:20:01.750 man, es gibt eine Turing-Maschine M1, die L erkennt, und eine Turing 01:20:01.750 --> 01:20:04.970 -Maschine M2, die das Kompliment erkennt. 01:20:05.450 --> 01:20:08.570 Und was man jetzt einfach macht, ist, man lässt beide Turing-Maschinen 01:20:08.570 --> 01:20:10.910 gleichzeitig laufen, also man simuliert die z.B. 01:20:11.010 --> 01:20:14.190 mit einer universellen Turing-Maschine und lässt beide gleichzeitig 01:20:14.190 --> 01:20:20.410 laufen und meint einfach, dass man das Schritt für Schritt arbeitet. 01:20:21.210 --> 01:20:24.290 Also einmal einen Schritt für die eine Turing-Maschine, dann einen 01:20:24.290 --> 01:20:27.070 Schritt für die andere Turing-Maschine und es so immer weiter macht. 01:20:27.690 --> 01:20:33.050 Und jetzt weiß man, dass eine von beiden auf alle Fälle terminieren 01:20:33.050 --> 01:20:39.750 wird, weil jedes Wort entweder in L oder in LC drin liegt. 01:20:40.350 --> 01:20:44.910 Das heißt, entweder M1 wird terminieren und sagen, das Wort liegt in L 01:20:44.910 --> 01:20:48.250 oder M2 wird terminieren und sagen, das Wort liegt in LC. 01:20:48.910 --> 01:20:52.750 Und dadurch, dass ich das parallel mache, weiß ich, dass die gesamte 01:20:52.750 --> 01:20:56.870 Turing -Maschine M irgendwann terminieren wird und sagen wird, okay, 01:20:56.950 --> 01:20:58.410 das liegt in L oder in LC. 01:20:59.030 --> 01:21:01.330 Und das ist im Prinzip die Idee von dem Beweis. 01:21:03.850 --> 01:21:07.650 Und den Hinweis kann man dann aber relativ gut verwenden. 01:21:07.650 --> 01:21:10.250 Dann ist das das letzte Inhaltliche für heute.