Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Das Wortproblem
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 125 Zeilen
- hallo heute wollen wir uns das wort problem anschauen aber vorher möchte ich erst noch ein paar dinge zu den vorangegangenen vorlesungen besprechen
- mein name ist marcus krietsch herzlich willkommen zurück zur kleinen videoreihe formale sprachen und auto mal wir hatten beim letzten mal ja bereits
- uns mit der chance kirche archiv beschäftigt und herausgefunden dass man mit grammatiken viele sprachen aber nicht alle beschreiben kann ja irgendwo
- ganz weit draußen gibt es die formalen sprache in ihrer gänze und davon gibt es über absehbar viele wir können sie nicht endlich beschreiben egal was wir tun die
- type-0 sprachen sind das allgemein sste was uns in form von grammatiken zur verfügung steht darin enthalten sind die kontextsensitiven die kontext freien und
- letztlich die regulären sprache und wir hatten gezeigt dass das alles eine hierarchie bildet bevor wir aber mit krampfartigen gearbeitet hatten hatten
- wir auch schon mit anderen operationen sprachen beschrieben und darauf möchte ich kurz zurück kommen dennis grab eine anmerkung online in guitar hat lukas
- festgestellt und gemeldet auch rückgemeldet von den übungen vielleicht dass es nicht immer ganz klar ist an den in der ersten vorlesung welche
- operatoren reihenfolgen wir genau annehmen wollen insbesondere hatte ich da geschrieben dass jacqueline esther und plus stärker binden als die anderen
- operatoren und sie anschließend die anderen operatoren in einer reihung gelistet gemeint war an dieser stelle dass die operatoren in dieser
- dargestellten reihenfolge auch der stärke nach in ihrer bindungsstärke herr geordnet sind das heißt also dass wir annehmen können dass der krieg die
- kombination am stärksten bindet das darauf die der schnitt der sprachen folgt anschließend die vereinigung und erst ganz zuletzt die differenz das
- heißt sie können diese bindungs regeln annehmen wenn sie möchten und jeder operator hat also zügig allen anderen operatoren eine definierte präferenz bei
- plus und standen müssen wir das natürlich nicht definieren weil man sind taktisch nicht schreiben kann was wäre deutlichkeit an der stelle
- zulässt oder relevant machen wird ok das heißt wir können diese abkürzung gern verwenden ich werde die folien auch noch mal ein bisschen arbeitern und das
- vielleicht auch im schriftlichen klarzustellen bedenken sie aber immer wenn sie solche abkürzungen verwenden gerade weil es
- eben so viele operationen sind und nicht einfach nur punkt rechnung geht vor strich rechnung ist es manchmal nicht so klar und leicht zu verstehen was ein
- ausdruck bedeutet wenn man aggressiv klammern ein sport manchmal ist es sinnvoll auch klammern zu setzen die eigentlich nicht nötig sind einfach um
- es deutlicher zu machen was man da ich meine und natürlich auch weil nicht unbedingt jeder leser die gleichen vorrang regeln annimmt wenn man etwas
- aufschreibt für andere das gilt auch für sie wenn sie jetzt im rahmen dieses kurses zum beispiel eine prüfung ablegen und dort eine ausdruck
- aufschreiben müssen können sie auch da klammern weglassen natürlich und wenn sie die richtigen regeln dabei anwenden wird das richtig und verständlich sein
- sie können die klammern aber in jedem fall auch immer setzen und das ist niemals falsch und dabei stellen sie auch sicher dass selbst dann wenn sie
- die regeln nicht ganz richtig erinnern der ausdruck die bedeutung hat die sie eigentlich meinen und dass auch jeder der diese prüfung zum beispiel
- korrigiert das korrekt versteht ihn so frank lehrmann setzen hat manchmal schon vorteile und ich möchte auch noch sagen vielleicht ein darstellt dass es
- durchaus nicht üblich ist in allen bereichen der literatur in allen lehrbüchern und in allen wissenschaftlichen veröffentlichungen
- die gleichen fragen regeln zu verwenden insofern darf man auch nicht annehmen dass das universelle regeln sind die überall gleich verstanden werden wenn
- man sie so praktiziert gut dass also erst klar als kleiner nachtrag zu den operatoren und jetzt wie gesagt zurück zu den grammatiken im
- prinzip hatten wir schon viel über grammatik gelernt aber was wir natürlich bisher gemacht haben ist grammatiken aus dem relativ theoretischen abstrakten
- blickwinkel zu sehen und wenn sie in der praxis schauen werden sie vielleicht noch andere formen von formalen grammatiken treffen die
- auch eine große bedeutung haben insbesondere bekannt und beliebt ist dort die sogenannten bacchus mauer vor bacchus als john bekkers eigentlich ein
- amerikanischer ingenieur und informatik pionier der hat nicht nur die bacchus lauer form im wesentlichen erfunden sondern auch vortrag entwickelt und
- viele andere beiträge geleistet zur entwicklung der informatik bernauer peter lauer ist ein däne der sich selbst gar nicht so stark mit der nach ihm
- benannten wachsen aber vorm identifizieren konnte aber der auch große beiträge zur informatik geleistet hat was ist diese
- bacchus neuer form im prinzip eine art ass kee syntax für typ 2 kramer decken also wenn sie etwas im computer auf schreiben wollen haben sie dieses symbol
- zum beispiel nicht zur verfügung dafür wird gern der doppelte doppelpunkt mit dem gleichheitszeichen verwendet in dieser schreibweise alternativen werden
- so wie bei uns mit der pipe dargestellt es gibt auch lehrbücher in den grammatiken zum beispiel statt der pipe das plus verwenden
- aber wir hatten die alternative ja schon genannt auf diese art und was auch ganz wichtig ist in der praxis ist natürlich die markierung von terminal- und nicht
- terminal- symbolen man kann nicht immer davon ausgehen dass die alle irgendwo ja als menge vorher aufgelistet und gegeben sind
- man kann auch sich nicht in irgendeiner weise einschränken und sagen alle großbuchstaben sind nicht termine symbole und die kleinen buchstaben sind
- ja nicht alle symbole dass wir für die praxis und brauchbar da man ja auch mal großbuchstaben benutzen will und deshalb braucht man eine
- kennzeichnung und die nahe legen die kennzeichnung ist dass man anführungszeichen verwendet für die terminale und dann wurde zusätzlich für
- die nicht haben ja symbole so eine notation mit spitzen klammern eingeführt also dass es die bnf und die wird heute noch viel aus verwendet in solcher oder
- ähnlicher form was ich ja auch erwähnen möchte ist das genau genommen die erste person der so eine formale grammatik zugeordnet werden kann nicht in dieser
- natation aber als eine idee von produktions regel ein panini ist der also als gelehrter das fünfte oder vierten jahrhundert vor christus die
- sprache sanskrit untersucht hat und dafür grammatische regeln aufgestellt hat und da auch schon auf ähnliche ideen gekommen ist insofern ist nichts neu von
- dem was wir hier lernen aber die bedeutung für die informatik ist natürlich eine ganz andere es gibt auch noch eine variante der bnf was sage ich
- eine es gibt dutzende varianten bmf die bekannteste vom namen her ist die erweiterte bmf bmf die niklas wird den sich auch sehen können eingeführt hat im
- prinzip so ähnlich wie die bnf selbst man verwendet kommas in der kombination ein kleiner unterschied aber vor allem gibt es hier zusätzliche abkürzungen mit
- eckigen klammern für 0 oder 1 also optionale bestandteile und mit geschäften klammern für null- oder mehr also das heißt den klinischen im prinzip
- in der grammatik selbst anstatt durch repressive regeln beides kann man natürlich auch so darstellen auch im bmbf darstellen aber mit dieser
- zusätzlichen schreibweise wird es einfacher und leichter lesbar wenn sie emf lesen heißt das allerdings nicht dass die von niklas wird überhaupt
- gemeint dass es gibt wie gesagt in der praxis viele solcher firmen es gibt einen iso standard für e bmf es gibt eine w3c version der emf des world
- wide web consortiums die hier natürlich auch viele formale sprachen betrachten müssen es gibt außerdem noch die abf dass die argumente bmf sein soll von bei
- etf und wenn sie irgendein beliebiges lehrbuch aus dem schrank nehmen dann werden sie auch sehen dass die gns die da eingeführt werden nicht unbedingt
- immer genau dem entsprechen was in irgendeinem dieser quellen genau verwendet wird in der regel ist es so die ideen sind immer die gleichen und
- man kann relativ leicht verstehen welche syntax im einzelfall verwendet wird aber so richtig er einheitlich und standardisiert ist das ganze an der
- stelle nicht okay dass also noch als nachtrag zum thema grammatiken in der anwendung und was ich jetzt machen soll wie gesagt ist noch einmal über das wort
- problem zu sprechen das eigentliche thema der heutigen vorlesung und dann einen kleinen ausblick zu geben worum geht es beim wort problem die
- eigentliche herangehensweise die wir bisher natürlich betrieben haben beim thema grammatiken ist sie als zeugen der formalismen zu verstehen das heißt also
- grammatiken erzeugen neue wörter und wir können jetzt bestimmte wörter ableiten und darauf auch bei und entsteht dann eine sprache praktisch wichtig ist
- allerdings oft das umgekehrte wir wollen ein gegebenes wort bezüglich seiner zugehörigkeit in einer sprache analysieren das heißt wir wollen
- erkennen ob ein wort in einer sprache liegt und das ist das sogenannte wort problem hier definiert das wort problem für eine sprache l über dem alphabet
- sigma besteht darin die folgende funktionen zu berechnen eingabe für die funktion ist ein wort über sigma eine zeichenkette ausgabe ist entweder ja
- wenn das wort in der sprache liegt oder nein wenn das wort nicht in der sprache liegt das ist alles das ist eine politische
- funktion die nur zwei ergebnisse kennt und uns nur sagen soll ob das wort in der sprache liegt natürlich ist es in der praxis nicht ausreichend wenn ich
- weiter verarbeiten will will ich meistens auch noch mehr über sie wissen also zum beispiel wenn sie eine programmiersprache kompilieren
- dann möchten sie die struktur des programms auch im detail verstehen es ist nicht zufriedenstellend wenn man nur erfährt von einem programm das es ein
- gültiges programm ist also zwei allein ist dort nicht die rückgabe aber dieses wort problem als einfachste variante der der board analyse ist trotzdem von
- großer bedeutung und vieles was wir für das wort problem sagen können gilt dann indirekt auch für andere probleme okay das wort problem kann stellenweise recht
- einfach sein also können sich zum beispiel hier die sprache a gefolgt von beliebig vielen bs vorstellen hier wieder mit der operator natation und es
- ist klar dass dieses wort problem für diese sprache durch einen sehr einfachen algorithmus gelöst werden kann wir testen einfach auf der erste
- buchstabe h ist und ob alle darauf folgenden buchstaben b sind wenn es überhaupt welche gibt null bis sind natürlich auch
- das kann man ohne weiteres implementieren dieser algorithmus würde also das wort problem lösen wird diese sprache andererseits ist es bei weitem
- nicht immer so dass man leicht einen algorithmus finden kann ein bestimmtes für eine bestimmte sprache und das wort problem zu lösen und das gilt selbst
- dann wenn die sprache durch grammatiken beschrieben wird also wir wissen natürlich es gibt sprachen verdient werden wir sicherlich keinen algorithmus
- finden weil einfach die menge der algorithmen nur absehbar ist das hatten wir im zusammenhang mit kantor besprochen aber es stellt sich heraus
- selbst dann wenn wir eine grammatik finden können ist es noch längst keine garantie dafür dass wir einen effizienten oder überhaupt irgendeinen
- algorithmus für das wort problem finden können okay gut einzelner ausblick in diese richtung ist schon mal auf dieser folie zu sehen also was ich hier habe
- ist eine tabelle mit den vier von uns bisher beschriebenen sprach klassen oben ist typ 0 die sprache die menge oder die klasse aller sprachen welche man mit
- irgendeiner grammatik beschreiben kann dann folgen die kontextsensitiven kontext freien regulären und wir werden lernen dass zu jedem nicht jeder dieser
- sprache ein bestimmtes berechnungsmodell passt das heißt also wenn wir darüber nachdenken welche algorithmen welche art von algorithmen braucht man um das wort
- problem zu lösen dann kann man die modellhaft darstellen und dabei werden wir vor allem automaten verwenden ja nicht umsonst das thema
- dieser vorlesungsreihe sprachen und automaten und ein allgemein ssten fall typ 0 stellt sich heraus dass wir da touring maschinen benötigen also die
- allgemein sste art von praktikablen automaten modell wenn man so wie in der informatik und je weiter wir dann uns spezialisieren in richtung regulär desto
- einfacher werden die modelle bei kontextsensitiven werden wenn nicht deterministisch touring maschinen mit linearem speicher benötigen wir werden
- noch genauer lernen was das ist bei context freien wird es noch viel einfacher da genügen uns so genannte keller automaten und im regulären
- reichen endlich automaten die wir als nächstes betrachten wird und dementsprechend entlang dieser verschiedene berechnungsmodelle ist auch
- das problem das wort problem jeweils immer einfacher ihr mann in richtung reguläre sprachen geht bei touring maschinen allgemein bei type-0 sprachen
- ist semi entscheid bares nicht entscheid bar im allgemeinen man kann also kein algorithmus angeben der mit sicherheit die antwort liefert die man sucht bei
- kontextsensitiv ist immer noch sehr komplex ich habe ja ein paar fußnoten um diese begriffe zu erklären die wir hier noch nicht eingeführt haben dass die
- klasse heißt psp ist vollständig grob gesagt der algorithmus wird exponentiell viel zeit benötigen um die entscheidung zu treffen und erst bei den beiden
- kleinsten sprach klassen haben wir dann algorithmen zur verfügung die in polen um mehr zeit das wort problem lösen und bei regulären es ist sogar noch viel
- einfacher als bei context freien auch wenn hier bei beiden polen dem er steht okay das ist also die übersicht die wir arbeiten wollen und dafür werden wir uns
- einige termine einige vorlesungen ihr zeit nehmen müssen bis wir das alles verstanden haben und auch wissen warum diese dinge jeweils gelten es gibt aber
- abgesehen von diesen fragen des wort problems auch noch viele andere fragestellungen die mit sprachen zu tun haben und die wir auch mit besprechen
- werden zum teil also wie schon gesagt es gibt verschiedene darstellungen für formale sprachen und da wären wir vielleicht noch ein paar mehr kennen
- dann grammatik und automaten die wichtigsten und dieser vielfalt ist natürlich eine wichtige frage auch wie kann man von einer art der darstellung
- in eine andere übersetzen also wenn ich ihnen eine grammatik gebe können sie daraus automatisch einen algorithmus also einen automaten zum beispiel
- erstellen der dann das wort problem für diese grammatik löst ist dass ein automatischer prozess oder braucht man da jedes mal ein informatiker
- informatikerin die sich daran setzen um das problem manuell zu lösen natürlich auch wie sich die frage ob zwei darstellungen die
- gleiche sprache beschreiben es gibt viele grammatiken in die das gleiche aussagen und jetzt haben wir auch noch überlegt dass man auch automaten oder
- andere berechnungsmodell dafür verwenden kann kann man irgendwie ermitteln dass zwei modelle das gleiche bedeuten oder vielleicht im sonderfall kann man
- wenigstens erkennen wenn schon das erste zu schwer sein sollte dass eine bestimmte darstellung die lehrer sprache beschreibt also dass man vielleicht
- etwas spezifiziert hat was es gar nicht gibt beziehungsweise was keine keine wörter enthalten kann das wäre in der regel nicht gewünscht
- ich ein algorithmus aufschreibe der nicht akzeptiert dann hätte ich mir das auch wesentlich leichter machen können wo ich einfach nur return fonds
- programmieren und im zusammenhang damit natürlich auch wie kann eine darstellung vereinfacht werden ja wenn ich wirklich später in force erreichen will dann das
- natürlich nett wenn man das automatisch erzeugen könnte einiges davon ist möglich einiges davon ist unmöglich wie sich herausstellen wird werden wir noch
- mit details in eine zweite fragestellung oder art von fragestellungen die uns beschäftigen wird ist die frage was passiert wenn man operationen anwendet
- um neuer sprachen zu erzeugen also wir haben gelernt wir können mehrere sprachen nehmen und können durch operationen daraus neue sprachen
- erzeugen zum beispiel könnte ich eine regulären sprache l1 und noch eine reguläre sprache l2 haben und der anschnitt wählen und die offensichtliche
- frage ist dann ist es immer noch eine reguläre sprache kann ich die auch durch eine reha grammatik darstellen oder könnte es sein dass sie komplexe wird
- das kann man natürlich in allen möglichen kombinationen von gammertingen und sprach klassenfrage das in so genannte abschluss eigenschaften ja also
- wenn eine klasse unterfahrt unterschnitt abgeschlossen ist zum beispiel würde es bedeuten dass wenn die beiden teil sprachen in dieser klasse liegen auch
- das schnitt selbst wieder in der klasse liegen muss wir werden sehen einige unserer schon eingeführten sprach klassen sind unterschnitt abgeschlossen
- andere eben nicht okay das also soll uns für die nächsten ein paar termine zumindest beschäftigen wir werden beginnend mit dem einfachsten
- fall der regulären sprachen wo man auch sehr viele techniken kennen kann ja viel allgemeines über die art wie wir mit solchen modellen umgehen und
- in dem zusammenhang kommen eben die regulären die endlichen automaten auch die regulären ausdrücken ins spiel von denen sie sich schon gehört haben und
- wir werden über solche eigenschaften wie eben dieser abschluss eigenschaften sprechen im anschluss danach schauen wir die
- kontext fremdsprachen an die nächst komplexere oder schwierigere art von sprachen da stellt sich heraus manches was wir bei julian sprachen gelernt
- haben wird auch dort funktionieren lässt sich übertragen aber anderes eben nicht wird schwieriger oder muss erweitert werden
- da müssen wir über normalform sprechen es wird den keller automaten als begriff geben und als ein neues berechnungsmodell und auch da wird es
- wieder viele eigenschaften geben die wir betrachten wollen geht das ist also der plan und damit beginnen wir dann gleich ab der nächsten vorlesung für heute war
- das erst einmal alles ich freue mich dass wieder dabei waren bis zum nächsten mal und schicken sie uns ihre anmerkungen in getappt die
- genaue folie für den heutigen termin verlinke ich ihnen auch nochmal unten ich möchte auch noch mal darauf hinweisen dass sie auch übungsaufgaben
- zu den jeweiligen vorlesungen unten verlinkt in der beschreibung mit finden können vielen dank