WEBVTT 00:05.060 --> 00:05.700 Okay. 00:06.500 --> 00:08.140 Herzlich willkommen zur Vorlesung. 00:09.140 --> 00:13.140 Die letzte Vorlesung in diesem Jahr und wir fangen ein neues Kapitel 00:13.140 --> 00:13.400 an. 00:13.500 --> 00:16.540 Wir haben jetzt das Kapitel Komplexitätstheorie abgeschlossen. 00:17.080 --> 00:20.660 Aber ich hatte Ihnen das letzte Mal auch schon angekündigt, Turing 00:20.660 --> 00:24.000 -Maschinen werden trotzdem wieder auftauchen. 00:24.860 --> 00:29.120 Der Grund ist auch, dass wir ein komplett neues Konzept kennenlernen. 00:29.420 --> 00:30.900 Das nennt sich Grammatik. 00:30.900 --> 00:36.560 Das hat allerdings Beziehungen zu dem, was wir davor gemacht haben, 00:36.880 --> 00:41.280 nämlich formale Sprachen und auch Berechnungsmodelle. 00:42.380 --> 00:47.160 Wir wollen Grammatiken jetzt erstmal einführen, dann sehen, wie 00:47.160 --> 00:53.900 Grammatiken Sprachen definieren und dann uns fragen, was das für 00:53.900 --> 00:57.120 Sprachen sind, die von verschiedenen Grammatiken mit verschiedenen 00:57.120 --> 01:00.700 Einschränkungen erstellt werden. 01:02.180 --> 01:07.500 Also Grammatiken ganz allgemein sind einfach Regelsysteme, mit denen 01:07.500 --> 01:09.980 Wörter erzeugt werden. 01:10.140 --> 01:15.260 Und der Unterschied in der Denkweise, die wir jetzt haben werden, ist 01:15.260 --> 01:21.700 so, dass wir einfach anfangen mit sozusagen dem leeren Wort und dann 01:21.700 --> 01:25.580 Regeln definieren, was man auf dieses Wort anwenden kann. 01:27.360 --> 01:29.540 Ersetzungen werden dort drin getätigt. 01:30.360 --> 01:33.520 Teilstrings werden ersetzt durch andere Teilstrings, kleiner oder 01:33.520 --> 01:34.040 größer. 01:34.880 --> 01:37.440 Und unter einer bestimmten Bedingung sind die Wörter, die dort 01:37.440 --> 01:40.140 entstehen, dann die Wörter in der Sprache. 01:42.000 --> 01:44.620 Also machen wir ein Beispiel. 01:45.920 --> 01:46.560 Klicken. 01:47.020 --> 01:49.000 Sie haben das beim letzten Mal kennengelernt. 01:49.100 --> 01:55.660 Ein Graph G mit Knotenmenge V und Kantenmenge E hat eine Clique, wenn 01:55.660 --> 01:58.440 es eine Teilmenge... 01:58.440 --> 02:01.060 Eine Clique in einem Graphen ist eine Teilmenge von Knoten, die 02:01.060 --> 02:03.280 paarweise miteinander durch Kanten verbunden sind. 02:04.300 --> 02:08.840 Und hier ist jetzt gerade die Sprache aller Graphen, die eine Clique 02:08.840 --> 02:12.020 der Größe Betrag von V halbe enthalten. 02:12.220 --> 02:15.160 Also eine Clique auf der Hälfte der Knoten. 02:16.140 --> 02:20.880 Und immer wenn ich hier sage, Sprache aller Graphen, dann natürlich 02:20.880 --> 02:24.420 meinen wir das unter einer geeigneten Kodierung, über die wir jetzt 02:24.420 --> 02:26.740 hier nicht explizit sprechen. 02:27.660 --> 02:33.440 Also, wie lässt sich diese Sprache aufbauen, sozusagen vom leeren 02:33.440 --> 02:33.800 Wort? 02:35.360 --> 02:39.820 Ganz grob würde man zum Beispiel die folgenden vier Schritte machen. 02:40.080 --> 02:44.240 Zuerst wählt man die Zahl der Knoten, die der Graph enthalten soll. 02:44.340 --> 02:47.320 Also vom leeren Wort sozusagen kreiert man erstmal die Knoten. 02:48.420 --> 02:51.200 N Stück für irgendeine Wahl von N. 02:51.620 --> 02:54.480 Diese Wahl ist zum Beispiel nicht deterministisch. 02:57.800 --> 03:01.920 Dann, im zweiten Schritt wird jetzt ausgewählt, welche von diesen N 03:01.920 --> 03:03.720 Knoten denn jetzt diese Clique bilden sollen. 03:05.020 --> 03:09.080 Wieder nicht deterministisch, einfach auswählen, die Hälfte der 03:09.080 --> 03:13.540 Knoten, jeden zweiten oder auch die erste Hälfte, oder halt irgendwie, 03:13.720 --> 03:14.860 dass es von der Zahl her stimmt. 03:15.400 --> 03:17.980 Und dann in einem dritten Schritt, der ist allerdings deterministisch, 03:18.680 --> 03:21.480 wäre dann in dieser ausgewählten Knotenmenge, müssten alle Kanten 03:21.480 --> 03:24.280 hinzugefügt werden, damit die Clique auch da ist. 03:26.120 --> 03:30.460 Und dann in einem vierten Schritt könnte man jede weitere Kante, die 03:30.460 --> 03:33.820 jetzt noch nicht da ist, sich nicht deterministisch entscheiden, ob 03:33.820 --> 03:34.720 die hin soll oder nicht. 03:36.500 --> 03:41.440 Also das ist irgendwie eine Art, Grafen mit dieser konkreten 03:41.440 --> 03:43.900 Eigenschaft zu erstellen. 03:45.960 --> 03:51.540 Und wir sehen das jetzt als eine Art, eine Sprache zu erstellen, indem 03:51.540 --> 03:53.100 wir bestimmten Regeln folgen. 03:53.640 --> 03:57.080 Wir können nicht beliebige Wörter da erstellen, sondern die müssen 03:57.080 --> 04:01.460 diesen Regeln folgen, damit sie genau die Wörter in dieser Sprache 04:01.460 --> 04:01.720 sind. 04:01.920 --> 04:04.600 Und das ist so die Idee hinter der Grammatik. 04:04.600 --> 04:10.580 Wir fangen an mit nichts oder dem leeren Wort und erlauben dann 04:10.580 --> 04:13.640 gewisse Übergänge, Ersetzungen in dem Wort. 04:14.480 --> 04:19.940 Und nach einem sozusagen Kriterium ist dann alle Wörter, die so 04:19.940 --> 04:22.620 erzeugt werden können, sind die Wörter der Sprache. 04:24.240 --> 04:27.440 Das so als grobes Beispiel. 04:27.560 --> 04:31.780 Und dabei können diese Regeln nicht deterministisch sein. 04:31.780 --> 04:37.240 Also es kann sein, dass mehrere Regeln anwendbar sind und dann sagen 04:37.240 --> 04:41.060 wir einfach, jede von denen ist anwendbar und führt zu einem 04:41.060 --> 04:43.880 unterschiedlichen Ergebnis, zu einem unterschiedlichen Wort. 04:44.300 --> 04:51.260 Also am Anfang erlauben wir jede Zahl n hier und anwenden der Regel 04:51.260 --> 04:56.140 für n gleich 3, gibt dann halt einen Grafen auf drei Knoten statt auf 04:56.140 --> 04:57.000 einer anderen Knotenzahl. 04:57.400 --> 04:57.620 Gut. 04:58.940 --> 05:02.380 Und wichtig ist hier, dass wir sozusagen für diese Sprache, die wir 05:02.380 --> 05:07.020 abstrakt einfach definiert haben da oben, als die Grafen, die eine 05:07.020 --> 05:10.500 Clique der Größe V halbe enthalten, dass wir diese Sprache so 05:10.500 --> 05:11.360 erstellen können. 05:11.760 --> 05:15.400 Dass wir für diese Sprache eine Grammatik gefunden haben. 05:15.520 --> 05:21.260 Wir haben die Regeln aufgesetzt, die, wenn man die Regeln befolgt, nur 05:21.260 --> 05:26.080 Wörter aus dieser Sprache generieren und außerdem jedes Wort aus der 05:26.080 --> 05:28.100 Sprache kann so generiert werden. 05:29.280 --> 05:29.920 Gut. 05:31.220 --> 05:34.800 Ein zweites Beispiel sind arithmetische Ausdrücke. 05:35.760 --> 05:44.780 Also wir reden von Ausdrücken, Termen auf, naja, weiß ich nicht, zum 05:44.780 --> 05:50.460 Beispiel Variablen oder was anderes, der Form entweder einfach nur A, 05:50.540 --> 05:53.520 eine Variable, oder wenn wir zwei arithmetische Ausdrücke schon haben, 05:53.520 --> 05:56.880 dann können wir die mit einem Plus konkatenieren oder mit einem Mal 05:56.880 --> 05:58.020 konkatenieren. 05:59.160 --> 06:06.380 Und dann ist klar, dass es jetzt ein bisschen offensichtlicher zu 06:06.380 --> 06:10.080 einem String korrespondiert, indem wir einfach hinschreiben, weiß ich 06:10.080 --> 06:14.600 nicht, Klammer auf A plus, Klammer auf A mal A, Klammer zu, Klammer zu 06:14.600 --> 06:15.600 plus A oder so. 06:15.980 --> 06:17.780 Also einfach diesen String. 06:18.060 --> 06:20.280 Und dass es ein ordentlicher arithmetischer Ausdruck ist. 06:20.280 --> 06:24.160 Zum Beispiel keine zwei Plus hintereinander auftauchen oder keine drei 06:24.160 --> 06:26.620 As gefolgt von sieben Mals oder so. 06:26.700 --> 06:29.580 Und dass die Klammerung ordentlich ist und die ordentlich Klammern 06:29.580 --> 06:30.980 wieder zugehen und so weiter. 06:33.180 --> 06:37.080 Und wir können die arithmetischen Ausdrücke, also diese Sprache, alle 06:37.080 --> 06:41.180 arithmetischen Ausdrücke auch wieder durch eine Grammatik erzeugen, 06:41.240 --> 06:48.240 indem wir anfangen von dem leeren Wort und dann Regeln erlauben, wie 06:48.240 --> 06:49.700 das Wort erweitert werden könnte. 06:49.700 --> 06:54.820 Also zum Beispiel, wenn wir die Worte schon haben, A1, dann könnten 06:54.820 --> 06:57.320 wir das erweitern, dann nehmen wir noch ein zweites Wort und die mit 06:57.320 --> 07:00.780 einem Plus konkatenieren oder Klammern drum setzen. 07:00.980 --> 07:03.280 Und die Klammern können überflüssig sein oder auch nicht. 07:04.180 --> 07:04.400 Okay? 07:05.040 --> 07:06.520 Das ist so die Idee. 07:06.760 --> 07:08.860 Diese arithmetischen Ausdrücke werden wir auch noch ein bisschen 07:08.860 --> 07:10.120 konkreter machen. 07:11.100 --> 07:11.620 Gut. 07:12.740 --> 07:13.580 Jetzt formal. 07:14.480 --> 07:15.420 Was ist eine Grammatik? 07:16.300 --> 07:21.000 Wir beschreiben eine Grammatik, die wird üblicherweise G heißen, was 07:21.000 --> 07:24.140 ein bisschen ungünstig ist, weil G auch Graphen sind, aber G für 07:24.140 --> 07:26.540 Grammatik ist, glaube ich, auch halbwegs anschaulich. 07:27.540 --> 07:28.740 Also das ist ein Viertupel. 07:28.820 --> 07:31.260 Wir haben wie immer ein endliches Alphabet Sigma. 07:31.520 --> 07:37.260 Das sind die erlaubten Symbole in den Wörtern, die wir kreieren 07:37.260 --> 07:37.580 wollen. 07:37.920 --> 07:43.340 Die heißen dann auch Terminale oder Terminalalphabet, die Menge der 07:43.340 --> 07:44.280 Terminalsymbole. 07:44.760 --> 07:48.420 Dann haben wir zusätzlich noch, das ist ähnlich wie bei der Turing 07:48.420 --> 07:53.480 -Maschine, das Bandalphabet haben wir noch Hilfssymbole, die wir 07:53.480 --> 07:56.940 unterwegs brauchen werden, während wir die Wörter kreieren in der 07:56.940 --> 07:57.440 Grammatik. 07:57.960 --> 08:03.460 Und die nennen wir V und die heißen Variablen oder Nicht-Terminale. 08:04.300 --> 08:08.380 Also in diesem Entstehungsprozess eines Wortes kann es sein, dass 08:08.380 --> 08:12.860 zwischendurch Nicht-Terminalsymbole kreiert werden. 08:13.800 --> 08:17.520 Dann letztendlich werden die am Ende aber auch alle wieder 08:17.520 --> 08:19.780 verschwinden müssen, damit es ein ordentliches Wort in der Sprache 08:19.780 --> 08:20.060 ist. 08:20.560 --> 08:24.920 Also V ist eine endliche Menge von Variablen, vielleicht ist die leer, 08:25.080 --> 08:28.220 vielleicht erlauben wir uns irgendwie sieben extra Variablen und die 08:28.220 --> 08:32.040 Variablen und die Terminalsymbole sind disjunkt. 08:32.960 --> 08:34.900 Dann gibt es ein Start-Symbol. 08:35.740 --> 08:37.820 Das korrespondiert so ein bisschen zu dem leeren Wort. 08:37.940 --> 08:43.040 Das ist einfach eine Variable, die wir üblicherweise mit Groß-S 08:43.040 --> 08:45.580 bezeichnen und damit fängt immer alles an. 08:46.120 --> 08:51.100 Wir fangen an mit dem Wort, was einfach nur Groß-S hat und dann folgen 08:51.100 --> 08:54.000 wir den Regeln, um dieses Wort zu verändern. 08:54.800 --> 08:56.740 Und was sind jetzt diese Regeln? 08:57.820 --> 09:03.660 Die heißen manchmal auch Produktionen oder Ableitungen oder 09:03.660 --> 09:04.220 Ableitungsregeln. 09:04.760 --> 09:07.500 Die sind sozusagen Ersetzungen. 09:07.500 --> 09:12.020 Die sind immer gegeben durch ein paar L, R, die linke Seite der 09:12.020 --> 09:18.160 Produktion und die rechte Seite der Produktion und beides sind Strings 09:18.160 --> 09:25.580 aus dem Alphabet Variablen und Terminale, wobei die linke Seite nicht 09:25.580 --> 09:26.060 leer ist. 09:26.200 --> 09:31.140 Also wir müssen immer irgendwas haben, was wir ersetzen wollen und die 09:31.140 --> 09:34.880 rechte Seite ist ein beliebiges Wort, das könnte auch das leere Wort 09:34.880 --> 09:35.100 sein. 09:35.100 --> 09:38.280 Das heißt dann einfach, dieser String wird rausgelöscht. 09:39.640 --> 09:45.540 Und wir schreiben manchmal auch statt dieses paar L, R, so L-Pfeil-R. 09:45.760 --> 09:50.440 Das heißt also, die linke Seite wird ersetzt durch die rechte Seite. 09:52.980 --> 09:54.980 Gut, was ist die Bedeutung davon? 09:55.260 --> 10:00.180 Also wenn wir ein Wort haben, Z, denken Sie zuerst daran, das Wort ist 10:00.180 --> 10:03.120 einfach nur S, die Startvariable. 10:04.380 --> 10:10.700 Und wenn wir jetzt da drin das Teilwort L sehen, Teilwort, erinnern 10:10.700 --> 10:13.800 Sie sich, ist in dem String einfach ein zusammenhängender Teilstring. 10:14.320 --> 10:17.120 Also aufeinanderfolgende Positionen, die genau L ergeben. 10:18.080 --> 10:20.480 Dann kann man die Regel anwenden. 10:21.140 --> 10:24.220 Ich sehe die linke Seite und dann darf ich die Regel anwenden, diese 10:24.220 --> 10:27.960 linke Seite zu ersetzen an dieser Stelle durch die rechte Seite R. 10:29.020 --> 10:32.980 Also dann darf L durch R in Z ersetzt werden. 10:34.100 --> 10:36.840 Lösche L raus und füge an dieser Stelle R ein. 10:37.220 --> 10:40.360 R könnte länger sein, könnte genauso lang, könnte kürzer sein. 10:42.100 --> 10:43.020 Das wissen wir nicht. 10:43.220 --> 10:45.960 Das ist dann in der Regel festgeschrieben, wie L und R aussieht. 10:48.880 --> 10:54.100 Wir schreiben dann, wenn ein Wort W in ein Wort Z überführt werden 10:54.100 --> 10:59.440 kann, durch das Anwenden einer Regel, egal welcher das ist, dann 10:59.440 --> 11:01.940 schreiben wir auch so W-Pfeil-Z. 11:03.200 --> 11:09.320 Das ist dann auch konsistent mit der Bezeichnung L-Pfeil-R, weil ja 11:09.320 --> 11:13.580 wirklich die Regel sagt, Wort L kann ersetzt werden durch Wort R, also 11:13.580 --> 11:16.160 kann Wort L in Wort R überführt werden. 11:17.360 --> 11:21.180 Und wenn wir sagen, vielleicht ist es nicht ein Schritt, sondern 11:21.180 --> 11:26.240 mehrere Schritte oder ein Schritt, wir wissen es nicht so genau, dann 11:26.240 --> 11:29.500 machen wir hier ein kleines Sternchen auf dem Pfeil, das heißt einfach 11:29.500 --> 11:33.660 mehrfach hintereinander Ausführungen von irgendwelchen Regeln, 11:33.760 --> 11:35.040 vielleicht auch verschiedenen Regeln. 11:35.340 --> 11:40.800 Also irgendwie kann das Wort W in das Wort Z überführt werden durch 11:40.800 --> 11:44.200 Anwendung von irgendwelchen Regeln aus unserer Regelmenge R. 11:45.280 --> 11:45.500 Groß R. 11:48.520 --> 11:49.120 Gut. 11:50.080 --> 11:58.900 Und dann ist jetzt von dieser Grammatik erzeugte Sprache alle Wörter Z 11:58.900 --> 12:04.460 aus Sigma-Sternen, für die gilt, dass S in Z überführt werden kann. 12:05.800 --> 12:07.260 Gehen wir das nochmal ganz kurz durch. 12:07.380 --> 12:12.200 In der Grammatik gibt es das Terminalalphabet Sigma, es gibt 12:12.200 --> 12:17.260 Variablen, ein zusätzliches Alphabet Groß V und es gibt dieses 12:17.260 --> 12:22.100 Staatssymbol Groß S, was eins der Variablen ist, und dann gibt es eine 12:22.100 --> 12:23.060 Menge von Regeln. 12:24.460 --> 12:31.780 Und die Frage ist, was kann ich aus S kreieren, was keine Variablen 12:31.780 --> 12:38.440 mehr enthält und immer in diesem Kreieren, Kreationsprozess, den 12:38.440 --> 12:39.500 Regeln gefolgt ist. 12:41.080 --> 12:44.240 Machen wir gleich ein Beispiel dazu. 12:44.240 --> 12:50.200 Diese Wörter sind dann die Wörter in der Sprache zu der Grammatik. 12:54.100 --> 12:54.580 Beispiel. 12:55.420 --> 12:58.540 Also das ist hier eine kleine Grammatik, die so ein bisschen so 12:58.540 --> 13:01.200 arithmetische Ausdrücke macht, nicht ganz, weil das viel zu viele 13:01.200 --> 13:03.320 Klammern sind, aber egal. 13:04.140 --> 13:04.940 Also, was haben wir? 13:06.000 --> 13:08.460 Wir wollen arithmetische Ausdrücke in einer Variablen. 13:08.700 --> 13:11.980 A, wir wollen Klammern haben, Klammer auf und Klammer zu, Plus und 13:11.980 --> 13:12.280 Mal. 13:12.500 --> 13:14.080 Also das ist unser Terminalalphabet. 13:14.300 --> 13:19.880 Das sind die Symbole, die in den kreierten Wörtern vorkommen sollen. 13:21.160 --> 13:25.140 Als Variablen haben wir nur diese eine Startvariable, wir werden keine 13:25.140 --> 13:28.640 weitere benötigen, um das Beispiel auch simpel zu halten. 13:30.280 --> 13:32.760 Okay, und dann gibt es eine Menge von Regeln. 13:33.220 --> 13:33.380 R. 13:33.940 --> 13:38.920 Und in unserem Fall haben wir fünf Regeln, die sehen so aus. 13:40.080 --> 13:43.880 Die linke Seite von jeder dieser Regeln ist einfach nur S. 13:44.020 --> 13:46.920 Also wenn immer ich ein S sehe in einem Wort, was ich irgendwo 13:46.920 --> 13:50.860 erschaffen habe, dann darf ich dieses S ersetzen, durch was auf der 13:50.860 --> 13:52.140 rechten Seite der Regel steht. 13:54.640 --> 13:58.040 Zum Beispiel, wenn ich ein S sehe, dann darf ich das S ersetzen durch 13:58.040 --> 13:59.780 diesen String. 14:00.800 --> 14:04.580 Klammer auf, S, Klammer zu, Plus, Klammer auf, S, Klammer zu. 14:06.140 --> 14:09.260 Damit habe ich wieder neue S kreiert, auf die ich jetzt wiederum 14:09.260 --> 14:10.400 Regeln anwenden könnte. 14:11.620 --> 14:16.560 Ich kann auch S einfach ersetzen durch nur diese eine Variable A, oder 14:16.560 --> 14:20.460 das gleiche mit einer Multiplikation, oder einfach nur durch A plus A 14:20.460 --> 14:21.340 oder A mal A. 14:24.400 --> 14:27.180 Und das definiert uns jetzt eine Sprache. 14:27.840 --> 14:34.240 Das definiert uns eine Sprache, die unendlich viele Wörter hat und zum 14:34.240 --> 14:38.340 Beispiel das Wort, was ich hier unten hingeschrieben habe, enthält. 14:38.720 --> 14:43.880 Also dieser String, Klammer auf, A plus A, Klammer zu, mal, Klammer 14:43.880 --> 14:45.080 auf, A, Klammer zu. 14:45.720 --> 14:49.360 Okay, dieser String ist in der Sprache zu dieser Grammatik. 14:49.900 --> 14:50.540 Naja, warum? 14:51.620 --> 14:56.900 Weil ich aus S durch Anwenden von Regeln dieses Wort kreieren kann. 14:57.140 --> 14:58.840 Okay, überlegen wir uns das einmal. 14:59.000 --> 15:02.440 Ich könnte zum Beispiel, also ich fange immer an mit S und dann kann 15:02.440 --> 15:05.680 ich mir jetzt aussuchen und ich mache die Regel, die zweite Regel 15:05.680 --> 15:05.960 hier. 15:06.520 --> 15:09.760 Ich ersetze S durch Klammer auf S mal Klammer auf A. 15:10.180 --> 15:10.620 Wie auch immer. 15:12.400 --> 15:16.560 Und jetzt kann ich wiederum Regeln anwenden. 15:16.760 --> 15:19.340 Ich sehe hier wieder ein S auf der linken Seite und auf dieses S 15:19.340 --> 15:22.820 könnte ich jetzt die vierte Regel anwenden oder das S auf der rechten 15:22.820 --> 15:26.240 Seite, da könnte ich die dritte Regel anwenden und dann entspricht das 15:26.240 --> 15:28.060 diesem Wort. 15:29.420 --> 15:31.920 Eigentlich müsst ihr jetzt hier auf diesem Pfeil ein kleines Sternchen 15:31.920 --> 15:32.220 rauf. 15:32.220 --> 15:35.640 Das werde ich auch gleich noch korrigieren, weil ich jetzt zwei Regeln 15:35.640 --> 15:37.100 angewendet habe und nicht nur eine. 15:41.300 --> 15:46.020 Und das Wort ist jetzt ein Wort ohne Variablen, ein String ohne 15:46.020 --> 15:48.360 Variablen, also es ist ein Wort in unserer Sprache. 15:50.740 --> 15:56.200 Dieser Prozess, dieses Ersetzen, endet nicht automatisch, wenn wir, 15:57.660 --> 16:01.060 sobald wir keine Variablen mehr haben, es könnte sein, dass wir auf 16:01.060 --> 16:03.700 dieses Wort noch weitere Regeln anwenden können. 16:04.140 --> 16:06.780 Aber hier können wir jetzt gerade in diesem konkreten Fall können wir 16:06.780 --> 16:10.300 keine neuen Regeln anwenden, weil einfach keine von diesen linken 16:10.300 --> 16:12.660 Seiten ich hier als Teilwort drin sehe. 16:17.080 --> 16:24.540 Und jetzt gibt es den zentralen Begriff für die nächsten paar Wochen 16:24.540 --> 16:25.720 hier in der Vorlesung. 16:25.720 --> 16:32.120 Also die zentrale Hierarchie, die wir in diesem Kapitel kennenlernen 16:32.120 --> 16:32.520 werden. 16:32.740 --> 16:35.320 Und das ist die sogenannte Chomsky-Hierarchie. 16:36.340 --> 16:40.180 Die ist benannt nach einem Amerikaner. 16:40.840 --> 16:42.180 Chomsky, habe ich den schon? 16:43.040 --> 16:46.260 Vielleicht stelle ich Ihnen den beim nächsten Mal einmal vor. 16:47.180 --> 16:55.940 Und diese Hierarchie soll jetzt Sprachen oder erstmal nur Grammatiken 16:55.940 --> 17:00.520 kategorisieren nach der Art von Regeln, die in ihnen erlaubt sind. 17:01.500 --> 17:05.620 Und damit kategorieren wir auch automatisch die Sprachen, die von 17:05.620 --> 17:06.940 diesen Grammatiken erzeugt werden. 17:07.700 --> 17:12.980 Das soll so gehen von sehr allgemeinen Grammatiken, ganz oben, Typ 0, 17:12.980 --> 17:17.980 bis zu sehr speziellen Grammatiken, wo die Regeln spezielle 17:17.980 --> 17:20.360 Anforderungen erfüllen müssen, Typ 3. 17:20.820 --> 17:23.420 Und entsprechend sind die Sprachen, die ganz oben sind, relativ 17:23.420 --> 17:25.880 allgemeine Sprachen oder schwere Sprachen. 17:26.580 --> 17:31.400 Und die Sprachen weiter unten in Typ 3 sind einfache Sprachen. 17:32.200 --> 17:39.720 Und für uns ist die Motivation, dass wir diese Komplexität der Sprache 17:40.460 --> 17:44.980 analysieren wollen im Sinne von, wie einfach ist es zu erkennen, ob 17:44.980 --> 17:46.340 ein Wort in der Sprache liegt. 17:46.700 --> 17:48.500 Also für ein Berechnungsmodell. 17:48.560 --> 17:51.840 Wir wollen das Wortproblem für diese Sprache lösen. 17:51.900 --> 17:55.960 Wir wollen entscheiden, ob ein gegebenes Wort von dieser Grammatik 17:55.960 --> 17:57.420 erzeugt werden kann. 17:59.120 --> 18:02.880 Und je allgemeiner die Grammatik ist, desto schwieriger ist diese 18:02.880 --> 18:04.140 Aufgabe im Allgemeinen. 18:05.140 --> 18:07.100 Ja, weil es ja mehr Sprachen gibt. 18:08.660 --> 18:12.060 Und dementsprechend ist es schwieriger, das Wortproblem zu lösen. 18:12.320 --> 18:16.380 Und wenn wir die Grammatiken einschränken, dann sind es sehr spezielle 18:16.380 --> 18:21.160 Sprachen und dann haben wir vielleicht Chancen, das Wortproblem 18:21.160 --> 18:22.280 effizient zu lösen. 18:22.860 --> 18:23.100 Okay? 18:24.160 --> 18:24.540 Gut. 18:26.260 --> 18:27.340 Also, das ist die Übersicht. 18:27.420 --> 18:29.180 Es kommen auch wirklich keine weiteren Typen mehr hinzu. 18:29.300 --> 18:32.080 Es geht nur von Typ 0 bis Typ 3. 18:32.880 --> 18:36.500 Typ 0 sind Grammatiken, so wie ich sie gerade vorgestellt habe. 18:36.980 --> 18:40.340 Grammatiken ohne weitere Einschränkungen an die Regeln. 18:40.640 --> 18:44.340 Die Regeln dürfen genauso aussehen, wie ich das Ihnen gesagt habe. 18:44.620 --> 18:47.880 Die einzige Bedingung ist, die linke Seite ist nicht das leere Wort. 18:48.920 --> 18:49.380 Das war's. 18:50.700 --> 18:52.740 Die linke Seite hat mindestens ein Symbol. 18:53.700 --> 18:54.360 Beliebig viele. 18:55.180 --> 18:56.320 Terminale, Nicht-Terminale. 18:56.960 --> 18:59.680 Die rechte Seite ist irgendein String. 18:59.680 --> 19:01.260 Darf das leere Wort sein. 19:01.440 --> 19:05.980 Terminale, Nicht-Terminale in irgendeiner Reihenfolge. 19:06.400 --> 19:06.560 Gut. 19:07.580 --> 19:10.940 Dann Typ 1 ist schon ein bisschen restriktiver. 19:11.260 --> 19:15.220 Ich darf nicht mehr beliebige Regeln in meiner Grammatik aufstellen. 19:15.720 --> 19:20.120 Die Regeln in Typ 1 Grammatiken haben die folgende Form. 19:21.520 --> 19:25.580 Entweder, fangen wir mit dem zweiten an, diese Regel hier ist erlaubt, 19:25.680 --> 19:28.200 nämlich aus S das leere Wort zu machen. 19:29.200 --> 19:35.620 Das ist wirklich nur für den Spezialfall, damit ich das leere Wort in 19:35.620 --> 19:36.660 meine Sprache reinkriege. 19:36.820 --> 19:40.820 Weil das die einzige Möglichkeit sein wird, das leere Wort in die 19:40.820 --> 19:42.420 Sprache reinzukriegen für Typ 1. 19:42.740 --> 19:45.400 Also machen Sie sich darüber keine großen Gedanken. 19:46.240 --> 19:48.360 Wichtiger ist der erste Fall. 19:48.820 --> 19:52.640 Also, die Regeln müssen so wie folgt aussehen. 19:52.720 --> 19:56.480 Die linke Seite ist U und die rechte Seite ist irgendein V. 19:56.480 --> 19:59.500 Und U darf jetzt schon mal nicht alles mehr sein. 20:00.120 --> 20:03.240 U darf nur aus Variablen bestehen. 20:04.980 --> 20:08.140 Ich darf keine Terminale auf der linken Seite haben. 20:08.540 --> 20:09.560 Nur Variablen. 20:10.060 --> 20:14.420 Das heißt also, wenn ich in so einer Sprache mal ein Terminal einführe 20:14.420 --> 20:16.800 durch eine Regel, dann wird das nie wieder verschwinden. 20:17.620 --> 20:18.680 Nie wieder geändert werden. 20:19.980 --> 20:22.360 Weil nur linke Seiten dürfen nur Variablen enthalten. 20:23.160 --> 20:26.940 Und mindestens einer, deswegen V+. 20:28.880 --> 20:33.720 Und die rechte Seite, die darf jetzt Variablen und Terminale 20:33.720 --> 20:34.400 enthalten. 20:35.300 --> 20:38.200 Allerdings, ich darf auf die rechte Seite nicht das Startsymbol 20:38.200 --> 20:38.660 schreiben. 20:40.080 --> 20:43.420 Weil ich sonst, das ist der einzige Grund, warum ich das mache, weil 20:43.420 --> 20:47.540 ich diese Regel hier erlaube mit Startsymbol leer. 20:47.540 --> 20:52.180 Und dann kommen die Sachen, dann kann man tricksen, sagen wir mal. 20:52.740 --> 20:56.460 Also auf der rechten Seite darf ich das Startsymbol nicht schreiben. 20:56.600 --> 20:59.680 Und ich darf auch nicht das leere Wort schreiben. 20:59.820 --> 21:02.680 Es muss mindestens ein Symbol haben. 21:03.420 --> 21:06.420 Also erstmal ist die rechte Seite nicht wirklich eingeschränkt. 21:06.780 --> 21:09.920 Aber jetzt kommt die ganz wichtige Einschränkung. 21:10.380 --> 21:14.260 Die rechte Seite ist mindestens so lang wie die linke Seite. 21:17.150 --> 21:22.250 Das Anwenden einer Regel darf das Wort nicht kürzer machen. 21:23.710 --> 21:25.630 Außer die Regel da. 21:29.000 --> 21:31.500 Okay, also nochmal. 21:33.040 --> 21:38.380 Die wichtigen Eigenschaften sind, wenn ich Terminale einführe, bleiben 21:38.380 --> 21:42.220 die dort und unverändert, weil auf der linken Seite keine Terminale 21:42.220 --> 21:42.880 stehen dürfen. 21:43.840 --> 21:49.080 Und die zweite Eigenschaft ist, das Wort kann in diesem Aufbauprozess 21:49.080 --> 21:51.880 im Prinzip nur wachsen oder gleich bleiben. 21:55.320 --> 22:00.860 Diese Grammatiken Typ 1 oder Chomsky 1 Grammatiken, die heißen auch 22:00.860 --> 22:02.840 Kontextsensitiv. 22:03.740 --> 22:08.340 Den Grund werde ich gleich nochmal kurz erklären, woher das kommt. 22:10.780 --> 22:17.520 Dann in der Hierarchie, einen Schritt weiter unten, sind Typ 2 22:17.520 --> 22:20.720 Grammatiken, die heißen auch Kontextfrei. 22:21.540 --> 22:26.720 Die sind noch einschränkender in ihren Regeln als die Typ 1 22:26.720 --> 22:27.320 Grammatiken. 22:28.300 --> 22:34.340 Also noch einschränkender heißt, alles was Typ 2 ist, ist auch Typ 1. 22:36.540 --> 22:38.420 Gut, wie sehen die Regeln aus? 22:38.500 --> 22:42.520 Die Regeln in der Kontextfreien Grammatik, in der Typ 2 Grammatik, 22:42.980 --> 22:44.660 haben die folgende Form. 22:45.600 --> 22:50.400 Auf der linken Seite darf nur eine einzelne Variable stehen. 22:52.800 --> 22:56.800 Die linke Seite hat genau Länge 1 und es ist eine Variable. 22:58.760 --> 23:03.280 Und die rechte Seite ist ein beliebiges Wort, es darf jetzt auch das 23:03.280 --> 23:08.800 leere Wort sein, aus Variablen und Terminalen. 23:09.960 --> 23:13.680 Aber ich darf immer nur eine einzelne Variable ersetzen durch 23:13.680 --> 23:15.960 irgendwas, was auf der rechten Seite steht. 23:19.160 --> 23:28.400 Das heißt jetzt wiederum, dass die Wörter, die können auch kürzer 23:28.400 --> 23:31.360 werden, weil ich auf der rechten Seite könnte ich das leere Wort 23:31.360 --> 23:31.580 haben. 23:31.580 --> 23:36.040 Also ich kann Variablen, wenn ich die Regel einführe, Variable, Pfeil, 23:36.260 --> 23:38.520 leeres Wort, dann kann ich die im Prinzip rausstreichen, wann immer 23:38.520 --> 23:38.860 ich will. 23:40.320 --> 23:44.420 Sie können sich trotzdem einmal überlegen, warum jede Typ 2 Grammatik 23:44.420 --> 23:46.480 auch eine Typ 1 Grammatik ist. 23:47.720 --> 23:50.440 Ganz wichtig, warum heißt die jetzt Kontextfrei? 23:52.060 --> 23:55.900 Sie müssen sich vorstellen, Sie haben schon ein Wort kreiert und da 23:55.900 --> 23:59.200 drin sehen Sie zum Beispiel diese Variable a und es gibt eine Regel, 23:59.600 --> 24:03.620 die sagt, wenn ich a sehe, darf ich das ersetzen durch irgendwas, was 24:03.620 --> 24:04.640 auf der rechten Seite steht. 24:05.460 --> 24:09.360 Ich kann in dieser Grammatik nicht modellieren Sachen wie, wenn vor 24:09.360 --> 24:14.640 dem a ein x steht, ist diese Ersetzung erlaubt und wenn vor dem a ein 24:14.640 --> 24:16.720 y steht, ist die Ersetzung nicht erlaubt. 24:17.200 --> 24:22.940 Also der Kontext, was außenrum ist um das a, das kann ich nicht mit 24:22.940 --> 24:26.200 abgreifen als Information in der Regel. 24:26.200 --> 24:28.500 Deswegen heißen die Kontextfrei. 24:28.900 --> 24:33.240 Wann immer ich ein a sehe, egal wie der Kontext ist, wie dieses a in 24:33.240 --> 24:38.820 dem Wort sich positioniert hat, egal wie der Kontext ist, das a darf 24:38.820 --> 24:39.460 ersetzt werden. 24:42.060 --> 24:45.260 Gut, das waren die kontextfreien Grammatiken. 24:46.540 --> 24:52.620 Der dritte und restriktivste Typ sind dann Typ 3 Grammatiken oder 24:52.620 --> 24:54.220 Chomsky 3 Grammatiken. 24:54.220 --> 24:57.900 Die heißen auch manchmal rechtslinear, aber ich glaube, da werde ich 24:57.900 --> 24:59.860 immer Typ 3 Grammatik zu sagen. 25:01.520 --> 25:08.340 Hier sehen die Ableitungsregeln noch eingeschränkter aus als bei Typ 25:08.340 --> 25:08.700 2. 25:08.880 --> 25:12.780 Die linke Seite ist wiederum genau eine Variable, a. 25:13.600 --> 25:17.720 Und die rechte Seite ist jetzt, wo sie hier oben noch völlige Freiheit 25:17.720 --> 25:19.640 hatte, ist jetzt auch eingeschränkt. 25:19.640 --> 25:24.500 Also entweder ist die rechte Seite das leere Wort oder die rechte 25:24.500 --> 25:29.300 Seite hat die folgende Form, klein a, groß b, mit einem Terminal, 25:29.440 --> 25:31.500 klein a und einer Variable, groß b. 25:33.260 --> 25:36.220 Also alles, was ich machen darf, ist eine Variable nehmen und sie 25:36.220 --> 25:40.920 ersetzen, entweder rausstreichen, oder sie ersetzen durch ein Terminal 25:40.920 --> 25:42.180 und eine Variable. 25:45.250 --> 25:51.250 Und das heißt aber auch, dass immer wenn ich das mache, wenn ich eine 25:51.250 --> 25:55.910 Regel anwende, dann wird entweder verschwindet eine Variable oder es 25:55.910 --> 25:57.290 kommt ein Terminal hinzu. 26:03.080 --> 26:07.460 Man kann sich dann auch überlegen, wir fangen ja an mit dem Wort, was 26:07.460 --> 26:08.600 nur groß S enthält. 26:10.300 --> 26:15.060 Das heißt, wir fangen an ja mit dieser Variable groß S. 26:15.160 --> 26:18.100 Das einzige, was wir jetzt machen können, ist eine Regel zu verwenden, 26:18.240 --> 26:20.020 wo auf der linken Seite groß S steht. 26:20.600 --> 26:23.740 Dann wird das S entweder gelöscht, gut, dann ist fertig, dann geht gar 26:23.740 --> 26:24.160 nichts mehr. 26:24.600 --> 26:27.840 Oder das S wird ersetzt durch ein Terminal und eine neue Variable. 26:30.320 --> 26:34.520 Und dann wiederum, es gibt nur eine einzige Variable in dem String. 26:35.960 --> 26:39.540 Entweder die wird gelöscht, weil die Regel das erlaubt oder wir uns 26:39.540 --> 26:44.340 dafür entscheiden, oder diese Variable wird ersetzt durch ein Terminal 26:44.340 --> 26:45.360 und wieder eine Variable. 26:46.260 --> 26:49.780 Das heißt, dieser Entstehungsprozess für diese rechtslinearen 26:49.780 --> 26:54.240 Grammatiken, für die Typ-3-Grammatiken, sind, dass das Wort im Prinzip 26:54.240 --> 26:57.900 von links nach rechts hingeschrieben wird mit den Terminalen und immer 26:57.900 --> 27:01.040 vorne steht sowas wie ein Zustand. 27:01.040 --> 27:05.180 Diese Variable kodiert einen Zustand und der kann sagen, okay, was ist 27:05.180 --> 27:10.080 denn das nächstmögliche Symbol, was ich hinschreiben darf und in 27:10.080 --> 27:11.100 welchen Zustand gehe ich dann. 27:11.700 --> 27:12.780 So müssen Sie sich das vorstellen. 27:13.280 --> 27:19.400 So, jetzt kommt die kleine Bemerkung, warum das Kontextsensitiv heißt 27:19.400 --> 27:20.180 bei den Grammatiken. 27:20.240 --> 27:25.280 Ich habe Ihnen schon ein bisschen versucht zu erklären, was 27:25.280 --> 27:28.020 kontextfrei heißt, also losgelöst vom Kontext. 27:28.020 --> 27:31.980 Und Kontextsensitiv ist dann halt, dass es nicht kontextfrei ist, also 27:31.980 --> 27:36.900 dass es die Ersetzung einer Variablen darf vom Kontext abhängen. 27:37.480 --> 27:41.600 Zum Beispiel könnten wir in der Kontextsensitiven Grammatik diese 27:41.600 --> 27:47.840 zwei, oder ja, wir könnten zum Beispiel diese Regel hier drin haben, 27:48.440 --> 27:50.900 die ist erlaubt, das sind alles, was ich groß schreibe, sind 27:50.900 --> 27:51.440 Variablen. 27:51.440 --> 27:56.780 Also, dass dieses Teilwort a, b, c, alles in Variablen, ersetzt wird 27:56.780 --> 27:58.900 durch a, x, y, c. 28:00.380 --> 28:06.020 Also, was da eigentlich quasi passiert, ich ersetze das b durch ein x, 28:06.020 --> 28:06.380 y. 28:07.680 --> 28:13.520 Okay, das geht aber nur, wenn vor dem b ein a und hinter dem b ein c 28:13.520 --> 28:13.900 steht. 28:14.540 --> 28:20.100 Also, das ist so eine Art, ich darf b ersetzen durch x, y, wenn davor, 28:20.100 --> 28:23.280 wenn der Kontext stimmt, wenn davor ein a kommt und dahinter ein c 28:23.280 --> 28:23.680 kommt. 28:24.020 --> 28:26.520 Zum Beispiel könnte ich sagen, wenn ich diese Regel hier nicht 28:26.520 --> 28:34.180 aufnehme, dann darf ich das b in dieser Situation, darf ich es nicht 28:34.180 --> 28:38.540 durch x, y ersetzen, weil davor jetzt ein d steht und hinter einem c. 28:39.800 --> 28:41.580 Also, der Kontext stimmt nicht. 28:42.820 --> 28:47.080 In der kontextfreien Grammatik wäre es so, wenn das hier erlaubt ist, 28:47.080 --> 28:52.400 dann ist automatisch auch das erlaubt, weil ob ich b durch x, y 28:52.400 --> 28:57.120 ersetzen darf, ist kontextfrei, es ist unabhängig von dem Kontext. 28:58.080 --> 29:02.560 Es wird in beiden Wörtern erlaubt sein. 29:03.140 --> 29:06.640 Das liegt daran, dass in der kontextfreien Grammatik die linke Seite 29:06.640 --> 29:08.180 nur exakt eine Variable hat. 29:08.400 --> 29:11.760 Da steht einfach b darf ersetzt werden durch x, y. 29:12.760 --> 29:15.320 Gut, also deswegen heißen die Kontextsensitiv. 29:17.100 --> 29:22.080 Alles klar, dann machen wir am besten gleich los. 29:22.220 --> 29:27.200 Was wir tun werden ist, wir werden jetzt entsprechend der Typen der 29:27.200 --> 29:31.880 Grammatiken, werden wir wieder Zusammenhänge herstellen mit dem, was 29:31.880 --> 29:33.500 wir schon gesehen haben in der Vorlesung. 29:33.920 --> 29:37.080 Also wir werden uns zu der entsprechenden Grammatik, werden wir uns 29:37.080 --> 29:41.700 die Sprachen angucken und untersuchen, wie allgemein oder wie 29:41.700 --> 29:44.380 schwierig, wie komplex diese Sprachen sein können. 29:45.820 --> 29:50.200 Und ich hatte das schon angedeutet, dass natürlich je allgemeiner die 29:50.200 --> 29:54.060 Grammatik ist, also Typ 0 ist das Allgemeinste, desto schwieriger, 29:54.200 --> 29:57.760 komplexer, allgemeiner sind die Sprachen, die von diesen Grammatiken 29:57.760 --> 29:59.400 erzeugt werden. 30:00.560 --> 30:06.180 Gut, jetzt haben wir hier den ersten Satz, der so eine Verbindung 30:06.180 --> 30:06.740 herstellt. 30:07.630 --> 30:13.640 Wenn L eine semi-entscheidbare Sprache ist, erinnern Sie sich? 30:14.100 --> 30:17.260 Semi-entscheidbar oder rekursiv aufzählbar ist das gleiche. 30:17.780 --> 30:22.480 Semi-entscheidbar heißt, es gibt eine Turing-Maschine, die die Sprache 30:22.480 --> 30:28.140 erkennt, die die Sprache akzeptiert, Entschuldigung, semi-entscheidbar 30:28.140 --> 30:28.840 akzeptiert. 30:29.000 --> 30:32.780 Also die bei Eingabe eines Wortes, wenn das Wort aus der Sprache 30:32.780 --> 30:35.980 kommt, dann hält sie auch nach endlicher Zeit und akzeptiert das Wort. 30:36.440 --> 30:40.640 Wenn das Wort nicht in der Sprache ist, dann wird sie entweder 30:40.640 --> 30:43.180 unendlich lange laufen oder ablehnen. 30:43.680 --> 30:47.100 Eine Turing-Maschine, die die Sprache akzeptiert. 30:48.320 --> 30:52.940 Also wenn L so eine Sprache ist, die semi-entscheidbar ist, dann gibt 30:52.940 --> 30:58.100 es dazu eine Chomsky-Null-Grammatik, die genau diese Sprache 30:58.100 --> 30:58.520 beschreibt. 31:03.100 --> 31:04.100 Machen wir das. 31:06.720 --> 31:10.920 Wir müssen also jetzt zeigen, wenn die Sprache semi-entscheidbar ist, 31:11.160 --> 31:12.180 dann gibt es die Grammatik. 31:12.460 --> 31:16.460 Was wir verwenden ist die Sprache semi-entscheidbar, also existiert 31:16.460 --> 31:19.620 eine Turing-Maschine, die deterministische Turing-Maschine ohne 31:19.620 --> 31:23.300 Beschränkung der Allgemeinheit, die die Sprache akzeptiert. 31:25.340 --> 31:25.780 Jetzt. 31:25.780 --> 31:28.220 Ohne Beschränkung der Allgemeinheit können wir annehmen, dass diese 31:28.220 --> 31:32.980 Turing -Maschine, Groß M, gutartig ist. 31:33.200 --> 31:36.920 Also wenn sie akzeptiert, dann akzeptiert sie in dem Endzustand Qj. 31:37.700 --> 31:40.220 Und es gibt keinen anderen akzeptierenden Endzustand. 31:41.300 --> 31:44.820 Und wir können die Turing-Maschine auch so umbauen, dass sie, wenn sie 31:44.820 --> 31:47.060 das Wort kriegt und sie hat sich jetzt irgendwie die Entscheidung 31:47.060 --> 31:49.860 getroffen, das soll bitte akzeptiert werden, dass sie vorher noch das 31:49.860 --> 31:50.820 komplette Band löscht. 31:52.380 --> 31:57.640 Also auf dem Band stehen nur Blanks, wenn akzeptiert wird. 31:58.020 --> 32:01.860 Das ist eine einfache Modifikation, die wir annehmen können. 32:02.600 --> 32:08.400 Und dann erinnern Sie sich, dass Q0 den Anfangszustand der endlichen 32:08.400 --> 32:11.740 Kontrolle von dieser Turing-Maschine bezeichnet. 32:11.820 --> 32:15.260 Und wir können auch noch ohne Beschränkung der Allgemeinheit annehmen, 32:15.260 --> 32:20.220 dass Q0 wirklich nur am Anfang in der Turing-Maschine benutzt wird und 32:20.220 --> 32:23.360 nie wieder in den Zustand Q0 gegangen wird von der Turing-Maschine. 32:23.980 --> 32:26.360 Das ist auch eine einfache Modifikation. 32:27.260 --> 32:27.460 Gut. 32:28.520 --> 32:29.940 Also wir haben jetzt so eine Turing-Maschine. 32:31.260 --> 32:36.500 Und wir wissen, wenn das Wort in der Sprache ist, dann gibt es eine 32:36.500 --> 32:42.440 Abarbeitung oder dann ist die Abarbeitung der Turing-Maschine so, dass 32:42.440 --> 32:43.640 sie nach endlicher Zeit hält. 32:43.640 --> 32:48.020 Und das Band löscht und akzeptiert. 32:48.420 --> 32:51.320 Wenn das Wort nicht in der Sprache ist, dann ist die Abarbeitung 32:51.320 --> 32:55.140 entweder unendlich lang oder akzeptiert eben nicht. 32:55.260 --> 32:57.620 Also hält in dem nicht akzeptierenden Zustand. 32:59.060 --> 33:04.800 Unsere Aufgabe ist jetzt eine Grammatik zu konstruieren, die diese 33:04.800 --> 33:05.760 Sprache beschreibt. 33:06.280 --> 33:11.260 Und hier werden wir das so machen, wie man sich das vielleicht schon 33:11.260 --> 33:12.640 vorstellt. 33:12.640 --> 33:15.860 Also der Unterschied zwischen Turing-Maschinen und Grammatiken ist ja 33:15.860 --> 33:16.320 der folgende. 33:17.080 --> 33:23.540 Turing-Maschinen fangen an mit dem Wort und bauen es sozusagen ab auf 33:23.540 --> 33:25.920 das leere Band und akzeptieren. 33:27.160 --> 33:32.120 Grammatiken fangen an mit dem leeren, also nur es, und bauen das Wort 33:32.120 --> 33:32.480 auf. 33:33.840 --> 33:36.360 Und das ist so der entscheidende Unterschied zwischen diesen 33:36.360 --> 33:39.920 Konzepten, den sie sich einmal verinnerlichen müssen. 33:39.920 --> 33:43.920 In der Grammatik werden die Wörter sozusagen aufgebaut und in den 33:43.920 --> 33:49.740 ganzen Entscheidern, in den Rechnungsmodellen, die Wortprobleme lösen, 33:49.980 --> 33:53.240 fangen wir an mit dem Wort und wollen es sozusagen reduzieren, wollen 33:53.240 --> 33:54.960 es aufbauen, quasi. 33:55.860 --> 34:01.640 Das heißt, wir werden die Grammatik, die Regeln der Grammatik jetzt 34:01.640 --> 34:07.280 rückwärts aufbauen müssen nach dem Verhalten der Turing-Maschine. 34:08.580 --> 34:13.340 Also man fragt sich am Ende, wenn das Wort in der Sprache der Turing 34:13.340 --> 34:16.760 -Maschine ist, wenn es am Ende das Band leer und wir sind im Zustand 34:16.760 --> 34:17.220 QJ. 34:19.620 --> 34:24.780 Das heißt für uns, sowas wie, am Ende haben wir es reduziert auf den 34:24.780 --> 34:25.800 Startsymbol S. 34:26.800 --> 34:30.360 Dann fragt man sich, okay, was könnte denn die Turing-Maschine dahin 34:30.360 --> 34:31.220 gebracht haben. 34:31.220 --> 34:37.620 Dann guckt man sich alle Übergänge an, die dahin führen und sagt sich, 34:37.800 --> 34:41.200 okay, in der Grammatik muss ich jetzt also erlauben, dass die 34:41.200 --> 34:46.940 dahingeführten Zustände Wörter repräsentieren, die aufgebaut wurden 34:46.940 --> 34:48.900 von dem S aus. 34:50.200 --> 34:57.300 Und dann arbeiten wir uns so rückwärts hoch und sagen, am Ende steht 34:57.300 --> 35:01.680 das Wort, alle Wörter können so konstruiert werden, die von der Turing 35:01.680 --> 35:03.980 -Maschine so abgebaut werden. 35:06.800 --> 35:08.960 So, machen wir das konkret. 35:10.240 --> 35:13.420 Die Grammatik ist beschrieben durch ein Viertupel. 35:15.040 --> 35:19.780 Das Terminalalphabet ist einfach das Terminalalphabet Sigma aus der 35:19.780 --> 35:20.400 Turing -Maschine. 35:21.040 --> 35:26.960 Wir brauchen Variablen und was wir machen als Variablen sind das Stack 35:26.960 --> 35:30.860 -Alphabet, also die zusätzlichen Symbole, die die Turing-Maschine auf 35:30.860 --> 35:31.920 das Band schreiben darf. 35:32.000 --> 35:37.080 Das brauchen wir jetzt Variablen und Variablen für die Zustände, damit 35:37.080 --> 35:39.800 wir in diesem Wort, was wir in der Grammatik aufbauen, codieren 35:39.800 --> 35:42.460 können, in welchem Zustand gerade die Turing-Maschine ist. 35:46.320 --> 35:49.380 Also jeder Zustand der Turing-Maschine ist eine Variable. 35:49.800 --> 35:52.420 Und dann haben wir noch die Startvariable S. 35:53.560 --> 35:56.500 Hier steht, dass S die Startvariable ist und dann haben wir eine Menge 35:56.500 --> 36:02.240 von Relationen, Groß-R, die wir jetzt noch entsprechend der Übergänge 36:02.240 --> 36:04.560 der Turing-Maschine definieren müssen. 36:05.040 --> 36:06.040 Gut, wie machen wir das? 36:07.140 --> 36:08.900 Wir machen das, wie gesagt, rückwärts. 36:09.800 --> 36:17.300 Also wenn wir in der Turing-Maschine einen Übergang haben von Zustand 36:17.300 --> 36:24.300 Q unter Lesen von Zeichen A gehe in Zustand Q' schreibe an die Stelle 36:24.300 --> 36:29.140 A' und bewege den Leseschreibkopf einen Schritt nach rechts. 36:30.500 --> 36:37.480 Dann wollen wir jetzt die Ableitungsregel A'Q' kann ersetzt werden 36:37.480 --> 36:39.440 durch QA einführen. 36:40.460 --> 36:41.840 Warum tun wir das? 36:42.720 --> 36:49.040 Wir wollen letztendlich einen String haben, der an genau einer Stelle 36:49.040 --> 36:54.200 eine Variable hat, die zu einem Zustand der Turing-Maschine 36:54.200 --> 36:56.200 korrespondiert. 36:57.220 --> 37:02.360 Und die Stelle, also dieser String repräsentiert, was gerade auf dem 37:02.360 --> 37:04.260 Band steht von der Turing-Maschine. 37:04.780 --> 37:08.220 Und die Stelle, wo dieser Zustand ist, repräsentiert die Stelle, wo 37:08.220 --> 37:09.280 der Leseschreibkopf ist. 37:12.460 --> 37:15.800 Und wir müssen das Ganze jetzt einmal rückwärts denken. 37:16.120 --> 37:19.600 Also wenn die Turing-Maschine sozusagen irgendwo hier so ist, also 37:19.600 --> 37:22.800 egal was da links und rechts daneben auf dem Band steht, dann heißt 37:22.800 --> 37:26.280 es, wir sind gerade in Zustand Q und der Leseschreibkopf liest gerade 37:26.280 --> 37:27.180 das Zeichen A. 37:29.560 --> 37:34.800 Danach wird das A ersetzt durch A' und der Leseschreibkopf geht einen 37:34.800 --> 37:39.500 Schritt nach rechts, sozusagen über die Stelle hinweg und ändert sich 37:39.500 --> 37:40.640 in den Zustand Q'. 37:42.400 --> 37:46.360 Und das ist genau diese... also wenn Sie die Ersetzung jetzt von 37:46.360 --> 37:49.100 rechts nach links lesen, dann ist das, was die Turing-Maschine tut. 37:49.460 --> 37:52.500 Wir müssen die aber von links nach rechts aufschreiben, weil 37:52.500 --> 37:54.940 Grammatiken aufbauen und Turing-Maschinen abbauen. 37:56.520 --> 37:57.000 Gut. 37:57.000 --> 38:01.320 Entsprechend, wenn die Turing-Maschine eine Anweisung hat, einen 38:01.320 --> 38:06.460 Übergang hat, unter den gleichen Voraussetzungen schreibe das Zeichen 38:06.460 --> 38:12.720 A', gehe in Zustand Q' und bewege dich nach links, dann sind wir 38:12.720 --> 38:17.180 sozusagen in irgendwie sowas, wobei B ein beliebiges Bandsymbol ist, 38:17.260 --> 38:18.460 kann auch ein Blank sein. 38:20.140 --> 38:24.040 Und also der Leseschreibkopf steht an dieser Stelle, er liest das A, 38:24.160 --> 38:27.920 wir sind in Zustand Q und dann sollen wir danach das A ersetzt haben 38:27.920 --> 38:29.420 durch ein A'. 38:29.960 --> 38:33.560 Wir sollen in Zustand Q' sein und wir sind einen Schritt nach links 38:33.560 --> 38:35.100 gegangen, also wir lesen jetzt dieses B. 38:36.580 --> 38:39.860 Deswegen brauchen wir diese Regeln für jedes B. 38:41.960 --> 38:46.320 Und entsprechend, wenn wir stehen bleiben sollen, dann ist die Regel 38:46.320 --> 38:50.380 so, nur dass das Q nicht über das A rüberspringt, wie ganz oben. 38:51.780 --> 38:52.260 Okay. 38:54.680 --> 39:04.500 So, jetzt müssen wir noch den Startzustand S einbauen und wir müssen 39:04.500 --> 39:07.220 noch diese ganzen Blanks loswerden, die irgendwie am Ende von der 39:07.220 --> 39:09.500 Turing -Maschine geschrieben worden sind. 39:10.280 --> 39:16.280 Und wieder, wir müssen andersrum denken, wir müssen also daran denken, 39:16.380 --> 39:20.700 dass wir anfangen mit S und dann müssen wir erstmal kreieren Zustand 39:20.700 --> 39:22.940 Qj mit beliebigen Blanks irgendwo. 39:24.640 --> 39:30.740 Und das tun wir so wie folgt, also wir erlauben diese Relation von S 39:30.740 --> 39:38.020 nach Qj und dann, solange wir in Qj sind, dürfen wir links und rechts 39:38.020 --> 39:41.000 davon Blanks einfügen. 39:41.000 --> 39:46.400 Dann können wir also uns entscheiden, wie oft wir diese Regel machen 39:46.400 --> 39:49.700 und dann werden immer so Blanks eingefügt, links und rechts vom Qj, so 39:49.700 --> 39:50.420 wie wir es brauchen. 39:50.900 --> 39:55.200 Und dann können wir die Berechnung rückwärts durchgehen von der Turing 39:55.200 --> 39:55.480 -Maschine. 39:57.020 --> 40:03.440 Gut, das ist also jetzt die komplette Beschreibung der Regelmenge für 40:03.440 --> 40:04.760 diese Grammatik. 40:04.760 --> 40:08.600 Das ist jetzt eine Typ-0-Grammatik, also alles, was wir beachten 40:08.600 --> 40:12.460 müssen, ist, dass die linke Seite von der Regel nicht leer ist, dass 40:12.460 --> 40:15.700 wir irgendwas immer links von diesen Pfeilen zu stehen haben und das 40:15.700 --> 40:16.760 ist hier erlaubt. 40:20.260 --> 40:23.320 Oh, was habe ich jetzt noch? 40:23.600 --> 40:26.340 Ach ja, ich habe noch eins vergessen, das war noch nicht die komplette 40:26.340 --> 40:26.900 Beschreibung. 40:27.860 --> 40:35.220 Also, wir müssen ja noch das Wort kreieren. 40:35.660 --> 40:42.960 Wir bauen jetzt gerade in der Grammatik dieses ganze Band auf und am 40:42.960 --> 40:49.440 Ende steht das Band da und es hat noch irgendwelche Blanks, links und 40:49.440 --> 40:52.540 rechts, die vielleicht benutzt worden sind in der Beschreibung und es 40:52.540 --> 40:53.780 hat noch den Zustand Q0. 40:54.680 --> 40:57.780 Und also so sieht es am Ende aus. 40:57.920 --> 41:02.460 Wir können jetzt so ein Wort kreieren, wenn wir die Turing-Maschine 41:02.460 --> 41:05.940 rückwärts laufen lassen, dann sieht es am Ende so aus. 41:06.100 --> 41:10.000 Wir haben Q0, Turing-Maschinen fangen ja immer an vor der Eingabe, 41:10.420 --> 41:13.160 hier haben wir die Eingabe und wir haben davor und dahinter noch 41:13.160 --> 41:13.900 irgendwelche Blanks. 41:14.320 --> 41:15.080 Warum sind die da? 41:15.180 --> 41:18.400 Naja, weil eventuell in dieser Berechnung irgendwie das Band bis dort 41:18.400 --> 41:19.900 und bis dorthin noch benutzt wurde. 41:20.780 --> 41:24.280 Und was wir jetzt wollen ist aber, dass nicht dieses Wort hier in der 41:24.280 --> 41:26.860 Grammatik ist, sondern dieses Wort soll in der Grammatik sein. 41:27.620 --> 41:32.320 Also wir müssen jetzt noch in der Grammatik Regeln einführen, die 41:32.320 --> 41:35.720 dafür sorgen, dass das hier wieder weggenommen wird. 41:36.280 --> 41:41.740 Also zuerst kümmern wir uns hier vorne um diese zusätzlichen Blanks. 41:41.960 --> 41:45.400 Wir sagen einfach, wenn wir in Q0 sind und links ein Blank ist, dann 41:45.400 --> 41:46.660 können die Blanks gelöscht werden. 41:48.740 --> 41:52.980 Dann diese Regel hier sagt, wir können einfach den Leseschreibkopf 41:52.980 --> 41:54.760 sozusagen nur ans Ende des Wortes schieben. 41:56.200 --> 41:59.560 Dieses Q0 soll nach hinten wandern und wenn es ganz hinten ist und da 41:59.560 --> 42:02.140 noch rechts davon Blanks sind, dann können wir die Blanks auch 42:02.140 --> 42:02.420 löschen. 42:02.860 --> 42:05.740 Und als letztes wollen wir das Q0 noch loswerden und dann steht 42:05.740 --> 42:06.880 wirklich nur noch das Wort da. 42:07.800 --> 42:14.740 Und das ist jetzt die einzige Möglichkeit, wie am Ende ein Wort 42:14.740 --> 42:19.360 erzeugt wird von der Grammatik, das keine Variablen mehr hat. 42:20.540 --> 42:26.140 Dieser Zustand muss wegkommen und die ganzen Blanks müssen wegkommen, 42:26.240 --> 42:28.320 weil das ja alles keine Terminale sind. 42:28.560 --> 42:29.860 Sind ja alles Variablen gewesen. 42:30.640 --> 42:33.180 Okay, so jetzt sind wir aber fertig, hoffe ich. 42:34.160 --> 42:41.620 Also zusammenfassend, wenn wir ein Wort in der Sprache haben, die 42:41.620 --> 42:45.920 semientscheidbar ist, dann kann es durch die Grammatik erzeugt werden, 42:46.540 --> 42:49.780 die Grammatik, die wir eben definiert haben, indem wir die 42:49.780 --> 42:53.780 akzeptierende Berechnung des Wortes rückwärts durchlaufen und das 42:53.780 --> 42:58.040 übersetzen in Regeln, die angewendet werden auf den Startzustand S. 42:59.320 --> 43:05.860 Also wenn das Wort in der Sprache ist, dann existiert eine endliche 43:05.860 --> 43:07.720 akzeptierende Berechnung. 43:08.440 --> 43:13.680 Diese können wir rückwärts interpretieren als Regeln, die dazu führen, 43:13.800 --> 43:17.400 dass S überführt wird in das Wort. 43:17.660 --> 43:19.560 Das heißt, das Wort ist in der Sprache der Grammatik. 43:21.720 --> 43:28.280 Umgekehrt, wenn eine Anwendung von Regeln aus der Grammatik können 43:28.280 --> 43:32.560 wiederum interpretiert werden als eine akzeptierende Berechnung der 43:32.560 --> 43:34.620 Turing -Maschine in endlichen Schritten. 43:35.960 --> 43:42.260 Also ist auch umgekehrt, jedes Wort in der Grammatik auch in der 43:42.260 --> 43:42.800 Sprache L. 43:43.380 --> 43:48.560 Gut, und das schließt jetzt den Beweis von diesem Satz. 43:50.660 --> 43:57.560 Also jede semi-entscheidbare Sprache wird von der Typ-0-Grammatik 43:57.560 --> 43:58.360 erzeugt. 43:58.540 --> 44:01.780 Also Grammatiken sind ganz schön mächtig. 44:08.130 --> 44:11.110 Jetzt gilt tatsächlich auch die Rückrichtung. 44:12.390 --> 44:16.850 Wenn ich eine Sprache habe, die von der Typ-0-Grammatik erzeugt wird, 44:17.310 --> 44:20.170 dann ist die Sprache semi-entscheidbar. 44:20.170 --> 44:24.110 Also jetzt müssen wir andersherum argumentieren. 44:24.210 --> 44:29.430 Wir gehen davon aus, dass wir eine Grammatik haben, die von der Typ-0 44:29.430 --> 44:33.130 -Grammatik, einfach eine Typ-0-Grammatik, eine ganz normale Grammatik 44:33.130 --> 44:36.250 ohne weitere Einschränkungen und wir müssen eine Turing-Maschine 44:36.250 --> 44:42.030 entwerfen, die die Wörter akzeptiert, die von dieser Grammatik erzeugt 44:42.030 --> 44:42.190 werden. 44:43.090 --> 44:45.870 Und das tun wir wie folgt, wir machen jetzt eine nicht 44:45.870 --> 44:52.290 deterministische Turing-Maschine, die genau diese Sprache akzeptiert. 44:52.750 --> 44:53.810 Also was tun wir? 44:54.550 --> 45:01.710 Wir schreiben S aufs Band und entscheiden dann nicht deterministisch, 45:02.610 --> 45:05.190 welche Regeln wir auf dieses S anwenden. 45:06.310 --> 45:09.530 Wir kennen die Grammatik, wir wissen, was alles für Regeln da sind, 45:09.590 --> 45:10.450 die anwendbar sind. 45:10.790 --> 45:13.890 Wir wissen nicht genau, welche Regeln wir anwenden müssen, um das Wort 45:13.890 --> 45:17.030 zu erhalten, sondern wir machen, wir haben zwar eine Eingabe von der 45:17.030 --> 45:20.290 Turing -Maschine, aber die ignorieren wir erstmal, schreiben uns S 45:20.290 --> 45:23.890 irgendwo hin und wenden dann nicht deterministisch Regeln an. 45:25.310 --> 45:27.950 Das können wir machen in der Turing-Maschine, können die Übergänge so 45:27.950 --> 45:29.910 definieren, dass die Turing-Maschine das tut. 45:31.630 --> 45:34.190 Und dann irgendwann entscheiden wir uns nicht deterministisch jetzt 45:34.190 --> 45:37.590 aufzuhören und zu sagen, okay stopp, fertig, Regeln sind angewendet 45:37.590 --> 45:40.650 und dann haben wir irgendwas da kreiert auf unserem Band und jetzt 45:40.650 --> 45:44.570 müssen wir das nur noch schnell vergleichen mit der Eingabe und wenn 45:44.570 --> 45:48.630 das exakt das gleiche ist, dann sagen wir, ja, das Wort wurde so 45:48.630 --> 45:51.150 erzeugt aus der Grammatik und wir akzeptieren. 45:57.020 --> 45:58.420 Den letzten Punkt, okay, 46:02.970 --> 46:04.570 also hier ist es anders aufgeschrieben. 46:06.670 --> 46:12.770 Hier ist es eine Regel anwenden, vergleichen, wenn gut, dann ja, wenn 46:12.770 --> 46:15.870 nicht, neue Regel anwenden, vergleichen. 46:17.010 --> 46:20.590 Ich habe es gerade ein bisschen anders gesagt, was auch geht, nämlich 46:20.590 --> 46:23.090 nicht deterministisch entscheiden, wenn wir fertig sind mit den Regeln 46:23.090 --> 46:24.830 anwenden, aber okay. 46:25.470 --> 46:29.770 Gut, also wenn das Wort in der Sprache der Grammatik ist, dann 46:29.770 --> 46:33.070 existiert eine akzeptierende Berechnung von dieser nicht 46:33.070 --> 46:35.490 deterministischen Turing-Maschine nach endlicher Zeit. 46:36.370 --> 46:38.950 Und die Sache ist, warum ist es nur semi-entscheidbar? 46:38.950 --> 46:45.590 Naja, es ist unklar, wie die Turing-Maschine irgendwann mal sagen 46:45.590 --> 46:50.170 soll, das ist nicht möglich, dieses Wort zu kreieren. 46:50.410 --> 46:55.050 Es gibt keinen geeigneten Zeugen dafür, dass das Wort nicht in der 46:55.050 --> 46:55.610 Sprache liegt. 46:57.650 --> 47:01.850 Okay, also, was haben wir jetzt gesehen? 47:01.990 --> 47:05.870 Wir haben gesehen, dass die semi-entscheidbaren Sprachen, die wir uns 47:05.870 --> 47:10.850 vor ein paar Wochen angeguckt haben, genau die Sprachen sind, also per 47:10.850 --> 47:14.410 Definition, die von deterministischen Turing-Maschinen akzeptiert 47:14.410 --> 47:14.770 werden. 47:16.150 --> 47:19.570 Das ist das Gleiche, das haben wir uns auch irgendwann mal überlegt, 47:20.250 --> 47:22.890 dass es die Sprachen sind, die von nicht deterministischen Turing 47:22.890 --> 47:28.110 -Maschinen akzeptiert werden, dass dort in der Akzeptanz der Sprachen, 47:28.790 --> 47:31.970 wenn wir nicht auf Laufzeit gucken, gibt es keinen Unterschied 47:31.970 --> 47:35.430 zwischen deterministischer Turing-Maschine und nicht deterministischer 47:35.430 --> 47:36.070 Turing -Maschine. 47:36.770 --> 47:39.450 Diese Unterschiede mit P und NP, die kommen erst, wenn wir uns 47:39.450 --> 47:40.470 Laufzeiten angucken. 47:40.810 --> 47:43.930 Nicht deterministisch kann einfach sehr viel schneller sein als 47:43.930 --> 47:44.170 deterministisch. 47:45.350 --> 47:49.230 Aber nur bei der Akzeptanz von Sprachen sind es die gleichen Sprachen, 47:49.270 --> 47:51.970 die da akzeptiert werden, nämlich die semi-entscheidbaren Sprachen. 47:52.770 --> 47:55.870 Und wir haben jetzt gesehen, mit den letzten beiden Sätzen, dass es 47:55.870 --> 48:01.250 auch das Gleiche ist, wie Typ 0 und Typ 0 Grammatiken erzeugte 48:01.250 --> 48:02.010 Sprachen. 48:02.010 --> 48:05.550 Okay, das ist ganz oben in der Chomsky-Hierarchie. 48:06.890 --> 48:16.010 Gut, das heißt für uns, Grammatiken sind ziemlich mächtig, können sehr 48:16.010 --> 48:22.670 komplizierte Sprachen beschreiben, durch diese Regelmengen und wie die 48:22.670 --> 48:23.310 das so machen. 48:24.510 --> 48:27.450 Tatsächlich sind, wenn wir die Grammatik nicht einschränken, dann ist 48:27.450 --> 48:28.710 es wahrscheinlich zu mächtig. 48:29.610 --> 48:33.930 Die Sprachen, die wir damit kreieren können, sind alle semi 48:33.930 --> 48:38.410 -entscheidbaren Sprachen und semi-entscheidbare Sprachen, wenn es zu 48:38.410 --> 48:39.530 viel für uns ist. 48:39.590 --> 48:42.870 Wir können nicht damit rechnen, dass wir semi-entscheidbare Probleme 48:42.870 --> 48:43.690 effizient lösen. 48:44.450 --> 48:49.310 Also insbesondere im Hinblick auf Programmiersprachen und Algorithmen 48:49.310 --> 48:54.770 und Programme ist wahrscheinlich Typ 0 Grammatiken etwas zu allgemein 48:54.770 --> 48:55.170 gefasst. 48:59.440 --> 49:01.600 Aber wir haben ja zum Glück die Hierarchie. 49:02.460 --> 49:04.660 Wir haben ja diese ganzen Abstufungen von Typ 0, ein bisschen 49:04.660 --> 49:09.780 spezieller Typ 1, Kontextsensitiv, noch spezieller Typ 2, Kontextfrei, 49:10.340 --> 49:12.580 noch spezieller Typ 3, Rechtslinear. 49:14.360 --> 49:17.600 Lassen Sie uns gleich mal ganz nach unten springen auf Typ 3, 49:17.840 --> 49:18.480 Rechtslinear. 49:20.680 --> 49:24.860 Also, da oben steht nochmal die genaue Anforderung, wann eine 49:24.860 --> 49:26.820 Grammatik rechtslinear heißt oder Typ 3. 49:28.020 --> 49:31.920 Die Regeln müssen derart sein, dass auf der linken Seite nur eine 49:31.920 --> 49:35.400 Variable steht und auf der rechten Seite ist entweder das leere Wort 49:35.400 --> 49:39.780 oder ein Terminal und eine Variable. 49:40.800 --> 49:43.840 Und ich hatte Ihnen schon die Intuition gegeben, dass die Wörter alle 49:43.840 --> 49:48.640 so aufs Band geschrieben werden und mit vorne dieser Variable kodiert, 49:48.760 --> 49:49.620 so eine Art Zustand. 49:50.620 --> 49:54.840 Und das suggeriert vielleicht schon, dass das relativ einfache 49:54.840 --> 49:58.100 Sprachen sind oder dass es algorithmisch relativ einfach ist, zu 49:58.100 --> 49:59.500 gucken, ob ein Wort erzeugt wird. 49:59.900 --> 50:00.900 Und tatsächlich ist es so. 50:01.580 --> 50:03.480 Wir haben den folgenden Satz. 50:05.080 --> 50:09.300 Die erinnern sich an reguläre Sprachen am Anfang der Vorlesung und 50:09.300 --> 50:12.940 endliche Automaten, die das zugehörige Automatenmodell waren. 50:13.860 --> 50:18.120 Die endlichen Automaten, die Klasse der von endlichen Automaten 50:18.120 --> 50:23.440 akzeptierten Sprachen, ist genau die Klasse der Chomsky 3, der von 50:23.440 --> 50:26.120 Chomsky 3 Grammatiken erzeugten Sprachen. 50:28.380 --> 50:31.160 Also genau die Klasse der regulären Sprachen. 50:32.960 --> 50:34.020 Machen wir das? 50:34.520 --> 50:38.400 Wir müssen jetzt hier in dem Satz beide Richtungen, also wenn regulär, 50:39.200 --> 50:42.940 dann Chomsky 3, wenn Chomsky 3, dann regulär. 50:43.280 --> 50:44.400 Also was machen wir zuerst? 50:45.280 --> 50:48.420 Wenn wir eine reguläre Sprache haben, dann wollen wir jetzt die 50:48.420 --> 50:51.060 Chomsky 3 Grammatik hinschreiben dazu. 50:52.300 --> 50:56.340 Also wir fangen an, wir haben einen endlichen Automaten und wir nehmen 50:56.340 --> 50:59.780 uns einen deterministischen endlichen Automaten in diesem Fall, der 50:59.780 --> 51:06.180 die Sprache akzeptiert oder erkennt. 51:06.360 --> 51:09.020 Hier bei endlichen Automaten ist es das gleiche. 51:09.040 --> 51:14.320 Also der die Sprache erkennt und wir müssen eine Typ 3 Grammatik 51:14.320 --> 51:17.720 aufstellen, die die zugehörige Sprache erzeugt. 51:18.100 --> 51:18.940 So, wie machen wir das? 51:20.160 --> 51:23.040 Wir brauchen für eine Grammatik, brauchen wir mal das 51:23.040 --> 51:26.060 Terminalalphabet, das ist natürlich das gleiche, Großsigma, wir 51:26.060 --> 51:29.380 brauchen Variablen, wir brauchen eine Startvariable und wir brauchen 51:29.380 --> 51:29.940 die Regeln. 51:30.460 --> 51:36.300 Als Variablen nehmen wir die Zustände des endlichen Automaten. 51:36.560 --> 51:39.340 Das ist sozusagen diese Variable, wenn das Wort aufgebaut wird, was 51:39.340 --> 51:43.000 vorne immer steht und ich habe das gerade eben schon Zustand genannt, 51:43.700 --> 51:44.820 in dem wir uns befinden. 51:45.120 --> 51:48.380 Das soll einfach kodieren, diese Variable, in welchem Zustand der 51:48.380 --> 51:49.380 endliche Automat ist. 51:53.000 --> 51:56.420 Die Startvariable sollte dieser Startzustand sein, von dem endlichen 51:56.420 --> 51:57.060 Automaten. 51:57.820 --> 52:02.920 Und die Regeln heißen, wenn ich in einem Endzustand bin, also ich habe 52:02.920 --> 52:07.100 ein Wort aufgebaut und bin jetzt in einem Endzustand, dann kann ich 52:07.100 --> 52:08.100 die Variable wegnehmen. 52:09.340 --> 52:13.080 Und dann bricht es ja ab, weil dann haben wir ein Wort, was keine 52:13.080 --> 52:16.060 Variablen mehr enthält und das ist dann ein Wort in der Sprache. 52:17.260 --> 52:22.840 Oder wenn ich nicht in einem Endzustand bin, dann gucke ich, was gibt 52:22.840 --> 52:23.840 es denn für Übergänge. 52:25.500 --> 52:28.200 Wir müssen uns wieder rückwärts denken. 52:28.540 --> 52:35.420 Also wenn ich aus Zustand Q unter Lesen von Zeichen A in Zustand Q' 52:35.780 --> 52:36.820 übergehe. 52:48.890 --> 52:52.410 Ich muss mal ganz kurz überlegen, ob da jetzt die Striche auf der 52:52.410 --> 52:53.230 falschen Seite sind. 52:54.390 --> 52:58.230 Ich habe jetzt so wie erwartet, dass Q' dann überführt wird in A und 52:58.230 --> 52:58.470 Q. 53:01.820 --> 53:04.220 Also ich folge jetzt einfach mal dem, was da steht auf dem Vorhinein. 53:04.480 --> 53:09.940 Also dann machen wir die Regel, wir haben den Zustand Q und wir 53:09.940 --> 53:12.260 überführen das in A Q'. 53:15.920 --> 53:17.960 Ja, doch, so ist richtig, wie es dort steht. 53:20.620 --> 53:21.960 Was ist die Idee? 53:21.960 --> 53:27.160 Wir simulieren sozusagen das Aufbauen des Wortes als das, was der 53:27.160 --> 53:29.920 endliche Automat schon gelesen hat. 53:30.440 --> 53:36.100 Er fängt an im Startzustand und dann kann er in den Zustand Q1 kommen 53:36.100 --> 53:37.480 unter Lesen von Zeichen A. 53:37.940 --> 53:41.880 Das heißt, wir bauen das Wort auf, was gesagt A schon gelesen und 53:41.880 --> 53:42.800 jetzt sind wir in Q1. 53:43.120 --> 53:48.540 Und dann kann er Zeichen B lesen und dadurch in den Zustand Q2 kommen. 53:48.540 --> 53:53.740 Das heißt, wir gehen in Q2 und schreiben B hin als schon gelesen. 53:54.580 --> 53:55.960 Es ist richtig so, wie es dort steht. 53:56.320 --> 53:57.140 Ich war nur verwirrt. 53:57.740 --> 54:00.140 Also das ist die Definition unserer Grammatik. 54:01.220 --> 54:02.740 Und hier kommt das Argument. 54:04.040 --> 54:08.480 Wenn wir jetzt ein Wort haben, was von dem endlichen Automaten 54:09.180 --> 54:12.860 akzeptiert wird, das ist ja ein deterministischer endlicher Automat, 54:12.920 --> 54:16.800 dann gibt es diese Abfolge von den Zuständen, durch die der Automat 54:16.800 --> 54:21.520 geht durch Lesen von den Zeichen ist Abfolge von Zuständen von Q0 bis 54:21.520 --> 54:22.280 Qn. 54:22.420 --> 54:26.600 Q0 ist der Startzustand und Qn ist ein akzeptierender Endzustand. 54:27.740 --> 54:32.820 Und dann können wir entsprechend dieses Wort genau so aufbauen, indem 54:32.820 --> 54:36.140 wir aus Q0 das erste Zeichen Q1. 54:36.240 --> 54:41.320 Das ist eine zulässige Regel, weil ja der Übergang von Q0 nach Q1 54:41.320 --> 54:44.220 unter Lesen von W1 ein zulässiger Übergang war. 54:44.220 --> 54:48.640 Und dann entsprechend bauen wir das Wort so auf und am Ende haben wir 54:48.640 --> 54:50.200 das... 54:50.200 --> 54:53.840 für den Endzustand dürfen wir den wegschmeißen durch das leere Wort 54:53.840 --> 54:55.100 und dann steht genau das Wort da. 54:55.800 --> 54:57.660 Und umgekehrt gilt es genauso. 54:59.640 --> 55:03.940 Also für alle Ableitungen von der Grammatik können wir das wieder 55:03.940 --> 55:06.700 interpretieren als eine Berechnung von dem endlichen Automaten. 55:08.160 --> 55:08.700 Gut. 55:10.060 --> 55:10.600 Rückrichtung. 55:10.760 --> 55:14.940 Wenn wir jetzt eine rechtslineare Grammatik haben, dann gibt es dazu 55:14.940 --> 55:17.040 einen endlichen Automaten. 55:17.620 --> 55:20.260 Und jetzt machen wir uns wieder das Leben einfach. 55:20.600 --> 55:24.340 Wir konstruieren einen nicht deterministischen endlichen Automaten. 55:24.620 --> 55:28.660 Weil wir ja nicht wissen, wenn ein Wort akzeptiert wird, welche... 55:29.140 --> 55:32.640 oder wenn ein Wort aus der Grammatik erzeugt wird, welche Regeln dazu 55:32.640 --> 55:33.000 führen. 55:33.080 --> 55:36.580 Das können ja mehrere Regeln anwendbar sein und wir müssen jetzt nicht 55:36.580 --> 55:39.420 deterministisch erlauben, die Regeln alle anzuwenden. 55:40.720 --> 55:41.440 Gut. 55:43.980 --> 55:48.980 Also gegeben ist die Grammatik und wir konstruieren den Automaten. 55:49.340 --> 55:52.140 Der hat die folgende Zustandsmenge. 55:52.500 --> 55:55.680 Das sind die Variablen aus unserer Grammatik. 55:56.000 --> 55:57.840 Der Startzustand ist die Startvariable. 55:58.320 --> 56:02.400 Die Endzustände sind die, die in der Regelmenge erlaubt sind zu 56:02.400 --> 56:02.720 löschen. 56:04.480 --> 56:10.040 Und die Übergänge, also ein Übergang aus dem Automaten ist ja unter 56:11.420 --> 56:13.160 Befinden in einem Zustand. 56:13.340 --> 56:16.860 Das ist jetzt Groß A, weil unsere Zustände sind ja die Variablen. 56:17.400 --> 56:22.680 Und Lesen eines Zeichen kleinen A geht in einen anderen Zustand Groß 56:22.680 --> 56:22.940 B. 56:23.940 --> 56:26.740 Und das ist jetzt genau wieder andersherum interpretiert. 56:27.300 --> 56:33.260 In der Typ 3 Grammatik sehen ja die Regeln, die Produktion so aus. 56:33.960 --> 56:37.840 Wenn ich auf der linken Seite Großes A habe, dann kann auf der rechten 56:37.840 --> 56:39.560 Seite klein A Groß B stehen. 56:39.920 --> 56:42.520 Das ist genau das, was wir davor gesehen haben. 56:42.940 --> 56:46.360 1 zu 1 übersetzt, bloß diesmal in die andere Richtung. 56:47.760 --> 56:48.280 Also. 56:49.500 --> 56:53.180 Machen wir uns das nochmal kurz klar, warum das das Gewünschte tut. 56:54.780 --> 57:02.900 Wenn wir ein Wort haben, was in der Sprache L liegt, das heißt, das 57:02.900 --> 57:06.660 ist die Sprache, die von der Grammatik erzeugt wird. 57:07.840 --> 57:12.600 Dann gibt es also, weil das Wort von der Grammatik erzeugt wird, dann 57:12.600 --> 57:18.760 gibt es also diese Folge von Regelanwendungen, von Ableitungen, die 57:18.760 --> 57:23.160 die Startvariable S überführt in das Wort W. 57:24.180 --> 57:28.480 Und weil die Grammatik Typ 3 Grammatik ist, wissen wir, wie diese 57:28.480 --> 57:29.400 Regeln aussehen. 57:29.480 --> 57:33.860 Das muss nämlich immer so sein, dass wir zwischendurch immer ein Wort 57:33.860 --> 57:37.880 haben, wo nur das letzte Symbol ist eine Variable. 57:38.560 --> 57:42.220 Und alle Symbole davor sind Terminalsymbole. 57:42.740 --> 57:45.940 Und jeder Übergang ist entweder so, dass diese letzte Variable 57:45.940 --> 57:51.800 weggenommen wird, oder es ein neues, Abhängigkeit von dieser Variable, 57:51.920 --> 57:55.660 ein neues Terminal und eine neue Variable hingeschrieben wird. 57:56.260 --> 58:00.800 So sind Typ 3 Grammatiken, weil sie diese Anforderungen an die 58:00.800 --> 58:01.700 Regelmenge haben. 58:02.620 --> 58:06.740 Das heißt, wenn das Wort in der Sprache liegt, dann gibt es in der 58:06.740 --> 58:09.520 Grammatik diese Ableitung des Wortes. 58:10.480 --> 58:14.920 Und diese Ableitung kann jetzt übersetzt werden in eine akzeptierende 58:14.920 --> 58:19.080 Berechnung des nicht-deterministischen endlichen Automaten. 58:25.890 --> 58:29.350 Der nicht-deterministische endliche Automat, der befindet sich in 58:29.350 --> 58:30.070 Zuständen. 58:31.630 --> 58:35.770 Die Zustände sind jetzt unsere Variablen, also der Startzustand ist S. 58:37.270 --> 58:42.750 Und der liest dann immer Symbole aus der Eingabe und geht dann in neue 58:42.750 --> 58:43.850 Zustände. 58:44.770 --> 58:48.190 Und hier ist es dem nicht-deterministischen endlichen Automaten, es 58:48.190 --> 58:53.150 ist ihm erlaubt aus dem Startzustand S, unter Lesen des ersten Symbols 58:53.150 --> 58:56.950 der Eingabe, in den Zustand A1 zu gehen. 58:56.950 --> 58:58.530 Warum ist es ihm erlaubt? 58:58.850 --> 59:03.130 Naja, weil hier vorne diese Regel in der Grammatik drin ist und wir 59:03.130 --> 59:04.650 das gerade so hingeschrieben haben. 59:05.770 --> 59:09.210 Machen Sie sich einmal klar, dass das jetzt nicht-deterministische 59:09.210 --> 59:10.070 endliche Automat ist. 59:10.170 --> 59:15.610 Es könnte sein, dass von S aus noch weitere Pfeile mit W1 gelabelt 59:15.610 --> 59:16.710 irgendwo anders hingehen. 59:17.290 --> 59:22.990 Weil es sein kann, dass es weitere Regeln in der Grammatik gibt, die 59:22.990 --> 59:31.510 auf der rechten Seite auf der linken Seite die gleiche Variable haben 59:31.510 --> 59:34.230 und auf der rechten Seite das gleiche Terminal haben und die sich nur 59:34.230 --> 59:38.570 daran unterscheiden, was dort für eine Variable steht. 59:39.610 --> 59:43.690 Wenn es Regeln gibt, die hier und dort das gleiche haben und nur sich 59:43.690 --> 59:48.310 hinten unterscheiden dann entspricht es zwei Übergängen an dem nicht 59:48.310 --> 59:51.970 -deterministischen endlichen Automaten unter Lesen des gleichen 59:51.970 --> 59:52.430 Zeichens. 59:52.430 --> 59:59.190 Gut, und analog können wir dann also diese Regeln übersetzen in 59:59.190 --> 01:00:01.490 Abarbeitung des endlichen Automaten. 01:00:02.750 --> 01:00:08.850 Das führt dann mit der letzten Regel, die wir hier angewendet haben, 01:00:09.170 --> 01:00:11.270 landen wir dann mit dem Automaten in AN. 01:00:11.890 --> 01:00:15.270 Jetzt haben wir das ganze Wort abgearbeitet und jetzt ist die Frage, 01:00:16.070 --> 01:00:17.670 akzeptiert der Automat oder nicht? 01:00:18.030 --> 01:00:25.390 Naja, der Automat akzeptiert ja, wenn AN ein Zielzustand ist, ein 01:00:25.390 --> 01:00:28.190 Endzustand, in der Menge groß F drin ist. 01:00:28.510 --> 01:00:31.530 Und warum wissen wir, dass jetzt AN in der Menge groß F drin ist? 01:00:31.930 --> 01:00:34.050 Naja, weil wir F so definiert haben. 01:00:34.550 --> 01:00:38.610 Wir haben F definiert als die Menge der Variablen, für die es diese 01:00:38.610 --> 01:00:43.490 Relation gibt, die gelöscht werden können am Ende und hier sehen wir, 01:00:44.150 --> 01:00:48.410 dass es diese Relation geben muss, weil hier einfach AN gelöscht 01:00:48.410 --> 01:00:48.670 wurde. 01:00:49.850 --> 01:00:53.990 Also ist das ein Endzustand und der Automat akzeptiert. 01:00:56.010 --> 01:00:59.430 Entsprechend wieder andersrum, alles was der Automat akzeptiert, kann 01:00:59.430 --> 01:01:03.210 nach dem gleichen Schema interpretiert werden als eine Folge von 01:01:03.210 --> 01:01:08.470 Regeln, die in der Grammatik dieses Wort W ableiten. 01:01:13.130 --> 01:01:20.130 Typ 3 Chomsky 3 Grammatiken erzeugen genau die regulären Sprachen. 01:01:21.110 --> 01:01:28.870 Das ist bekanntermaßen eingeschränkt, sehr viel mehr eingeschränkt als 01:01:28.870 --> 01:01:30.490 alle semientscheidbaren Sprachen. 01:01:31.070 --> 01:01:34.330 Wir haben uns am Anfang der Vorlesung damit beschäftigt, wir haben 01:01:34.330 --> 01:01:38.610 auch gesehen, dass relativ simple Sprachen, zum Beispiel die der 01:01:38.610 --> 01:01:41.390 korrekten Klammerausdrücke, nicht regulär sind. 01:01:42.890 --> 01:01:48.970 Also sind die Typ 3 Grammatiken vielleicht ein bisschen zu 01:01:49.730 --> 01:01:57.550 eingeschränkt, um irgendwie für Programmiersprachen geeignet zu sein. 01:01:58.590 --> 01:02:03.150 Also wir haben bisher gesehen, Typ 0 ist sehr allgemein 01:02:03.150 --> 01:02:05.730 semientscheidbar, das kriegen wir nicht hin im Computer. 01:02:06.390 --> 01:02:10.950 Typ 3 ist sehr speziell, regulär, das kriegen wir sehr einfach hin mit 01:02:10.950 --> 01:02:13.810 endlichen Automaten, was so die einfachsten Berechnungsmodelle sind, 01:02:13.870 --> 01:02:14.930 die wir hier kennengelernt haben. 01:02:15.730 --> 01:02:19.670 Also irgendwas, was tatsächlich im Computer umgesetzt wird, sollte 01:02:19.670 --> 01:02:21.870 irgendwo zwischen Typ 0 und Typ 3 liegen. 01:02:22.410 --> 01:02:27.430 Wir haben ja da zum Glück zwei Typen noch kennengelernt, Typ 1 und Typ 01:02:27.430 --> 01:02:31.110 2, und wir werden uns jetzt mit den beiden Typen ein bisschen 01:02:31.110 --> 01:02:31.730 beschäftigen. 01:02:33.150 --> 01:02:36.770 Typ 1, kontextsensitive Sprachen. 01:02:38.850 --> 01:02:45.770 Typ 1 Grammatiken sind schon super, die können gut im Computer 01:02:45.770 --> 01:02:51.470 umgesetzt werden, die haben auch eine Beziehung zu Turing-Maschinen, 01:02:52.470 --> 01:02:56.670 allerdings nicht beliebige Turing-Maschinen, sondern Turing-Maschinen 01:02:56.670 --> 01:02:58.630 mit eingeschränktem Platz. 01:03:00.570 --> 01:03:01.890 Und zwar 01:03:05.110 --> 01:03:11.750 wir haben eine Turing-Maschine, die hat dieses Band, wo die Eingabe 01:03:11.750 --> 01:03:15.550 drauf steht, und jetzt wollen wir die einfach mal einschränken und 01:03:15.550 --> 01:03:20.270 sagen, dieses Band darf nicht mehr benutzt werden, als nur durch die 01:03:20.270 --> 01:03:20.650 Eingabe. 01:03:22.290 --> 01:03:25.050 Und irgendwie der Anschauung halber ist das ganz gut, stellen Sie sich 01:03:25.050 --> 01:03:29.410 einfach vor, dass die Eingabe steht auf einem Read-Only-Band, und da 01:03:29.410 --> 01:03:32.570 drunter haben wir nochmal genauso viel Speicher, um zu arbeiten. 01:03:34.990 --> 01:03:35.590 Gut. 01:03:37.950 --> 01:03:41.390 Also wir messen jetzt den Speicherbedarf der Turing-Maschine anhand 01:03:41.390 --> 01:03:44.010 des Arbeitsbandes und nicht des Eingabebandes. 01:03:44.290 --> 01:03:46.990 Aber eigentlich macht das keinen großen Unterschied, das ist bloß, 01:03:47.150 --> 01:03:48.370 sonst wird das jetzt technisch. 01:03:49.670 --> 01:03:54.630 Und jetzt definieren wir uns die folgenden Klassen von Sprachen. 01:03:55.670 --> 01:03:58.330 D-Tape N und N-Tape N. 01:03:58.330 --> 01:04:01.790 Oder D-Tape S von N und N-Tape S von N. 01:04:03.210 --> 01:04:09.450 Also S von N, das ist der Platz, den wir der Turing-Maschine erlauben 01:04:09.450 --> 01:04:10.870 bei Eingaben der Länge N. 01:04:11.750 --> 01:04:15.890 Also S von N ist irgendeine Funktion von N, da steht sowas wie N² oder 01:04:15.890 --> 01:04:18.370 2 hoch N hoch 3 oder so. 01:04:19.310 --> 01:04:22.850 Das ist einfach irgendeine Funktion, den Platz, den Maximalplatz, den 01:04:22.850 --> 01:04:25.830 wir der Turing-Maschine erlauben, wenn das eine Eingabe der Größe N 01:04:25.830 --> 01:04:26.150 kriegt. 01:04:27.250 --> 01:04:33.030 Und D-Tape S von N ist dann die Klasse der Sprachen, für die es eine 01:04:33.030 --> 01:04:36.270 deterministische Turing-Maschine gibt, die sich an dieser 01:04:36.270 --> 01:04:38.170 Platzbeschränkung halten kann. 01:04:39.630 --> 01:04:44.290 Also wir klassifizieren jetzt die Probleme wieder nach Turing 01:04:44.290 --> 01:04:49.650 -Maschinen, aber statt nach Laufzeit zu klassifizieren, wie wir das in 01:04:49.650 --> 01:04:52.570 der Komplexitätstheorie gemacht haben, klassifizieren wir jetzt nach 01:04:52.570 --> 01:04:54.200 Speicherplatz, nach Speicherbedarf. 01:04:57.800 --> 01:05:02.240 Bei dem T und NP, da haben wir Laufzeiten gesagt, polynomiell, nicht 01:05:02.240 --> 01:05:03.200 polynomiell und so. 01:05:04.800 --> 01:05:07.960 Und jetzt, die Laufzeit ist uns egal, wie lange das braucht. 01:05:08.360 --> 01:05:11.640 Wichtig ist uns, dass der Speicher nicht explodiert von der Turing 01:05:11.640 --> 01:05:16.780 -Maschine, dass die Speicheranforderungen innerhalb dieser Schranke S 01:05:16.780 --> 01:05:17.700 von N bleibt. 01:05:18.800 --> 01:05:22.620 Und dann haben wir entsprechend zwei Klassen, nämlich einmal für 01:05:22.620 --> 01:05:26.360 deterministische Turing-Maschinen mit so wenig Speicher und nicht 01:05:26.360 --> 01:05:30.380 -deterministische Turing-Maschinen mit entsprechend so wenig Speicher. 01:05:30.560 --> 01:05:34.640 Und das sind dann die Klassen DTape S von N und NTape S von N. 01:05:38.580 --> 01:05:46.680 Klar ist, dass jede deterministische Turing-Maschine ja auch eine 01:05:46.680 --> 01:05:48.720 nicht -deterministische Turing-Maschine ist, die den nicht 01:05:48.720 --> 01:05:50.060 -determinismus einfach nicht nutzt. 01:05:50.060 --> 01:05:54.540 Und deswegen sind natürlich die Sprachen, die in DTape S von N sind, 01:05:54.660 --> 01:05:58.080 auch enthalten in den Sprachen, die in NTape S von N sind. 01:05:59.260 --> 01:06:03.500 Und für den Spezialfall, das S von N, das ist jetzt der Spezialfall, 01:06:03.600 --> 01:06:11.820 der uns wirklich interessiert, dass das N ist, also wir brauchen exakt 01:06:11.820 --> 01:06:15.200 so viel Band, dürfen wir nur benutzen, wie die Eingabe lang ist. 01:06:17.020 --> 01:06:24.900 Für den Spezialfall ist NTape N und NTape O von N sozusagen das 01:06:24.900 --> 01:06:25.340 Gleiche. 01:06:25.480 --> 01:06:29.600 Also es macht keinen Unterschied, ob ich jetzt sage, bei Eingaben der 01:06:29.600 --> 01:06:36.660 Länge N darf ich genau N Platz auf dem Band nehmen oder 2N oder 3N 01:06:36.660 --> 01:06:39.900 oder 4N, das ist alles das Gleiche, das sind die gleichen Klassen. 01:06:40.240 --> 01:06:44.980 Das kann alles simuliert werden durch, naja, so diese Tricks, die wir 01:06:44.980 --> 01:06:47.700 auch gesehen haben bei den Multiband-Turing-Maschinen, die gleichen 01:06:47.700 --> 01:06:48.720 Tricks funktionieren hier. 01:06:49.420 --> 01:06:53.380 Aber es ist ein Unterschied, ob ich sage, ich darf Speicher N benutzen 01:06:53.380 --> 01:06:55.700 oder ich darf Speicher N² benutzen. 01:06:55.860 --> 01:06:56.700 Das macht einen Unterschied. 01:06:58.020 --> 01:07:02.200 Aber ob ich jetzt N oder 7N benutze, das ist das Gleiche. 01:07:02.940 --> 01:07:06.800 Also für nicht deterministische Turing-Maschinen ist das das Gleiche 01:07:06.800 --> 01:07:09.720 und das ist der interessante Fall für uns, NTape N. 01:07:10.020 --> 01:07:13.100 Aber Sie dürfen auch, wenn Sie Ihre Turing-Maschine konstruieren 01:07:13.100 --> 01:07:15.800 können, mit 2N Speicher ist geschenkt. 01:07:16.920 --> 01:07:17.360 Gut. 01:07:18.600 --> 01:07:26.940 Und jetzt ist die Aussage, Chomsky 1 sind die Grammatiken, die 01:07:26.940 --> 01:07:31.700 Sprachen erzeugen, die genau in NTape N sind. 01:07:33.660 --> 01:07:38.620 Also es gibt einen Zusammenhang zwischen kontextfreien Sprachen, das 01:07:38.620 --> 01:07:44.980 sind die Chomsky 1 Grammatiken oder Sprachen und nicht 01:07:44.980 --> 01:07:48.120 deterministischen Turing-Maschinen mit linearem Speicher. 01:07:50.760 --> 01:07:54.680 Der zweite Zusammenhang ist wirklich so, dass es wie davor auch genau 01:07:54.680 --> 01:07:56.320 das richtige Berechnungsmodell ist. 01:07:56.780 --> 01:08:01.680 Also wenn eine Sprache erzeugt wird von der Chomsky 1 Grammatik, dann 01:08:01.680 --> 01:08:04.860 existiert eine nicht deterministische Turing-Maschine, Laufzeit ist 01:08:04.860 --> 01:08:10.560 uns egal, die die Sprache erkennt und deren Platzbedarf linear 01:08:10.560 --> 01:08:11.300 beschränkt ist. 01:08:12.180 --> 01:08:15.220 Andersrum, wenn es eine nicht deterministische Turing-Maschine gibt, 01:08:15.820 --> 01:08:20.080 die dessen Platzbedarf linear beschränkt ist, dann gibt es eine 01:08:20.080 --> 01:08:23.720 Chomsky 1 Grammatik, die die entsprechende Sprache erzeugt. 01:08:24.540 --> 01:08:26.160 Den Beweis tun wir hier nicht. 01:08:30.810 --> 01:08:33.950 So, noch eine Bemerkung. 01:08:34.730 --> 01:08:38.850 Ich habe jetzt nicht deterministische Turing-Maschine da verwendet und 01:08:38.850 --> 01:08:41.190 nicht deterministische Turing-Maschine. 01:08:41.890 --> 01:08:45.190 Es könnte sein, dass das das gleiche ist. 01:08:45.450 --> 01:08:46.190 Wir wissen es nicht. 01:08:47.370 --> 01:08:54.750 Also, ob wir den nicht determinismus loswerden, ohne den Speicherplatz 01:08:54.750 --> 01:08:58.190 signifikant zu erhöhen, ist ein offenes Problem. 01:09:00.430 --> 01:09:06.250 Genauso wie im Prinzip diese Frage, ob p gleich np ist, ist ja die 01:09:06.250 --> 01:09:09.790 Frage, ob wir den nicht determinismus loswerden, ohne dass wir die 01:09:09.790 --> 01:09:14.770 Laufzeit signifikant erhöhen, wobei dort wirklich die Signifikanz 01:09:14.770 --> 01:09:19.730 erheblich ist, also ohne, dass wir die Laufzeit von Polynomial auf 01:09:19.730 --> 01:09:21.630 Superpolynomial erhöhen müssen. 01:09:22.630 --> 01:09:27.430 Und hier ist der Speicherplatz wirklich sehr eng gefasst. 01:09:27.630 --> 01:09:30.430 Also, wenn wir linearen speichern, wollen wir bei linearen Speicher 01:09:30.430 --> 01:09:30.770 bleiben. 01:09:31.970 --> 01:09:33.470 Und das ist ein offenes Problem. 01:09:34.110 --> 01:09:37.590 Ich kann persönlich nicht sagen, was dort die Vermutung im Allgemeinen 01:09:37.590 --> 01:09:38.670 ist, ob das gilt oder nicht. 01:09:39.430 --> 01:09:40.010 Weiß ich nicht. 01:09:40.130 --> 01:09:41.050 Da stecke ich nicht drin. 01:09:41.190 --> 01:09:45.090 Wir kümmern uns eigentlich mehr um Laufzeiten als um Speicher, aber 01:09:45.090 --> 01:09:47.410 die entsprechende Frage für Speicher ist offen. 01:09:48.010 --> 01:09:48.010 Gut. 01:09:50.610 --> 01:09:55.690 So, dann schauen wir uns noch mal das Problem Clique an. 01:09:55.950 --> 01:09:58.050 Das Entscheidungsproblem Clique. 01:09:58.370 --> 01:10:01.250 Und ich möchte Sie wenigstens davon überzeugen, dass das 01:10:01.250 --> 01:10:04.470 Entscheidungsproblem Clique, was so ähnlich ist wie unser 01:10:04.470 --> 01:10:09.950 motivierendes Beispiel am Anfang, dass das zum Beispiel erzeugt wird 01:10:09.950 --> 01:10:12.810 von einer kontextfreien Sprache. 01:10:13.030 --> 01:10:16.210 Also, dass es eine nicht-diminutivistische Turing-Maschine gibt, die 01:10:16.210 --> 01:10:18.550 in linearen Speicherplätzen das Problem löst. 01:10:19.090 --> 01:10:21.210 Einfach damit wir es einmal gesehen haben. 01:10:21.270 --> 01:10:21.430 Gut. 01:10:23.490 --> 01:10:25.010 Clique ist das folgende. 01:10:25.150 --> 01:10:26.750 Wiederum hier die Definition. 01:10:26.870 --> 01:10:27.690 Wir haben einen Graphen. 01:10:27.790 --> 01:10:29.090 Jetzt G ist wieder ein Graph. 01:10:29.670 --> 01:10:31.570 Knotenmenge, Kantenmenge und eine Teilmenge. 01:10:31.690 --> 01:10:38.830 V' der Knoten bildet eine Clique, wenn je zwei Elemente je zwei Knoten 01:10:38.830 --> 01:10:41.850 in dieser Teilmenge benachbart sind, also durch eine Kante verbunden 01:10:41.850 --> 01:10:42.230 sind. 01:10:43.470 --> 01:10:48.850 Beispielsweise das hier ist ein Graph und die Frage ist dann noch zu 01:10:48.850 --> 01:10:52.070 einem gegebenen Parameter, K gleich 5. 01:10:53.010 --> 01:10:56.270 Gibt es in diesem Graphen eine Clique der Größe mindestens 5? 01:10:57.430 --> 01:10:59.970 Also, das ist das Entscheidungsproblem. 01:11:01.110 --> 01:11:01.710 Okay. 01:11:02.470 --> 01:11:06.390 Und entsprechend, Sie erinnern sich, Entscheidungsprobleme haben wir 01:11:06.390 --> 01:11:08.250 in Sprachen übersetzt. 01:11:08.610 --> 01:11:13.850 Also, worum wir uns hier kümmern ist, die Sprache aller Wörter, die 01:11:13.850 --> 01:11:16.730 Codierungen sind von Ja-Instanzen. 01:11:17.630 --> 01:11:23.090 Also, das soll codierte Graphen sein, die Ja-Instanzen sind, also 01:11:23.090 --> 01:11:26.110 codierte Graphen, die eine Clique der Größe mindestens 5 haben. 01:11:26.610 --> 01:11:31.290 Und die Frage ist dann, gegeben ein Graphen, also gegeben ein Wort, 01:11:31.770 --> 01:11:34.730 eine Codierung von einem Graphen, liegt dieses Wort in der Sprache? 01:11:35.890 --> 01:11:39.490 Codiert es einen Graphen, wo die Clique der Größe mindestens 5 ist, ja 01:11:39.490 --> 01:11:39.950 oder nein? 01:11:40.690 --> 01:11:40.690 Gut. 01:11:44.050 --> 01:11:48.190 Das Clique-Problem gehört sogar zu DTapeN. 01:11:49.350 --> 01:11:51.730 Also, wir können eine deterministische Turing-Maschine mit linearem 01:11:51.730 --> 01:11:54.990 Speicherbedarf konstruieren. 01:11:55.610 --> 01:11:59.070 Laufzeit ist uns egal, aber wir können das Clique-Problem entscheiden 01:11:59.070 --> 01:12:01.190 ohne viel Speicher. 01:12:02.070 --> 01:12:09.950 Also, gegeben ist der Graph G mit Knoten Menge v1 bis vn und diese 01:12:09.950 --> 01:12:13.850 Zahl k das ist die Größe der Clique, die wir benutzen wollen. 01:12:14.190 --> 01:12:16.390 Also, was ist die Eingabelänge? 01:12:16.650 --> 01:12:17.770 Naja, mindestens n. 01:12:20.030 --> 01:12:22.690 Wir haben sogar noch ein bisschen mehr, weil wir ja die Kanten auch 01:12:22.690 --> 01:12:23.930 noch codieren müssen. 01:12:25.050 --> 01:12:30.270 Und was wir jetzt machen wollen ist wir wollen einfach suchen nach der 01:12:30.270 --> 01:12:32.430 Clique, in dem wir alle Möglichkeiten durchgehen. 01:12:33.210 --> 01:12:39.090 Alle Möglichkeiten für diese Teilmengen v' aus v und schauen, ob es 01:12:39.090 --> 01:12:41.910 die entsprechende Bedingung erfüllt. 01:12:42.570 --> 01:12:43.910 Wie gehen wir die Teilmengen durch? 01:12:44.110 --> 01:12:52.190 Naja, wir können einen n-Vektor der heißt c nehmen, der einfach Nullen 01:12:52.190 --> 01:12:57.010 und Einsen hat und die Bedeutung ist, wenn der Vektor an der Stelle i 01:12:57.010 --> 01:13:01.530 eine 1 hat, dann heißt es, dass der Knoten i sozusagen in dieser Test 01:13:01.530 --> 01:13:03.210 -Clique drin liegt. 01:13:04.350 --> 01:13:07.030 Und so gehen wir einfach alle 0,1-Vektoren durch. 01:13:07.590 --> 01:13:13.150 Das kann man mit Naturing-Maschine machen, quasi ohne sehr viel mehr 01:13:13.150 --> 01:13:14.250 Speicher zu brauchen. 01:13:14.470 --> 01:13:16.910 Wir haben den 0,1-Vektor und dann brauchen wir vielleicht noch ein 01:13:16.910 --> 01:13:20.530 bisschen, aber wirklich wenig, um zu sagen, was ist der nächste 0,1 01:13:20.530 --> 01:13:20.890 -Vektor. 01:13:21.090 --> 01:13:22.990 Wir können die der Reihe nach durchgehen. 01:13:23.570 --> 01:13:26.490 Und dann brauchen wir auch nicht besonders viel Speicher, um so einen 01:13:26.490 --> 01:13:31.110 0,1-Vektor zu nehmen und zu vergleichen auf der Eingabe, auf dem Read 01:13:31.110 --> 01:13:34.570 -Only -Band, ob jetzt alle die, die eine 1 dort bekommen haben, 01:13:34.650 --> 01:13:36.490 wirklich oben verbunden sind durch eine Kante. 01:13:37.790 --> 01:13:43.390 Und wir müssen auch noch testen, ob wir denn mindestens K-Elemente auf 01:13:43.390 --> 01:13:44.250 1 gesetzt haben. 01:13:45.670 --> 01:13:49.810 Also wir zählen die Einsen in dem Vektor, vergleichen das mit K, 01:13:50.450 --> 01:13:54.690 überprüfen für jedes Paar, die auf 1 gesetzt wurden, ob in der Eingabe 01:13:55.350 --> 01:13:58.510 die beiden entsprechenden Knoten mit einer Kante verbunden sind. 01:13:58.750 --> 01:14:02.090 Und das geht relativ einfach. 01:14:03.190 --> 01:14:08.410 Also die Vektoren können nacheinander, beginnend mit 0,0,0,0,0,0,0 01:14:08.410 --> 01:14:12.390 generiert werden, ohne zusätzlichen Speicher. 01:14:13.110 --> 01:14:19.570 Das hat Länge n und der positive Test akzeptiert dann die Instanz, 01:14:19.670 --> 01:14:24.490 wenn wir irgendwann mal eins gefunden haben, wo wir mindestens K 01:14:24.490 --> 01:14:28.150 -Einsen gesetzt haben und für jede 2 Einsen, die wir dort gesetzt 01:14:28.150 --> 01:14:29.710 haben, oben die Kante existiert. 01:14:30.350 --> 01:14:35.070 Und ansonsten sind wir auch irgendwann durch mit allen möglichen 0,1 01:14:35.070 --> 01:14:41.750 -Vektoren der Länge n und können am Ende sagen nein, wenn keins davon 01:14:41.750 --> 01:14:43.450 einen positiven Test ergeben hat. 01:14:44.430 --> 01:14:47.350 Insgesamt schaffen wir das alles mit linearem Speicherplatz. 01:14:47.970 --> 01:14:53.630 Die Laufzeit, werden Sie sicherlich wissen, ist exponentiell hier. 01:15:00.510 --> 01:15:04.770 Sowas wie 2 hoch n, wenn man sich nicht besonders anstrengt. 01:15:06.830 --> 01:15:10.770 Das heißt, ich konnte Sie hoffentlich davon überzeugen, dass dieses 01:15:14.090 --> 01:15:16.610 Clickentscheidungsproblem in DTapen drin ist. 01:15:16.710 --> 01:15:19.150 Es gibt eine deterministische Turingmaschine, die die Sprache 01:15:19.670 --> 01:15:23.930 entscheidet und der Speicherbedarf ist linear in der Eingabegröße. 01:15:24.370 --> 01:15:27.870 Das heißt, mit dem Satz davor, den ich nicht bewiesen habe, dass diese 01:15:27.870 --> 01:15:31.630 Sprache Chomsky 1 die Sprache ist. 01:15:31.950 --> 01:15:36.130 Dass das durch eine kontextsensitive Grammatik erzeugt werden kann. 01:15:36.130 --> 01:15:37.430 Gut. 01:15:40.690 --> 01:15:44.530 Das war jetzt kontextfrei, das war Typ 1. 01:15:45.170 --> 01:15:52.570 Wir finden also nicht deterministische Turingmaschinen, die in 01:15:52.570 --> 01:15:54.950 linearem Speicherplatz das machen können. 01:15:55.290 --> 01:16:00.730 Das gibt uns auch quasi eine obere Schranke an die Zeitfunktion, aber 01:16:00.730 --> 01:16:03.830 da wollen wir nicht richtig drüber reden. 01:16:04.750 --> 01:16:08.230 Zu dem Typ... was habe ich gerade gesagt? 01:16:08.330 --> 01:16:14.470 Wir waren gerade bei kontextsensitiv. 01:16:21.110 --> 01:16:22.530 Habe ich gerade kontextfrei gesagt? 01:16:22.610 --> 01:16:23.110 Ich hoffe nicht. 01:16:23.330 --> 01:16:25.190 Also wir sind die ganze Zeit bei kontextsensitiv. 01:16:30.770 --> 01:16:31.570 Also, genau. 01:16:31.690 --> 01:16:33.110 Wir haben linearen Speicherplatz. 01:16:33.730 --> 01:16:37.730 Wenn wir uns um die Laufzeit kümmern, können wir nicht besonders viel 01:16:37.730 --> 01:16:38.270 erwarten. 01:16:38.410 --> 01:16:41.710 Also solange nicht p gleich np ist, kann man zeigen, dass diese 01:16:41.710 --> 01:16:46.190 kontextsensitiven Typ 1 Grammatiken, das Wortproblem, kann nicht in 01:16:46.190 --> 01:16:48.310 polynomialer Zeit entschieden werden. 01:16:49.430 --> 01:16:55.410 Also click ist ja so ein Beispiel von der np-vollständigen Sprache. 01:16:55.610 --> 01:16:58.670 Die werden wir wohl nicht in polynomialer Zeit entscheiden können. 01:16:59.230 --> 01:16:59.570 Und auch 01:17:03.110 --> 01:17:03.670 ja... 01:17:03.670 --> 01:17:04.630 Ich spreche gerade durcheinander. 01:17:05.830 --> 01:17:06.050 Gut. 01:17:06.290 --> 01:17:07.390 Eine zweite Bemerkung. 01:17:08.490 --> 01:17:16.670 Typ 1 Grammatiken Sie erinnern sich, die Regeln waren auf der linken 01:17:16.670 --> 01:17:20.070 Seite dürfen nur Variablen stehen und die rechte Seite darf nicht 01:17:20.070 --> 01:17:22.370 kürzer sein als die linke Seite. 01:17:22.630 --> 01:17:24.850 Das waren die Anforderungen an die Typ 1 Grammatik. 01:17:25.350 --> 01:17:28.730 Mit dieser einen Ausnahme, ich darf das Staatssymbol s durch das leere 01:17:28.730 --> 01:17:29.270 Wort ersetzen. 01:17:29.590 --> 01:17:30.450 Das ist die einzige Ausnahme. 01:17:31.470 --> 01:17:35.350 Und ansonsten linke Seite nur Variablen, rechte Seite irgendwas, nicht 01:17:35.350 --> 01:17:39.230 das Staatssymbol und nicht kürzer. 01:17:40.190 --> 01:17:43.310 Es gibt, das ist schon so ein kleiner Vorgeschmack auf das, was wir in 01:17:43.310 --> 01:17:45.710 den nächsten Wochen, dann im Januar, sehen werden. 01:17:46.790 --> 01:17:50.810 Man kann die Regeln auch noch weiter einschränken. 01:17:51.630 --> 01:17:53.470 Nämlich, dass sie diese Form haben. 01:17:53.630 --> 01:17:56.710 Also alle Regeln haben eine von diesen vier Formen. 01:17:57.150 --> 01:17:59.030 Und das ist nicht wirklich eine Einschränkung. 01:17:59.130 --> 01:18:00.170 Das ist äquivalent. 01:18:03.410 --> 01:18:05.130 Jetzt gehen wir einmal durch. 01:18:05.190 --> 01:18:07.110 Was sind diese fünf möglichen Formen? 01:18:07.210 --> 01:18:10.130 Naja, wir dürfen Variablen ersetzen durch andere Variablen. 01:18:10.230 --> 01:18:11.910 Einfach ein 1 zu 1 Tausch. 01:18:12.870 --> 01:18:17.070 Wir dürfen eine Variable ersetzen durch zwei Variablen. 01:18:18.550 --> 01:18:21.790 Wir dürfen zwei Variablen ersetzen durch zwei andere Variablen. 01:18:22.290 --> 01:18:24.850 Wir dürfen eine Variable durch ein Terminal ersetzen. 01:18:25.590 --> 01:18:29.400 Und dieser Sonderfall der Start, die Startvariable darf durch das 01:18:29.400 --> 01:18:30.380 leere Wort ersetzt werden. 01:18:32.220 --> 01:18:36.660 Das sind, wenn Sie scharf hingucken, sehen Sie, dass alle diese fünf 01:18:36.660 --> 01:18:43.380 Regeln sind erlaubt in kontextsensitiven Grammatiken. 01:18:44.400 --> 01:18:47.540 An sich, so wie wir es definiert haben, erlauben kontextsensitive 01:18:47.540 --> 01:18:52.620 Grammatiken noch mehr Regeln, wo wirklich lange Sachen links und 01:18:52.620 --> 01:18:53.600 rechts auftreten. 01:18:54.060 --> 01:18:59.500 Aber man kann zeigen, dass man eine äquivalente Grammatik bauen kann, 01:18:59.940 --> 01:19:04.380 die dessen Regeln nur so aussehen und die gleiche Sprache erzeugt. 01:19:04.920 --> 01:19:10.040 Also wenn Sie sich unwohl fühlen mit dieser langen Definition, das 01:19:10.040 --> 01:19:13.280 sind tatsächlich die Art von Regeln, die wir haben wollen. 01:19:13.720 --> 01:19:16.240 Achso, was ich noch vergessen habe, natürlich auf der rechten Seite 01:19:16.240 --> 01:19:18.620 darf nie das Startsymbol stehen. 01:19:18.840 --> 01:19:23.140 Also c und d sind Variablen, die nicht das Startsymbol beinhalten. 01:19:23.140 --> 01:19:30.680 Und so eine Art von Beweisen werden wir noch ein paar Mal führen, dass 01:19:30.680 --> 01:19:34.580 wir Grammatiken überführen in andere Grammatiken, die äquivalent sind, 01:19:34.740 --> 01:19:38.180 die die gleiche Sprache erzeugen, die aber von der Struktur der Regeln 01:19:38.180 --> 01:19:43.840 einfacher sind, um zum Beispiel zu erlauben, Rechnungsmodelle für 01:19:43.840 --> 01:19:44.980 diese Grammatiken aufzustellen. 01:19:45.440 --> 01:19:47.720 Aber ich greife voraus, das will ich nicht. 01:19:49.660 --> 01:19:52.220 So, jetzt nochmal eine kleine Notation. 01:19:53.020 --> 01:20:03.700 Diese Regelmengen sind oft so, dass die gleiche linke Seite in 01:20:03.700 --> 01:20:07.100 verschiedenen Regeln auftaucht und dann haben wir eine abkürzende 01:20:07.100 --> 01:20:12.340 Schreibweise, also die mit so einem Pipe die rechten Seiten trennt. 01:20:12.560 --> 01:20:16.100 Also das heißt einfach nur, ich habe die Regel, s darf durch Alpha 01:20:16.100 --> 01:20:18.860 ersetzt werden und s darf auch durch Beta ersetzt werden. 01:20:18.860 --> 01:20:23.940 Oder unten steht dann, s darf ersetzt werden durch Alpha oder Beta, so 01:20:23.940 --> 01:20:24.940 kann man das lesen. 01:20:27.020 --> 01:20:30.500 Jetzt sind wir bei kontextfreien Typ 2 Grammatiken. 01:20:31.960 --> 01:20:32.820 Ja, nochmal kurz. 01:20:33.420 --> 01:20:35.960 Typ 0 war semientscheidbar, ist zu mächtig. 01:20:36.160 --> 01:20:39.180 Typ 3 war regulär, ist zu eingeschränkt. 01:20:39.660 --> 01:20:47.180 Typ 2 war nTape n, hat entweder vollständige Sprachen drin, auch zu 01:20:47.180 --> 01:20:48.600 allgemein. 01:20:49.320 --> 01:20:50.680 Und jetzt sind wir bei Typ 1. 01:20:50.780 --> 01:20:53.540 Typ 1 ist so ungefähr das, was wirklich schön ist für uns. 01:20:53.840 --> 01:20:54.320 Kontextfrei. 01:20:55.700 --> 01:21:00.560 So, kontextfreie Grammatiken waren so definiert, die linke Seite ist 01:21:00.560 --> 01:21:04.620 eine Variable und die rechte Seite ist irgendwas. 01:21:07.040 --> 01:21:10.020 Wieder kontextfrei, eine Variable unabhängig vom Kontext, links und 01:21:10.020 --> 01:21:12.580 rechts, darf ersetzt werden durch die rechte Seite. 01:21:14.400 --> 01:21:18.680 Und ein Beispiel wäre jetzt diese Sprache, die wir schon am Anfang mal 01:21:18.680 --> 01:21:22.600 kennengelernt haben, als ein Beispiel einer nicht regulären Sprache, 0 01:21:22.600 --> 01:21:23.660 hoch n, 1 hoch n. 01:21:24.260 --> 01:21:28.120 Und ich möchte Sie kurz davon überzeugen, dass diese Sprache von einer 01:21:28.120 --> 01:21:31.120 kontextfreien Grammatik erzeugt wird, indem ich Ihnen die Grammatik 01:21:31.120 --> 01:21:31.360 gebe. 01:21:33.180 --> 01:21:36.380 Die Variablen sind nur eine Variable, das Startsymbol. 01:21:38.080 --> 01:21:40.180 Das Terminalalphabet ist 0 und 1. 01:21:40.180 --> 01:21:44.020 Und dann haben wir nur zwei Regeln, hier in der Kurzschreibweise. 01:21:44.800 --> 01:21:49.900 Ich darf eine Variable s auf der linken Seite ersetzen durch 0, 1 oder 01:21:49.900 --> 01:21:51.480 durch 0, s, 1. 01:21:54.100 --> 01:21:58.000 Und dann kann ich damit Wörter erzeugen steht gar nicht da, ich habe 01:21:58.000 --> 01:21:58.900 jetzt ein Beispiel erwartet. 01:22:00.680 --> 01:22:03.060 Damit kann ich diese Sprache erzeugen. 01:22:04.340 --> 01:22:09.400 Ich fange an mit s, dann kann ich das ersetzen durch 0, 1 und dann 01:22:09.400 --> 01:22:11.300 habe ich das 0 hoch 1, 1 hoch 1. 01:22:11.680 --> 01:22:16.800 Oder ich ersetze s durch 0, s, 1 und danach das s durch 0, 1 dann habe 01:22:16.800 --> 01:22:18.800 ich 0, 0, 1, 1 und so weiter. 01:22:21.740 --> 01:22:26.740 Zweites Beispiel sind die Palindrome, die wir auch kennengelernt haben 01:22:26.740 --> 01:22:31.440 als etwas, was nicht regulär ist, also nicht Typ 3. 01:22:32.080 --> 01:22:36.120 Ich möchte Sie auch wiederum davon überzeugen, dass das Typ 2 machbar 01:22:36.120 --> 01:22:36.400 ist. 01:22:36.400 --> 01:22:38.760 Dass es eine kontextfreie Sprache ist. 01:22:39.760 --> 01:22:41.980 Wie waren die Palindrome nochmal definiert? 01:22:42.120 --> 01:22:45.320 Wörter aus dem 0, 1, die rückwärts gelesen das gleiche ergeben. 01:22:46.280 --> 01:22:50.300 Also in dem Setting sind die Palindrome nicht unbedingt gerade Länge, 01:22:50.520 --> 01:22:55.860 sondern nur ein Symbol 0, nur ein Symbol 1 oder das leere Wort sind 01:22:55.860 --> 01:22:56.580 auch Palindrome. 01:22:57.980 --> 01:23:02.320 Und die wichtige Erkenntnis ist, dass wenn wir ein Palindrom haben, w, 01:23:02.600 --> 01:23:08.560 dann ist auch 0, w, 0 ein Palindrom und 1, w, 1 ist auch ein 01:23:08.560 --> 01:23:08.960 Palindrom. 01:23:10.160 --> 01:23:13.660 Und jedes Palindrom kann so sukzessive aufgebaut werden. 01:23:14.420 --> 01:23:18.020 Das heißt, wir können die Grammatik so definieren, wie dann nur eine 01:23:18.020 --> 01:23:22.140 Variable, Terminalalphabet 0, 1 und wir haben die folgenden Regeln. 01:23:22.300 --> 01:23:28.560 s kann ersetzt werden durch leeres Wort 0 oder 1 und s kann auch 01:23:28.560 --> 01:23:33.660 ersetzt werden durch 0, s, 0 oder 1, s, 1. 01:23:35.240 --> 01:23:41.740 Und alles, was davon erzeugt wird, ist palindromisch und jedes 01:23:41.740 --> 01:23:43.400 Palindrom wird so erzeugt. 01:23:46.730 --> 01:23:52.350 Beispiel 3, die Sprache aller Wörter aus 0, 1, bei der die Anzahl der 01:23:52.350 --> 01:23:55.090 Nullen gleich der Anzahl der Einsen ist. 01:23:55.230 --> 01:23:57.030 Und wir haben uns aus irgendeinem Grund das leere Wort hier 01:23:57.030 --> 01:23:57.530 ausgeschlossen. 01:23:58.650 --> 01:24:00.710 Das ist schon ein bisschen komplizierter, da brauchen wir jetzt schon 01:24:00.710 --> 01:24:01.790 drei Variablen. 01:24:02.750 --> 01:24:05.750 Aber man kann es auch basteln. 01:24:06.450 --> 01:24:09.170 Und ich sage auch basteln, weil das ist auch so ein bisschen so die 01:24:09.170 --> 01:24:12.070 Aufgabe, eine Grammatik zu finden zu einer gegebenen Sprache, ist auch 01:24:12.070 --> 01:24:16.370 so eine kleine Kunst und wieder, je öfter Sie das sehen, desto mehr 01:24:16.370 --> 01:24:19.490 kennen Sie die Tricks, die man da so machen kann. 01:24:19.590 --> 01:24:21.530 Also, ich glaube, das ist ganz hilfreich. 01:24:22.690 --> 01:24:26.870 Wir haben Variablen s, a und b, Terminalalphabet 0, 1. 01:24:27.730 --> 01:24:36.670 So, jetzt können wir s ersetzen durch 0 und ein b oder durch 1 und ein 01:24:36.670 --> 01:24:36.870 a. 01:24:38.090 --> 01:24:45.110 Die Idee ist, wir bauen das Wort auf von links nach rechts und die bs 01:24:45.110 --> 01:24:50.270 sagen uns, ich muss da noch kompensieren, da fehlt mir noch eine 1. 01:24:51.410 --> 01:24:56.070 Und die as sagen uns, ich muss kompensieren, da fehlt mir noch eine 0. 01:24:56.070 --> 01:24:59.630 Wir wollen genau die gleiche Anzahl 0 wie 1. 01:25:00.710 --> 01:25:05.190 Also, jedes b ist für uns, merke, es fehlt noch eine 1. 01:25:05.310 --> 01:25:07.390 Und jedes a ist für uns, merke, es fehlt noch eine 0. 01:25:08.970 --> 01:25:14.130 Also, wenn ich jetzt ein a sehe, dann kann ich, a heißt ja, es fehlt 01:25:14.130 --> 01:25:17.430 eine 0, dann kann ich a durch die 0 ersetzen und bin happy. 01:25:19.090 --> 01:25:24.030 Ich kann a auch durch die 0 ersetzen und sagen jetzt, sozusagen, der 01:25:24.030 --> 01:25:26.670 Teilstring, den ich aufgebaut habe, der hat genauso viele 0 wie 1. 01:25:28.430 --> 01:25:31.030 Und mit s nochmal was Neues anfangen. 01:25:31.850 --> 01:25:37.050 Oder ich füge noch eine 1 an, jetzt habe ich schon 2 0 im Rückstand, 01:25:37.410 --> 01:25:38.850 also habe ich a a. 01:25:41.570 --> 01:25:43.190 Und das gleiche analog mit b. 01:25:43.610 --> 01:25:47.050 b heißt, es fehlt mir eine 1, also ich kann einfach ein b durch eine 1 01:25:47.050 --> 01:25:51.070 ersetzen, oder durch eine 1 und ein neues Start, oder durch eine 0 und 01:25:51.070 --> 01:25:52.130 jetzt fehlen mir schon 2 1. 01:25:53.550 --> 01:25:55.990 Und jetzt kann man zeigen, dass das das Gewünschte tut. 01:25:56.090 --> 01:25:59.110 Das sind alle Regeln, die wir brauchen und über die Reduktion, über 01:25:59.110 --> 01:26:04.210 die Länge der erzeugten Wörter kann man sehen, dass zu jedem Zeitpunkt 01:26:04.210 --> 01:26:10.050 ist die Anzahl der Nullen plus die Anzahl der versprochenen Nullen, 01:26:10.410 --> 01:26:14.850 nämlich die a's, das gleiche ist wie die Anzahl der Einsen plus die 01:26:14.850 --> 01:26:17.810 Anzahl der versprochenen Einsen, nämlich die b's. 01:26:20.810 --> 01:26:25.830 Und dann sehen Sie, dass das auf beiden Seiten immer für jede Regel 01:26:25.830 --> 01:26:27.750 erfüllt ist und dann folgt das. 01:26:30.950 --> 01:26:36.150 Gut, das war das letzte Beispiel zu kontextfreien Grammatiken. 01:26:36.270 --> 01:26:38.730 Lassen Sie mich noch mal ganz kurz wiederholen, was wir heute gesehen 01:26:38.730 --> 01:26:39.930 haben, weil es wirklich eine Menge war. 01:26:39.990 --> 01:26:41.750 Wir haben heute Grammatiken kennengelernt. 01:26:42.750 --> 01:26:49.210 Grammatiken sind Regelwerke, wie Wörter aufgebaut werden entlang von 01:26:49.210 --> 01:26:51.010 Produktionen, von Ableitungsregeln. 01:26:51.590 --> 01:26:57.010 Beginnend mit dem sozusagen leeren Wort, nur dem Startsymbol, können 01:26:57.010 --> 01:27:01.910 wir immer ersetzen Teilwörter in dem schon kreierten Zwischenprodukt, 01:27:02.070 --> 01:27:04.610 kann man ein Teilwort, was eine linke Seite ist, ersetzen durch die 01:27:04.610 --> 01:27:06.150 entsprechende rechte Seite einer Regel. 01:27:07.250 --> 01:27:08.850 Das erzeugt uns Sprachen. 01:27:10.430 --> 01:27:13.450 Das sind alle Wörter, die erzeugt werden können, die keine 01:27:13.450 --> 01:27:15.910 Hilfssymbole mehr da drin haben, keine Variablen. 01:27:17.150 --> 01:27:18.930 Im Allgemeinen ist das sehr mächtig. 01:27:18.990 --> 01:27:22.230 Wir können da sehr mächtige Sprachen mit kreieren. 01:27:22.730 --> 01:27:27.870 Alle semi-entscheidbaren Sprachen können so erzeugt werden durch 01:27:27.870 --> 01:27:29.810 allgemeine Grammatiken Typ 0. 01:27:30.390 --> 01:27:31.550 Dann haben wir es eingeschränkt. 01:27:32.290 --> 01:27:35.750 Typ 3 Grammatiken hatten sehr eingeschränkte Regeln. 01:27:36.170 --> 01:27:38.270 Das waren genau die regulären Sprachen. 01:27:38.390 --> 01:27:39.910 Das war vielleicht zu eingeschränkt. 01:27:40.230 --> 01:27:42.630 Dann sind wir wieder nach oben gegangen und haben gesagt Typ 1 01:27:42.630 --> 01:27:46.550 Grammatiken, da war die Einschränkung relativ marginal und haben 01:27:46.550 --> 01:27:52.110 gesehen, das sind die N-Tape-N Sprachen, nicht deterministische Turing 01:27:52.110 --> 01:27:53.870 -Maschinen mit linearem Streicherplatz. 01:27:55.030 --> 01:27:59.390 Ist schon schön, ist zumindest entscheidbar, ist nicht semi 01:27:59.390 --> 01:28:02.230 -entscheidbar nur, sondern wenigstens entscheidbar und ist auch 01:28:02.230 --> 01:28:03.830 halbwegs gut entscheidbar. 01:28:03.910 --> 01:28:07.590 Der Platz ist nicht explodiert, aber über Laufzeiten können wir nichts 01:28:07.590 --> 01:28:07.910 sagen. 01:28:08.010 --> 01:28:10.610 Wir haben gesehen, dass es NP-vollständige Probleme gibt da drin. 01:28:11.390 --> 01:28:13.530 Also so richtig praktikabel ist es auch nicht. 01:28:14.210 --> 01:28:16.390 Und jetzt das Letzte, was wir uns angucken wollen und was auch 01:28:16.390 --> 01:28:19.810 wirklich der Fokus sein wird, sind die Typ 1 Sprachen. 01:28:20.290 --> 01:28:22.710 Die sind mächtiger als die regulären Sprachen. 01:28:23.110 --> 01:28:26.050 Wir haben ein paar nicht reguläre Sprachen gesehen. 01:28:26.590 --> 01:28:31.070 Die gehen, Palindrome, 0 hoch N, 1 hoch N, diese Sprache, die waren 01:28:31.070 --> 01:28:31.970 alle nicht regulär. 01:28:33.030 --> 01:28:36.950 Die können wir in Typ 1 machen und wir werden auch sehen, dass jede 01:28:36.950 --> 01:28:39.970 Typ 1 Sprache effizient entschieden werden kann. 01:28:40.490 --> 01:28:44.250 Wir werden polynomiale Algorithmen kennenlernen, die Typ 1 Sprachen, 01:28:44.370 --> 01:28:45.670 kontextfreie Sprachen erkennen. 01:28:46.690 --> 01:28:50.790 Gut, das wird uns eine ganze Weile in Beschlag nehmen, mindestens den 01:28:50.790 --> 01:28:51.710 ganzen Januar. 01:28:52.230 --> 01:28:54.490 Jetzt kommen Sie erstmal gut ins neue Jahr und frohe Weihnachten.