Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Die Chomsky-Hierarchie (formale Sprachen und Grammatiken)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 108 Zeilen
- und weil das so kompliziert werden kann teilt man Grammatiken jetzt noch in bestimmte Kategorien auf es gibt sehr viele verschiedene Kategorien von
- Grammatiken aber es gibt eine ganz grobe Aufteilung in vier Kategorien nach Schwierigkeitsgrad quasi und die will ich Ihnen mal aufschreiben also man
- macht folgendes wir stellen so eine Tabelle auf die zu Ehren von Herrn chomski den Namen chomski Hierarchie bekommt
- und in dieser Tabelle äh machen wir das ganz einfach wir führen irgendwelche Restriktionen auf also das heißt wir führen irgendwelche
- Regeln auf da dafür welche Produktionen okay sind und welche nicht und dann geben wir den Grammatiken die diese Regeln erfüllen einfach ein
- Namen dafür gibt's eine Bezeichnung das erste ist ganz simpel es gibt überhaupt keine Regeln also jede
- Produktion ist erlaubt keine Regeln und wenn man überhaupt keine Regeln hat wenn man
- irgendwas zulässt dann ist das quasi das komplizierteste was man sich an Grammatik vorstellen kann da können unter anderem solche Regeln auftauchen
- wie diese blaue Regel eben wo ich quasi mit dem Hintern wieder umreiße was ich vorher schon aufgebaut habe solche Grammatiken in denen alles erlaubt ist
- nennt man phrasenstrukturgrammatiken oder auch ganz simpel man nennt sie Typ
- nullgammatik so und jetzt
- äh kann man sich das Leben deutlich einfacher machen wenn man sagt das was hier passiert durch die blaue Regel dass ich Zeichenketten haben habe die erst
- länger werden und dann wieder kürzer das will ich nicht und das kann ich folgendermaßen ganz simpel vermeiden indem ich
- sage Produktionen bei denen die linke Seite der Produktion länger ist als die rechte lasse ich nicht zu das ist eine ganz simple Regel also Produktion im
- Prinzip ist erlaubt was immer Sie wollen aber links darf nichts stehen was länger ist als die rechte
- Seite also hier müsste ich hinschreiben Restriktionen für
- Produktionen die so aussehen Produktion sehen ja immer so aus irgendeine linke Seite PIL irgendeine rechte Seite die linke Seite nenne ich jetzt mal Alpha
- und die rechte Seite Beta und die Restriktion die ich eben gesagt habe ist die linke Seite darf nicht länger sein als die rechte oder mit anderen Worten
- die linke Seite darf höchstens so langsam wie die rechte also die Restriktion ist die folgende Alpha kleiner g=ich
- Beta wenn diese Regel eingehalten wird dann nennt man solche Grammatiken kontextsensitiv
- und ich sage Ihnen gleich Beispiele dann versteht man auch warum es diese warum man diese Bezeichnung benutzt kontextsensitiv oder einfacher Typ 1 das
- sind Typ 1 Grammatiken also bevor wir mal weiter machen gucken wir uns mal Beispiele dafür
- an ich schreibe ihn mal ein paar Produktionen hin welche von diesen vier Produktionen hier wäre wohl nicht zugelassen für eine Typ
- 1 Grammatik für eine kontextsensitive ja die zweite ist nicht zugelassen weil bei der zweiten die linke Seite drei Buchstaben hat und die rechte Z alle
- anderen sind immer noch zugelassen für kontextsensitive Grammatiken das bedeutet kontextsensitiv grammaten können Grammatiken können immer noch
- ziemlich kompliziert sein ja also hier kann es ihn z.B passieren sie haben schon abgeleitet die Zeichenkette a gefolgt von dem ter nichtterminalen
- Symbol t gefolgt von BB und dann dürfen sie das einfach umschaffeln und durch vier andere Zeichen ersetzen wobei sie z.B aus
- dem aus dem Terminal Symbol t hier ein B machen und ausd dem was schon ein terminales Symbol war machen Sie ein T und so weiter also das ist trotzdem
- immer noch ziemlich kompliziert aber die einzige Regel von diesen Vieren die nicht erlaubt ist ist die
- hier nicht erlaubt in kontextsensitiven Grammatiken oder damit ich nicht so viel schreiben muss in Typ 1 Grammatiken
- das ist eigentlich alles okay die Sache hat nur einen Haken sie sie haben häufig Sprachen die sie beschreiben wollen in denen auch die
- leere Zeichenkette vorkommen kann und wenn sie mal ein bisschen scharf nachdenken dann werden Sie feststellen dass sie nachdem was wir dahineschrieben
- haben mit kontextsensitiven Grammatiken keine leeren Zeichenketten erzeugen können denn um die leere Zeichenkette zu erzeugen muss ja auf der rechten Seite
- der Produktion die leere Zeichenkette stehen anders kann es ja gar nicht sein irgendwann muss ich ja mal die leere Zeichenkette bekommen aber die leere
- Zeichenkette besteht ja aus Null Zeichen und das würde bedeuten dass auf der linken Seite auch null Zeichen stehen dürfen höchstens denn unsere Regel ist
- ja linke Seite darf höchstens so viel seit Zeichen wie die Rechte haben darum ist das eigentlich eine sinnvolle Regel mit der linken und der rechten Seite und
- deren Länge allerdings muss man eine Ausnahme zulassen nämlich man muss die Regel zulassen dass aus dem als zumindest aus Symbol eine die
- leere Zeichenkette werden kann das nennt man die Sonderregel dann ma ich also hier so eine
- Fußnote also dieses hier ist die Restriktion Fußnote
- Ausnahme ist die sogenannte Sonderregel die besagt die Produktion S ist
- erlaubt also die Regel für kontextsensitive Grammatiken ist die linke Seite darf niemals länger als die rechte sein
- Ausnahme diese Produktion darf wenn Sie wollen dabei sein weil diese Produktion ja die Regel eigentlich verl
- ja wenn sie im Skript nachlesen dann ist die EPS Sonderregel noch ein bisschen komplizierter die EPS Sonderregel besagt eigentlich dass das hier nur erlaubt ist
- unter bestimmten Bedingungen da will ich aber gar nicht weiter drauf eingehen weil man diese Bedingung immer umgehen kann das ist im Skript auch alles
- erklärt aber das ist jetzt eigentlich zu technisch um da drauf einzugehen so weil man mit dieser ein Einschränkung mit dieser
- Restriktion immer noch ziemlich komplizierte Grammatiken machen kann und das komplizierte ist in diesem Fall das kontextsensitive das habe ich eben
- vielleicht noch gar nicht so deutlich gesagt äh möchte man das noch einfach haben mit Kontext sensitiv meine ich dieses hier
- was hier steht wenn sie sich mal die erste Regel angucken sagt ja im Prinzip etwas darüber aus was sie mit dem nichtterminalen Symbol t machen können
- ja also diese Regel sagt sie dürfen t durch das auf der rechten Seite ersetzen aber Sie können das so interpretieren dass es sagt sie dürfen t nur dann
- ersetzen wenn T in einem bestimmten Kontext auftaucht nämlich wenn T eingebettet ist in ein a links und zwei BS
- rechts das macht Typ 1 Grammatiken obwohl sie einfacher sind als Typ nullgammatiken auch immer noch sehr schwer die Regeln hängen immer davon ab
- was ich zwischendurch für einen Kontext hatte darum sagt man wenn ich die noch einfacher machen will dann will ich all diese Regeln hier oben nicht mehr
- zulassen und nur noch solche Regeln wie diese hier zulassen wo Links nur ein Zeichen steht ganz simpel
- wenn Links nur ein Zeichen steht dann hängt das nicht mehr vom Kontext ab sondern ich kann wenn ich irgendwo ein großes T sehe sagen ich kann jetzt
- alle tregeln anwenden unabhängig davon was links und rechts steht also die Restriktion die man womit man das ganze noch stärker einschränkt
- ist dass die die linke Seite also Alpha in unserer Produktion nur aus einem Zeichen bestehen darf das heißt die linke Seite
- muss ein Zeichen sein aus der Menge der nichtterminalen Symbole kann man ganz einfach so hinschreiben das bekommt natürlich auch einen Namen und das heißt
- jetzt sinnvollerweise kontextfrei weil es nicht mehr vom Kontext abhängt oder wie sie sich schon
- gedacht haben Typ 2 Grammatik bevor or ich ihen es kommt noch eine weitere Kategorie in dieser
- chomsk Hierarchie bevor ich ihn die letzte auch noch sage sollten wir uns mal folgendes [Musik]
- überlegen natürlich ist jede kontextsensitive Grammatik eine phrasenstrukturgrammatik weil jede Grammatik ist eine
- phrasenstrukturgrammatik steht ja da ne jede weil es keine weiteren Restriktionen gibt was interessanter ist ist jede kontextfreie Grammatik ist
- natürlich auch automatisch eine kontextsensitive Grammatik weil nach unseren Regeln steht ja auf der linken
- Seite darf nur ein Zeichen stehen daraus folgt natürlich automatisch dass die rechte Seite auf jeden Fall länger ist als die linke Seite die einzige
- Möglichkeit dass die rechte Seite kürzer ist als die linke Seite wäre dass rechts nur ein steht aber das wurde ja durch unsere
- Sonderregel abgedeckt werden das heißt offensichtlich ist jede Typ 2 Grammatik auch eine Typ 1 Grammatik also das halt schon mal
- fest offensichtlich ist jede Typ 2 Grammatik eine Typ 1
- Grammatik und jede Typ 1 Grammatik eine Typ Null Grammatik das ist sowieso klar weil es bei bei Typ n0 ja keine Einschränkung
- gibt so und jetzt kann man sich das Leben noch leichter machen und da schreibe ich ihn erstmal einfach die Regeln und den Namen hin und dann wird
- durch den Namen glaube ich auch klar werden warum man diese weitere Einschränkung noch
- einführt der nächste einfachere Typ von Grammatiken der dann natürlich Typ 3 heißen wird muss bei denen muss folgende Regel
- eingehalten werden erste Regel wie bei kontextfreien Grammatiken darf Links nur ein Zeichen stehen ein nichtterminales Zeichen aber die zweite Regel ist noch
- wesentlich schärfer die besagt nämlich rechts sind nur folgende Dinge zugelassen also die rechte Seite ich schreib es erstmal hin ist aus
- dieser Menge das bedeutet auf der rechten Seite einer Regel sind nur ganz bestimmte
- Dinge erlaubt entweder steht rechts die leere Zeichenkette y oder ein Wort was aus zwei Zeichen besteht wobei das erste Zeichen Terminal
- und das zweite nicht Terminal ist das ist eine sehr sehr strenge Regel die fast alle Grammatiken ausschließt und diese Grammatiken nennt man
- regulär und Sie können sich wahrscheinlich schon denken warum man diese Grammatiken regulär nennt weil nämlich mit diesen Grammatiken genau die
- regulären Sprachen rauskommen die man auch durch endliche Automaten oder durch reguläre Ausdrücke bekommen hätte das werden wir uns gleich anschauen wird
- relativ schnell klar werden aber erstmal schauen wir uns vielleicht mal an was das bedeutet also wann eine Regel regulär ist und wann nicht wir hatten ja
- schon Beispiele also hier sollte ich noch mal ergänzen diese diese eine die ich hier eingemarkert hatte die ist ja nicht
- erlaubt in Typ 1 Grammatiken und was ich vorhin gesagt aber nicht aufgeschrieben habe diese drei hier sind nicht
- erlaubt in kontextfreien Grammatiken oder in Typ 2 Grammatiken
- diese Regel hier unten die wäre nach un nach dem was hier steht auch erlaubt in einer regulären Grammatik weil ein
- terminales gefolgt von einem nichtterminalen Symbol darastehen muss also hier Terminal gefolgt von nicht Terminal also diese Regel ist sogar in
- Kontext in regulär matiken erlaubt aber ich könnte z.B solche Regeln hinschreiben t geht über in 2 t das ist kontextsensitiv kontextfrei aber nicht
- mehr regulär oder ich könnte sowas hinschreiben wie t geht über in das hier oder ich könnte sowas hinschreiben wie t geht über
- in auch was ganz simples TB all diese Regeln die geschrieben habe entsprechen nicht mehr den Regeln für reguläre Grammatiken weil auf der
- rechten Seite immer genau zwei Zeichen stehen müssen und das erste Zeichen muss nicht Terminal also ein kleiner Buchstabe und das zweite Zeichen
- Terminal also ein großer sein all diese Dinger sind nicht
- erlaubt in Typ 3 Grammatiken sie sehen das ist schon eine ziemlich starke Einschränkung da bleibt einem
- kaum noch was übrig wie man überhaupt Regeln aufschreiben kann was es natürlich dann umgekehrt wieder leichter macht
- zu analysieren was eine Grammatik kann und was nicht je einfacher die Grammatik ist desto einfacher ist es sie zu analysieren also die einzige Regel die
- in allen vier grammatiktypen erlaubt wäre wäre diese hier oder was auch in allen Typen erlaubt wäre wäre diese hier das ist auch immer
- möglich und eine Sache sollte ich hier noch ergänzen das hatte ich hier ja schon angefangen diese Restriktion hier oben für Typ 2
- Grammatiken die steht ja hier auch das heißt eine Typ 3 Grammatik ist natürlich automatisch eine Typ 2 Grammatik weil da ist die Restriktion D nur noch schärfer
- also kann ich diesen Satz hier fortführen und kann sagen außerdem ist natürlich jede Typ dre Grammatik eine ty Z
- Grammatik also was schon mal klar sein sollte hoffentlich ist durch diese diese einfü dieses
- Einführen von Restriktionen habe ich nach und nach die Grammatiken einfacher gemacht und ich habe bestimmte Grammatiken
- [Musik] ausgeschlossen zumindest erstmal anschaulich gesagt das wird dadurch einfacher was
- jetzt noch nicht klar ist und damit werden wir uns jetzt beschäftigen ist sorgen dieser Einschränkung dafür dass ich z.B sagen wir mal mit Typ 2
- Grammatiken irgendwelche Sprachen erzeugen kann die ich nicht mit Typ 3 erzeugen könnte also sorgen die wirklich für Unterschiede in den Sprachen denn
- was glaube ich relativ offensichtlich ist ist natürlich ist es wie bei Automaten so ich kann verschiedene Automaten für dieselbe Sprache angeben
- und ich kann auch verschiedene Grammatiken für dieselbe Sprache angeben vielleicht könnte es ja sein dass wenn ich nur scharf genug nachdenke dass ich
- jede Sprache die ich mit einer Typ 2 Grammatik erzeugen kann auch mit einer Typ 3 Grammatik erzeugen kann vielleicht geht das
- ja das ist das was wir uns jetzt gleich als nächstes überlegen aber erstmal müssen wir so bisschen den Umgang mit diesen Grammatiken üben wir hten noch
- eine Frage e ja und zwar wenn die Produktion Meer Grammatik dafür sorgen dass ich nie ein Wort hinbekommen weil immer noch ein nicht terminales Zeichen
- drin ist beschreibt dann die Grammatik die eine Lehre Sprache also le Menge okay ist trotzdem Grammatik ist nicht irendwi kaputt eine Grammatik aber nach
- unseren Regeln müssen wir dann sagen alle Wörter die abgeleitet werden können und es kann kein Wort abgeleitet sein also ist dann die leere Menge
Zum Nachlesen
Chomsky-HierarchieSie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …
Formale GrammatikFormale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.
Kontextsensitive GrammatikKontextsensitive Grammatik. Formale Grammatik, die den Typ-1-Grammatiken der Chomsky-Hierarchie entsprechen. Artikel · Diskussion.
Kontextfreie SpracheKontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären …