Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Berechenbarkeit #47 - Das Wortproblem für Typ-1-Sprachen ist entscheidbar
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 63 Zeilen
- 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
- modelle gesehen die uns die typ einsprachen definieren einmal die monotonen grammatiken und einmal die lineare beschränkten automaten wir
- hatten gesehen die beschreibung genau die gleiche sprach klasse erwirken die ineinander übersetzen und jetzt wollen wir uns
- ü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
- 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
- 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
- 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
- type-0 grammatiken die wir gegenseitig aufeinander reduzieren können und jetzt in den letzten zwei videos haben wir gezeigt dass wir das wort
- 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
- probleme tatsächlich entscheid ba sind und weil wir sie aufeinander schon reduziert haben ja macht euch nochmal klar diese beiden
- übersetzungen die wir gemacht haben sind quasi reduktionen auch gewesen zwischen diesen beiden probleme mir ja deswegen reicht es jetzt von einem dieser beiden
- 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
- 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
- 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
- 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
- so eine das kann so eine sehr lange berechnung geben um für ein relativ kurzes wort herauszufinden ob es in der sprache
- liegt und das kann jetzt nicht mehr passieren und wir wollen jetzt sehen dass wir das für entscheid barkeit ausnutzen können
- 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
- 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
- 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
- übergang machen können auch wenn wir sind und belesen diesen übergang machen ja das heißt eine nicht deterministisch tutoren maschine
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- konfigurations grafen der hier entsteht eine akzeptierende konfiguration zu erreichen und ein ganz wichtiger punkt ist dabei jetzt dass dieser graf nur
- endlich groß wird denn unser eingabe wort hat ja irgend eine feste endliche länge und wir wissen eine konfiguration kann
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- aber der lesekopf kann auch mal auf dem links oder auf dem rechts begrenzt erstehen deswegen +2 viele ja und wenn wir viel
- 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
- 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
- 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
- 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ß
- wird anders als bei touring maschinen das der fall wäre also ganz allgemeinen ton maschinen die theoretisch in unendlich viele verschiedene
- konfigurationen gelangen könnten da gibt sich dann also ein solcher graf jeder knoten hier ist eine konfiguration jede kante bedeutet ich
- kann von einer konfiguration in eine andere konfiguration gehen wir haben eine stadt konfiguration wir haben vielleicht verschiedene
- akzeptierende konfiguration und die frage ist dann nur noch kann man in diesem grafen hier von einer stadt konfiguration zu einer akzeptierenden
- konfiguration kommen das ist also jetzt die frage und damit haben wir das problem quasi reduziert auf erreichbarkeit in graphen
- und erreichbarkeit in graphen das ist vielleicht etwas klarer dass dieses problem entscheidbar ist ja gegeben ein graf stadt kloten und auch mehrere
- entknoten meinetwegen gibt es einen pfad von einem starken zu einem der entknoten das ist entscheid war gibt so verschiedene methoden man kann zum
- 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
- 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
- und am ende können eigentlich nur zwei verschiedene sachen passieren entweder trifft man irgendwann auf einer akzeptierende konfiguration dann kann
- man anhalten und sagen ja das wort wird akzeptiert bzw ja es gibt einen pfad vom staat zu einer akzeptierenden konfiguration oder es ist
- irgendwann der fall dass man keine akzeptierende konfirmation gefunden hat und auch keinen neuen knoten mehr erreichen kann dann ist man auch fertig
- 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
- 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
- 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
- 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
- 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
- ganze unbeschränkten tholen maschine potenziell unendlich viele konfigurationen gibt und das ist so ein intuitiver grund warum man sagen kann
- bei touring maschinen ist das wort problem nicht entscheidend war ja das ist unentschuldbar ok ich hoffe die idee ist klar geworden
- warum diese beiden probleme entscheid bar sind und im nächsten video geht es dann wieder weiter mit noch mehr unentschuldbaren problemen