Berechenbarkeit #47 - Das Wortproblem für Typ-1-Sprachen ist entscheidbar
NLogSpace
https://www.youtube.com/watch?v=5dTDTApDjl4

Transkript (automatisch erstellt)

0:00 herzlich willkommen zu diesem video wir wollen jetzt sehen dass das board problem für typ 1 sprachen entscheidbar ist also wir hatten da zwei verschiedene
0:08 modelle gesehen die uns die typ einsprachen definieren einmal die monotonen grammatiken und einmal die lineare beschränkten automaten wir
0:16 hatten gesehen die beschreibung genau die gleiche sprach klasse erwirken die ineinander übersetzen und jetzt wollen wir uns
0:22 überlegen wenn man eine zb monotonen grammatik bekommt und ein wort dann kann man entscheiden ob dieses wort in dieser von dieser grammatik erzeugten sprache
0:33 liegt und genau so werden linear bestände automaten bekommen und ein wort dazu wir wollen wissen akzeptiere das wort ja dieses problem dass es auch
0:41 entscheid ba man steht ja im gegensatz zum wort problem von typ 0 grammatiken oder von polen maschinen von denen wir schon wissen dass sie unentschieden sind
0:49 also hier nochmal unser bisheriges bild voller unentschuldbare probleme da hatten wir das wort problem für thun maschinen und das wort problem für
0:58 type-0 grammatiken die wir gegenseitig aufeinander reduzieren können und jetzt in den letzten zwei videos haben wir gezeigt dass wir das wort
1:05 problem für el bas und das wort problem von monotonie grammatiken aufeinander reduzieren können und wir überlegen uns jetzt nur noch dass diese beiden
1:13 probleme tatsächlich entscheid ba sind und weil wir sie aufeinander schon reduziert haben ja macht euch nochmal klar diese beiden
1:20 übersetzungen die wir gemacht haben sind quasi reduktionen auch gewesen zwischen diesen beiden probleme mir ja deswegen reicht es jetzt von einem dieser beiden
1:29 probleme zu zeigen dass es entscheid bar ist dann folgt auch daraus dass das andere entscheider ist wir hatten ja schon eine ganze menge wort probleme
1:37 kennen gelernt daher hier nochmal eine übersicht es geht jetzt um diese beiden wort probleme also gegeben eine monotone grammatik und wort frage generiert diese
1:48 grammatik dieses wort und auch das wort problem gegeben eine lpa unten wort akzeptiert dieser eba dieses wort unsere ursprüngliche motivation für diese typ
1:59 einsprachen kam er auch daher dass das wort problem für touren maschinen unentschuldbar war und wir uns gedacht okay woran kann das liegen ja da gibt es
2:06 so eine das kann so eine sehr lange berechnung geben um für ein relativ kurzes wort herauszufinden ob es in der sprache
2:14 liegt und das kann jetzt nicht mehr passieren und wir wollen jetzt sehen dass wir das für entscheid barkeit ausnutzen können
2:20 also machen wir mal das wort problem für el bas hereingabe ist jetzt ein lpa und wort ja hier mal als beispiel wie so eine eingabe aussehen könnte wie könnten
2:31 wir jetzt herausfinden ob dieses wort hier von diesem lpa akzeptiert wird die erste idee wäre jetzt vielleicht ok lassen wir diesen elfer auf diesem wort
2:41 einfach mal laufen aber achtung lpa es waren nicht deterministisch ja wir können hier zum beispiel hier in krone sind und wer lesen können wir diesen
2:51 übergang machen können auch wenn wir sind und belesen diesen übergang machen ja das heißt eine nicht deterministisch tutoren maschine
2:58 wir können nicht einfach sagen wir lassen die mal so loslaufen es gibt viele verschiedene möglichkeiten aber wir können uns ja trotzdem mal die
3:06 stadt konfiguration für dieses wort angucken das wort steht hier auf dem band wir stehen auf dem ersten symbol und sind im zustand kohl 0
3:13 und dann könnte man sich alle möglichen folge konfigurationen angucken also wir könnten in kundus die sbb durch neue ersetzen und schritt nach rechts
3:21 gehen und in q1 landen das wäre dann diese konfiguration wir könnten auch das bmw lassen und nach rechts gehen und noch gut 2
3:29 dann wären wir in dieser konfiguration hier dann können wir das durch solche pfeile symbolisieren dass wir von dieser in dieser konfiguration gehen können
3:37 und ja von diesem konfigurationen könnte man weitermachen von hier aus kann man vielleicht noch weiter gehen und von hier aus kann man weiter gehen ja man
3:44 könnte sich diesen gesamten grafen von allen konfigurationen vorstellen man kann tatsächlich diese frage ob so ein wort von einem l b h reduziert wird
3:54 die kann man jetzt reduzieren auf das erreichbarkeit problem in grafenau wir fragen uns ja nur ist es möglich von dieser stadt konfiguration in diesem
4:03 konfigurations grafen der hier entsteht eine akzeptierende konfiguration zu erreichen und ein ganz wichtiger punkt ist dabei jetzt dass dieser graf nur
4:13 endlich groß wird denn unser eingabe wort hat ja irgend eine feste endliche länge und wir wissen eine konfiguration kann
4:21 nie mehr platz einnehmen als die länge des eingabe ortes wir können immer versuchen eine gute abschätzung dafür zu finden für die anzahl der möglichen
4:30 konfigurationen die wir erreichen können also wer ist ja dass eingabe wort wir nennen mal cudi zustands menge von unserem lpa der hier hat sechs zustände
4:40 und wenn dann mal gamma das arbeits alphabet also alle symbole die jemals auf dem band vorkommen können jetzt machen wir eine abschätzung für
4:49 die anzahl der knoten in diesem grafen also für die anzahl der konfiguration die dieser lpa jemals erreichen könnte und zwar steht ja in jedem feld immer
4:59 ein symbol aus dem arbeits alphabet also hier haben wir größe von gamma viele möglichkeiten und hier haben wir größe von gamma viele möglichkeiten und so
5:09 weiter wie oft haben wir so viele möglichkeiten länge des wortes oft da haben wir also größe von gamma hoch länge von w
5:18 viele möglichkeiten für die beschriftung des arbeits bandes dann haben wir für die position des lese kopfes länge von je +2 viele möglichkeiten länge von weh
5:30 aber der lesekopf kann auch mal auf dem links oder auf dem rechts begrenzt erstehen deswegen +2 viele ja und wenn wir viel
5:38 verschiedenen zuständen können wir seien in größe von q vielen ja die anzahl der möglichen konfigurationen den indie dieser eba auf dieser eingabe jemals
5:49 gelangen kann ist höchstens diese zahl hier und das ist eine feste endliche zahl die hängt nur von der eingabe ab in der eingabe stehen all diese sachen drin
6:00 der eba ist teil der eingabe das wort ist teil der eingabe das heißt diese zahlen könnte man ganz konkret aus der eingabe heraus berechnen
6:09 man könnte ganz konkret diese zahl hier ausrechnen ja und hauptsache dass es eine endliche zahl denn dann wissen wir dass dieser graf hier nur endlich groß
6:19 wird anders als bei touring maschinen das der fall wäre also ganz allgemeinen ton maschinen die theoretisch in unendlich viele verschiedene
6:28 konfigurationen gelangen könnten da gibt sich dann also ein solcher graf jeder knoten hier ist eine konfiguration jede kante bedeutet ich
6:38 kann von einer konfiguration in eine andere konfiguration gehen wir haben eine stadt konfiguration wir haben vielleicht verschiedene
6:46 akzeptierende konfiguration und die frage ist dann nur noch kann man in diesem grafen hier von einer stadt konfiguration zu einer akzeptierenden
6:56 konfiguration kommen das ist also jetzt die frage und damit haben wir das problem quasi reduziert auf erreichbarkeit in graphen
7:04 und erreichbarkeit in graphen das ist vielleicht etwas klarer dass dieses problem entscheidbar ist ja gegeben ein graf stadt kloten und auch mehrere
7:14 entknoten meinetwegen gibt es einen pfad von einem starken zu einem der entknoten das ist entscheid war gibt so verschiedene methoden man kann zum
7:24 beispiel einfach mal nach und nach alle knoten markieren die erreichbar sind ja immer man fängt mit der stadt konfiguration auch an und dann alle die
7:33 davon in einem schritt erreichbar sind nimmt man mit dazu und alle die davon erreichbar sind nimmt man auch mit dazu und so macht man immer weiter
7:44 und am ende können eigentlich nur zwei verschiedene sachen passieren entweder trifft man irgendwann auf einer akzeptierende konfiguration dann kann
7:52 man anhalten und sagen ja das wort wird akzeptiert bzw ja es gibt einen pfad vom staat zu einer akzeptierenden konfiguration oder es ist
8:03 irgendwann der fall dass man keine akzeptierende konfirmation gefunden hat und auch keinen neuen knoten mehr erreichen kann dann ist man auch fertig
8:13 und sagte nein das wort wird nicht akzeptiert und es gibt keinen pfad von einer stadt zu einer akzeptierenden konfiguration ja und das zeigt dass das
8:21 wort problem für lbs entscheid ba ist noch ein ganz wichtig ist dabei noch mal dass dieses verfahren wirklich nur endlich lange dauert das ist ja genau
8:30 die bedingungen für entscheid mag ein verfahren das für jede eingabe nach etlicher zeit die richtige antwort liefert und eine ganz wichtige rolle hat
8:40 dabei eben gespielt dass hier die anzahl der konfiguration auch nur endlich ist ja denn so können wir in endlicher zeit diesen grafen komplett hinschreiben wir
8:49 können diesen erreichbarkeit algorithmus für graphen zb darauf ausführen und das dauert alles nur endlich lange während es bei einer touring maschine einer
8:59 ganze unbeschränkten tholen maschine potenziell unendlich viele konfigurationen gibt und das ist so ein intuitiver grund warum man sagen kann
9:07 bei touring maschinen ist das wort problem nicht entscheidend war ja das ist unentschuldbar ok ich hoffe die idee ist klar geworden
9:14 warum diese beiden probleme entscheid bar sind und im nächsten video geht es dann wieder weiter mit noch mehr unentschuldbaren problemen