YT YouTube2Text

YouTube2Text → Transcripts → Automaten für Typ-1-Sprachen

Automaten für Typ-1-Sprachen — Transcript

by Prof. Markus · 4,567 words · 763 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00so wir wollen über sprachen vom typ 1
0:03sprechen kontextsensitive grammatiken
0:05sind die richtigen grammatiken um diese
0:08art von sprachen zu definieren wir
0:10wissen kontextsensitiv heißt einfach die
0:12grammatik ersetzt immer nur teile des
0:16wortes durch längere teil oder teile die
0:19mindestens genauso lang sind
0:20das ist die einzige einschränkung die
0:23wir fordern
0:25und wir haben für diese art von
0:26grammatiken bisher noch kein geeignetes
0:28berechnungsmodell wir haben für typ 2
0:30grammatiken die keller automaten für
0:32type-0 grammatiken die touring maschinen
0:34aber was ist dazwischen was sind die
0:37richtigen automaten für typ 1 sprachen
0:40das wollen wir uns jetzt anschauen und
0:43in diesem kurzen video klären wir kommen
0:45zurück mein name ist marcus krietsch
0:47dies sind die videos zum thema formale
0:49sprachen und automaten an der tu dresden
0:56ich hatte gerade gesagt irgendwie müssen
0:59wir zwischen keller automat der
1:02öffentlich zu schwach sind ist und
1:04touring maschinen die offensichtlich zu
1:06stark sind einen mittelweg finden ja der
1:08typ 1 liegt im prinzip dazwischen mit
1:12touring maschinen können wir natürlich
1:13die einsprachen erkennen und zwar aller
1:16denn jeder typ 1 sprache ist auch eine
1:18typ 0 sprache
1:19aber sie sind nicht weg sagt sie können
1:21doch viel mehr und mit keller automaten
1:23können wir viele typ einsprachen nicht
1:25erkennen nur die speziellen die auch vom
1:29typ 2 ist das heißt wir brauchen etwas
1:31in der mitte und die lösung dafür ist es
1:34nicht etwa noch ein ganz neues automaten
1:37modell einzuführen sondern einfach die
1:39automaten die wir für typ 0 haben die
1:42touring maschinen in ihrer mächtigkeit
1:44einzuschränken und das tut man einfach
1:46in denen man den arbeitsspeicher der
1:49touring maschine beschränkt das ergebnis
1:53ist das was man als linear beschränkte
1:56touring maschinen oder auch linear bande
1:59tomaten bezeichnet eine
2:03nicht deterministisch maschine die den
2:05lese schreib kopf nicht über das letzte
2:07eingabe zeichen hinaus bewegen kann
2:10versucht sie das bleibt der kopf statt
2:12dessen an der letzten bahn stelle stehen
2:14das heißt in diesem fall haben wir ein
2:17verhalten das wir bisher nur von vom
2:20linken rand des bandes kennen auch am
2:22rechten es ist nicht möglich
2:24zusätzlichen speicher zu erzieherin
2:26alles was die touring maschine berechnen
2:28will muss sie in den verfügbaren
2:30speicher quetschen dh so ein automat
2:35sein mba kann nur die lineare menge an
2:38speicher nutzen die durch die eingabe
2:41bereits belegt wird warum ist das linear
2:43naja wenn die eingabe eine bestimmte
2:45länge hat sagen wir en dann haben wir
2:48auch in zellen im speicher zur verfügung
2:53wenn sie also die den verfügbaren
2:56speicher mit der verfügbaren eingaben
2:57mit der eingabe länge vergleichen dann
2:59sehen sie eine lineare funktion und das
3:01ist hier gemeint mit linie
3:03ok es stellt sich auch heraus dass man
3:09durchaus auch das schaffen kann doppelt
3:11so viel speicher zum beispiel zu
3:12verwenden indem man nämlich einfach an
3:14jedes an jeden ort des bandes zwei
3:17zeichen codiert ja wir haben ja so eine
3:20idee dass man mehrere zeichen an einem
3:22platz kotieren kann schon beim letzten
3:24mal gesehen als mit die typ wir sprachen
3:26mit touring maschinen erkannt oder mit
3:30ihren maschinen zusammen gebracht haben
3:31und gezeigt haben wie eine grammatik
3:33einer tod- maschine simuliert daten wir
3:34ja auch variablen benutzt in der
3:36grammatik als der nicht terminal-
3:37symbole die eigentlich drei dinge auf
3:39einmal codieren und genau so könnten
3:41auch band symbole einer tormaschine mehr
3:43als eine information enthalten
3:46doppelt so viele bands symbole dreimal
3:49so viele bands symbole viermal so viele
3:50bands symbole 1000 mal so viele bands
3:52symbole aber in jedem fall ist der
3:55speicher den wir dadurch insgesamt
3:56gewinnen immer noch linear beschränkt ja
3:59also die tormaschine kann nur eine menge
4:04hand symbol speichern die proportional
4:06wächst mit der länge des
4:08eingabe wortes deshalb also den ja
4:10beschritt beispiel
4:13wir hatten schon einmal vor einigen
4:16videos in der vorlesung 18
4:18die sprache aig hoch mit hilfe einer
4:22tormaschine erkannt zumindest hatten wir
4:24das skizziert wie man das macht ich
4:27hatte gesagt ja die idee ist einfach wir
4:28ersetzen jedes einzelne a mit einer
4:30markierten version und jedes mal wenn
4:33wir das blut ersetzen wir auch genau 1 b
4:34und ein c wobei wir abbrechen und wieder
4:41und die eingabe ablehnen falls wir kein
4:45geeignetes boc finden für ein so lange
4:49das gut geht und dass man bis es in
4:51gleichen mengen auftauchen machen wir
4:53weiter bis alles ersetzt sind
4:55und nachdem das geschehen ist prüfen wir
4:58noch ob jetzt das wort tatsächlich nur
5:01aus einer kette von markierten aus
5:03gefolgt von markierten bs von gefolgt
5:05von markierten cs besteht und falls das
5:07so ist dann ist die akzeptanz hier
5:11gegeben wenn wir uns diesen algorithmus
5:14ansehen dann sehen wir leicht dass der
5:16tatsächlich auskommt ohne irgendwelchen
5:18zusätzlichen speicher zu reduzieren wir
5:20können diesen dieses verfahren also nur
5:23auf der gegebenen eingabe anwenden wir
5:26setzen zeichen aber wir müssen keine
5:29zusätzlichen bereiche im speicher dafür
5:33einplanen ja ok gut also dass heißt so
5:39etwas geht wir haben sogar schon
5:40beispiele dafür gesehen und natürlich
5:41ist das hier auch eine kontextsensitive
5:43sprache das heißt das passt zusammen
5:49wir wollen jetzt noch erkennen dass das
5:53tatsächlich das gleiche ist also ich
5:55möchte dass wieder beweisen so wie ich
5:56auch bei typ nur bewiesen habe dass die
5:58touring maschinen genau das richtige
5:59automaten modell sind möchte ich jetzt
6:01hier bei typ 1 zeigen dass die ligen
6:03jahr beschränkten automaten das richtige
6:06automaten modell sind dabei vereinfachen
6:10wir es uns ein ganz kleines bisschen wir
6:12sie erinnern sich bei den typ
6:14einsprachen schon für die
6:17kontextsensitiven grammatiken hatten wir
6:18eine
6:20besonderheit mit dem leeren bot das
6:25lehrer bord kann nicht durch eine
6:28normale typ 1 kammer durch eine ganz
6:31einfache kontextsensitive grammatik
6:33erzeugt werden denn da müsste man das
6:34staatssymbol zumindest löschen können
6:36und das ist ja eine verkürzung durch
6:38eine produktions regel eigentlich ist
6:41das nicht erlaubt dafür hatten wir
6:42sonderfälle wir haben apps i lon freie
6:44kammern ticken betrachtet und so weiter
6:46und so fort das war ein bisschen
6:47aufwendig oder ein bisschen eher ein
6:49kleiner umweg auf dem weg dieser
6:51beschreibung hier würde das auch wieder
6:55zu sonderfällen führen weil natürlich in
6:58dem moment wo ich das leere wort als
7:01eingabe betrachtet dann hätte die
7:05tormaschine 0 speicherzellen zur
7:07verfügung nach meiner definition dich
7:08gerade gegeben hat und das geht
7:10natürlich nicht der lese schreib kopf
7:11muss irgendwo stehen also mindestens
7:12eine speicherzelle müssen wir zu lassen
7:14und insofern ist dieser sonderfall durch
7:18das was ich gesagt habe nicht abgedeckt
7:19man kann das leicht beheben
7:21aber das ist nicht sehr interessant wir
7:23sparen uns die umwege ok also die
7:26einsprachen ohne die sprachen die das
7:28leere worte hat und für diese fälle kann
7:31man leicht sehen zumindest wir können
7:33das mit dem was wir bereits wissen dass
7:35typ 1 grammatiken genau diejenigen
7:37sprachen erzeugen die von einem mba
7:40erkannt werden kann
7:41wieso können wir das leicht sehen naja
7:44weil die assindia touring maschinen und
7:46im prinzip wissen wir schon wie man die
7:49beziehung zwischen touring maschinen und
7:52grammatiken herstellen kann das haben
7:54wir beim letzten mal für typ 0 sprachen
7:56schon gesehen und diesmal können wir
7:58eigentlich fast das gleiche tun das was
8:00wir damals getan haben ist im prinzip
8:02schon die lösung für das was wir gleich
8:04vorher beweis
8:07wir können wieder fast die gleiche
8:09konstruktion anwenden erster schritt wir
8:11wollen zeigen dass eine typ 1 grammatik
8:13mit einem mba gelöst werden kann
8:16und dazu müssen wir uns einfach nur
8:18erinnern wie wir das blatt ohne
8:19maschinen allgemein gemacht haben wir
8:21hatten einfach gesagt
8:22die eingabe die die touring maschine
8:24erhält ist ja das was die grammatik am
8:26ende zeigen soll und wir wenden dann
8:28grammatikregeln rückwärts an das heißt
8:30wir versuchen die dinge die dort auf dem
8:34eingabe band vorhanden sind zu erklären
8:36durch die anwendung von grammatikregeln
8:39und hoffen dass wir durch diese
8:40rückwärts anwendung über viele
8:43zwischenschritte vielleicht irgendwann
8:44zum staatssymbol gelang und dann wissen
8:46wir das wort hätte erzeugt werden können
8:48durch die grammatik wir haben hier
8:50wichtig wichtig herr minister touring
8:52maschinen das heißt wir können wieder
8:53frei raten wie mit welchem auf welchen
8:58weg wir das schaffen wollen das muss
9:00also nicht zielgerichtet sein es reicht
9:02wenn wir irgendwelche regeln rückwärts
9:04an wänden auf irgendwelche teil wörter
9:05und hoffen dass wir dabei erfolg das
9:09gute an kontextsensitiven grammatiken
9:11ist jetzt dass wenn wir die regeln
9:13rückwärts anwenden natürlich das wort
9:15dabei immer kürzer wort oder höchstens
9:17so lange bleibt wie es vorher war
9:19weil ja die butter auf der rechten seite
9:22von produktions regeln bei typ 1
9:24grammatiken immer länger oder höchstens
9:26gleich lang sind wie die wörter auf der
9:28linken seite also wenn wir so rückwärts
9:30anwenden danach setzen wir ein langes
9:33wort durch ein tendenziell kürzeres das
9:36heißt dieser ersetzung kann immer in
9:37gleichem speichern
9:39ausgeführt werden hoffentlich wird das
9:41wird auch irgendwann mal echt kürzer
9:42dann brauchen wir sogar weniger speicher
9:44in jedem fall brauchen wir nicht mehr
9:45speicher man damit klar dass das machbar
9:49ist umgekehrt
9:52lpa zu typ 1 kam hat eben wie kann eine
9:55typ 1 grammatik eine touring maschinen
9:57mit linearen speicher simulieren auch
9:59das werden wir im prinzip ganz ähnlich
10:01machen wie beim letzten mal für typen da
10:04hatten wir schon mal eine grammatik für
10:05eine touring maschine und die können wir
10:07hier einfach wieder verwenden fast wir
10:11haben wir die grammatik ich hatte beim
10:12letzten war ja erwähnt die ist ganz
10:13einfach man kann die regeln auf einer
10:15folie darstellen hatte ich gar nicht
10:16gemacht aber hier sehen sie alle auf
10:19einer vorher das sind genau die regeln
10:20die wir verwendet hatten um eine
10:23tormaschine in einer typ 0 grammatik zu
10:25simulieren erst haben wir beliebige
10:28eingabe wörter generiert und hinter
10:32denen noch beliebig viele zusätzliche
10:36lehrstellen erzeugt das waren hier diese
10:37blanks das wort dazu da dass wir
10:40zusätzlichen arbeitsspeicher bekommen
10:42dann hatten wir drei formen von regeln
10:45die die übersetzte die die ersetzung in
10:47der tormaschine und die schritte der
10:49tormaschine kodieren indem wir immer ab
10:52den bereich in dem sich der lese schreib
10:54kopf gerade befindet entsprechend
10:56umschreiben so dass es genau einem
10:58schritt entspricht
10:59und dann hatten wir noch regeln zum
11:01abschluss bei denen wir dann immer wenn
11:04ein zustand ein endzustand ist und es
11:07keine weiteren bewegungsmöglichkeiten
11:09gibt mit dieser kombination von
11:10brandzeichen ickx und endzustand co
11:13dann haben wir immer einfach diese
11:17gepackten dreistelligen nicht terminal-
11:21symbole durch ihren obersten bestandteil
11:23ersetzt und wenn das einmal passiert war
11:26haben wir alles der reihe nach ersetzt
11:28links und rechts von den schönen
11:30ersetzten stellen wurden auch weitere
11:31ansetzungen vorgenommen so lange bis gar
11:33nichts mehr auf dem band steht außer
11:35eingabe symbole und vielleicht längst
11:38die durch diesen zusätzlichen speicher
11:40entstanden sind und die haben wir
11:41einfach gelöscht so und genau so
11:44funktioniert es auch hier wieder die
11:46einzige unterscheidung ist das natürlich
11:49für typ 1 nicht alle dieser regeln
11:51okay sind die erste und wir sehen fast
11:55alle legen hier führen zu etwas längeren
11:56oder gleich lange
11:58aber es gibt zwei wege die zu einer
12:02verkürzung führen das ist diese regel
12:04die b durch y r setzt und diese regel
12:06die das gelenk durch apps i lon ersetzt
12:09und beide regeln sind problematisch aber
12:14beiträgen brauchen wir natürlich nur
12:15deshalb weil wir zusätzlichen speicher
12:18eingeführt haben die erste regel könnte
12:21man auch durch umformulierung der
12:22grammatik ohnehin loswerden ja also
12:25anstatt hier ein y zu erzeugen wenn wir
12:29genügend längst haben könnten wie auch
12:30noch ein lenkt mehr erzeugen und es
12:33dabei belasten kein bäder anhängen das
12:36würde auch dazu führen dass wir das
12:39ganze die generierung beenden und das
12:41wäre nicht schlimm wenn wir ein gelenk
12:42mehr oder weniger erzeugen dann im
12:44zweifel geben wir da tun maschinen noch
12:46eine stelle mehr speicher die sie nicht
12:47nutzt das wäre nicht schlimm
12:48also das heißt dieses exelon könnten wir
12:51tatsächlich auch mit veränderung der
12:52grammatik loswerden dieses y hier unten
12:55aber nicht denn das ist das y was die
12:59länge des speichers die vergrößert
13:02werden musste um die berechnung der
13:04tormaschine durchzuführen wieder
13:05künstlich verkürzt damit nur die eingabe
13:07übrig bleibt
13:09und das ist genau das was ja bei einer
13:13typ einsprachen beim eba nicht wo kommen
13:16soll
13:16ja also das ist gleich zusehen dass wir
13:20das nicht wohl wenn wir jetzt aber ein
13:22mba haben ja keinen zusätzlichen
13:23speicher braucht dann können wir alles
13:25was hier mit b zu tun hat zur erzeugung
13:27von links einfach weglassen und damit
13:30müssen wir sie auch am ende nicht
13:31löschen
13:31das heißt die grammatik vereinfacht sich
13:34wie hier dargestellt
13:36ich habe hier alles ohne die rbs
13:40geschrieben dadurch müssen ein paar
13:42dinge hier zusammengeführt werden aber
13:44das ist nicht weiter schlimm ich kann
13:46noch mal hin und her gehen da sehen sie
13:47was hier passiert also wir hatten hier
13:49die möglichkeit ein zeichen zu erzeugen
13:52oder auch direkt zu den blues über zu
13:55gehen das ist im prinzip die möglichkeit
13:57dass das leere wort am anfang steht
13:59diese möglichkeit fällt dann weg
14:01und auch wenn wir fertig waren mit der
14:04generierung des eingabe wortes sind wir
14:06immer in dieser phase übergegangen mit
14:08der man noch
14:09oder mehr blanks erzeugt das fällt jetzt
14:11flach dafür haben wir die möglichkeit
14:14direkt nach der generierung eines
14:17einzigen eingabe zeichens die
14:19generierung zu beenden dann haben wir
14:21nur auf dem eingabe bahn tritt nur einen
14:23zustand wenn du den staat zu standort
14:25stehen oder wenn wir uns anschließend
14:27mehrere dinge zu generieren dann können
14:29wir entweder das fortsetzen indem wir
14:32hier wieder an hängen oder an
14:34irgendeiner stelle aufhören
14:35das ist die generierung alles andere
14:37bleibt gleich bis auf die letzte zeile
14:39dann müssen wir keine y mehr keine
14:41blanks mehr löschen denn es gibt hier
14:43keine links hinter generierung also
14:46werden auch keiner auftauchen
14:48nach dieser ein kollabieren der
14:51dreistellige symbole in ihre obere spur
14:55okay das ist schon alles damit haben wir
14:58den beweis erbracht
15:00die grammatik funktioniert wie zuvor und
15:02für apps benötigen wir den zusätzlichen
15:04speicher nicht damit ist der beweis
15:07schon fertig okay das zeigt also dass
15:12typ einsprachen und linear beschränkte
15:15touring maschinen genau die gleichen
15:18sprachen akzeptieren bzw
15:21generieren müsste man sagen bei
15:23grammatiken was noch bleibt ist die
15:26frage wie es denn aussieht mit dem wort
15:29problem für typ 1 wir wissen für typ 0
15:32ist das wort problem sehr schwer
15:33es ist ein entscheid bord tatsächlich
15:36also man kann es zwar touring erkennen
15:38in der regel also immer aber man kann es
15:41nicht immer entscheiden also das
15:43bedeutet insbesondere für wörter die
15:45nicht der sprache angehören kann man
15:47nicht nach endlich vielen schritten der
15:50tui maschine sicher sein dass sie
15:52tatsächlich nicht akzeptiert werden das
15:54könnte immer weitergehen nur für die
15:55wird er die akzeptiert werden wird die
15:57touring maschine garantiert akzeptieren
15:59und also auch halten wie es bei typ 1
16:03neuer typ 1 hat eine natürliche grenze
16:05die natürliche grenze ist die größe des
16:08speichers kann typ 1 nicht trotzdem in
16:14endlosschleifen laufen
16:16klar kann
16:18natürlich ja also auch mit endlich im
16:20speicher kann eine tui maschine in
16:22endlosschleifen geraten sie muss ja
16:24eigentlich überhaupt nichts tun sie muss
16:26auch den speichern nicht vergrößern oder
16:27irgendwie verändern
16:28sie kann auch einfach so übergänge
16:31ausführen die keinen unterschied machen
16:34sie kann auch wenn sie mag den speicher
16:37dabei verändern immer vor und zurück
16:39laufen und etwas umschreiben und wieder
16:40von vorne
16:41all das ist möglich und in vielen dieser
16:43fälle kann die tormaschine tatsächlich
16:46ewig laufen
16:47das heißt auch hier ist nicht
16:49sichergestellt dass jeder mba
16:51irgendwann hält können wir trotzdem die
16:56das wort problem für typ 1 entscheiden
16:58gibt es trotzdem eine möglichkeit um
17:00dieses halte problem von lbs
17:02herumzukommen können wir wissen dass der
17:04lwl nicht hält denn das ist es ja nicht
17:07wahr wenn wir wüssten dass der lpa
17:09garantiert nicht anhält dann wäre es
17:13nicht schlimm wenn er eine
17:14endlosschleife ausführen würde wir
17:16könnten das dann rechtzeitig erkennen
17:18und würden einfach dann die ausgabe auf
17:22einsetzen also das wort würde dann nicht
17:25akzeptiert werden
17:26das problem bei typ 0 ist eben nur das
17:28was alte problem und entscheidbar ist
17:30und deshalb wissen wir nicht ob es
17:31vielleicht noch zum halten kommen wird
17:33oder ob das tatsächlich unendlich läuft
17:36ok bei typ 1 geht das natürlich
17:38irgendwie denn typ 1 hat ja nun endlich
17:41viel speicher das heißt typ 1 hat auch
17:44nur endlich viele konfiguration auf
17:48einem beschränkten speicher gibt es nur
17:49beschränkt wieder konfiguration ihr
17:52könnt sogar genau ausrechnen wie viele
17:53das sind wenn ich erzählen im speicher
17:55habe dann kann ich größe von gamma hoch
17:59n wieder verschiedene speicher inhalte
18:02darstellen kann hat das band alphabet
18:05ich kann in jeder dieser speicher
18:09bewegungen an allen positionen den lese
18:11schreib kopf haben das heißt ich habe
18:13nochmal einmal mehr möglichkeiten und
18:15ich kann mich dabei in verschiedenen
18:17zuständen befinden also im kardinal i
18:19tät von vielen das heißt die gesamtzahl
18:22der möglichen konfigurationen ist diese
18:25also ziemlich groß ja exponentiell hier
18:29bezüglich n
18:29aber natürlich endlich das heißt es gibt
18:34nicht so viele verschiedene
18:35konfigurationen in den titeln maschine
18:38sein kann und natürlich wenn die
18:40tormaschine in einer konfiguration ist
18:43dann bestimmt das völlig was sie und da
18:45aus noch tun kann
18:46können wir also einfach sagen wenn die
18:49tormaschine zweimal an der gleichen
18:51konfiguration vorbei kommt also eine
18:53konfiguration mehrmals besucht dann
18:55wissen wir ha
18:56sie ist in einer schleife die wird jetzt
18:57immer weiter die gleichen konfiguration
18:59abarbeiten und immer wieder zu dem
19:02gleichen ort com ist das so ja also noch
19:08mal wenn sie eine tolle maschine sie
19:09haben eine iba sie würden den laufen
19:10lassen sie beobachten die konfiguration
19:12in die er dabei durchläuft und wenn eine
19:16konfiguration die schon mal aufgetaucht
19:17war noch einmal auftaucht dann brechen
19:20sie ab und sagen verwerfen ist das okay
19:28so halb ja nicht ganz warum die ich weiß
19:31nicht deterministische automaten sind
19:34nicht deterministisch touring maschinen
19:35das bedeutet natürlich können sie in dem
19:42fall schon relativ frei verwerfen sie
19:43müssen allerdings auch noch alle anderen
19:47möglichen abläufe betrachten und da gibt
19:51es vielleicht an einen da akzeptiert
19:53es könnte ihnen auch passieren dass der
19:56der zwei eine konfiguration doppelt
19:58besucht noch akzeptieren kann weil es ja
20:02möglich sein könnte dass auf dieser
20:03schleife bieter nicht deterministisch
20:05entscheidungen passieren und mit einer
20:06anderen entscheidung kann man vielleicht
20:08doch noch zur akzeptanz kommt ja das ist
20:10aber tatsächlich nicht schlimm wenn sie
20:11an der stelle verwerfen würde dann ist
20:14das durchaus gerechtfertigt denn die
20:16maschine hätte die richtige entscheidung
20:18um diesen diese schleife zu verlassen ja
20:21vielleicht schon eher treffen können
20:22also man muss der tunnel maschine nicht
20:24erlauben die selbe schleife tausend mal
20:26zu durchlaufen um am ende doch noch den
20:29richtigen ausgang zu finden sondern man
20:31kann erwarten dass die boeing maschine
20:33den ausgang gleich beim ersten mal
20:34findet und überhaupt keine schleifen
20:36benutzt auf ihrem weg zur akzeptanz wenn
20:39es denn überhaupt einen weg zur
20:40akzeptanz
20:41insofern wäre das ein mögliches
20:44verfahren mit dem man arbeiten kann
20:47wir haben noch ein bisschen was anderes
20:50hier vorm kleine abwandlungen davon ist
20:53vielleicht noch ein bisschen
20:53anschaulicher macht was hier passiert
20:55denn und bei der wir nicht einmal die
20:58tormaschine simulieren müssen
21:01die idee ist dass wir die konfiguration
21:05ja im prinzip im vorfeld kennen ja wir
21:07wissen ja wenn der impotenz zeichen lang
21:11ist welche möglichen konfigurationen es
21:13gibt und damit müssen wir die
21:15tormaschine gar nicht simulieren das ist
21:17schon da das bekannt was überhaupt
21:18eintreten kann man kann außerdem anhand
21:21der touring maschinen beschreibung
21:23natürlich entscheiden ob man von einer
21:25konfiguration in eine andere wechseln
21:26kann oder nicht
21:27ziemlich einfach dass die
21:29übergangsregionen die kann man also
21:30berechnen man kann das einfach ablesen
21:33ob es möglich ist von der einen
21:34konfiguration die andere zu kommen und
21:37das bedeutet wir können das gesamte
21:39verhalten einer touring maschine die so
21:42beschränkt ist also mit hilfe eines
21:46grafen darstellen einen grafen also eine
21:49art wie ein netzwerker eine
21:51mathematische struktur aus knoten und
21:56kanten hier in dem fall eingerichteter
21:58graf der also darstellt als in seinen
22:04knoten die möglichen konfigurationen
22:05oder den pfeilen die von einem knoten
22:07zum anderen gehen die möglichen
22:08übergänge
22:09das heißt es gibt immer dann einen fall
22:10in den graben wenn man von einer
22:13konfiguration zur anderen gelangen kann
22:16und das nennt man konfigurations graf
22:18dieser konfigurations kraft ist groß
22:20jahr exponentiell aufgrund der grund
22:22hohen anzahl an konfiguration aber er
22:24lässt sich berechnen das heißt sie
22:25könnten einfach für eine bestimmte
22:27eingabe gern länger sie jetzt kennen und
22:29für eine bestimmte konfiguration hat
22:31auch für eine bestimmte maschine
22:33beschreiben diesen grafen berechnen und
22:35er würde ihnen sozusagen eine landkarte
22:36all dessen liefern was die touring
22:38maschinen überhaupt im prinzip tun kann
22:42man kann das problem dann also auf
22:46diesen grafen beziehen und anders
22:48ausdrücken so wie hier beschrieben wort
22:51problem mit konfigurations grafen gibt
22:55es eine akzeptierende and konfiguration
22:58akzeptieren der and konfiguration eine
23:00und der mann nicht weiter laufen kann
23:03also in der die tormaschine hält eine
23:05sackgasse im graphen die in einem
23:07zustand sich befindet hinein akzeptieren
23:09das wäre eine akzeptieren und
23:11konfiguration wort problem gibt es eine
23:13solche akzeptieren und konfiguration die
23:16im konfigurations grafen von der stadt
23:18konfiguration aus erreichbar ist also zu
23:21der aus einer einfahrt durch diese
23:26pfeile gibt in der richtung der pfeile
23:28natürlich das entspricht ja dann einem
23:30lauf eine tui maschine
23:31und wenn so ein lauf möglich ist dann
23:34akzeptiere die tormaschine das heißt das
23:37wort problem ist eigentlich nur eine
23:38erreichbarkeit frage für den endlichen
23:40grafen und dort kann man lösen ja wir
23:42nicht grafen ihnen gebe und sie sollen
23:44prüfen ob man von einem knoten zu einem
23:46anderen gelangen kann oder zu
23:48irgendeinem anderen aus einer menge von
23:49anderen knoten dann können sie das mit
23:51einem programm tun und in dem fall wenn
23:55das der graf ist mit dem sie arbeiten
23:56dann lösen sie damit schon das wort
23:58problem dann wissen sie dann schon ob
23:59diese touring maschine akzeptieren würde
24:02oder eben nicht ohne dass ich sie in dem
24:05sinne ausgeführt haben daraus folgt das
24:09wort problem für typ 1 sprachen ist
24:11entscheid ba und der beweis ist einfach
24:13das was ich ihnen gerade gesagt habe
24:15erster schritt wir berechnen den grafen
24:17zweiter schritt wir prüfen ob die eine 1
24:20konfiguration erreichbar ist okay dass
24:23ein algorithmus und das ist schon mal um
24:26welten besser als das was wir bei type-0
24:27haben denn da ist es eben nicht
24:29entschuldbar
24:30aber es ist natürlich immer noch nicht
24:32besonders schnell ja es dauert
24:34exponentiell
24:35es braucht auch exponentiell viel
24:37speicher wenn wir das so machen wir
24:39könnten den grafen natürlich auch dort
24:44zum teil im speicher halten denn er
24:45lässt sich jederzeit wieder berechnen da
24:47besteht ja entsteht ja gesetzen wie er
24:50sich aus dem
24:51was wir schon wissen also es ist auch
24:53möglich den weg vielleicht in einer
24:56anderen art und weise versuchen aber es
24:58dauert sicherlich exponentiell lange um
25:01zu prüfen ob man von einem knoten zum
25:02anderen kommen kann weil einfach die
25:03partie so lange sich also das wird sich
25:05nicht vermeiden lassen
25:07das ist also komplexer ist also
25:11schwierig es kann kein sehr schneller
25:13algorithmus aber es stellt sich heraus
25:15nach allem was wir wissen ist das wort
25:18problem von typ 1 sprachen zum teil
25:20wirklich so schwer
25:22ja also dieser algorithmus bedeuten
25:24benötigt natürlich immer exponentiell
25:26viel zeit was kein gutes merkmal für
25:28einen algorithmus ist aber bis heute ist
25:31nicht bekannt ob es überhaupt
25:33irgendeinen algorithmus gibt der worst
25:35case im schlimmsten fall weniger als das
25:39benötigen würde
25:40natürlich kann man zumindest versuchen
25:42und das machen wir der informatiker in
25:44der regel wenn wir schwere probleme
25:45haben man kann zumindest versuchen ein
25:47algorithmus zu finden der in vielen
25:50wichtigen praktischen fällen viel
25:53weniger zeit benötigt der worst case
25:55lässt sich nicht verhindern aber man
25:58möchte natürlich nicht unbedingt ein
25:59algorithmus der immer so schlecht ist
26:01als wenn der worst case in allen fällen
26:02eintritt das ist ein großer unterschied
26:04ja ok aber wir wissen nicht ob wir
26:07wirklich besser sein können es gibt
26:09natürlich kontextsensitive sprachen auch
26:11solche die nicht kontext frei sind
26:14die diese komplexität nicht aufweisen
26:17yahoo theorie theorie das schaffen sie
26:20unter exponentiell vielen schritten das
26:22heißt mit dem algorithmus ich ihn
26:24genannt hatte mit der touring maschine
26:26wir ersetzen einfach die zeichen und da
26:28gehen wir ein bisschen hin und her aber
26:29das ist im prinzip ein
26:31beim prüfen des verfahrens aber es gibt
26:34eben auch fälle in denen man tatsächlich
26:36nicht unter exponentiell langen
26:39berechnungen bleibt und ich glaube
26:42solche wenn man vielleicht doch noch
26:43sehen in einem späteren video
26:46eine frage die man vielleicht am ende
26:48noch stellen kann ist ist typ 0 denn
26:51wirklich mächtiger als die b 19 im
26:53prinzip mit der letzten vorher und dem
26:55ergebnis dass typ 1 entscheiden
26:57das wird ein entscheidendes wort problem
26:59hat haben wir das auch schon beantwortet
27:00denn das muss also sein dass typ 0
27:04mächtiger ist denn dort scheint es gibt
27:06es offenbar sprachen für die das wort
27:07problem nicht entscheiden da ist und wir
27:10haben auch schon konkrete beispiele
27:11dafür gesehen zum beispiel das alte
27:13problem kann keine typ 1 sprache sein
27:16da ist nicht entschuldbar ist wenn es
27:18ein typ ein sprache wäre hätten wir ja
27:19mit dem algorithmus den wir gerade
27:20angegeben haben ein
27:22entscheidungsverfahren für das alte
27:23problem und das haben wir bewiesen kann
27:25es nicht geben
27:26das ist ein bisschen mit dem holzhammer
27:31ja also kein unentschuldbares problem
27:34ist vom typ 1 das stimmt es gibt aber
27:38auch viele andere viele entscheider
27:40probleme die nicht vom typ 1 sind und
27:43man kann es auch auf eine ähnliche art
27:45und weise durchaus zeigen einfach weil
27:49es probleme gibt die mit den
27:51eingeschränkten ressourcen eines lpa
27:54nicht lösbar sind
27:55also man findet probleme da informatik
27:58die zum beispiel nur mit doppelt
28:01exponentiell großem speicher gelöst
28:03werden können und das ist natürlich
28:05deutlich mehr als in jeder speicher und
28:07man kann auch beweisen dass es nicht
28:08möglich ist etwas was doppelt
28:11exponentiell viel speicher benötigt
28:14mediensprecher zu müssen das gilt schon
28:17für einfache exponentiellen speichern
28:18übrigens und so gibt es also doch eine
28:21ganze menge von schweren problemen von
28:23denen wir ganz sicher sind dass sie
28:25nicht auf b ausgelöst werden können es
28:27gibt aber auch schwere probleme bei
28:28denen wir zwar denken dass sie dort
28:29nicht gelöst werden können bei denen der
28:31beweis aber bisher aus steht ja also
28:33bestimmte probleme die exponentiell zeit
28:35noch lösbar sind
28:36aber von denen man nicht glaubt dass sie
28:38in linearen speichert lösbar sind
28:41existieren ebenfalls ja also die grenze
28:43ist ein bisschen unscharf aber es gibt
28:46auf jeden fall sehr viele entscheider
28:47probleme die auch schon jenseits von typ
28:491 liegen das ist vielleicht das was wir
28:52uns hier merken kann
28:52ok damit haben wir typ 1 behandelt viel
28:57mehr möchte ich dazu gar nicht sagen
28:59wir haben gelernt das lineare
29:01beschränkte tun maschinen das richtige
29:02automaten modell dafür sind und dass das
29:05wort problem wird diese sprachen
29:07zumindest noch entscheidbar ist aber
29:09doch um einiges komplizierter als die
29:11polygamie allen dort probleme die wir
29:13vorher bei dem typ zwei sprachen und das
29:16recht bei den regeln ansprachen
29:17angetroffen haben eine kleinigkeit wäre
29:20ich noch sagen zu sprachen nämlich ich
29:22werde noch kurz über abschluss
29:23eigenschaften von typ 0 und im eintreten
29:25dass man im nächsten video und dann
29:27haben wir fast alles über formale
29:29sprachen gesagt was ich in dieser
29:30videoreihe überhaupt sagen will muss und
29:34auf wiedersehen bis bald

About this transcript

This page contains the full transcript of Automaten für Typ-1-Sprachen by Prof. Markus, generated from the public captions YouTube serves with the video. The transcript has 4,567 words across 763 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.