Das Wortproblem
Prof. Markus
https://www.youtube.com/watch?v=MbLcL_wHEOY

Transkript (automatisch erstellt)

0:00 hallo heute wollen wir uns das wort problem anschauen aber vorher möchte ich erst noch ein paar dinge zu den vorangegangenen vorlesungen besprechen
0:09 mein name ist marcus krietsch herzlich willkommen zurück zur kleinen videoreihe formale sprachen und auto mal wir hatten beim letzten mal ja bereits
0:19 uns mit der chance kirche archiv beschäftigt und herausgefunden dass man mit grammatiken viele sprachen aber nicht alle beschreiben kann ja irgendwo
0:27 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
0:36 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
0:48 letztlich die regulären sprache und wir hatten gezeigt dass das alles eine hierarchie bildet bevor wir aber mit krampfartigen gearbeitet hatten hatten
0:55 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
1:08 festgestellt und gemeldet auch rückgemeldet von den übungen vielleicht dass es nicht immer ganz klar ist an den in der ersten vorlesung welche
1:19 operatoren reihenfolgen wir genau annehmen wollen insbesondere hatte ich da geschrieben dass jacqueline esther und plus stärker binden als die anderen
1:27 operatoren und sie anschließend die anderen operatoren in einer reihung gelistet gemeint war an dieser stelle dass die operatoren in dieser
1:37 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
1:46 kombination am stärksten bindet das darauf die der schnitt der sprachen folgt anschließend die vereinigung und erst ganz zuletzt die differenz das
1:56 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
2:06 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
2:14 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
2:24 vielleicht auch im schriftlichen klarzustellen bedenken sie aber immer wenn sie solche abkürzungen verwenden gerade weil es
2:29 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
2:37 ausdruck bedeutet wenn man aggressiv klammern ein sport manchmal ist es sinnvoll auch klammern zu setzen die eigentlich nicht nötig sind einfach um
2:45 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
2:56 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
3:04 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
3:11 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
3:18 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
3:26 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
3:32 durchaus nicht üblich ist in allen bereichen der literatur in allen lehrbüchern und in allen wissenschaftlichen veröffentlichungen
3:39 die gleichen fragen regeln zu verwenden insofern darf man auch nicht annehmen dass das universelle regeln sind die überall gleich verstanden werden wenn
3:49 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
4:00 prinzip hatten wir schon viel über grammatik gelernt aber was wir natürlich bisher gemacht haben ist grammatiken aus dem relativ theoretischen abstrakten
4:07 blickwinkel zu sehen und wenn sie in der praxis schauen werden sie vielleicht noch andere formen von formalen grammatiken treffen die
4:16 auch eine große bedeutung haben insbesondere bekannt und beliebt ist dort die sogenannten bacchus mauer vor bacchus als john bekkers eigentlich ein
4:28 amerikanischer ingenieur und informatik pionier der hat nicht nur die bacchus lauer form im wesentlichen erfunden sondern auch vortrag entwickelt und
4:39 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
4:47 benannten wachsen aber vorm identifizieren konnte aber der auch große beiträge zur informatik geleistet hat was ist diese
4:54 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
5:01 zum beispiel nicht zur verfügung dafür wird gern der doppelte doppelpunkt mit dem gleichheitszeichen verwendet in dieser schreibweise alternativen werden
5:13 so wie bei uns mit der pipe dargestellt es gibt auch lehrbücher in den grammatiken zum beispiel statt der pipe das plus verwenden
5:21 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
5:29 terminal- symbolen man kann nicht immer davon ausgehen dass die alle irgendwo ja als menge vorher aufgelistet und gegeben sind
5:37 man kann auch sich nicht in irgendeiner weise einschränken und sagen alle großbuchstaben sind nicht termine symbole und die kleinen buchstaben sind
5:45 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
5:51 kennzeichnung und die nahe legen die kennzeichnung ist dass man anführungszeichen verwendet für die terminale und dann wurde zusätzlich für
5:59 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
6:11 ä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
6:21 natation aber als eine idee von produktions regel ein panini ist der also als gelehrter das fünfte oder vierten jahrhundert vor christus die
6:34 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
6:44 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
6:55 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
7:07 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
7:16 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
7:27 in der grammatik selbst anstatt durch repressive regeln beides kann man natürlich auch so darstellen auch im bmbf darstellen aber mit dieser
7:35 zusätzlichen schreibweise wird es einfacher und leichter lesbar wenn sie emf lesen heißt das allerdings nicht dass die von niklas wird überhaupt
7:44 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
7:53 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
8:04 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
8:14 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
8:21 man kann relativ leicht verstehen welche syntax im einzelfall verwendet wird aber so richtig er einheitlich und standardisiert ist das ganze an der
8:29 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
8:41 problem zu sprechen das eigentliche thema der heutigen vorlesung und dann einen kleinen ausblick zu geben worum geht es beim wort problem die
8:49 eigentliche herangehensweise die wir bisher natürlich betrieben haben beim thema grammatiken ist sie als zeugen der formalismen zu verstehen das heißt also
9:00 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
9:09 allerdings oft das umgekehrte wir wollen ein gegebenes wort bezüglich seiner zugehörigkeit in einer sprache analysieren das heißt wir wollen
9:18 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
9:28 sigma besteht darin die folgende funktionen zu berechnen eingabe für die funktion ist ein wort über sigma eine zeichenkette ausgabe ist entweder ja
9:37 wenn das wort in der sprache liegt oder nein wenn das wort nicht in der sprache liegt das ist alles das ist eine politische
9:45 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
9:53 weiter verarbeiten will will ich meistens auch noch mehr über sie wissen also zum beispiel wenn sie eine programmiersprache kompilieren
9:58 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
10:08 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
10:20 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
10:29 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
10:42 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
10:49 buchstabe h ist und ob alle darauf folgenden buchstaben b sind wenn es überhaupt welche gibt null bis sind natürlich auch
10:56 das kann man ohne weiteres implementieren dieser algorithmus würde also das wort problem lösen wird diese sprache andererseits ist es bei weitem
11:05 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
11:16 dann wenn die sprache durch grammatiken beschrieben wird also wir wissen natürlich es gibt sprachen verdient werden wir sicherlich keinen algorithmus
11:21 finden weil einfach die menge der algorithmen nur absehbar ist das hatten wir im zusammenhang mit kantor besprochen aber es stellt sich heraus
11:30 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
11:36 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
11:48 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
11:58 irgendeiner grammatik beschreiben kann dann folgen die kontextsensitiven kontext freien regulären und wir werden lernen dass zu jedem nicht jeder dieser
12:07 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
12:15 problem zu lösen dann kann man die modellhaft darstellen und dabei werden wir vor allem automaten verwenden ja nicht umsonst das thema
12:23 dieser vorlesungsreihe sprachen und automaten und ein allgemein ssten fall typ 0 stellt sich heraus dass wir da touring maschinen benötigen also die
12:35 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
12:49 einfacher werden die modelle bei kontextsensitiven werden wenn nicht deterministisch touring maschinen mit linearem speicher benötigen wir werden
12:57 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
13:04 reichen endlich automaten die wir als nächstes betrachten wird und dementsprechend entlang dieser verschiedene berechnungsmodelle ist auch
13:14 das problem das wort problem jeweils immer einfacher ihr mann in richtung reguläre sprachen geht bei touring maschinen allgemein bei type-0 sprachen
13:22 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
13:33 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
13:40 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
13:50 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
13:57 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
14:07 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
14:17 abgesehen von diesen fragen des wort problems auch noch viele andere fragestellungen die mit sprachen zu tun haben und die wir auch mit besprechen
14:26 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
14:34 dann grammatik und automaten die wichtigsten und dieser vielfalt ist natürlich eine wichtige frage auch wie kann man von einer art der darstellung
14:43 in eine andere übersetzen also wenn ich ihnen eine grammatik gebe können sie daraus automatisch einen algorithmus also einen automaten zum beispiel
14:51 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
14:58 informatikerin die sich daran setzen um das problem manuell zu lösen natürlich auch wie sich die frage ob zwei darstellungen die
15:08 gleiche sprache beschreiben es gibt viele grammatiken in die das gleiche aussagen und jetzt haben wir auch noch überlegt dass man auch automaten oder
15:14 andere berechnungsmodell dafür verwenden kann kann man irgendwie ermitteln dass zwei modelle das gleiche bedeuten oder vielleicht im sonderfall kann man
15:24 wenigstens erkennen wenn schon das erste zu schwer sein sollte dass eine bestimmte darstellung die lehrer sprache beschreibt also dass man vielleicht
15:32 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
15:40 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
15:48 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
15:56 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
16:03 mit details in eine zweite fragestellung oder art von fragestellungen die uns beschäftigen wird ist die frage was passiert wenn man operationen anwendet
16:14 um neuer sprachen zu erzeugen also wir haben gelernt wir können mehrere sprachen nehmen und können durch operationen daraus neue sprachen
16:21 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
16:30 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
16:38 das kann man natürlich in allen möglichen kombinationen von gammertingen und sprach klassenfrage das in so genannte abschluss eigenschaften ja also
16:47 wenn eine klasse unterfahrt unterschnitt abgeschlossen ist zum beispiel würde es bedeuten dass wenn die beiden teil sprachen in dieser klasse liegen auch
16:56 das schnitt selbst wieder in der klasse liegen muss wir werden sehen einige unserer schon eingeführten sprach klassen sind unterschnitt abgeschlossen
17:03 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
17:15 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
17:24 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
17:32 wir werden über solche eigenschaften wie eben dieser abschluss eigenschaften sprechen im anschluss danach schauen wir die
17:39 kontext fremdsprachen an die nächst komplexere oder schwierigere art von sprachen da stellt sich heraus manches was wir bei julian sprachen gelernt
17:46 haben wird auch dort funktionieren lässt sich übertragen aber anderes eben nicht wird schwieriger oder muss erweitert werden
17:53 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
18:02 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
18:13 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
18:22 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
18:30 zu den jeweiligen vorlesungen unten verlinkt in der beschreibung mit finden können vielen dank