WEBVTT 00:05.040 --> 00:09.200 Herzlich Willkommen zur Vorlesung Theoretische Grundlagen der 00:09.200 --> 00:10.200 Informatik. 00:10.940 --> 00:13.380 Mittlerweile könnten Sie mich eventuell kennen. 00:13.520 --> 00:17.140 Ich bin Thorsten Hückert und ich vertrete Professor Wagner 00:17.140 --> 00:18.620 ausnahmsweise. 00:20.980 --> 00:22.980 Okay, was machen wir heute? 00:23.520 --> 00:26.940 Wir gehen einer Frage nach und werden diese Frage heute auch komplett 00:26.940 --> 00:31.380 beantworten und die Frage sollte sich aus dem ergeben, was Sie letzte 00:31.380 --> 00:35.020 Woche kennengelernt haben, nämlich dem Äquivalenzklassenautomaten. 00:36.100 --> 00:40.180 Und das war eine Methode, um einen deterministischen endlichen 00:40.180 --> 00:42.260 Automaten zu verkleinern. 00:42.900 --> 00:47.960 Einen kleineren deterministischen endlichen Automaten daraus zu 00:47.960 --> 00:52.340 konstruieren, der, wenn man Glück hat, weniger Zustände hat. 00:53.220 --> 00:57.080 Okay, und dazu hatten wir uns definiert, dass Zustände äquivalent 00:57.080 --> 01:00.080 sind, also eigentlich das gleiche tun und dann ist die Idee, dass man 01:00.080 --> 01:01.340 einen davon einsparen kann. 01:02.100 --> 01:06.740 Okay, und dann ist die natürliche Frage, die man sich stellt, wenn ich 01:06.740 --> 01:10.000 damit meine Zustände reduzieren kann, super, wenn ich meine Zustände 01:10.000 --> 01:14.600 damit aber nicht mehr reduzieren kann, geht es vielleicht anders, 01:15.100 --> 01:17.580 meine Zustände zu reduzieren, die Anzahl der Zustände. 01:18.120 --> 01:22.880 Okay, oder ist es vielleicht so, dass der Äquivalenzklassenautomat zu 01:22.880 --> 01:27.140 dem gegebenen deterministischen endlichen Automaten schon derjenige 01:27.140 --> 01:31.420 ist mit den minimalen Anzahl von Zuständen. 01:31.680 --> 01:36.500 Okay, schon mal ein kleiner Spoiler-Alert, also heute wird das Wort 01:36.500 --> 01:42.740 äquivalent extrem oft benutzt werden und nicht immer bezieht es sich, 01:42.840 --> 01:46.820 also es heißt immer das gleiche, gleichbedeutend, äquivalent, 01:46.940 --> 01:53.160 gleichwertig, aber wir wir vergleichen verschiedene Arten von Objekten 01:53.160 --> 01:53.460 dort. 01:54.020 --> 01:58.140 Hier zum Beispiel reden wir davon, dass es der äquivalente Automat 01:58.140 --> 02:03.040 ist, das ist also gleichbedeutend unter Automaten, was einfach heißt, 02:03.100 --> 02:04.980 sie akzeptieren die gleiche Sprache. 02:06.900 --> 02:11.440 Und in der Definition des Äquivalenzautomaten haben wir schon die 02:11.440 --> 02:14.720 Äquivalenz von Zuständen, das ist also gleichbedeutend und der Welt 02:14.720 --> 02:15.680 der Zustände. 02:16.820 --> 02:20.960 Und wir werden heute noch eine andere Form von Äquivalenz sehen, 02:21.120 --> 02:23.080 nämlich gleichbedeutend in der Welt von Wörtern. 02:23.900 --> 02:26.720 Okay, es könnte also ein bisschen verwirrend sein, ich versuche da ein 02:26.720 --> 02:31.260 bisschen darauf hinzuweisen, wann wir über welche Sachen sprechen, 02:31.760 --> 02:34.820 aber Äquivalenz wird oft auftreten. 02:35.680 --> 02:41.560 Okay, also ist der Äquivalenzklassenautomat eines gegebenen DEA der 02:41.560 --> 02:46.340 äquivalente Automat mit der kleinsten Anzahl Zuständen, kleinsten 02:46.340 --> 02:47.480 möglichen Anzahl Zustände. 02:48.320 --> 02:51.140 Okay, das ist die Frage, der wir heute nachgehen wollen und ich 02:51.140 --> 02:52.440 verrate schon mal die Antwort. 02:52.820 --> 02:57.740 Ja, okay, aber warum? 02:58.360 --> 03:02.300 Okay, und das Warum beschäftigt uns natürlich die ganze Weile. 03:02.840 --> 03:06.720 Wir werden das beweisen und wir werden das in zwei Schritten machen. 03:06.860 --> 03:10.400 Wir werden erstmal etwas ganz anderes tun und erst ganz am Ende wieder 03:10.400 --> 03:12.420 auf den Äquivalenzklassenautomaten zu sprechen kommen. 03:12.960 --> 03:18.040 Okay, das ganz andere was wir tun werden ist, wir werden einen anderen 03:18.040 --> 03:21.620 Automaten konstruieren, der gar nichts mit unserem ersten Automaten zu 03:21.620 --> 03:26.800 tun hat, sondern der einfach abhängt von der Sprache, die akzeptiert 03:26.800 --> 03:28.040 wird von dem ersten Automaten. 03:28.320 --> 03:31.080 Also wir gucken uns nur die Sprache an, unabhängig davon wie unser 03:31.080 --> 03:32.740 erster Automat aussieht. 03:33.240 --> 03:38.220 Einfach die Sprache L und zu dieser Sprache L konstruieren wir einen 03:38.220 --> 03:42.460 kleinstmöglichen Automaten und der wird der sogenannte Automat der 03:42.460 --> 03:43.880 Nerode -Relation sein. 03:44.620 --> 03:49.320 Okay, zu einem Überfluss ist das eine Äquivalenzrelation. 03:50.000 --> 03:52.140 Das ist diese dritte Äquivalenz, die ich meinte. 03:53.180 --> 03:56.180 Dann haben wir also einen kleinsten Automaten und dann besinnen wir 03:56.180 --> 04:00.640 uns zurück auf unsere original Frage und vergleichen jetzt diesen 04:01.640 --> 04:06.540 Äquivalenzklassenautomat aus der letzten Vorlesung mit diesem von aus 04:06.540 --> 04:12.660 der Nerode-Relation und zeigen, dass der hier nicht mehr Zustände als 04:12.660 --> 04:13.300 der da hat. 04:14.100 --> 04:16.040 Okay, und damit wissen wir, dass also auch unser 04:16.040 --> 04:20.180 Äquivalenzklassenautomat minimale Anzahl Zustände hat. 04:20.700 --> 04:27.900 Okay, gut, nochmal zur Wiederholung des Äquivalenzklassenautomates, 04:28.020 --> 04:32.060 auch wenn wir es gleich nicht so richtig brauchen, weil wir erstmal 04:32.060 --> 04:35.380 über diese Nerode-Relation reden, trotzdem jetzt nochmal zur 04:35.380 --> 04:38.160 Wiederholung aus der letzten Vorlesung, was sind die wichtigsten 04:38.160 --> 04:39.240 Begriffe. 04:39.780 --> 04:44.460 Also das Erste ist, wir definieren uns eine Äquivalenz auf der Menge 04:44.460 --> 04:46.980 der Zustände eines gegebenen DEA. 04:48.240 --> 04:53.820 Wir sagen zwei Zustände sind äquivalent, wenn der DEA in diesen beiden 04:53.820 --> 05:01.960 Zuständen ist und dann, wenn er die gleichen Wörter liest, also für 05:01.960 --> 05:05.840 jedes Wort W, wenn ich jetzt losgehe von diesem Zustand P und dann W 05:05.840 --> 05:10.140 lese oder wenn ich von Zustand Q losgehe und W lese, dann ist das für 05:10.140 --> 05:13.720 das Akzeptanzverhalten unwichtig, ob ich jetzt in P oder in Q 05:13.720 --> 05:14.460 gestartet bin. 05:14.800 --> 05:19.200 Okay, und das Akzeptanzverhalten ist natürlich dadurch definiert, ob 05:19.200 --> 05:22.920 diese diese Übergangsfunktion letztendlich in F landet oder nicht. 05:23.360 --> 05:28.280 Also ich sage, ich lande von P aus, durch Lesen von W in F, genau 05:28.280 --> 05:32.780 dann, wenn ich von Q aus, durch Lesen von W in F lande. 05:34.100 --> 05:36.560 Das heißt, wenn ich erstmal da einmal hingekommen bin zu diesen 05:36.560 --> 05:39.720 Zuständen P und Q, ist es für mich eigentlich egal, ob ich jetzt in P 05:39.720 --> 05:40.440 oder Q bin. 05:42.140 --> 05:44.780 Das soll heißen, dass die beiden Zustände äquivalent sind. 05:46.680 --> 05:51.600 Kleiner technischer Caveat ist, P und Q sollten überhaupt erreichbare 05:51.600 --> 05:52.540 Zustände sein. 05:53.780 --> 05:58.740 Das ist irgendwie intuitiv klar, dass also was wir am allerersten 05:58.740 --> 06:01.200 Schritt tun ist, wir schmeißen erstmal alle Zustände weg, die 06:01.200 --> 06:02.220 überhaupt nicht erreichbar sind. 06:02.760 --> 06:07.040 Also die gar nicht von S aus durch irgendeine Abfolge des Automatens 06:07.040 --> 06:08.700 erreicht werden können. 06:08.880 --> 06:11.940 Okay, also wenn P und Q beide erreichbar sind, dann ist das die 06:11.940 --> 06:13.240 Definition der Äquivalenz. 06:14.060 --> 06:19.740 Gut, jetzt können ganze Zustandsmengen äquivalent sein. 06:21.020 --> 06:26.520 Und insbesondere bildet diese Relation eine Äquivalenzrelation. 06:27.340 --> 06:32.100 Also wenn jeder Zustand ist zu sich selbst äquivalent, wenn A 06:32.100 --> 06:35.620 äquivalent zu B ist und B äquivalent zu C ist, dann ist auch A 06:35.620 --> 06:36.540 äquivalent zu C. 06:37.200 --> 06:40.660 Das sind die Sachen, die man nachprüfen müsste rein formal, um eine 06:40.660 --> 06:42.040 Äquivalenzrelation zu überprüfen. 06:42.340 --> 06:45.180 Das werden wir heute nie so richtig formal tun. 06:45.840 --> 06:49.360 Ich gehe davon aus, dass das alles halbwegs einleuchtend ist, dass das 06:49.360 --> 06:50.400 eine Äquivalenzrelation ist. 06:51.060 --> 06:51.940 Okay, gut. 06:52.420 --> 06:58.700 Also diese Relation lässt unsere Zustandsmenge zerfallen in 06:58.700 --> 06:59.620 Äquivalenzklassen. 07:00.540 --> 07:03.880 Okay, indem wir einfach sagen, okay, das sind die gleichen oder 07:03.880 --> 07:05.780 gleichartig, die die Äquivalenz sind. 07:06.100 --> 07:08.920 Eventuell ist ein Zustand nur alleine in seiner Äquivalenzklasse. 07:09.360 --> 07:11.700 Aber eventuell hat so eine Äquivalenzklasse auch 100 Zustände. 07:13.660 --> 07:13.940 Gut. 07:14.740 --> 07:20.400 Die sind aber natürlich alle endlich die Klassen, weil der DEA endlich 07:20.400 --> 07:21.260 viele Zustände hat. 07:21.580 --> 07:26.600 Und es ist immer so, dass wir die Äquivalenzklasse, die den Zustand P 07:26.600 --> 07:30.680 enthält, so mit eckigen Klammern P bezeichnen. 07:30.820 --> 07:35.080 Also eckige Klammer P ist das gleiche wie eckige Klammer Q, genau 07:35.080 --> 07:36.780 dann, wenn P äquivalent zu Q ist. 07:37.300 --> 07:40.880 Das ist sozusagen ein Repräsentant aus der Klasse, aber welcher ist 07:40.880 --> 07:41.000 es? 07:41.380 --> 07:43.920 Es ist sozusagen gegeben, den Zustand, was ist die Klasse dazu? 07:44.700 --> 07:44.860 Gut. 07:46.160 --> 07:51.560 Das ist diese Äquivalenzklassenzerlegung eines DEA und dazu haben wir 07:51.560 --> 07:53.880 uns jetzt einen Automaten definiert, in dem wir einfach gesagt haben, 07:54.000 --> 07:59.020 okay, wir identifizieren Zustände, die äquivalent sind, zu einem 07:59.020 --> 07:59.540 Zustand. 08:00.280 --> 08:02.880 Also formal gesehen ist unsere Zustandsmenge des 08:02.880 --> 08:09.100 Äquivalenzklassenautomats die Klassen, die Äquivalenzklassen des 08:09.100 --> 08:10.020 ersten Automats. 08:10.680 --> 08:13.740 Okay, in dem wir einfach gesagt haben, okay, das ist die Klasse 1, 08:13.940 --> 08:15.220 Klasse 2, Klasse S. 08:17.720 --> 08:20.560 Dementsprechend ist unser Startzustand auch die Klasse, die den 08:20.560 --> 08:21.460 Startzustand enthält. 08:23.380 --> 08:27.900 Und dann das Alphabet ist das gleiche, die Endzustände sind halt auch 08:27.900 --> 08:32.080 einfach nur unter Äquivalenzklassen abgeschlossen und die 08:32.080 --> 08:35.260 Übergangsfunktion tut das, was man erwartet. 08:35.800 --> 08:40.680 Wenn ich von Klasse 1 A lese, dann ist es egal, wo ich in Klasse 1 bin 08:40.680 --> 08:43.400 und A lese, die sind ja schließlich äquivalent, also wähle ich mir 08:43.400 --> 08:46.440 einfach irgendeinen Repräsentanten aus, lese von dem A, gucke in 08:46.440 --> 08:52.980 welcher Klasse ich lande, das ist die Klasse, wo dieses Delta 08:52.980 --> 08:53.580 hinführt. 08:54.540 --> 09:00.340 Gut, also, das war die Wiederholung von letzter Woche. 09:00.760 --> 09:06.000 Nochmal beachte, hier rede ich die ganze Zeit über Äquivalenz und 09:06.000 --> 09:08.680 Zuständen eines DEA. 09:11.040 --> 09:16.400 Wir haben dann gezeigt, letzte Woche, dass dieser neue Automat, der 09:16.400 --> 09:21.260 hier, äquivalent ist zu dem alten Automat. 09:21.320 --> 09:25.020 Das ist jetzt ein anderes Äquivalent, das ist ein Äquivalenzbegriff, 09:25.180 --> 09:26.240 der Automaten vergleicht. 09:27.580 --> 09:31.040 Und da heißt Äquivalent sein, sie akzeptieren dieselbe Sprache. 09:31.980 --> 09:42.840 Gut, also, soweit so gut, jetzt aber erst mal diesen kleinen Umweg, 09:43.300 --> 09:49.440 und zwar reden wir jetzt über etwas, das ist eine Äquivalenzrelation R 09:49.440 --> 09:57.920 auf Sigma Stern, auf der Menge aller Wörter über dem Alphabet Sigma. 09:58.820 --> 10:01.540 Okay, also jetzt will ich was völlig Neues mir angucken. 10:01.640 --> 10:05.080 Ich möchte wissen, ein Äquivalenzbegriff, der einfach Wörter 10:05.080 --> 10:05.620 gruppiert. 10:05.800 --> 10:11.000 Sagt, das Wort ist äquivalent, was auch immer das heißen mag, zu einem 10:11.000 --> 10:11.640 anderen Wort. 10:12.440 --> 10:15.120 Okay, und alles, was ich jetzt erst mal will, ist mir, ich gucke mir 10:15.120 --> 10:18.540 an, irgendjemand gibt mir so eine Äquivalenzrelation R. 10:21.940 --> 10:24.980 Also, er sagt mir zu je zwei Wörter, ob sie jetzt äquivalent sind oder 10:24.980 --> 10:26.340 nicht, und das ist eine Äquivalenzrelation. 10:26.520 --> 10:29.420 Also, jedes Wort ist zu sich selbst äquivalent und das ist transitiv. 10:30.520 --> 10:35.480 Gut, und dann möchte ich wissen, ob diese Äquivalenzrelation 10:35.480 --> 10:37.020 rechtsinvariant ist. 10:37.560 --> 10:39.940 Okay, und das ist die Definition von rechtsinvariant. 10:40.540 --> 10:45.200 Rechtsinvariant heißt, wenn ich zwei Wörter habe, egal welche Wörter, 10:45.300 --> 10:52.080 x, y, und die sind äquivalent, das ist die Schreibweise, also x steht 10:52.080 --> 10:53.160 in Relation zu y. 10:54.240 --> 10:57.340 R steht für Relation, das heißt, die beiden Wörter sind äquivalent. 10:57.420 --> 10:58.800 Vielleicht ist x dasselbe wie y. 10:59.340 --> 11:00.080 Vielleicht aber auch nicht. 11:00.660 --> 11:01.420 Die sind äquivalent. 11:03.180 --> 11:07.040 Also, wenn das so ist, wenn die äquivalent sind und R ist 11:07.040 --> 11:12.760 rechtsinvariant, dann gilt, egal was sich hinten für ein n daran 11:12.760 --> 11:18.680 hängt, z, ein anderes Wort, an x und an y, das ändert die Äquivalenz 11:18.680 --> 11:19.340 nicht. 11:20.000 --> 11:21.120 Die bleiben äquivalent. 11:22.800 --> 11:26.960 Also das ist trivial, wenn z das leere Wort ist, dann hat sich nämlich 11:26.960 --> 11:29.300 x und y noch nicht geändert, die sind immer noch äquivalent, aber wenn 11:29.300 --> 11:33.020 ich hinten einfach noch ein Symbol ranhänge, zum Beispiel, dann sind 11:33.020 --> 11:36.860 die beiden neuen Wörter, die sind jetzt beide eins länger, immer noch 11:36.860 --> 11:37.340 äquivalent. 11:37.980 --> 11:41.500 Und egal was ich hinten für ein String ranhänge, hinten ist hier, was 11:41.500 --> 11:44.660 ich hinten für ein String ranhänge, die bleiben äquivalent, wenn sie 11:44.660 --> 11:45.880 am Anfang äquivalent waren. 11:46.740 --> 11:50.040 Könnte sein, dass Sachen vorher nicht äquivalent waren, durch das 11:50.040 --> 11:53.160 Anhängen von Strings äquivalent werden, aber Äquivalenz wird nicht 11:53.160 --> 11:53.680 zerstört. 11:56.120 --> 11:56.220 Okay? 11:56.860 --> 11:57.140 Gut. 11:59.640 --> 12:06.820 Das ist der Begriff der Rechtsinvarianz einer Äquivalenzrelation auf 12:06.820 --> 12:08.180 der Menge aller Wörter. 12:09.540 --> 12:14.060 Wir sehen ein Beispiel, ja doch, machen wir sofort die paar Beispiele. 12:14.200 --> 12:16.200 Also ich habe einfach mal drei Beispiele hier reingemacht. 12:17.340 --> 12:21.340 R1 sei jetzt mal die Relation, die die beiden Wörter nimmt und 12:21.340 --> 12:23.220 vergleicht, ob sie dasselbe erste Zeichen. 12:25.600 --> 12:26.160 Okay? 12:27.360 --> 12:31.060 Also zwei Wörter sind äquivalent, wenn beide mindestens ein Zeichen 12:31.060 --> 12:33.620 haben und das erste ist dasselbe. 12:34.100 --> 12:39.240 Das ist eine Äquivalenzrelation, das sieht man relativ leicht ein und 12:39.240 --> 12:43.860 jetzt überprüfen wir mal, ob diese Äquivalenzrelation rechtsinvariant 12:43.860 --> 12:44.260 ist. 12:45.220 --> 12:49.260 Wenn ich zwei Wörter habe, die sind äquivalent, das heißt sie haben 12:49.260 --> 12:53.040 dasselbe erste Zeichen und ich hänge jetzt an beide Wörter das gleiche 12:53.040 --> 12:56.840 hinten ran, dann sind die entstehenden Wörter haben immer noch vorne 12:56.840 --> 12:58.360 dasselbe erste Zeichen. 13:00.060 --> 13:00.520 Okay? 13:01.560 --> 13:03.700 Das heißt, die bleiben äquivalent. 13:04.580 --> 13:05.260 Okay? 13:05.680 --> 13:08.180 Also R1 ist rechtsinvariant. 13:09.740 --> 13:10.420 Gut. 13:11.700 --> 13:13.160 Gucken wir uns R2 an. 13:13.240 --> 13:18.840 R2 heißt, ist eine andere Äquivalenzrelation, zum Beispiel x und y 13:18.840 --> 13:22.100 sind äquivalent, wenn sie dasselbe letzte Zeichen haben. 13:23.880 --> 13:24.560 Okay? 13:25.020 --> 13:27.740 Also zwei Wörter sind äquivalent, wenn beide mindestens ein Zeichen 13:27.740 --> 13:30.080 haben und das letzte von beiden ist dasselbe. 13:31.240 --> 13:33.700 Gucke ich mir wieder an, ist das rechtsinvariant. 13:34.440 --> 13:39.860 Ich habe zwei Wörter, die haben dasselbe letzte Zeichen, ich hänge an 13:39.860 --> 13:47.020 beide Wörter ein neues Wort z ran, dasselbe an beide Wörter und gucke 13:47.020 --> 13:49.940 mir jetzt die Äquivalenz von den beiden Wörtern an und jetzt sehe ich 13:49.940 --> 13:54.320 ja, die sind wieder äquivalent, weil jetzt wird verglichen das letzte 13:54.320 --> 13:57.660 Zeichen von den neuen, von dem angehängten z und das ist natürlich auf 13:57.660 --> 13:59.160 beiden Seiten das gleiche. 13:59.740 --> 14:00.260 Okay? 14:02.220 --> 14:06.020 Hier sieht man auch, das ist also sozusagen ein bisschen so ein 14:06.020 --> 14:11.220 anderer Grund, warum die rechtsinvariant ist, zum Beispiel hier in 14:11.220 --> 14:15.560 diesem R2 ist es so, dass eventuell vorher x und y nicht äquivalent 14:15.560 --> 14:19.340 waren und durch das Anhängen von z werden die automatisch äquivalent. 14:20.280 --> 14:24.460 Also ich kann neue Äquivalenzen kreieren durch dieses Anhängen, aber 14:24.460 --> 14:25.520 ich kann sie nicht zerstören. 14:29.560 --> 14:34.180 Gut, letzte Äquivalenzrelation R3 ist zwei Wörter werden äquivalent, 14:34.260 --> 14:36.780 wenn sie dasselbe vorletzte Zeichen haben. 14:37.200 --> 14:40.060 Okay, also sie sind äquivalent, wenn beide mindestens zwei Zeichen 14:40.060 --> 14:42.900 haben und das vorletzte ist bei beiden das gleiche. 14:44.280 --> 14:48.140 Okay, das ist wieder eine Äquivalenzrelation, das kann man auch wieder 14:48.140 --> 14:49.820 schnell einsehen. 14:49.820 --> 14:55.640 Jetzt ist aber die Sache, das ist eventuell oder das ist nicht 14:55.640 --> 14:57.060 rechtsinvariant. 14:57.760 --> 15:03.060 Okay, wenn ich zwei Wörter habe, die sind äquivalent, die haben 15:03.060 --> 15:06.920 dasselbe vorletzte Zeichen und ich hänge etwas ran, jetzt frage ich 15:06.920 --> 15:11.660 mich jetzt, haben diese beiden Wörter xz und yz dasselbe vorletzte 15:11.660 --> 15:12.060 Zeichen? 15:13.580 --> 15:21.680 Das ist wohl wahr, wenn z das leere Wort ist, wenn z mindestens zwei 15:21.680 --> 15:22.380 Zeichen hat. 15:23.440 --> 15:27.840 Wenn z nur ein Zeichen hat, könnte es immer noch wahr sein, wenn zum 15:27.840 --> 15:30.460 Beispiel x und y vorher dasselbe letzte Zeichen hatten. 15:31.120 --> 15:31.940 Weiß ich aber nicht. 15:32.860 --> 15:37.700 Wenn x und y vorher nicht dasselbe Zeichen hatten und z nur ein 15:37.700 --> 15:41.360 Zeichen hat, dann merke ich, jetzt habe ich eine Äquivalenz zerstört. 15:42.460 --> 15:44.460 Okay, das ist nicht rechtsinvariant. 15:46.600 --> 15:47.160 Gut. 15:48.540 --> 15:51.800 Das ist der Begriff der Rechtsinvarianz. 15:52.240 --> 15:55.340 Ein paar Beispielen und hoffentlich bekommen sie jetzt auch so langsam 15:55.340 --> 15:59.700 so ein Gefühl für Äquivalenzrelationen auf Wörter. 16:00.560 --> 16:05.020 Gut, jetzt mit den Äquivalenzrelationen kann man das Gleiche machen 16:05.020 --> 16:09.180 wie vorher mit den Zuständen. 16:09.400 --> 16:13.280 Also meine Menge aller Wörter Sigma Stern zerfällt jetzt in 16:13.280 --> 16:14.160 Äquivalenzklassen. 16:16.640 --> 16:20.240 Es könnten jetzt sehr viele sein, weil Sigma Stern ist unendlich. 16:21.280 --> 16:25.700 Okay, es könnten also unendlich viele sein oder nur endlich viele 16:25.700 --> 16:26.480 Äquivalenzklassen. 16:27.920 --> 16:31.080 Vielleicht nur eine, vielleicht ist alles Äquivalent zueinander. 16:32.040 --> 16:34.880 Vielleicht ist jedes Wort nur seine eigene Äquivalenzklasse, dann ist 16:34.880 --> 16:36.340 es natürlich unendlich viele Äquivalenzklassen. 16:37.180 --> 16:39.880 Gut, aber diese Anzahl der Äquivalenzklassen, die interessiert uns 16:39.880 --> 16:43.700 jetzt ganz besonders und das heißt der Index von R. 16:44.340 --> 16:49.240 Wir geben R, wie viele Äquivalenzklassen bekommen wir denn dadurch, 16:49.320 --> 16:50.280 wenn wir uns das angucken. 16:50.400 --> 16:55.360 Und das ist der Index von R und wir schreiben so int R als Zeichen. 16:56.180 --> 16:59.300 Und für uns wird es besonders wichtig sein, ob dieser Index endlich 16:59.300 --> 17:01.340 oder unendlich ist. 17:06.330 --> 17:12.230 Gut, jetzt habe ich die ganze Zeit von einer hypothetischen 17:12.230 --> 17:16.230 Äquivalenzrelation R gesprochen, die uns irgendwie von außen jemand 17:16.230 --> 17:18.970 gibt und wir können dann überprüfen, ob die Rechtsinvarianz ist. 17:19.670 --> 17:22.370 Wir haben ein paar Beispiele gesehen, aber eigentlich interessiert uns 17:22.370 --> 17:26.930 eine ganz bestimmte Relation und zwar das ist die Neurode-Relation. 17:28.710 --> 17:33.870 Die ist definiert auf Basis einer Sprache L. 17:35.330 --> 17:38.070 Wir gucken uns eine beliebige Sprache L an. 17:38.290 --> 17:40.090 Das ist einfach nur eine Teilmenge von Wörtern. 17:40.870 --> 17:42.130 Die muss nicht regulär sein. 17:42.250 --> 17:44.970 Irgendeine Sprache, vielleicht die leere Sprache, irgendwas. 17:46.930 --> 17:50.030 Und auf Basis dieser Sprache L definieren wir uns eine 17:50.030 --> 17:55.230 Äquivalenzrelation auf der Menge aller Wörter und die ist dann R sub L 17:55.230 --> 17:57.910 und zwar definieren wir uns die wie folgt. 17:58.230 --> 18:02.470 Wir gucken uns an X und Y, zwei beliebige Wörter, und wollen jetzt 18:02.470 --> 18:04.450 wissen, sind die äquivalent oder sind sie nicht äquivalent. 18:04.930 --> 18:08.090 Und der Test, den wir durchführen, ist das folgende. 18:08.610 --> 18:14.330 Wir gucken uns alle Wörter an aus Z wieder, die wir hinten ranhängen 18:14.330 --> 18:16.250 können an X und Y. 18:17.330 --> 18:20.910 Inklusive das leere Wort, alle einbuchstabigen Wörter, aber dann 18:20.910 --> 18:23.990 hängen wir an X und Y immer dasselbe Wort ran, auch wenn X und Y 18:23.990 --> 18:25.530 verschieden sind. 18:26.330 --> 18:29.070 Und dann gucken wir uns immer, wenn wir uns ein Wort Z genommen haben 18:29.070 --> 18:35.110 und rangehängt haben, gucken wir ob das Ergebnis jetzt auf XZ und ob 18:35.110 --> 18:38.350 das Ergebnis YZ in L liegen. 18:38.690 --> 18:40.150 Ob das jetzt Wörter meiner Sprache sind. 18:41.470 --> 18:45.290 Und ich sage X und Y sind äquivalent, wenn egal welches Z ich 18:45.290 --> 18:47.610 ranhänge, das gleiche Ergebnis rauskommt. 18:47.610 --> 18:52.450 Entweder sagen beide nein, nicht in der Sprache, oder beide sagen ja 18:52.450 --> 18:53.270 in der Sprache. 18:58.400 --> 19:03.900 Es kann jetzt natürlich für verschiedene Z, kann das manchmal ja und 19:03.900 --> 19:04.660 manchmal nein sein. 19:04.760 --> 19:08.660 Wichtig ist, dass X und Y sozusagen da drin übereinstimmen, dass wenn 19:08.660 --> 19:11.260 man Z an sie ranhängt, ob das jetzt in der Sprache ist oder nicht. 19:13.500 --> 19:18.220 Das definiert erstmal so eine Relation. 19:19.660 --> 19:23.720 Es ist leicht zu sehen, dass die Relation, 19:27.180 --> 19:31.520 dass jedes Wort zu sich selbst in Relation steht, äquivalent zu sich 19:31.520 --> 19:32.120 selbst ist. 19:32.820 --> 19:36.280 Weil dann einfach X ist gleich Z und dann ist das hier trivialerweise 19:36.280 --> 19:36.700 erfüllt. 19:38.380 --> 19:43.280 Aber wir müssten noch Transitivität überprüfen, das mache ich jetzt 19:43.280 --> 19:44.100 nicht. 19:44.520 --> 19:49.980 Was ich aber überprüfe, ist, dass diese Relation rechtsinvariant ist. 19:51.520 --> 19:56.200 Das ist eine Äquivalenzrelation auf der Menge aller Wörter, es kommt 19:56.200 --> 19:59.180 von irgendeiner Sprache und egal welche Sprache das ist am Anfang, 19:59.320 --> 20:02.720 egal wie wild die ist, diese Sprache, diese Relation ist immer 20:02.720 --> 20:03.640 rechtsinvariant. 20:03.880 --> 20:05.260 Okay, was müssen wir dafür überprüfen? 20:05.720 --> 20:08.780 Wir müssen also überprüfen, wenn wir zwei Wörter haben, die sind eine 20:08.780 --> 20:13.960 Relation XY und wir nehmen jetzt ein beliebiges Z, für alle Z aus 20:13.960 --> 20:19.020 Sigma Stern, müssen auch XZ und YZ in Relation sein. 20:19.100 --> 20:21.520 Das ist also das, was wir überprüfen. 20:21.760 --> 20:25.440 Wenn sie in Relation waren, dann sind diese längeren Wörter auch noch 20:25.440 --> 20:25.900 in Relation. 20:26.320 --> 20:28.820 Die wird nicht zerstört, die Relation. 20:29.340 --> 20:30.820 Gut, wie machen wir das? 20:31.320 --> 20:36.860 Gut, das Erste, was wir tun, ist, wir setzen ein die Definition, die 20:36.860 --> 20:40.660 Definition, dass die beiden in Relation sind von dort oben. 20:41.060 --> 20:45.540 Also wir wissen, dass egal welches Wort, ich habe jetzt W genannt, das 20:45.540 --> 20:49.420 ist im Prinzip das hier oben, egal welches Wort W wir ranhängen, wir 20:49.420 --> 20:53.520 wissen, dass XW in L ist, genau dann, wenn YW in L ist. 20:54.500 --> 20:58.160 X und Y sind sich eigentlich darüber, ob, wenn man W an sie ranhängt, 20:58.260 --> 20:59.800 das in der Sprache landet oder nicht. 21:00.740 --> 21:07.140 Gut, dann ist es natürlich auch, wenn ich XZ mir angucke und dann noch 21:07.140 --> 21:14.900 W ranhänge, ist es das gleiche, wie wenn ich X nehme und ich hänge ZW. 21:16.100 --> 21:20.140 Und auf der anderen Seite, wenn ich YZ mir angucke und dann W 21:20.140 --> 21:23.500 ranhänge, ist es gleich, als wenn ich mir Y angucke und dann ZW 21:23.500 --> 21:23.760 ranhänge. 21:26.760 --> 21:32.580 Das heißt, wenn ich hier dieses ZW als ein Wort betrachte, dann ist es 21:32.580 --> 21:34.940 ganz klar, dass das von hier oben gilt. 21:36.420 --> 21:39.540 Und das jetzt hier ist aber die Definition wieder für die Äquivalenz 21:39.540 --> 21:40.940 von XZ und YZ. 21:42.680 --> 21:49.860 Also sind die, für jedes W ist XZW in L genau oder wenn YZW in L ist, 21:49.900 --> 21:56.300 also sind XZ und YZ äquivalent, das heißt in Relation, das heißt diese 21:56.300 --> 21:59.100 Relation ist rechtsinvariant. 21:59.900 --> 22:07.420 Okay, gut, es ist erstmal einfach so hingeschrieben, definiert und 22:07.420 --> 22:10.800 eine Eigenschaft überprüft. 22:12.060 --> 22:13.420 Warum ist das jetzt wichtig? 22:13.700 --> 22:17.320 Wichtig ist das wegen des folgenden Satzes, der Satz von Nerode, aus 22:17.320 --> 22:19.920 dem allerhand folgt. 22:22.240 --> 22:24.180 Folgende Aussagen sind Äquivalenz. 22:24.440 --> 22:27.540 Das ist der vierte Äquivalenzbegriff auf der Menge der Aussagen. 22:30.600 --> 22:36.020 Also das Erste ist, die erste Aussage ist, eine Sprache wird von einem 22:36.020 --> 22:38.800 deterministischen endlichen Automaten erkannt bzw. 22:39.600 --> 22:40.240 akzeptiert. 22:41.360 --> 22:45.920 Das heißt also, schon nach dem was wir wissen, das ist eine reguläre 22:45.920 --> 22:46.280 Sprache. 22:47.860 --> 22:53.580 Dass L eine reguläre Sprache ist, ist Äquivalenz dazu, dass L als 22:53.580 --> 23:00.800 Teilmenge der Wörter gesehen, die Vereinigung von Äquivalenzklassen 23:00.800 --> 23:07.120 einer rechtsinvarianten Äquivalenzrelation mit endlichen Index ist. 23:08.100 --> 23:09.600 Okay, also was heißt das? 23:10.160 --> 23:16.660 Es gibt eine Äquivalenzrelation, irgendeine, ja, aber nicht ganz 23:16.660 --> 23:19.340 irgendeine, die muss einen endlichen Index haben, das heißt, die 23:19.340 --> 23:24.700 zerlegt die Menge aller Wörter in endlich viele Äquivalenzklassen und 23:24.700 --> 23:28.760 dann L ist die Vereinigung von einem oder keinen oder mehreren von 23:28.760 --> 23:30.120 diesen Äquivalenzklassen. 23:33.500 --> 23:37.520 Wenn es ein endlicher Index ist, ist es also eine Vereinigung von 23:37.520 --> 23:39.360 potenziell unendlichen Mengen. 23:41.000 --> 23:42.700 Okay, gut. 23:43.520 --> 23:46.240 Es gibt so eine Rechtsinvariante und diese Äquivalenzrelation muss 23:46.240 --> 23:47.400 rechtsinvariant sein. 23:47.440 --> 23:49.560 Es muss rechtsinvariant sein und einen endlichen Index haben. 23:49.820 --> 23:50.000 Gut. 23:51.540 --> 23:57.560 Und das ist also genau dann, wenn L von einem deterministischen 23:57.560 --> 23:58.660 endlichen Automaten akzeptiert. 23:59.340 --> 24:02.720 Und der dritte Punkt ist, beide diese Sachen sind auch wiederum 24:02.720 --> 24:06.460 äquivalent dazu, dass die Neurode-Relation, die wir gerade uns 24:06.460 --> 24:12.020 angeguckt haben, die jetzt sehr auf der Sprache L basiert, einen 24:12.020 --> 24:13.020 endlichen Index hat. 24:16.040 --> 24:16.340 Okay. 24:18.900 --> 24:21.920 Das heißt, zum Beispiel könnten wir diesen Satz, wenn wir ihn dann 24:21.920 --> 24:25.400 bewiesen haben, so benutzen, um zu zeigen, dass eine Sprache regulär 24:25.400 --> 24:25.960 ist oder nicht. 24:26.020 --> 24:27.280 Wir nehmen uns die Sprache L her. 24:29.200 --> 24:31.520 Daraus ergibt sich die Neurode-Relation. 24:31.520 --> 24:37.080 Wir gucken uns die an, gucken, was ihr Index ist. 24:37.480 --> 24:40.900 Wenn die Antwort unendlich ist, war die Sprache nicht regulär. 24:41.500 --> 24:45.120 Wenn die Antwort endlich ist, war die Sprache regulär. 24:47.480 --> 24:47.680 Okay. 24:52.010 --> 24:55.530 So, jetzt, wie beweisen wir solche Sätze? 24:55.850 --> 24:56.950 Vielleicht haben Sie das schon mal gesehen. 24:57.110 --> 25:00.330 Also wir haben jetzt hier die Äquivalenz von drei Aussagen 1, 2 und 3. 25:00.930 --> 25:05.290 Und wir wollen also zeigen, dass die die Äquivalenz sind. 25:05.410 --> 25:08.190 Also normalerweise, wenn man zwei Aussagen hat, dann macht man aus 1 25:08.190 --> 25:10.330 folgt 2 und aus 2 folgt 1. 25:10.990 --> 25:11.110 Okay. 25:11.610 --> 25:13.530 Jetzt könnte ich das natürlich für jedes Paar machen. 25:13.630 --> 25:16.610 Also ich könnte erst mal zeigen, dass 1 und 2 äquivalent ist oder und 25:16.610 --> 25:19.670 dann das 2 und 3 äquivalent ist und dann vielleicht noch das 1 und 3 25:19.670 --> 25:20.330 äquivalent ist. 25:20.810 --> 25:24.970 Aber besonders elegant und schön ist es, wenn man einen sogenannten 25:24.970 --> 25:25.910 Ringschluss macht. 25:26.250 --> 25:34.090 Das heißt, wir zeigen aus 1 folgt 2, aus 2 folgt 3 und aus 3 folgt 1. 25:34.890 --> 25:34.930 Okay. 25:35.410 --> 25:37.570 Wir haben also drei Beweise zu führen. 25:39.870 --> 25:40.970 Fangen wir an. 25:42.610 --> 25:44.990 Der erste Teil. 25:45.250 --> 25:49.650 Also da oben sind noch mal die Aussagen, für die wir uns jetzt 25:49.650 --> 25:50.090 interessieren. 25:50.210 --> 25:50.930 1 und 2. 25:51.070 --> 25:55.590 Nämlich 1 ist, es gibt einen endlichen deterministischen Automaten, 25:55.710 --> 25:59.730 der die Sprache akzeptiert und 2 ist, es gibt eine rechtsequivalente 25:59.730 --> 26:04.290 Äquivalenzrelation mit endlichem Index, sodass L Vereinigung von 26:04.290 --> 26:06.030 einigen Äquivalenzklassen ist. 26:06.530 --> 26:06.610 Okay. 26:06.810 --> 26:10.950 Das heißt, wir haben gegeben den Automaten und müssen finden die 26:10.950 --> 26:11.710 Äquivalenzrelation. 26:14.070 --> 26:15.690 Also, machen wir das. 26:16.430 --> 26:20.870 A sei jetzt dieser deterministische endliche Automat, der L akzeptiert 26:20.870 --> 26:26.410 und wir definieren uns jetzt eine Äquivalenzrelation auf den Wörtern 26:26.410 --> 26:29.470 auf Grundlage des Automaten. 26:30.730 --> 26:35.610 Also nicht auf Grundlage der Sprache wie davor, also quasi, es ist ja 26:35.610 --> 26:39.210 auf Grundlage der Sprache, aber auf Grundlage dieses exakten 26:39.210 --> 26:39.990 Automaten. 26:40.330 --> 26:40.390 Okay. 26:40.930 --> 26:41.990 R sub a. 26:42.830 --> 26:44.990 Und zwar definiere ich das so. 26:45.130 --> 26:52.550 Zwei Wörter, x und y, sind äquivalent in dieser Relation, wie ich 26:52.550 --> 26:58.610 jetzt gerade definiere, wenn ich die beiden Wörter in den Automaten 26:58.610 --> 27:04.230 stecke und Abarbeitung der beiden Wörter landet im gleichen Zustand. 27:06.690 --> 27:11.510 Also formal hingeschrieben ist das delta s x ist dasselbe wie delta s 27:11.510 --> 27:12.050 y. 27:12.330 --> 27:14.190 Landen im gleichen Zustand. 27:14.330 --> 27:15.650 Im exakt denselben Zustand. 27:16.610 --> 27:18.570 Dann sage ich, die beiden Wörter sind äquivalent. 27:19.710 --> 27:20.150 Okay. 27:20.810 --> 27:23.650 Da habe ich erst mal eine Relation definiert. 27:25.450 --> 27:29.390 Jetzt müssen wir wiederum uns überlegen, dass es wirklich eine 27:29.390 --> 27:30.690 Äquivalenzrelation ist. 27:30.910 --> 27:32.450 Also x ist äquivalent zu x. 27:32.550 --> 27:39.190 Das ist klar, dass wenn x und y äquivalent sind, dann landen also x 27:39.190 --> 27:40.790 und y im selben Zustand. 27:40.890 --> 27:44.310 y und z sind äquivalent, also y und z landen auch im selben Zustand. 27:44.530 --> 27:46.590 Also sind auch x und z äquivalent. 27:46.870 --> 27:49.070 Das ist immer selber Zustand, selber Zustand, selber Zustand. 27:49.570 --> 27:50.970 Also das ist eine Äquivalenzrelation. 27:51.350 --> 27:55.150 Man müsste noch überprüfen, dass die rechts invariant ist. 27:55.450 --> 27:56.150 Nur mal kurz gucken. 27:57.630 --> 28:02.710 Ja, also das wollen wir gleich tun, dass die rechts invariant ist. 28:03.230 --> 28:07.430 Und wir müssten überprüfen, das war die zweite, also wir haben ja 28:07.430 --> 28:08.150 einiges zu tun. 28:08.390 --> 28:11.270 Wir müssen eine Äquivalenzrelation finden, die soll rechts invariant 28:11.270 --> 28:15.250 sein und die soll endlich einen Index haben und die soll irgendwas 28:15.250 --> 28:18.330 noch mit unserer Sprache L zu tun haben, nämlich L soll die 28:18.330 --> 28:20.230 Vereinigung von ein paar Äquivalenzklassen sein. 28:21.050 --> 28:22.570 Also noch einiges zu tun. 28:23.730 --> 28:26.130 Das erste ist rechts invariant nachprüfen. 28:27.190 --> 28:29.370 Nachprüfen, dass der Index endlich ist. 28:29.510 --> 28:33.110 Wir werden insbesondere zeigen, dass der Index dieser Relation ist 28:33.110 --> 28:36.670 genau die Anzahl der nicht überflüssigen Zustände von A. 28:37.310 --> 28:40.110 Also die Zustände, die tatsächlich erreicht werden können. 28:41.310 --> 28:43.430 Und die ist endlich unser Automat. 28:45.290 --> 28:48.750 Und das dritte ist, dass L was mit dieser Relation zu tun hat, nämlich 28:48.750 --> 28:52.150 die Vereinigung von den Äquivalenzklassen, von einigen 28:52.150 --> 28:53.430 Äquivalenzklassen ist. 28:54.170 --> 29:01.610 Nun, die Äquivalenzklassen von R A gehören zu den Zuständen des 29:01.610 --> 29:02.170 Automaten. 29:02.910 --> 29:07.030 Ich habe für jeden Zustand des Automatens eine Äquivalenzklasse, weil 29:07.030 --> 29:10.030 ich sage, gehört das an den Äquivalenten, wenn sie in diesem Zustand 29:10.030 --> 29:10.810 enden. 29:11.850 --> 29:14.610 Also habe ich sozusagen eine Äquivalenzklasse für jeden Zustand. 29:15.670 --> 29:16.830 Das ist relativ leicht zu sehen. 29:17.490 --> 29:23.070 Und dann sage ich, okay, meine Sprache L sind genau die, die in 29:23.070 --> 29:24.030 Endzuständen landen. 29:24.170 --> 29:27.610 Das ist also eine Vereinigung von einigen von diesen Zuständen. 29:28.350 --> 29:30.150 Gut, aber der Reihe nach. 29:30.550 --> 29:31.430 Rechts invariant. 29:32.650 --> 29:37.450 Oh ne, muss ich sie so einfach davon überzeugen. 29:39.030 --> 29:40.730 Gut, warum ist das rechts invariant? 29:43.110 --> 29:44.210 Was müssen wir zeigen? 29:44.290 --> 29:49.790 Wir müssen zeigen, wenn zwei Wörter äquivalent sind und ich hänge an 29:49.790 --> 29:53.370 beide das gleiche ran, dann sind sie immer noch äquivalent. 29:54.930 --> 29:57.410 Okay, gut, gehen wir da durch. 29:58.030 --> 29:59.870 Ich habe zwei Wörter, die sind äquivalent. 30:00.430 --> 30:02.810 Nach Definition heißt es, sie landen im selben Zustand. 30:04.030 --> 30:06.450 Exakt im selben Zustand des Automats. 30:07.270 --> 30:10.110 Wenn ich jetzt an beide Wörter das gleiche ranhänge, dann heißt es, 30:10.150 --> 30:12.970 der Automat tut von dort an genau das gleiche. 30:12.990 --> 30:16.330 Von dem selben Startzustand, mit dem selben Input. 30:16.890 --> 30:20.170 Das heißt, er wird, weil das ein deterministischer endlicher Automat 30:20.170 --> 30:22.670 ist, er wird exakt wieder in dem selben Zustand landen. 30:22.850 --> 30:26.870 Nicht vielleicht den, wo ich gerade war, aber diese beiden parallelen 30:26.870 --> 30:31.430 Delten sind wirklich identisch in dem Fall. 30:32.350 --> 30:40.330 Das heißt, x und dann z im Automaten endet im gleichen Zustand wie y 30:40.330 --> 30:41.350 und dann z. 30:41.550 --> 30:43.770 Weil ich einfach weiß, nach x bzw. 30:43.810 --> 30:47.430 y bin ich schon am gleichen Punkt und dann macht ich weiß noch was. 30:47.890 --> 30:49.090 Gut, das ist rechts invariant. 30:50.870 --> 30:54.930 Der Index, habe ich auch gerade schon erwähnt, ist genau die Anzahl 30:54.930 --> 30:56.370 der nicht überflüssigen Zustände. 30:56.950 --> 31:00.310 Also die, die wirklich erreicht werden können, gehören zu einer 31:00.310 --> 31:02.390 Äquivalenzklasse, die Zustände. 31:03.790 --> 31:09.470 Und die Wörter in der Sprache sind genau die, die in Endzuständen 31:09.470 --> 31:09.890 enden. 31:11.310 --> 31:16.730 Das heißt, zu der gehörigen Äquivalenzklasse von Wörtern, die sind, 31:17.030 --> 31:19.810 wenn es ein Endzustand ist, sind die alle in der Sprache. 31:20.310 --> 31:23.750 Wenn es kein Endzustand ist, ist keiner davon in der Sprache. 31:26.800 --> 31:29.980 Gut, endlichen Index habe ich auch. 31:31.340 --> 31:33.000 Okay, soweit klar? 31:37.230 --> 31:41.530 Gut, also das ist der erste von drei Schritten in diesem Ringschluss. 31:41.990 --> 31:43.650 Aus 1 folgt 2. 31:45.250 --> 31:50.890 Jetzt wissen wir, wir haben 2 und wir müssen 3 zeigen. 31:51.730 --> 32:01.350 Wir wissen, es gibt diese ominöse Äquivalenzrelation R, die ist rechts 32:01.350 --> 32:07.870 invariant, hat endlichen Index und L ist die Vereinigung von einigen, 32:08.050 --> 32:11.210 vielleicht Null, vielleicht allen Äquivalenzklassen dieser 32:11.210 --> 32:13.590 Äquivalenzrelation. 32:14.270 --> 32:16.870 Das wissen wir, das kriegen wir jetzt gegeben, so wie wir gerade eben 32:16.870 --> 32:18.110 den Automaten gegeben haben. 32:19.010 --> 32:25.070 Und jetzt müssen wir zeigen, dass die Narrowed-Relation, die eventuell 32:25.070 --> 32:29.630 eine ganz andere ist, dass die einen endlichen Index hat. 32:31.030 --> 32:33.830 Okay, gut, wie machen wir das? 32:34.530 --> 32:39.770 Wir zeigen, dass die Relation, die uns da oben gegeben wurde, in 32:39.770 --> 32:47.290 Aussage 2, egal wie die aussieht, die ist eine sogenannte Verfeinerung 32:47.290 --> 32:50.950 von der Narrowed-Relation. 32:51.810 --> 32:55.970 Also wenn ich mir jetzt sozusagen, wie soll man sich das vorstellen, 32:56.170 --> 33:00.130 vielleicht irgendwie die unendliche Menge aller Wörter liegt jetzt 33:00.130 --> 33:04.070 hier auf dem Boden und die sind dann so eingefärbt oder eingekreist in 33:04.070 --> 33:04.930 Äquivalenzklassen. 33:05.170 --> 33:07.690 Alle, die hier liegen, sind Äquivalent, alle, die hier liegen, sind 33:07.690 --> 33:08.630 Äquivalent und so weiter. 33:09.530 --> 33:16.230 Und dann eine Verfeinerung heißt, dass die andere Relation, die R 33:16.230 --> 33:20.670 -Relation, hat kleinere Kreise, das heißt eventuell ist eine 33:20.670 --> 33:23.790 Äquivalenzklasse nochmal aufgesplittet in andere Äquivalenzklassen. 33:26.490 --> 33:34.350 Aber es ist halt, wenn sie in R Äquivalent sind, dann sind sie auch in 33:34.350 --> 33:35.950 RL Äquivalent. 33:37.030 --> 33:41.830 Das heißt eine Verfeinerung oder RL ist eine Vergröberung von R. 33:42.990 --> 33:44.770 Also das ist formal zu zeigen. 33:45.150 --> 33:50.570 Wir zeigen, wenn zwei Wörter Äquivalent sind in R, dann sind sie auch 33:50.570 --> 33:51.870 Äquivalent in RL. 33:53.730 --> 33:57.110 Diese Äquivalenzklassen aus RL sind einfach Vereinigungen von 33:57.110 --> 33:58.170 Äquivalenzklassen aus R. 33:58.630 --> 34:00.430 Einfach zusammengenommen und so zu sagen, okay. 34:04.710 --> 34:07.850 Dann folgt natürlich, wenn wir das einmal gezeigt haben, dann folgt 34:07.850 --> 34:11.370 natürlich, dass der Index von RL höchstens der Index von R ist. 34:11.550 --> 34:15.970 Eventuell ist RL gleich R, gilt hier alles trivial. 34:17.010 --> 34:20.110 Aber ansonsten, wenn es eine Vergröberung ist, hat es nur weniger 34:20.110 --> 34:20.930 Äquivalenzklassen. 34:22.870 --> 34:27.370 Und weil der Index von R nach Annahme Endlich ist, ist dann halt der 34:27.370 --> 34:29.990 Index von RL Endlich, was wir zu zeigen haben. 34:30.130 --> 34:30.310 Gut. 34:30.810 --> 34:37.690 Also sei also x in Relation zu y mit dieser ominösen Rechtsinvarianten 34:37.690 --> 34:40.770 -Äquivalenzrelation R die in Endlichen-Index sind. 34:42.230 --> 34:44.850 Wir benutzen jetzt natürlich die Rechtsinvarianz R. 34:45.470 --> 34:45.830 Gut. 34:46.790 --> 34:51.550 Weil R Rechtsinvariant ist, das ist nochmal die Definition, wir 34:51.550 --> 34:57.150 wissen, für alle z, die wir hinten ranhängen, an x oder y, wird die 34:57.150 --> 34:58.630 Relation erhalten. 34:59.950 --> 35:00.430 Okay. 35:01.970 --> 35:05.270 Das heißt das hier. 35:05.350 --> 35:06.390 Einfach nur Rechtsinvarianz. 35:09.050 --> 35:12.710 Weiterum wissen wir, dass diese ominöse Äquivalenzrelation R auch noch 35:12.710 --> 35:14.490 was mit unserer Sprache L zu tun hat. 35:14.490 --> 35:19.370 Nämlich, die Sprache L ist eine Vereinigung von Äquivalenzklassen aus 35:19.370 --> 35:19.810 R. 35:20.430 --> 35:27.470 In anderen Worten sagen wir, dass eine Äquivalenzklasse von R ist 35:27.470 --> 35:33.470 entweder ganz in der Sprache oder gar nicht in der Sprache. 35:35.810 --> 35:39.190 Die Äquivalenzklasse kann nicht Elemente von der Sprache und Elemente 35:39.190 --> 35:40.170 nicht aus der Sprache haben. 35:40.710 --> 35:43.650 Dann wäre die Sprache nicht die Vereinigung von den Äquivalenzklassen. 35:46.750 --> 35:51.230 Eine Äquivalenzklasse, jede Äquivalenzklasse von R ist entweder ganz 35:51.230 --> 35:54.250 in der Sprache L oder gar nicht in der Sprache L. 35:55.310 --> 35:59.150 Das hat damit zu tun, dass die Äquivalenzklassen disjunkt sind und ich 35:59.150 --> 36:00.770 einfach nur Vereinigung von Äquivalenzklassen. 36:00.770 --> 36:01.670 Gut. 36:03.450 --> 36:14.030 Das heißt, ich habe, wenn ich mir jetzt hier xz und yz angucke, die 36:14.030 --> 36:15.570 sind in der gleichen Äquivalenzklasse. 36:18.250 --> 36:21.550 Die sind in der gleichen Äquivalenzklasse, egal was z ist für 36:21.550 --> 36:23.630 gegebenes xy in Relation. 36:23.850 --> 36:26.030 Egal was z ist, die sind in der gleichen Äquivalenzklasse. 36:26.030 --> 36:32.970 Das heißt, sie sind entweder beide in L oder beide nicht in L. 36:39.900 --> 36:44.020 Das heißt, ich habe entweder beide in L oder beide nicht in L. 36:46.040 --> 36:50.340 Das gilt unter der Voraussetzung, dass x in Relation zu y ist. 36:52.040 --> 36:53.260 Und R reicht. 36:54.680 --> 36:57.060 Das ist aber genau die Definition. 36:58.220 --> 37:04.100 x und y sind in Relation in der Nerode-Relation, wenn für jedes z 37:04.100 --> 37:06.340 hinten das gilt. 37:06.780 --> 37:09.420 Entweder sind beide in L oder beide nicht in L. 37:09.500 --> 37:11.380 Das ist genau die Nerode-Relation. 37:14.730 --> 37:21.050 Also wir haben gezeigt, in Relation in R folgt in Relation in Nerode. 37:22.690 --> 37:24.830 Und das war genau das, was wir zu tun hatten. 37:25.510 --> 37:27.950 Nerode ist eine Vergröberung von R. 37:28.930 --> 37:32.350 Das heißt, Nerode hat höchstens weniger oder höchstens so viele 37:32.350 --> 37:34.250 Äquivalenzklassen wie R. 37:35.750 --> 37:40.290 R hat endlichen Index nach Voraussetzung, also hat Nerode endlichen 37:40.290 --> 37:40.550 Index. 37:41.550 --> 37:42.890 Das war alles, was wir zeigen mussten. 37:43.990 --> 37:44.710 Das ist Punkt 3. 37:45.310 --> 37:47.750 Die Nerode-Relation hat endlichen Index. 37:50.410 --> 37:51.250 Gut. 37:53.110 --> 37:56.530 Letzter Schritt im Ringschluss von 3 nach 1. 37:57.270 --> 38:01.390 Wir wissen jetzt, die Nerode-Relation hat einen endlichen Index. 38:02.430 --> 38:07.570 Wir haben eine Sprache L und dessen Nerode-Relation hat endlichen 38:07.570 --> 38:08.030 Index. 38:08.130 --> 38:12.230 Wir müssen zeigen, dass es einen deterministischen endlichen Automaten 38:12.230 --> 38:15.590 gibt, der die Sprache akzeptiert. 38:16.460 --> 38:22.590 Und jetzt müssen wir also aus dieser Nerode-Relation einen zugehörigen 38:22.590 --> 38:23.730 Automaten konstruieren. 38:23.910 --> 38:28.030 Und das wird der sogenannte Nerode-Automat oder der Automat der Nerode 38:28.030 --> 38:30.470 -Relation sein. 38:30.810 --> 38:31.210 Gut. 38:31.290 --> 38:32.750 Wie basteln wir uns diesen Automaten? 38:33.230 --> 38:36.810 Wir müssen wieder dieses ganze Fünftupel beschreiben. 38:36.810 --> 38:49.190 Wir sagen, die Zustände des Automaten gehören zu den Äquivalenzklassen 38:49.190 --> 38:50.290 der Nerode-Relation. 38:51.070 --> 38:54.950 Für jede Nerode-Relation, für jede Äquivalenzklasse der Nerode 38:54.950 --> 38:56.670 -Relation, nehme ich mir einen Zustand her. 38:58.870 --> 39:01.970 Ich bezeichne das hier nur den Namen des Zustands. 39:02.910 --> 39:04.250 Den Namen des Zustands. 39:04.690 --> 39:07.590 Ich kann die auch durchnummerieren oder färben und sage, das ist der 39:07.590 --> 39:10.450 rote Zustand zu der roten Äquivalenzklasse und so weiter. 39:10.790 --> 39:11.010 Gut. 39:11.090 --> 39:12.210 Das ist meine Zustandsmenge. 39:13.230 --> 39:19.770 Die ist schon mal endlich, weil die hat genauso viele Zustände, wie es 39:19.770 --> 39:21.130 vorher Äquivalenzklassen gab. 39:21.350 --> 39:23.770 Und wir wissen, die ist endlich. 39:24.150 --> 39:25.690 Weil wir Punkt 2 haben. 39:25.750 --> 39:27.590 Die Nerode-Relation hat endlichen Index. 39:27.590 --> 39:32.010 Also wir brauchen so viele Zustände, wie es dort Äquivalenzklassen 39:32.010 --> 39:32.970 gibt. 39:33.370 --> 39:33.610 Gut. 39:34.990 --> 39:36.610 Jetzt, was ist der Startzustand? 39:36.670 --> 39:40.170 Der Startzustand ist die Äquivalenzklasse, in der das leere Wort zu 39:40.170 --> 39:40.710 finden ist. 39:44.010 --> 39:44.290 Okay. 39:44.550 --> 39:46.950 Das ist eine von diesen Äquivalenzklassen. 39:47.250 --> 39:48.070 Definieren wir uns so. 39:49.390 --> 40:02.210 Jetzt nochmal die Endzustände sind die Äquivalenzklassen, die Wörter 40:02.210 --> 40:03.450 aus der Sprache enthalten. 40:08.070 --> 40:12.890 Tatsächlich ist es so, dass so eine Äquivalenzklasse der Nerode 40:12.890 --> 40:17.050 -Relation entweder komplett in der Sprache drin ist oder gar nicht. 40:20.270 --> 40:23.870 Das heißt, diese kleine wohldefiniert hier in Klammern. 40:24.010 --> 40:28.070 Egal, was ich mir angucke aus der Sprache und ich gucke mir die 40:28.070 --> 40:29.390 Äquivalenzklassen dazu an. 40:29.890 --> 40:31.530 Das ist immer das gleiche Resultat. 40:44.130 --> 40:48.650 Also hier in dem Fall von Äquivalenzrelation ist immer die Frage, wenn 40:48.650 --> 40:51.630 ich jetzt hier referenziere auf eine Äquivalenzrelation, dann habe ich 40:51.630 --> 40:53.150 da immer einen Vertreter drin stehen. 40:53.310 --> 40:54.390 X oder hier ist es B. 40:55.310 --> 41:00.430 Und dann sage ich, ich nehme alle die Äquivalenzklassen, sodass zu 41:00.430 --> 41:02.410 diesem Vertreter W irgendwas gilt. 41:03.010 --> 41:05.810 Und wohldefiniert heißt, dass es unabhängig ist von der Wahl des 41:05.810 --> 41:06.350 Vertreters. 41:09.610 --> 41:13.130 Das ist egal, welchen Vertreter aus der Klasse ich mir angucke, er hat 41:13.130 --> 41:15.150 entweder diese Eigenschaft hier hinten oder er hat sie nicht. 41:15.870 --> 41:19.910 Sonst könnte jemand herkommen und sagen, die Äquivalenzklasse von W 41:19.910 --> 41:23.130 ist aber das gleiche wie die Äquivalenzklasse von V, aber W hat die 41:23.130 --> 41:25.530 Eigenschaft und V hat die Eigenschaft nicht, was ist denn nun? 41:26.030 --> 41:27.450 Nehme ich die Klasse oder nehme ich sie nicht? 41:28.030 --> 41:29.190 Und das heißt, die ist wohldefiniert. 41:29.270 --> 41:31.190 Das ist unabhängig von der Wahl des Vertreters. 41:35.950 --> 41:39.590 Also das sind meine Endzustände, das sind die Klassen, die ganz in L 41:39.590 --> 41:40.110 drin sind. 41:40.850 --> 41:44.910 Und dann tut die Übergangsfunktion, die Übergangsfunktion ist jetzt 41:44.910 --> 41:45.970 sozusagen auf einer Klasse. 41:47.330 --> 41:53.030 Das ist ein Zustand, das sind alles Wörter, eine Menge von Wörtern, 41:53.110 --> 41:55.690 die sind äquivalent in der New Growth Relation. 41:56.490 --> 42:00.410 Und dann nehme ich mir ein beliebiges Wort aus dieser Zustandsmenge, 42:00.930 --> 42:04.110 aus dieser Klasse raus, einen beliebigen Vertreter. 42:05.090 --> 42:09.770 Tue Zeichen A ran, kriege ein neues Wort. 42:10.430 --> 42:13.430 Das liegt jetzt in vielleicht einer anderen Äquivalenzklasse. 42:14.290 --> 42:17.350 Und das ist das Ziel meiner Übergangsfunktion. 42:17.630 --> 42:22.470 Wenn ich aus dieser Klasse A lese, gehe ich in diese Klasse, die X A 42:22.470 --> 42:22.670 hat. 42:22.750 --> 42:26.970 Und das ist wiederum wohldefiniert, also unabhängig von dem Vertreter 42:26.970 --> 42:27.410 von X. 42:27.690 --> 42:29.190 Ich werde immer in dem gleichen Ding landen. 42:31.810 --> 42:37.350 Gut, also, das ist genau der Claim, das ist hier oben genau das 42:37.350 --> 42:37.730 gleiche. 42:38.070 --> 42:40.810 Das ist wohldefiniert, das habe ich jetzt einfach so gesagt. 42:41.230 --> 42:44.810 Aber wir müssen uns davon natürlich überzeugen, dass es unabhängig 42:44.810 --> 42:48.530 davon ist, welches X ich hier nehme, dass solange die vorher 42:48.530 --> 42:51.410 äquivalent waren, landen die danach in der gleichen Klasse. 42:53.170 --> 42:55.150 Und das ist aber genau die Rechtsinvarianz. 42:55.890 --> 42:58.750 Also wenn ich zwei Wörter nehme, die kommen aus der gleichen Klasse, 42:59.130 --> 43:01.750 das ist gleich, heißt hier gleiche Klasse, aber W und W' sind 43:01.750 --> 43:04.010 vielleicht andere Vertreter, verschiedene Vertreter der gleichen 43:04.010 --> 43:09.190 Klasse, dann ist das Rechtsinvariant, das heißt, egal was ich hinten 43:09.190 --> 43:14.330 dran hänge, also auch dieses eine Zeichen, dann sind die danach immer 43:14.330 --> 43:15.170 noch in Relation. 43:15.930 --> 43:18.030 Das heißt, die sind wiederum in derselben Klasse. 43:19.230 --> 43:21.110 Vielleicht ist es jetzt eine neue Klasse, vielleicht ist es eine 43:21.110 --> 43:21.330 andere. 43:23.190 --> 43:27.810 Aber das heißt also, dass die Äquivalenzklasse von W'A ist das gleiche 43:27.810 --> 43:32.350 wie die Äquivalenzklasse von W'A, also egal was ich hier für ein X 43:32.350 --> 43:34.970 gewählt habe, hier hinten steht immer die gleiche Klasse. 43:37.690 --> 43:38.210 Uldefiniert. 43:40.470 --> 43:43.330 Jetzt ist es okay, jetzt habe ich einfach diesen Automaten definiert, 43:44.390 --> 43:49.230 wir haben alle Teile, die dafür da nötig sind, jetzt müssen wir noch 43:49.230 --> 43:52.290 wissen, ob der jetzt wirklich unsere Sprache L akzeptiert. 43:53.670 --> 43:58.130 Das heißt, wir müssen gucken, was passiert denn mit einem Wort B. 44:00.710 --> 44:04.570 Unter dieser Übergangsfunktion Delta. 44:05.190 --> 44:07.130 Also Delta von S W. 44:07.510 --> 44:10.310 Nochmal, jetzt gucken wir uns an, S war die Äquivalenzklasse von dem 44:10.310 --> 44:14.010 leeren Wort und darauf wende ich jetzt W an, das heißt, das muss ich 44:14.010 --> 44:18.350 hier reingucken, was passiert, wenn ich das hier, X ist jetzt das 44:18.350 --> 44:23.830 leere Wort und B ist jetzt, das ist diese Erweiterung, von der Sie 44:23.830 --> 44:28.310 jetzt mittlerweile wissen müssten, wenn es nicht nur ein Zeichen ist, 44:28.430 --> 44:31.730 sondern ein ganzes Wort, dann heißt es nach der Definition, ich mache 44:31.730 --> 44:36.910 einfach E, also Epsilon W, dann gucken wir da von der Äquivalenzklasse 44:36.910 --> 44:42.290 an, das ist aber Epsilon W ist natürlich das gleiche wie W, und da von 44:42.290 --> 44:42.970 der Äquivalenzklasse. 44:42.970 --> 44:45.810 Und jetzt frage ich mich, ob diese Äquivalenzklasse, das ist jetzt der 44:45.810 --> 44:49.690 Zustand, in den W geschickt wird in diesem Automaten, ist das ein 44:49.690 --> 44:51.450 akzeptierender Zustand, ja oder nein? 44:53.750 --> 44:58.530 Und das heißt also, wenn diese Äquivalenzklasse hier in meinem 44:58.530 --> 45:05.970 definierten F ist, dann ist es ein Ja und ansonsten nicht, und F habe 45:05.970 --> 45:08.330 ich aber genau so definiert, dass die Wörter, die aus der Sprache 45:08.330 --> 45:10.250 kommen, genau in diesem Zustand sind. 45:10.470 --> 45:11.610 Also tut es genau das Richtige. 45:14.050 --> 45:17.690 Okay, das heißt, ich habe es wirklich geschafft, aus der 45:17.690 --> 45:26.570 Äquivalenzrelation auf der Menge aller Wörter, die hat bestimmte 45:26.570 --> 45:29.870 Eigenschaften und aus der Relation habe ich einen Automaten gebaut, 45:30.070 --> 45:30.990 der die Sprache akzeptiert. 45:32.670 --> 45:38.510 Gut, das schließt diesen letzten Schritt von 3 nach 1 und beweist den 45:38.510 --> 45:39.290 Satz von Leroy. 45:41.810 --> 45:47.430 Wir wissen jetzt also, es ist gleichbedeutend zu sagen, es gibt einen 45:47.430 --> 45:50.250 endlichen deterministischen Automaten, der L akzeptiert. 45:51.250 --> 45:57.210 Zu sagen, es gibt eine rechtsinvariante Äquivalenzrelation auf der 45:57.210 --> 46:01.550 Menge aller Wörter, die einen endlichen Index hat, sodass meine 46:01.550 --> 46:04.830 Sprache eine Vereinigung von ein paar Äquivalenzklassen ist. 46:05.670 --> 46:08.730 Und wiederum ist es gleichbedeutend zu sagen, dass diese ganz 46:08.730 --> 46:11.210 spezielle New Road Relation endlich einen Index hat. 46:16.960 --> 46:20.020 Jetzt kommt das Korollar, an dem wir eigentlich nur interessiert 46:20.020 --> 46:20.980 waren. 46:22.040 --> 46:27.020 Ganz am Anfang hatten wir die Frage, ob wir kleinstmögliche Automaten 46:27.020 --> 46:27.840 bauen können. 46:28.540 --> 46:29.920 Kleinstmögliche Anzahl der Zustände. 46:30.120 --> 46:34.020 Und jetzt ist die Aussage, dieser Automaten New Road Relation ist 46:34.020 --> 46:34.980 kleinstmöglich. 46:34.980 --> 46:38.300 Es gibt keinen mit weniger Zuständen. 46:38.980 --> 46:45.040 Und das folgt relativ leicht aus den drei Teilen in dem Beweis, den 46:45.040 --> 46:46.020 wir gemacht haben. 46:46.300 --> 46:53.020 Also sei A-irgendein Automat, der L akzeptiert. 46:53.080 --> 46:58.260 Ich möchte zeigen, dass A- mindestens so viele Zustände hat, wie der 46:58.260 --> 46:59.660 Automat der New Road Relation. 47:01.720 --> 47:05.240 Das heißt, das New Road Automat ist minimal. 47:06.020 --> 47:10.080 A-beliebig, akzeptiert die Sprache, muss mindestens so viele Zustände 47:10.080 --> 47:11.520 haben, kann nicht weniger haben. 47:12.180 --> 47:16.020 Gut, in diesem Schritt von 1 nach 2 haben wir uns genau so einen 47:16.020 --> 47:19.940 Automaten genommen und haben daraus eine Äquivalenzrelation gebastelt, 47:20.180 --> 47:26.360 deren Index war die Anzahl der Zustände oder höchstens die Anzahl der 47:26.360 --> 47:28.700 Zustände von dem Automaten. 47:28.700 --> 47:31.320 Das war genau die Anzahl der erreichbaren Zustände. 47:32.780 --> 47:37.900 Das heißt, aus diesem Automaten kriegen wir eine Äquivalenzrelation Q. 47:40.960 --> 47:44.820 Aus der Äquivalenzrelation R A'. 47:44.820 --> 47:49.160 Dann in dem Beweis von 2 nach 3 haben wir angefangen mit so einer 47:49.160 --> 47:53.960 Äquivalenzrelation und haben gezeigt, dass die New Road Relation 47:53.960 --> 47:57.360 höchstens einen kleineren, also höchstens so großen Index hat. 47:58.200 --> 48:02.560 Also diese Ungleichung der Index von R L ist kleiner gleich der Index 48:02.560 --> 48:03.380 von R A'. 48:04.620 --> 48:08.540 Im letzten Schritt haben wir dann wiederum aus R L einen wieder neuen 48:08.540 --> 48:15.500 Automaten gebaut, der Automat von New Road, der als Zustände hatte die 48:15.500 --> 48:17.300 Äquivalenzklassen der New Road Relation. 48:17.560 --> 48:20.900 Das heißt, die Zustandsmächtigkeit, die Mächtigkeit der Zustandsmenge 48:20.900 --> 48:21.940 war genau der Index. 48:21.940 --> 48:26.440 Das ist nachdem hier höchstens der Index von der anderen Relation, die 48:26.440 --> 48:30.220 von dem ersten Automaten kam, und der Index der anderen Relation von 48:30.220 --> 48:34.000 dem ersten Automaten ist höchstens die Zustandsmenge, die Mächtigkeit 48:34.000 --> 48:35.860 der Zustandsmenge des ersten Automaten. 48:36.280 --> 48:38.240 Und das ist die Ungleichung, die ich haben wollte. 48:38.720 --> 48:42.200 Also ist der New Road Automat minimal. 48:44.340 --> 48:44.820 Okay? 48:46.720 --> 48:50.900 Jetzt endlich sind wir also fertig mit dem ersten Schritt dieses 48:50.900 --> 48:52.680 großen Umweges, den wir machen wollten. 48:52.980 --> 48:55.980 Wir wollten eigentlich den Äquivalenzklassenautomaten uns angucken aus 48:55.980 --> 48:58.940 der letzten Vorlesung und zeigen, dass der minimal ist. 48:59.260 --> 49:03.440 Jetzt haben wir einen anderen Automaten kreiert, nämlich den New Road 49:03.440 --> 49:06.200 Automaten, und haben gezeigt, dass der minimal ist. 49:06.240 --> 49:07.620 Und jetzt müssen wir die beiden noch vergleichen. 49:09.540 --> 49:10.220 Gut. 49:10.740 --> 49:12.880 Das ist der Satz, der das entsprechende tut. 49:13.240 --> 49:19.540 Der Äquivalenzklassenautomat A3' ist minimal. 49:22.060 --> 49:22.740 Gut. 49:23.400 --> 49:28.620 Also sei L die Sprache, die der Automat akzeptiert. 49:29.480 --> 49:32.620 Also nochmal, der Äquivalenzklassenautomat basiert jetzt auf einem 49:32.620 --> 49:34.460 Automaten, mit dem wir gestartet sind. 49:34.460 --> 49:39.420 Ein Automat ohne überflüssige Zustände und haben damit darauf 49:39.420 --> 49:43.420 basierend einen Äquivalenzklassenautomat definiert. 49:44.720 --> 49:48.940 Dann kann man zeigen, dass A' keine überflüssigen Zustände hat. 49:49.740 --> 49:56.180 Das heißt, es reicht zu zeigen, dass die Anzahl der Zustände in meinem 49:56.180 --> 49:59.520 Äquivalenzklassenautomat genau der Index der New Road Relation ist. 50:00.000 --> 50:00.200 Okay? 50:00.780 --> 50:03.660 Weil das ist genau die kleinste Anzahl Zustände, die möglich ist. 50:03.660 --> 50:06.240 Und wenn ich das erreiche, bin ich fertig. 50:10.280 --> 50:18.000 Also müssen wir uns angucken, was heißt es... 50:25.510 --> 50:27.710 Wir gucken uns zwei Wörter an. 50:28.930 --> 50:29.530 Wörter. 50:29.610 --> 50:33.470 Äquivalenz von Wörtern hier auf der linken Seite in der New Road 50:33.470 --> 50:33.810 Relation. 50:35.230 --> 50:39.750 Das hier ist die Äquivalenz von Zuständen, die wir ganz am Anfang 50:39.750 --> 50:39.990 hatten. 50:39.990 --> 50:42.330 Das ist ein völlig anderer Begriff. 50:45.990 --> 50:50.410 Wir wollen zeigen, dass wenn zwei Wörter in der New Road Relation 50:50.410 --> 50:56.290 Äquivalenz sind, dann sind die Zustände, die unser erster Automat 50:56.290 --> 51:01.330 macht, mit den beiden Wörtern, sind die Äquivalenz. 51:02.070 --> 51:04.210 Vielleicht nicht dieselben, vielleicht landen die nicht im selben 51:04.210 --> 51:06.570 Zustand, aber die landen in äquivalenten Zuständen. 51:06.570 --> 51:10.990 Die Äquivalenz von Zuständen eines Automatens war, von dort aus ist es 51:10.990 --> 51:15.590 egal, für das Akzeptanzverhalten, ob ich dort oder dort bin. 51:15.690 --> 51:19.350 Egal was ich lese, es läuft beides in F oder beides nicht in F. 51:20.250 --> 51:21.230 Okay, das wollen wir zeigen. 51:22.210 --> 51:22.990 Also tun wir das. 51:24.950 --> 51:29.010 Wort Paar ist in Relation nach New Road, heißt für alles was ich 51:29.010 --> 51:34.410 ranhänge, ist es unerheblich für die Eigenschaft in der Sprache zu 51:34.410 --> 51:34.690 sein. 51:35.710 --> 51:39.190 Links, also XZ in L genau dann, wenn YZ in L ist. 51:40.110 --> 51:44.870 Gut, XZ ist in L genau dann, wenn das hier gilt, weil unser Automat, 51:44.950 --> 51:47.490 der erste Automat, einfach L akzeptiert. 51:48.110 --> 51:51.830 Wenn ich von S starte und XZ lese, lande ich in F. 51:52.130 --> 51:54.170 Das ist genau die Definition von in L sein. 51:54.990 --> 51:56.710 Genau dann, wenn ich das hier tue. 51:57.290 --> 52:00.550 Gut, jetzt wenn ich aber den Automaten einfach so angucke, kann ich 52:00.550 --> 52:01.590 mir den auch aufsplitten. 52:01.670 --> 52:07.390 Ich lese erstmal von S aus nur das Wort X und mach dann den zweiten 52:07.390 --> 52:08.030 Teil Z. 52:09.230 --> 52:13.330 Und genauso hier drüben, ich lese von S aus erstmal nur das Wort Y und 52:13.330 --> 52:14.410 mach den zweiten Teil Z. 52:14.830 --> 52:18.310 Und jetzt sind diese kleinen Dinger hier, das ist jetzt wieder ein 52:18.310 --> 52:18.790 Zustand. 52:19.630 --> 52:27.390 Das ist der Zustand, in dem der Automat ist, nachdem er X gelesen hat. 52:27.510 --> 52:30.970 Und das ist der Zustand, in dem der Automat ist, nachdem er Y gelesen 52:30.970 --> 52:31.250 hat. 52:31.590 --> 52:34.410 Und wenn ich mir jetzt hier ein kleines P und ein kleines Q vorstelle, 52:34.530 --> 52:38.390 dann ist das hier genau die Definition von äquivalenten Zuständen. 52:41.360 --> 52:47.180 Egal was ich danach noch lese, für jedes Z ist aus dem Zustand raus Z 52:47.180 --> 52:50.760 lesen in F, genau dann, wenn aus dem Zustand raus Z lesen in F. 52:51.280 --> 52:53.840 Das heißt, das ist die Äquivalenz von den Zuständen. 52:56.380 --> 53:04.040 Das heißt, für je zwei Wörter in der gleichen Äquivalenzklasse, in der 53:04.040 --> 53:11.280 Neurode -Relation, kriege ich eine Äquivalenzklasse von Zuständen. 53:12.000 --> 53:15.040 Und das ist genau das, was ich haben will. 53:15.720 --> 53:16.200 Gut. 53:17.180 --> 53:17.600 Mann, oh Mann. 53:17.860 --> 53:19.360 Ganz schönes Biest, aber wir haben es geschafft. 53:20.960 --> 53:24.900 Das schließt dieses Kapitel über deterministische endliche Automaten. 53:25.000 --> 53:28.340 Ich werde noch ein bisschen anfangen mit dem neuen Kapitel, aber hier 53:28.340 --> 53:31.440 nochmal die Zusammenfassung von dem, was wir bisher wissen. 53:32.820 --> 53:35.520 Wir haben kennengelernt, deterministische endliche Automaten, für die 53:35.520 --> 53:37.840 meisten von Ihnen wahrscheinlich nicht zum ersten Mal kennengelernt, 53:38.580 --> 53:42.780 als ein erstes Modell eines sehr einfachen Computers. 53:43.480 --> 53:46.160 Der kann gewisse Sachen berechnen. 53:46.300 --> 53:51.800 Der kann entscheiden, ob ein gewisses Wort in einer Sprache ist oder 53:51.800 --> 53:52.300 nicht. 53:52.760 --> 53:56.220 Und zwar genau für die regulären Sprachen kann der Automat. 53:56.560 --> 53:58.220 Gibt es so einen Automaten, der das entscheidet. 53:58.300 --> 54:02.000 Das ist sozusagen unser Modell von einem Algorithmus. 54:03.060 --> 54:06.460 Wir wissen, dass die Menge der regulären Sprachen genau die sind, die 54:06.460 --> 54:09.940 von einem DEA erkannt werden und auch genau die sind, die von einem 54:09.940 --> 54:10.940 NEA erkannt werden. 54:10.940 --> 54:13.740 Also dieser Nicht-Determinismus, den wir mal eingeführt haben, der war 54:13.740 --> 54:17.000 ganz hilfreich, um Beweise zu führen oder auch um die Zustandsmenge 54:17.000 --> 54:21.120 klein zu halten, aber nicht hilfreich, um neue Probleme zu lösen. 54:21.680 --> 54:23.700 Löst genau die gleichen Probleme, genau die gleichen Sprachen. 54:24.820 --> 54:28.780 Wir wissen, wie man aus dem NEA ein DEA konstruiert mit der 54:28.780 --> 54:29.820 Potenzmengen -Konstruktion. 54:31.540 --> 54:37.360 Wir kennen das Pumping-Lemma, um zu zeigen, dass gewisse Sprachen 54:37.360 --> 54:38.840 nicht regulär sind. 54:38.840 --> 54:42.880 Dass es für diese Sprachen keinen endlichen Automaten gibt, der sie 54:42.880 --> 54:43.440 erkennt. 54:46.720 --> 54:50.480 Wenn das Pumping-Lemma nicht gilt, ist die Sprache nicht regulär. 54:51.120 --> 54:54.160 Aber eventuell gilt das Pumping-Lemma und trotzdem ist die Sprache 54:54.160 --> 54:54.780 nicht regulär. 54:54.880 --> 54:56.840 Es ist nur ein Hilfsmittel, es muss nicht immer funktionieren. 54:58.340 --> 55:01.840 Als letztes haben wir den Äquivalenzklassenautomat kennengelernt. 55:01.840 --> 55:07.100 Wenn wir irgendeinen Automaten gefunden haben, der die Sprache 55:07.100 --> 55:12.700 erkennt, können wir diesen Äquivalenzklassenautomat daraufhin 55:12.700 --> 55:15.680 deterministisch konstruieren. 55:16.560 --> 55:20.380 Und der wird ein kleinster Automat sein, der die Sprache erkennt. 55:20.700 --> 55:22.520 Das ist extrem hilfreich. 55:23.560 --> 55:26.720 Der wird tatsächlich genau der Nerode-Automat sein, aber das beweisen 55:26.720 --> 55:27.200 wir dir nicht. 55:27.560 --> 55:28.680 Er wird ein kleinster. 55:31.620 --> 55:37.500 Wir könnten uns auch die Nerode-Relation angucken, die auf Grundlage 55:37.500 --> 55:42.020 der Sprache L die Menge aller Wörter in Äquivalenzklassen zerteilt. 55:42.440 --> 55:45.960 Und aufgrund dieser Relation, wenn die endlich ist, können wir uns 55:45.960 --> 55:47.600 einen endlichen Automaten daraus definieren. 55:47.700 --> 55:48.340 Der ist auch minimal. 55:49.560 --> 55:52.440 Das waren die wichtigsten Punkte aus diesem Kapitel. 55:56.330 --> 55:58.930 Dann möchte ich noch mit dem neuen Kapitel anfangen. 55:58.930 --> 56:02.850 Es geht um Turing-Maschinen und Berechenbarkeit. 56:03.070 --> 56:08.110 Das ist jetzt so ein bisschen ein großer Step, deswegen will ich kurz 56:08.110 --> 56:14.130 so eine kleine Entspannpause einlegen und einfach sozusagen jeden fünf 56:14.130 --> 56:16.750 Minuten Zeit gönnen, kurz auszuspacen. 56:17.010 --> 56:20.570 Und ich erzähle einfach ein bisschen was Historisches zu diesen ganzen 56:20.570 --> 56:24.290 Namen, die wir erwähnt haben bisher. 56:25.210 --> 56:29.290 Also Ernil Nerode kam heute besonders oft vor. 56:30.070 --> 56:34.690 Der hat diesen Automaten 1958 definiert. 56:36.010 --> 56:40.950 Er selber wurde 1932 geboren, hat seinen Ph.D. 56:41.010 --> 56:49.150 in Chicago gemacht und ist tatsächlich heute im Stolzenalter von 1985 56:49.150 --> 56:50.830 noch aktiv. 56:50.830 --> 56:57.090 Große Koryphäe in der Informatik, in den theoretischen Gebieten der 56:57.090 --> 57:00.830 Informatik, in der Logik, in der Aussagenlogik, in den Fundamentals of 57:00.830 --> 57:06.830 Mathematics hat mit Tarski und Gödel und so zusammengearbeitet. 57:10.550 --> 57:15.470 Genau, also kann man sich ausrechnen, 25 war er, als er diesen 57:15.470 --> 57:16.490 Automaten definiert hat. 57:16.490 --> 57:21.950 Einige Leute sagen dazu eigentlich den Nerode-Meihl-Automaten. 57:23.350 --> 57:25.310 Das wird irgendwie beiden zugeschrieben. 57:25.630 --> 57:28.850 Wir sagen einfach nur Nerode-Automat, aber dann lassen Sie mich auch 57:28.850 --> 57:30.370 noch John Meihl erwähnen. 57:31.630 --> 57:33.590 Jahrgang 23, Ph.D. 57:33.650 --> 57:40.050 aus Harvard, ist leider schon früh verstorben an Lungenkrebs, ist aber 57:40.050 --> 57:46.370 auch eine große Persönlichkeit in der Logik und in der theoretischen 57:46.370 --> 57:49.330 Informatik, einer der Gründerväter. 57:51.270 --> 57:54.990 Dann Turing, das was wir jetzt tun, die Turing-Maschine. 57:55.370 --> 57:58.250 Ich glaube, ich muss nicht so viel über Turing sagen, der sollte 57:58.250 --> 58:00.490 eigentlich allen ein Begriff sein. 58:01.370 --> 58:05.810 Hier ist wieder mal kurz vielleicht zu erwähnen, dass Turing die 58:05.810 --> 58:08.830 Maschine schon 1936 definiert hat. 58:08.830 --> 58:11.090 Also weit vor dem Nerode-Automaten. 58:11.290 --> 58:15.010 Das heißt, unsere Vorlesung ist nicht unbedingt chronologisch im 58:15.010 --> 58:22.690 Aufzeigen dieser Entdeckungen, sondern eher sinngemäß aufbauend in der 58:22.690 --> 58:23.870 Verstärkung. 58:24.070 --> 58:27.210 Die Turing-Maschine wird stärker sein als der Nerode-Automat. 58:28.110 --> 58:33.130 Okay, Turing, 1912 schon geboren, Ph.D. 58:33.170 --> 58:38.970 aus Princeton, obwohl er eigentlich die ganze Zeit in England, am 58:38.970 --> 58:43.110 King's College war, nur kurze Zeit in Amerika. 58:45.010 --> 58:49.150 Ja, extrem begabter Mann, wurde als Wunderkind gehandelt, ist leider 58:49.150 --> 58:50.090 zu früh gestorben. 58:51.610 --> 58:55.870 Zyanit, Vergiftung, unklar, ob Selbstmord, Unfall oder was auch immer. 58:58.430 --> 59:01.830 Wahrscheinlich am meisten auch bekannt, naja, für die Turing-Maschine 59:01.830 --> 59:06.530 hier, aber auch für Enigma im Zweiten Weltkrieg. 59:06.610 --> 59:10.290 Es gibt Filme über Turing und genügend Bücher, da muss ich nicht viel 59:10.290 --> 59:10.570 sagen. 59:11.230 --> 59:17.810 Okay, ich glaube, es ist genug Zeit zum Erholen vielleicht gewesen. 59:17.810 --> 59:22.030 Dann würden wir jetzt in die Turing-Maschine einsteigen. 59:22.650 --> 59:26.410 Das Gute ist, dass Sie wahrscheinlich die schon kennen, aber es ist 59:26.410 --> 59:29.070 trotzdem wichtig, dass wir uns die nochmal genau angucken, um 59:29.070 --> 59:35.410 eventuell kleine Abweichungen zu bemerken und im Notfall auszuhalten. 59:38.540 --> 59:39.220 Motivation. 59:39.560 --> 59:43.240 Die Motivation ist, wir haben gesehen, endlich Automaten können etwas, 59:44.020 --> 59:47.860 reguläre Sprachen entdecken, aber die können nicht alles. 59:48.560 --> 59:51.100 Sie können relativ einfache Aufgaben, sowas wie reguläre 59:51.100 --> 59:55.920 Klammerausdrücke nicht erkennen, können nicht zählen, sagen wir immer. 59:56.600 --> 01:00:00.120 Also ist vielleicht doch ein bisschen zu begrenzt als 01:00:00.120 --> 01:00:00.940 Berechnungsmodell. 01:00:02.000 --> 01:00:06.680 Das heißt, wir wollen uns überlegen, gibt es ein größeres, ein 01:00:06.680 --> 01:00:11.260 mächtigeres Berechnungsmodell, was ähnlich einfach strukturiert ist, 01:00:11.320 --> 01:00:16.520 dass wir es analysieren können, was halt mehr Probleme lösen kann. 01:00:18.000 --> 01:00:22.340 Gibt es vielleicht Berechnungsmodelle, die alle Probleme lösen können? 01:00:23.620 --> 01:00:27.840 Oder gibt es Probleme, die nicht gelöst werden können? 01:00:28.680 --> 01:00:33.440 Das ist die Frage der Berechenbarkeit, auf die wir letztendlich hinaus 01:00:33.440 --> 01:00:34.080 wollen. 01:00:34.080 --> 01:00:43.380 Also die Hauptfrage in dem Kapitel ist, welche Probleme sind 01:00:43.380 --> 01:00:44.020 berechenbar? 01:00:44.140 --> 01:00:48.420 Für welche Probleme gibt es Berechnungsmodelle, die diese Probleme 01:00:48.420 --> 01:00:49.400 lösen können? 01:00:49.960 --> 01:00:53.440 Wir werden jetzt anfangen mit der Turing-Maschine und zeigen, dass sie 01:00:53.440 --> 01:00:56.920 sehr mächtig ist und wie mächtig werden wir das auch sehen. 01:00:58.480 --> 01:01:02.440 Als Erinnerung, Sie haben wahrscheinlich schon mal eine Register 01:01:02.440 --> 01:01:03.300 -Maschine gesehen. 01:01:04.060 --> 01:01:08.240 Und das ist wahrscheinlich das, was in unserer Vorstellung einem 01:01:08.240 --> 01:01:13.740 Programm, einer Ausführung eines Programms am ähnlichsten ist. 01:01:15.260 --> 01:01:20.300 Also bei der Register-Maschine, die verweist immer auf so ein Programm 01:01:20.300 --> 01:01:21.900 und hat so einen Zähler. 01:01:21.900 --> 01:01:26.760 Das ist einfach nur die Zeile in dem Programm, in dem die Maschine 01:01:26.760 --> 01:01:27.380 gerade ist. 01:01:28.220 --> 01:01:32.900 Und dann, je nachdem, was die Zeile sagt, kann sie operieren auf so 01:01:32.900 --> 01:01:33.700 einem Akkumulator. 01:01:33.840 --> 01:01:38.760 Das ist, wo er jetzt gerade Werte, so ein endlicher Speicher, in dem 01:01:38.760 --> 01:01:41.420 er gerade Werte gespeichert hat und auf dem er rechnen kann. 01:01:42.020 --> 01:01:47.640 Und er kann manchmal auch Daten ablegen oder Daten holen aus den 01:01:47.640 --> 01:01:49.100 sogenannten Registern. 01:01:49.100 --> 01:01:54.100 Und das ist so ein unendlich langes Array von Speichern. 01:01:54.780 --> 01:02:01.140 Und das ist so das Modell, was vielleicht sinngemäß am nächsten am 01:02:01.140 --> 01:02:02.060 Programmieren dran ist. 01:02:02.420 --> 01:02:07.080 Und das haben Sie höchstwahrscheinlich auch schon mal gesehen, wie so 01:02:07.080 --> 01:02:07.660 ein Ding funktioniert. 01:02:07.660 --> 01:02:09.860 Ich will nicht auf alle Details eingehen. 01:02:11.520 --> 01:02:17.880 Das sind so die Standardfunktionen, auf die man dann versucht, alles 01:02:17.880 --> 01:02:18.760 runterzubrechen. 01:02:19.240 --> 01:02:22.200 Also man kann Werte laden aus dem Register. 01:02:22.360 --> 01:02:23.840 Man kann Werte schreiben in die Register. 01:02:24.000 --> 01:02:27.800 Man kann Werte addieren, multiplizieren, dividieren, was auch immer. 01:02:27.940 --> 01:02:31.280 Man kann Go-To-Befehle machen und man versucht es dann da so 01:02:31.280 --> 01:02:35.660 runterzubrechen und sich alles auszugucken. 01:02:36.900 --> 01:02:42.960 Was wir jetzt tun, ist relativ ähnlich tatsächlich, das letzte Mal, 01:02:43.060 --> 01:02:46.380 dass ich das Wort verwende, tatsächlich äquivalent zu 01:02:46.380 --> 01:02:49.080 Registermaschinen, nämlich wir gucken uns Turing-Maschinen an. 01:02:49.240 --> 01:02:51.660 Die sehen ein bisschen anders aus, tun aber wirklich, können das 01:02:51.660 --> 01:02:52.020 Gleiche. 01:02:52.860 --> 01:02:56.820 Die sind vielleicht nicht so sinnbildlich so nah an dem Programm dran 01:02:56.820 --> 01:03:01.520 und sind vielleicht ein bisschen unintuitiv, sind aber wirklich für 01:03:01.520 --> 01:03:05.200 die Sachen, die wir vorhaben, für Berechenbarkeit von Problemen 01:03:05.200 --> 01:03:08.100 analysieren, sind Turing-Maschinen super. 01:03:09.380 --> 01:03:09.980 Gut. 01:03:12.600 --> 01:03:13.520 Turing-Maschine. 01:03:14.140 --> 01:03:16.600 Was wir auch schon mal gesehen haben, aber wir gehen nochmal genau 01:03:16.600 --> 01:03:18.800 durch, wie das für uns aussieht. 01:03:18.960 --> 01:03:22.480 Also eine Turing-Maschine besteht aus drei Teilen. 01:03:23.100 --> 01:03:28.440 Das erste ist ein Eingabe-Rechenband unendlich zu beiden Seiten. 01:03:30.980 --> 01:03:34.380 Unendlich weit nach links und nach rechts ausgehend. 01:03:34.720 --> 01:03:40.440 Auf diesem Band steht die Eingabe in so auch Zellen oder Registern 01:03:40.440 --> 01:03:40.680 drin. 01:03:41.680 --> 01:03:46.500 Und auf dieses Band kann die Maschine auch zwischendurch etwas ablegen 01:03:46.500 --> 01:03:51.160 oder Werte ändern und darauf findet die Berechnung statt. 01:03:51.240 --> 01:03:53.100 Und am Ende auch die Ausgabe steht auf diesem Band. 01:03:55.560 --> 01:04:01.700 Dann gibt es so einen Lese-Schreibkopf, der immer auf einer Zelle des 01:04:01.700 --> 01:04:07.000 Bandes steht und der kann diese Zelle jetzt auslesen oder auch 01:04:07.000 --> 01:04:08.160 überschreiben, verändern 01:04:12.300 --> 01:04:15.700 und kann sich dann noch bewegen nach links oder rechts, immer einen 01:04:15.700 --> 01:04:17.660 Schritt nach links oder einen Schritt nach rechts, oder stehen. 01:04:18.980 --> 01:04:21.600 Das ist das, was der Lese-Schreibkopf kann. 01:04:21.600 --> 01:04:27.060 Und dann gibt es die sogenannte endliche Kontrolle, das symbolisiert 01:04:27.060 --> 01:04:31.640 so ein bisschen den Befehlszähler und das Programm in der 01:04:31.640 --> 01:04:32.380 Registermaschine. 01:04:32.960 --> 01:04:38.080 Also je nachdem, was diese endliche Kontrolle ist, da steht sozusagen 01:04:38.080 --> 01:04:41.200 drin, was der Lese-Schreibkopf gerade tun soll. 01:04:42.720 --> 01:04:47.000 Also abhängig von dem Zustand der endlichen Kontrolle und dem, was 01:04:47.000 --> 01:04:49.500 drin steht, tut die Turing-Maschine irgendwas. 01:04:49.500 --> 01:04:52.640 Lesen, Schreiben, Laufen. 01:04:56.110 --> 01:05:01.250 Also, die Kontrolle, die ist einfach wie bei den endlichen 01:05:01.250 --> 01:05:05.630 deterministischen Automaten, die ist einfach immer in genau einem von 01:05:05.630 --> 01:05:07.250 endlich vielen Zuständen. 01:05:09.390 --> 01:05:14.690 So wie ein Software, ein Programm, ein Code immer bei der Ausführung 01:05:14.690 --> 01:05:16.910 in genau einer Zeile gerade ist. 01:05:17.390 --> 01:05:21.690 Es gibt endlich viele mögliche Zustände, in denen die endliche 01:05:21.690 --> 01:05:23.350 Kontrolle sich befinden kann. 01:05:24.410 --> 01:05:27.430 Und, ja, habe ich schon gesagt, das ist so ungefähr die Befehlszähler 01:05:27.430 --> 01:05:27.990 -Theorem. 01:05:33.190 --> 01:05:33.630 Weiter? 01:05:33.630 --> 01:05:34.190 War ich? 01:05:34.270 --> 01:05:34.710 Ja, war ich schon. 01:05:34.830 --> 01:05:34.990 Gut. 01:05:36.170 --> 01:05:37.930 Dann das Eingabe- und Rechenband. 01:05:38.630 --> 01:05:42.110 Es enthält jetzt eine Folge von Symbolen, also die Symbole werden 01:05:42.110 --> 01:05:45.150 wieder aus einem Alphabet, aus einem endlichen Alphabet kommen. 01:05:46.830 --> 01:05:50.470 Wir stellen uns so Zahlen vor, aber, naja, im Allgemeinen sind das 01:05:50.470 --> 01:05:51.490 wieder Symbole. 01:05:51.930 --> 01:05:54.170 Ein Symbol pro Zelle. 01:05:55.370 --> 01:05:58.690 Und das entspricht sozusagen dem Register. 01:06:01.110 --> 01:06:06.070 Und dann, was die Turing-Maschine tun kann, ist, sie kann das aktuelle 01:06:06.070 --> 01:06:10.330 Symbol lesen, wo der Leseschreibkopf gerade steht. 01:06:10.330 --> 01:06:14.530 Sie kann den Zustand aus der endlichen Kontrolle sozusagen lesen, 01:06:14.670 --> 01:06:15.930 überprüfen, in welchem Zustand sie sind. 01:06:16.330 --> 01:06:19.590 Und aus diesen beiden Informationen, aus dem Symbol, was gelesen wird, 01:06:19.690 --> 01:06:23.850 und dem Zustand, in dem ich bin, gibt es eine Vorschrift, was dann 01:06:23.850 --> 01:06:24.470 passieren wird. 01:06:24.750 --> 01:06:26.210 Das ist wieder so eine Übergangsfunktion. 01:06:27.250 --> 01:06:29.490 Und was passieren soll, was kann passieren? 01:06:29.610 --> 01:06:32.870 Es kann sein, dass sich der Zustand hier unten ändert in einen anderen 01:06:32.870 --> 01:06:33.410 Zustand. 01:06:35.430 --> 01:06:41.530 Es kann sein, dass das Symbol überschrieben wird, durch ein anderes 01:06:41.530 --> 01:06:41.870 Symbol. 01:06:42.590 --> 01:06:46.150 Und es kann sein, dass der Leseschreibkopf nach einem Schritt nach 01:06:46.150 --> 01:06:49.670 rechts geht, oder ein Schritt nach links geht, oder stehen bleiben 01:06:49.670 --> 01:06:49.910 soll. 01:06:53.570 --> 01:06:58.810 So, also, das ist die formale Definition hinter diesem Bild einer 01:06:58.810 --> 01:07:00.390 deterministischen Turing-Maschine. 01:07:01.530 --> 01:07:03.470 Endliche Menge von Zuständen. 01:07:04.050 --> 01:07:07.210 Sigma ist wieder ein endliches Eingabealphabet. 01:07:07.990 --> 01:07:12.910 Wir lassen jetzt auch noch ein Blank-Symbol zu, das ist sozusagen, da 01:07:12.910 --> 01:07:15.670 steht nichts drin, in der Zelle von dem Eingabeband. 01:07:16.070 --> 01:07:17.010 Das ist also ein Blank-Symbol. 01:07:17.690 --> 01:07:20.270 Also das Blank-Symbol ist nicht aus dem Eingabealphabet. 01:07:21.070 --> 01:07:25.010 Außerdem lassen wir dann auch noch zu, dass die Turing-Maschine 01:07:25.010 --> 01:07:29.870 eventuell während ihrer Ausführung neue Symbole benutzt. 01:07:29.870 --> 01:07:32.490 Die nicht in dem Eingabealphabet drin sind. 01:07:32.970 --> 01:07:37.490 Und wir bezeichnen dann mit Gamma das gesamte Bandalphabet. 01:07:37.650 --> 01:07:39.730 Also alle Symbole, die jemals auf dem Band stehen dürfen. 01:07:40.050 --> 01:07:43.590 Das beinhaltet insbesondere Sigma, und das Blank-Symbol aber kann noch 01:07:43.590 --> 01:07:44.050 mehr sein. 01:07:45.030 --> 01:07:46.630 Und welche Hilfs-Symbole. 01:07:48.150 --> 01:07:54.210 Es gibt einen Start-Zustand, S, wo die endliche Kontrolle zu Beginn 01:07:54.210 --> 01:07:57.850 der Ausführung, in dem es sich befindet. 01:07:57.850 --> 01:07:59.270 Und dann gibt es diese Übergangs-Funktion. 01:08:00.070 --> 01:08:04.150 Übergangs-Funktion hängt ab von dem Zustand, in dem die endliche 01:08:04.150 --> 01:08:05.170 Kontrolle gerade ist. 01:08:05.670 --> 01:08:09.650 Dem Bandsymbol, das gerade an der Zelle von dem Lese-Schreiben-Kopf 01:08:09.650 --> 01:08:09.910 ist. 01:08:10.510 --> 01:08:14.810 Und bildet dann jetzt ab, deterministisch, auf neuer Zustand für die 01:08:14.810 --> 01:08:15.650 endliche Kontrolle. 01:08:15.870 --> 01:08:18.630 Neues Bandsymbol für diese Zelle. 01:08:18.750 --> 01:08:20.990 Wird überschrieben, oder vielleicht auch das gleiche. 01:08:20.990 --> 01:08:25.530 Und die Informationen gehen nach links, nach rechts oder bleiben 01:08:25.530 --> 01:08:25.850 stehen. 01:08:25.970 --> 01:08:30.170 L, R oder N, genau, für den Lese-Schreiben-Kopf. 01:08:31.650 --> 01:08:36.410 Und schlussendlich gibt es eine Menge von Zuständen. 01:08:36.670 --> 01:08:42.030 F, eine Teilmenge, der Zustandsmenge, das sind die Endzustände. 01:08:42.150 --> 01:08:43.890 Und hier ist ein ganz klein wenig anders. 01:08:44.070 --> 01:08:47.870 Die Turing-Maschine stoppt, sobald das erste Mal ein Endzustand 01:08:47.870 --> 01:08:48.370 erreicht wird. 01:08:50.170 --> 01:08:50.730 Okay. 01:08:52.210 --> 01:08:55.190 Also wenn, das ist so eine ausgezeichnete Menge von Endzuständen, und 01:08:55.190 --> 01:08:57.190 sobald so ein Endzustand erreicht wurde, sofort stoppt. 01:09:00.030 --> 01:09:00.590 Gut. 01:09:00.790 --> 01:09:03.830 Wir malen wieder so ne Bilder. 01:09:05.370 --> 01:09:12.850 Wir visualisieren diesen Übergang von Q A nach P, B und L. 01:09:12.850 --> 01:09:19.370 Also wir sind im Zustand Q, wir lesen Symbol A, wir schreiben und dann 01:09:19.370 --> 01:09:23.690 heißt es, wenn wir in Q sind und A lesen, dann heißt es, schreibe B an 01:09:23.690 --> 01:09:27.850 diese Stelle und gehe zum Beispiel hier einen Schritt nach links und 01:09:27.850 --> 01:09:33.710 ändere den Zustand in P. Das ist so die grafische Art, wie wir so eine 01:09:33.710 --> 01:09:35.810 Turing -Maschine aufmalen. 01:09:39.030 --> 01:09:40.730 Das ist die Bedeutung geworden. 01:09:41.870 --> 01:09:45.350 Also ein paar kleine Konventionen, die vielleicht nicht Standard sind. 01:09:46.750 --> 01:09:50.190 Wir sagen, dass der Zustand, in dem die Turing-Maschine startet, der 01:09:50.190 --> 01:09:52.330 ist üblicherweise mit S gekennzeichnet. 01:09:52.790 --> 01:09:57.410 Wir sagen außerdem, dass der Lese-Schreibkopf anfängt immer an der 01:09:57.410 --> 01:10:01.850 linkesten Stelle des Bandes, das ein Eingabesymbol enthält. 01:10:02.790 --> 01:10:03.330 Ein Blank. 01:10:04.050 --> 01:10:06.990 Das ist sozusagen immer unsere Position 0 auf dem Band. 01:10:09.890 --> 01:10:13.110 Und wir sagen, die Turing-Maschine stoppt, wie gerade schon erwähnt, 01:10:13.190 --> 01:10:16.170 wenn sie zum ersten Mal in einen Endzustand kommt. 01:10:16.750 --> 01:10:19.750 Oder es gibt noch eine zweite Möglichkeit, wann die Turing-Maschine 01:10:19.750 --> 01:10:20.910 stoppt. 01:10:21.210 --> 01:10:24.990 Nämlich, wenn ganz offensichtlich ist, dass sie jetzt nichts mehr tut. 01:10:25.730 --> 01:10:27.370 Einfach so was wie fertig. 01:10:28.270 --> 01:10:34.890 Und das ist zum Beispiel, oder insbesondere in dem Fall, dass wir sind 01:10:34.890 --> 01:10:37.570 in einem Zustand Q und lesen gerade ein Symbol A. 01:10:37.770 --> 01:10:42.190 Und für dieses Paar Q A sagt unsere Übergangsfunktion, nun bleibe in 01:10:42.190 --> 01:10:44.450 Q, lasse A und bewege den Schreibkopf. 01:10:45.630 --> 01:10:48.390 Dann ist klar, die Maschine steht. 01:10:49.170 --> 01:10:49.790 Ist vorbei. 01:10:50.630 --> 01:10:53.030 Und dann sagen wir, die Maschine stoppt. 01:10:54.410 --> 01:10:57.690 Also sie stoppt, wenn sie das erste Mal in einen Endzustand erreicht. 01:10:57.890 --> 01:11:02.130 Oder wenn sie mal in so eine Situation reinläuft. 01:11:03.370 --> 01:11:07.070 Das heißt insbesondere, weil sie stoppt, wenn sie in einen Endzustand 01:11:07.070 --> 01:11:11.950 kommt, wir werden nicht spezifizieren, was jetzt Delta von Q A ist, 01:11:12.010 --> 01:11:13.070 wenn Q ein Endzustand ist. 01:11:13.350 --> 01:11:15.810 Weil es wird sowieso nie ausgewertet. 01:11:16.150 --> 01:11:19.150 Also es gibt keine Übergänge aus Endzuständen heraus. 01:11:24.440 --> 01:11:27.260 Vielleicht sage ich hier nochmal eine kleine erste Bemerkung. 01:11:27.780 --> 01:11:32.680 Ich sage immer, wenn die Turing-Maschine stoppt, ist es möglich, dass 01:11:32.680 --> 01:11:34.340 die Turing-Maschine nicht stoppt. 01:11:36.180 --> 01:11:44.020 Es kann sein, dass mit bestimmten Übergangsfunktionen und bestimmten 01:11:44.020 --> 01:11:47.760 Eingaben die Turing-Maschine einfach unendlich lange weitermacht. 01:11:47.760 --> 01:11:51.000 Also man kann sich ganz leicht was überlegen, indem man einfach sagt, 01:11:51.440 --> 01:11:54.480 zum Beispiel die Übergangsfunktion sagt immer, bleibe in dem Zustand, 01:11:54.580 --> 01:11:56.200 lasse das Symbol, aber gehe einen Schritt nach rechts. 01:11:58.160 --> 01:12:00.600 Dann wird die Turing-Maschine anfangen und immer nach rechts gehen. 01:12:02.040 --> 01:12:03.020 Okay, dann stoppt sie nicht. 01:12:03.100 --> 01:12:04.140 Sie kommt in keinen Endzustand. 01:12:04.260 --> 01:12:07.600 Sagen wir mal, es gibt keinen Endzustand und sie wird nicht in dieser 01:12:07.600 --> 01:12:08.580 Situation landen. 01:12:09.440 --> 01:12:11.860 Also sie könnte eventuell nicht stoppen. 01:12:12.840 --> 01:12:22.300 Gut, jetzt ist die Frage, was erkennt, berechnet diese Turing 01:12:22.300 --> 01:12:22.560 -Maschine? 01:12:25.440 --> 01:12:33.640 Also wir gehen wieder davon aus, wir fangen an mit dem Zustand S und 01:12:33.640 --> 01:12:36.440 wir lesen das erste Symbol der Eingabe. 01:12:36.440 --> 01:12:42.260 Das linkeste Symbol aus dem Eingabeband. 01:12:44.100 --> 01:12:47.160 Okay, und hier ist jetzt diese grafische Darstellung, was passieren 01:12:47.160 --> 01:12:47.500 soll. 01:12:48.200 --> 01:12:49.160 Also gehen wir durch. 01:12:49.800 --> 01:12:53.420 Wir sind jetzt an S und wir sagen immer, wir lesen eine 0. 01:12:53.900 --> 01:12:59.420 Dann sagt die Turing-Maschine, lasse die 0 dort stehen, bewege den 01:12:59.420 --> 01:13:03.600 Schreibkopf 1 nach rechts und gehe in den Zustand Q1 über. 01:13:06.020 --> 01:13:11.300 Wenn ich in dem Zustand Q1 bin, dann kann ich sagen, und ich lese eine 01:13:11.300 --> 01:13:14.180 0, lasse es und gehe einen Schritt nach rechts. 01:13:14.340 --> 01:13:16.940 Ich lese eine 1, lasse es und gehe einen Schritt nach rechts und so 01:13:16.940 --> 01:13:17.220 weiter. 01:13:17.640 --> 01:13:22.040 Also hier sieht man, dass wird die Turing-Maschine dann in so ein 01:13:22.040 --> 01:13:27.480 Endloses nach rechts laufen, ohne dass das Band weiter überschrieben 01:13:27.480 --> 01:13:27.740 wird. 01:13:27.740 --> 01:13:28.580 Okay. 01:13:30.120 --> 01:13:32.540 Gehen wir wieder zurück am Startzustand. 01:13:33.280 --> 01:13:39.720 Wenn ich dann eine 1 lese, dann sagt die Übergangsfunktion, schreibe 01:13:39.720 --> 01:13:48.960 blank statt der 1 und gehe einen Schritt nach links und wechsele in 01:13:48.960 --> 01:13:49.820 den Zustand Q2. 01:13:50.080 --> 01:13:51.660 Und dieser Zustand ist ein Endzustand. 01:13:53.800 --> 01:13:54.400 Okay. 01:13:54.780 --> 01:13:56.980 Hier haben wir jetzt eine Vollständigkeit halber einfach nochmal 01:13:56.980 --> 01:14:00.560 ausgehende Übergänge aus dem Endzustand gemacht, aber wie gesagt, 01:14:01.200 --> 01:14:03.040 werden wir in Zukunft vermeiden. 01:14:03.320 --> 01:14:06.620 Weil Endzustand erreicht, heißt sowieso sofort die Turing-Maschine 01:14:06.620 --> 01:14:06.980 stoppen. 01:14:07.620 --> 01:14:09.140 Also was tut diese Turing-Maschine? 01:14:10.120 --> 01:14:10.720 Nun, 01:14:14.200 --> 01:14:14.700 was tut sie? 01:14:14.700 --> 01:14:14.800 Okay. 01:14:17.700 --> 01:14:17.880 Ja. 01:14:21.550 --> 01:14:24.310 Ja, und wenn, in welchem Fall? 01:14:27.360 --> 01:14:27.900 Genau. 01:14:28.640 --> 01:14:35.360 Also die Turing-Maschine erkennt die Wörter aus 0,1 Stern, die mit 01:14:35.360 --> 01:14:36.160 einer 1 beginnen. 01:14:37.280 --> 01:14:40.080 Und wenn es eine 1 ist, dann stoppt die Maschine. 01:14:41.120 --> 01:14:46.300 Auf dem Ausgabeband steht dann das gleiche Wort, bloß mit der 01:14:46.300 --> 01:14:47.700 gelöschten ersten 1. 01:14:48.500 --> 01:14:54.220 Und wenn es eine 0 ist, das erste Zeichen, dann stoppt die Maschine 01:14:54.220 --> 01:14:56.640 nicht und sie verändert auch das Band. 01:14:58.720 --> 01:14:59.320 Okay. 01:15:00.680 --> 01:15:04.440 Und außerdem der Leseschreibkopf steht nach dem Stopp links neben der 01:15:04.440 --> 01:15:05.780 Stelle, wo die führende 1 war. 01:15:07.460 --> 01:15:08.060 Gut. 01:15:09.740 --> 01:15:12.220 Ja, das ist so ein kleines Beispiel. 01:15:12.580 --> 01:15:16.140 Also, es gibt Eingaben, hier in diesem kleinen Beispiel, wo die Turing 01:15:16.140 --> 01:15:18.020 -Maschine eventuell niemals stoppt. 01:15:20.900 --> 01:15:24.040 Welche Eingaben sind das in diesem Beispiel, das wissen wir, falls die 01:15:24.040 --> 01:15:25.780 nicht mit einer 1 beginnt. 01:15:27.960 --> 01:15:30.620 Nun sagen wir, ähm... 01:15:31.920 --> 01:15:37.640 Genau, noch eine andere Besonderheit im Gegensatz zu deterministischen 01:15:37.640 --> 01:15:42.400 endlichen Automaten ist, die Turing-Maschine, die erkennt nicht nur 01:15:42.400 --> 01:15:46.040 eventuell irgendwelche Sprachen, irgendwelche Eingaben und stoppt oder 01:15:46.040 --> 01:15:51.800 tut es nicht, sondern sie verändert auch die Eingabe und man kann sich 01:15:51.800 --> 01:15:58.300 angucken, wenn die Turing-Maschine stoppt, in welchem Zustand ist das 01:15:58.300 --> 01:16:02.720 Rechenband und an welcher Stelle ist der Leseschreibkopf. 01:16:03.380 --> 01:16:04.760 Und das ist sozusagen die Ausgabe. 01:16:05.260 --> 01:16:09.680 Also die Turing-Maschine kann auch, statt nur Ja, Nein zu sagen oder 01:16:09.680 --> 01:16:12.340 Stoppen oder Nichtstoppen, kann sie auch eine Ausgabe auf das 01:16:12.340 --> 01:16:13.340 Rechenband schreiben. 01:16:14.720 --> 01:16:14.900 Okay. 01:16:15.440 --> 01:16:19.740 Also die Ausgabe referenziert für uns immer den Inhalt des Bandes nach 01:16:19.740 --> 01:16:20.520 der Bearbeitung. 01:16:20.520 --> 01:16:24.660 Okay, man kann es jetzt mathematisch, formell sich so überlegen, dass 01:16:24.660 --> 01:16:27.820 man sagt, okay, die Turing-Maschine tut eigentlich das Folgende, sie 01:16:27.820 --> 01:16:35.700 nimmt irgendetwas, was auf dem Rechenband steht und bildet es ab auf 01:16:35.700 --> 01:16:38.060 etwas, was danach auf dem Rechenband stehen könnte. 01:16:38.220 --> 01:16:40.820 Danach könnten jetzt natürlich diese Hilfssymbole stehen, deswegen 01:16:40.820 --> 01:16:41.960 steht da Gamma und nicht Sigma. 01:16:42.960 --> 01:16:46.780 Und das ist nur eine partielle Funktion, weil eventuell für einige 01:16:46.780 --> 01:16:53.100 Eingabewerte es keine wohldefinierte Ausgabe gibt, wenn die Turing 01:16:53.100 --> 01:16:54.160 -Maschine nicht stoppt. 01:16:55.000 --> 01:16:55.040 Okay. 01:16:57.360 --> 01:17:03.600 Die formelle Definition wäre dann also hier in unserem Fall F von W 01:17:03.600 --> 01:17:10.960 ist gleich V, wenn W gerade 1 konkateniert mit V ist, also das ist die 01:17:10.960 --> 01:17:18.120 Ausgabe, und undefiniert sonst nur eine partielle Funktion. 01:17:19.700 --> 01:17:20.020 Gut. 01:17:30.060 --> 01:17:34.640 Das ist... genau, ich glaube, der letzte Punkt ist der wichtigste. 01:17:35.820 --> 01:17:40.680 Wenn wir für ein bestimmtes QA-Paar keinen Übergang einzeichnen, unser 01:17:40.680 --> 01:17:46.000 Bild, dann heißt es für uns dort, stoppt die Turing-Maschine. 01:17:46.660 --> 01:17:50.440 Also zum Beispiel können Sie sich einfach denken, jedes Mal, wenn Sie 01:17:50.440 --> 01:17:55.680 für so ein paar QA keine Übergangsfunktion, keinen ausgehenden Pfeil 01:17:55.680 --> 01:17:59.240 definiert sehen, dann können Sie sich denken, okay, für dieses Paar 01:17:59.240 --> 01:18:02.120 geht QA über auf QAN. 01:18:03.040 --> 01:18:04.040 Und damit stoppt die Maschine. 01:18:04.820 --> 01:18:07.720 Okay, zum Beispiel hier von S aus ist nicht klar, wenn jetzt unser 01:18:07.720 --> 01:18:11.420 Alphabet mehr als nur die 1 enthält, was soll dann passieren, wenn er 01:18:11.420 --> 01:18:15.460 eine 0 liest, und hier hinten aus N-Zuständen meinen wir sowieso keine 01:18:15.460 --> 01:18:16.140 Übergänge raus. 01:18:16.640 --> 01:18:16.660 Okay. 01:18:17.460 --> 01:18:17.660 Gut. 01:18:18.080 --> 01:18:19.220 So, jetzt allerletzte Folie. 01:18:20.680 --> 01:18:23.020 Definiert einfach nur vier Wörter. 01:18:23.020 --> 01:18:28.640 Wir sagen, was es heißt, dass eine Turing-Maschine eine Eingabe 01:18:28.640 --> 01:18:32.940 akzeptiert, also ein Wort auf dem Rechenband als Eingabe akzeptiert, 01:18:33.220 --> 01:18:35.140 heißt, wenn sie stoppt. 01:18:36.320 --> 01:18:36.800 Okay. 01:18:37.580 --> 01:18:42.500 Wenn mit diesem Wort auf dem Eingabewand die Turing-Maschine stoppt, 01:18:42.520 --> 01:18:44.900 dann heißt es, die Turing-Maschine akzeptiert dieses Wort. 01:18:44.900 --> 01:18:48.800 Und dann die Menge der Wörter, die akzeptiert werden von dieser 01:18:48.800 --> 01:18:53.440 gegebenen Turing-Maschine ist die Sprache L, die akzeptiert wird von 01:18:53.440 --> 01:18:53.980 der Turing-Maschine. 01:18:54.260 --> 01:18:58.260 Also eine Sprache L wird akzeptiert von einer Turing-Maschine, wenn 01:18:58.260 --> 01:19:01.460 genau für die Wörter in dieser Sprache die Turing-Maschine stoppt. 01:19:01.980 --> 01:19:03.900 Für die anderen Wörter... 01:19:10.900 --> 01:19:13.080 Oh, ganz kurz, ganz wichtig. 01:19:13.920 --> 01:19:15.060 Das sind diese kleinen Feinheiten. 01:19:15.060 --> 01:19:18.680 Also nicht nur, dass sie stoppt, sondern sie stoppt in einem Zustand 01:19:18.680 --> 01:19:19.200 aus F. 01:19:21.100 --> 01:19:23.060 Es gibt zwei Möglichkeiten zu stoppen. 01:19:23.740 --> 01:19:29.560 Weil wir F treffen, oder weil wir dieses Tur-Nichts-Mehr-Fertig 01:19:29.560 --> 01:19:30.880 abgearbeitet haben. 01:19:32.160 --> 01:19:36.960 Und wenn wir akzeptieren, nur wenn wir auf F treffen und deswegen 01:19:36.960 --> 01:19:38.140 stoppen, aus dem Grund. 01:19:40.080 --> 01:19:43.800 Also es gibt im Prinzip drei Möglichkeiten, drei mögliche Szenarien, 01:19:43.920 --> 01:19:46.680 was passieren könnte mit einer Turing-Maschine und einer Eingabe. 01:19:47.360 --> 01:19:50.620 Die Eingabe könnte letztendlich auf F treffen und die Turing-Maschine 01:19:50.620 --> 01:19:51.100 stoppt. 01:19:51.760 --> 01:19:56.860 Die Eingabe könnte so sein, dass die Turing-Maschine ewig weitermacht. 01:19:57.100 --> 01:19:58.460 Die Turing-Maschine stoppt nicht. 01:19:59.380 --> 01:20:03.880 Oder drittens, die Turing-Maschine stoppt, aber nicht, weil sie auf F 01:20:03.880 --> 01:20:07.520 trifft, sondern weil sie auf so einen Zustand trifft, wo sie einfach 01:20:07.520 --> 01:20:08.080 nichts mehr tut. 01:20:09.520 --> 01:20:10.400 Drei Möglichkeiten. 01:20:10.600 --> 01:20:14.600 Nur die erste, stoppen wegen F, heißt akzeptieren. 01:20:17.200 --> 01:20:19.200 Und dementsprechend auch für die Sprache jetzt. 01:20:19.800 --> 01:20:22.900 Wir sagen, die Wörter aus der Sprache sind genau die Wörter, die 01:20:22.900 --> 01:20:24.560 stoppen wegen F haben. 01:20:24.560 --> 01:20:29.160 Und die Wörter, die nicht aus der Sprache sind, egal. 01:20:30.940 --> 01:20:34.220 Entweder stoppt nicht oder stoppt aber nicht in F. 01:20:34.440 --> 01:20:37.480 Für manche Wörter so, für manche Wörter so spezifizieren wir nicht. 01:20:38.520 --> 01:20:44.560 Wir sagen, eine Sprache ist entscheidbar, wenn die Turing-Maschine 01:20:44.560 --> 01:20:52.740 immer stoppt und in F genau auf der Sprache und in Nicht-F genau nicht 01:20:52.740 --> 01:20:53.340 in der Sprache. 01:20:54.080 --> 01:20:59.600 Die Turing-Maschine stoppt immer nach endlicher Zeit und dann kann man 01:20:59.600 --> 01:21:05.220 sozusagen ablesen an dem Endzustand, ob es in F ist, dann war das Wort 01:21:05.220 --> 01:21:07.760 in der Sprache und wenn es nicht in F ist, ist das Wort nicht in der 01:21:07.760 --> 01:21:07.940 Sprache. 01:21:08.140 --> 01:21:09.700 Das ist eine entscheidbare Sprache. 01:21:10.220 --> 01:21:13.320 Eine Sprache heißt entscheidbar oder wird entschieden durch die Turing 01:21:13.320 --> 01:21:14.680 -Maschine, wenn das geht. 01:21:15.080 --> 01:21:21.400 Das heißt, hier darf die Turing-Maschine für irgendeine Eingabe mal 01:21:21.400 --> 01:21:21.940 nicht stoppen. 01:21:24.880 --> 01:21:29.280 Andersrum heißt eine Sprache semi-entscheidbar, wenn sie wenigstens 01:21:29.280 --> 01:21:32.100 akzeptiert wird von der Turing-Maschine. 01:21:32.420 --> 01:21:35.940 Das heißt, sie darf auf 9 Instanzen unendlich lang brauchen. 01:21:39.120 --> 01:21:45.300 Gut, das ist ganz wichtig, sich einmal vor Augen zu führen, was es 01:21:45.300 --> 01:21:48.460 heißt, dass eine Sprache semi-entscheidbar ist oder entscheidbar. 01:21:52.540 --> 01:21:54.420 Meinenwegen auch aus rein praktischer Sicht. 01:21:54.780 --> 01:21:58.100 Wir sehen die Turing-Maschine als ein Programm geschrieben und ich 01:21:58.100 --> 01:22:05.180 garantiere Ihnen, dass mein Programm semi-entscheidbar, also Ihre 01:22:05.180 --> 01:22:09.660 Sprache, die Sie gerne entschieden haben wollen, ich sage, die wird 01:22:09.660 --> 01:22:13.160 semi -entschieden von der Turing-Maschine oder sie wird rekursiv 01:22:13.160 --> 01:22:13.740 aufgezählt. 01:22:14.480 --> 01:22:18.720 Das heißt, wenn das Wort in der Sprache ist, garantiere ich Ihnen, 01:22:18.820 --> 01:22:22.420 meine Turing-Maschine stoppt und sagt, ja, das Wort ist in der 01:22:22.420 --> 01:22:22.740 Sprache. 01:22:23.340 --> 01:22:27.180 Wenn das Wort nicht in der Sprache ist, garantiere ich Ihnen, dass die 01:22:27.180 --> 01:22:31.580 Turing -Maschine entweder unendlich lange braucht oder stoppt und 01:22:31.580 --> 01:22:32.860 sagt, nein, es ist nicht in der Sprache. 01:22:35.900 --> 01:22:38.900 Vielleicht nicht besonders praktikabel, weil dann schmeißen Sie ein 01:22:38.900 --> 01:22:42.460 Wort rein und warten und warten und warten und Sie wissen halt nicht, 01:22:42.580 --> 01:22:44.200 wann unendlich lange vorbei ist. 01:22:46.840 --> 01:22:47.340 Gut. 01:22:48.720 --> 01:22:49.180 Alles klar. 01:22:49.480 --> 01:22:50.200 Das war's für heute.