Die Chomsky Hierarchie
Andreas Schaefer
https://www.youtube.com/watch?v=ltVR-lNbnfY

Transkript (automatisch erstellt)

0:00 die sprach klassen man typischerweise in der theoretischen informatik betrachtet werden einige archiv ausgehend von großer bis hin zu kleine
0:07 ausdrucks mächtigkeit zu dieser hierarchie kann man auf der einen seite gelangen indem man bei grammatiken die erlaubten regeln den produktionen
0:15 vorkommen dürfen immer weiter einschränkt die gleiche ehre hier hält man interessanterweise auch über die automaten modelle die chomskys benannt
0:25 nach dem us-amerikanischen linguist noam chomsky die am wenigsten restriktive klasse ist die klasse der jones ging 0 grammatiken generell sind ja grammatiken
0:35 vier truppe wir haben auf der einen seite eine menge von nicht terminalen prozent ein alphabet sigma eine menge von produktionen an staaten oas wobei
0:44 wir immer davon ausgehen dass die menge der nicht terminale und die mengen der terminale dass dieses jungen sind also kein gemeinsames element besitzen und
0:55 für die schulklasse an grammatiken haben wir fast gar keine einschränkungen eine kleine einschränkung gibt es schon die einschränkungen sind immer auf die
1:06 produktion bezogen ist dass piraten produktion einer solchen form alpha wird ersetzt durch beta und diese einschränkungen steht so ein bisschen
1:14 unhandlich auskommen deswegen einmal genauer an auf der linken seite das alpha das muss nach definition aus einem string
1:26 bestehen der am anfang eine kombination aus terminal- und nicht terminen hat davon aber beliebig viele es dürfen auch mal sein danach muss ein
1:36 nicht termin kommen das heißt in der linken seite einer produktion muss auf jeden fall mindestens ein nicht terminal- stehen
1:44 sonst was kann eine zulässige produktion und dahinter dürfen dann wieder beliebige kombinationen aus dem nahen oder nicht dem laden kommen in dem alter
1:54 das ist auch erlaubt hier darf es auch wieder das leere worte sein wichtige einschränkungen die man also bei den champs genug rating hand ist das
2:02 auf der linken seite tatsächlich ein nicht terminal- vorkommen für die rechte seite der produktion haben wir keine einschränkung das darf
2:11 ein beliebiger string aus nicht termin an termin sein darf insbesondere das leere wort sein und wenn man einmal definiert hat was
2:20 sonst nur grammatik ist kann man auch sagen dass eine chance - sprache ist und das läuft ganz einfach so dass man sagt eine sprache ist schon 20
2:27 genau dann wenn es einen dschungel grammatik gibt die diese sprache erzeugt eine beispiel grammatik an hier auf der rechten seite in dieser grammatik gibt
2:37 es produktionen die wort verkürzen sind zwei produktionen wie hier ich es geht über nach y nachdem ich dass es durch das leere
2:43 worte ersetzen kann aber auch diese produktion hier xb geht über nachwuchs auch diese produktion ist verkürzen
2:52 und da kann ich einfach dass beh weglassen wenn es in der nähe an sechs steht es gibt andere produktionen zum beispiel
2:59 hier diese produktion die erlaubt es mir dass grosz b quasi über das kleine bär überzuziehen und dabei zu verdoppeln also da kann man sehr viel machen mit
3:08 hilfe dieser allgemeinen produktion und tatsächlich es ist so dass die jim skinner grammatiken au äquivalents zu den touring maschinen sind
3:16 das heißt ich kann auf der einen seite zu jeder sonst nur grammatik eine tormaschine konstruieren die die gleiche sprache akzeptiert und ich kann es
3:23 wieder tun maschine auch eine grammatik konstruieren die quasi diese tour in maschine simuliert als grammatik jetzt wenn sie einmal zeit und lust haben
3:32 können sie ja mal probieren was für eine sprache sie eigentlich hier mit dieser beispiel grammatik erzeugen können wir gehen einen schritt weiter an der stelle
3:42 und schränkt die grammatiken weiter ein die nächste klasse ist die klasse der chomsky 1 grammatiken beziehungsweise kontextsensitiven grammatiken warum die
3:52 grammatiken kontextsensitiv heißen wird er sofort klar werden wenn wir die einschränkung für die produktion dieser grammatik klasse angucken
4:00 die idee es nämlich folgende wir verlangen dass die produktionen die form haben wie sich angegeben ist also alpha1 große alpha 2 kann ersetzt werden durch
4:10 alpha 1 beta alpha 2 wobei die idee ist dass man dieses a das großartig termin a la das das ersetzt durch eine zeichenkette
4:19 bitter aber in diesem fall muss der kontext erhalten bleiben es ist wir gucken auf der linken seite einmal den kontext an alpha 1 und alpha 2 wir
4:30 dürfen die regeln nur anwenden wenn dieses großer in diesem kontext von alpha 12 auftritt und müssen dann aber bei der ersetzung auch diesem kontext
4:39 beibehalten und deswegen heißen solche regeln seien kontextsensitiv weil sie eben den kontext angucken man diese regel nur anwenden kann
4:46 wenn das nicht seminar dass ich jetzt eigentlich setzen möchte in einem bestimmten kontext auftaucht eine wichtige weitere einschränkung ist an
4:54 der stelle dass das wetter also die zeichenkette durch die sich das adan ersetze das große die muss aus mindestens einem
5:04 zeichen bestehen die darf nicht das leere wort sein das ist hier durch das plus in der definition festgelegt der vorteil ist
5:12 nämlich oder der effekt ist dass deswegen die produktion niemals wort verkürzen sind dh wenn ich eine bestimmte satz form abgeleitet habe weiß
5:20 ich wenig weitere regeln anwenden kann die zeichenkette die ich herausbekommen nicht mehr kürzer werden sie kann höchstens noch länger werden und das
5:27 wiederum hat später auch auswirkungen auf die ein schreibt das wort problems gucken wir ja mal auch da eine beispiel grammatik an auf der rechten seite haben
5:37 wir so eine grammatik und wenn es da so eine produktion angucken zb diese hier groß cd wird ersetzt durch große kleins sie da ist es so dass ich das gros die
5:46 durch einen kleinen zeh ersetzen kann aber nur wenn es im kontext von große auftaut also dass rechts von dem großen zeh auftaucht nur dann kann ich dieser
5:55 ersetzung machen oder analog hier dieser ersetzung cb geht über nach cd die ersetzt quasi das b durch einen de aber nur wenn ein c links davon steht auch
6:07 hier an der stelle können sie einmal puzzle und überlegen was für eine sprache durch diese grammatik wohl erzeugt werden könnte hier gibt es auch
6:14 ein exzellentes automaten modell das sind die sogenannten gegen jahr beschränkten automaten die werden wir aber in zukunft nicht
6:20 mehr weiter groß angucken an dieser stelle gibt es nur ein kleines problem bei der definition und das problem ist dass leere worte psion nach
6:29 der definition für sie betrachtet haben wäre es nicht möglich in der grammatik das y zu erzeugen weil das eps immer als leeres wort wäre ja auf jeden fall wort
6:38 verkürzen weil man mit dem staatssymbol groß es startet länge 1 hat und apps gelandet hätte länge 0 demnach wer das wort verkürzen keine erlaubte produktion
6:48 damit man aber trotzdem die möglichkeit hat sprachen zu beschreiben mit chance gamescom antiken die das leere worte enthalten
6:55 deshalb erlaubt man zusätzlich die regel es geht über nach y als weitere regel allerdings fordert man dann dass das staatssymbol es dass das
7:05 nicht auf der rechten seite einer produktion vorkommen darf dann hat man diesen sonderfall quasi per hand ausgeschlossen
7:12 und natürlich heißen auch die sprache des g1 oder kontextsensitiv wenn es eine solche dramatik gibt die kontextsensitiv ist um die sprache erzeugt gehen wir in
7:23 der hierarchie eine stufe weiter zu den champs g2 grammatiken weitere einschränkungen es gibt zwei grammatiken sind die sogenannten kontext freien
7:32 grammatiken warum die kontext frei heißen sieht man sofort die produktion die erlaubt sind müssen die form haben geht über nacht peter das heißt da ist
7:42 jetzt eben kein kontext mehr die regel kann angewendet werden unabhängig davon welche zeichen links oder rechts vorkommen wichtig ist ja dass die
7:53 einzige einschränkung leben ist es auf der linken seite der produktion nur genau ein nicht termin ansteht und mehr nicht
7:58 auf der rechten seite darf dann irgendwas stehen an dieser stelle wunderte sich vielleicht dass prinzipiell hieraus einen epson auf der
8:07 rechten seite erlaubt wäre was eigentlich nicht in fonds k1 grammatiken zum beispiel erlaubt es man kann aber zeigen dass man eine solche produktion
8:14 eliminieren könnte ohne dass ich die sprache ändert deshalb ist es an dieser stelle erlaubt und wir können da etwas großzügiger sein
8:23 typische beispiele grammatik sehen sie hier auf der rechten seite dass es eine grammatik für auch ngo rehn auch zu dieser sprach klasse gibt es ein
8:32 exzellentes automat modell das sind ja so genannten keller automaten die einen stack haben auf dem sie werte zwischen speichern können diese sprach
8:43 klasse silber hat sehr viele anwendungen weil zb quasi jede programmiersprache diese so kennen er hat eine syntax definiertes durch eine grammatik
8:55 es geht zwei grammatik zum beispiel java c die haben alle eine formale grammatik die beschreiben was ein gültiges und
9:02 taktisch korrektes java der cd programm ist und der compiler würde als ersten schritt prüfen ob das überhaupt ein syntaktische projektes programm ist und
9:11 hier braucht man an der stelle grammatiken dafür gibt es auch eigene tools die quasi eine grammatik als eingabe bekommen und dann ein solcher
9:18 automatische prüfung quasi implementieren können es sind sogenannte partner generatoren typische tools wie zum beispiel an
9:26 teller oder jack hunter ist der moderne und für java jack ist ein bisschen älter sehr klassisches tool machen wir noch einen schritt weiter zu letzten und
9:37 restriktivsten klasse zur klasse der sogenannten sonstigen träger martin 1 noch recht linear bei den rechts linearen grammatiken sind nur noch drei
9:47 arten von produktionen überhaupt erlaubt die erste art ist eine produktion vom typ ich ersetze ein nicht terminal- genau durch ein termin an gefolgt von
9:56 einem nicht terminalen das nicht terminal- steht hier auf der rechten seite das der grund warum die produktion recht linear heißt weil eben das nicht
10:03 immer nach rechts steht zweite erlaubte produktions typ ist der typische sitze ein nicht einmal durch einen terminal- und
10:12 ganz ganz am ende ist es auch erlaubt dass ich einen nicht terminal- ersetzen durch das leere worte auch hier sehen ein beispiel auf der rechten seite das
10:23 jetzt eine grammatik der erzeugt alle wörter die nur aus es bestehen also beliebig langen kette von ars weil ich einmal dass es durchaus ersetzen kann
10:31 dann kann ich beliebig viele aaaahs erzeugen wenn ich irgendwann durch bin dann erst das erst durch y und habe mein wort hergestellt hier an der stelle
10:40 sieht man schon dass die diese regeln 16 jahren regeln dass die sehr ähnlich aussehen zu den traditionen automaten und das kein zufall
10:49 tatsächlich sind die endlichen automaten die das äquivalent berechnungsmodell dafür alles eben endlich den automaten gibt es nichts in ihre grammatik und
10:57 umgekehrt und entsprechend äquivalent dazu sind dann auch die regulären ausdrücken die chance die drei sprachen sind deswegen auch entsprechend die
11:08 regulären sprachen eine sprache soll schon sg tri wieder heißen wir uns eine grammatik dafür gibt diese sprache erzeugt und das ist eben genau für die
11:14 regulären sprachen der fall typischerweise wird diese sprach klasse weniger durch grammatiken beschrieben sondern viel häufiger durch endlich
11:22 automaten reguläre ausdrücke da wiederum sind die aber sehr relevant für die anwendung sie haben in programmiersprachen reguläre ausdrücke
11:30 oder zum beispiel auch auf der kommandozeile da wir bei der bildung der verschiedenen dzemski klassen die produktion immer weiter eingeschränkt
11:39 haben deswegen ist es klar dass die chance gelassen einige rallye bilden ganzen der mitte ist die klarste chance key drei
11:47 sprachen gesprochen bilden dann natürlich auch an die arche ist die klarste chance gesprochen als der regulären sprachen die man entsprechend
11:56 durch grammatik durch mehrere grammatiken endlich automaten oder reguläre ausdrücke beschreiben kann drumherum liegen dann die kontext freien
12:06 sprachen die man eben von extra grammatik oder keller automaten beschreiben kann drum herum da liegen dann die
12:13 kontextsensitive sprachen die chance geheimsprachen deren automat modell waren die linien beschränken automaten die wir nicht weiter angucken werden und
12:22 ganz außen drumherum liegen die chance genuss sprachen die eben auch die tollen akzeptierbaren sprachen sind