Die Chomsky-Hierarchie (formale Sprachen und Grammatiken)
Weitz / HAW Hamburg
https://www.youtube.com/watch?v=M43x9-S4D00

Transkript (automatisch erstellt)

0:00 und weil das so kompliziert werden kann teilt man Grammatiken jetzt noch in bestimmte Kategorien auf es gibt sehr viele verschiedene Kategorien von
0:09 Grammatiken aber es gibt eine ganz grobe Aufteilung in vier Kategorien nach Schwierigkeitsgrad quasi und die will ich Ihnen mal aufschreiben also man
0:20 macht folgendes wir stellen so eine Tabelle auf die zu Ehren von Herrn chomski den Namen chomski Hierarchie bekommt
0:34 und in dieser Tabelle äh machen wir das ganz einfach wir führen irgendwelche Restriktionen auf also das heißt wir führen irgendwelche
0:43 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
0:55 Namen dafür gibt's eine Bezeichnung das erste ist ganz simpel es gibt überhaupt keine Regeln also jede
1:15 Produktion ist erlaubt keine Regeln und wenn man überhaupt keine Regeln hat wenn man
1:24 irgendwas zulässt dann ist das quasi das komplizierteste was man sich an Grammatik vorstellen kann da können unter anderem solche Regeln auftauchen
1:31 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
1:40 nennt man phrasenstrukturgrammatiken oder auch ganz simpel man nennt sie Typ
1:59 nullgammatik so und jetzt
2:09 ä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
2:19 länger werden und dann wieder kürzer das will ich nicht und das kann ich folgendermaßen ganz simpel vermeiden indem ich
2:26 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
2:36 Prinzip ist erlaubt was immer Sie wollen aber links darf nichts stehen was länger ist als die rechte
2:46 Seite also hier müsste ich hinschreiben Restriktionen für
2:56 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
3:04 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
3:14 die linke Seite darf höchstens so langsam wie die rechte also die Restriktion ist die folgende Alpha kleiner g=ich
3:21 Beta wenn diese Regel eingehalten wird dann nennt man solche Grammatiken kontextsensitiv
3:32 und ich sage Ihnen gleich Beispiele dann versteht man auch warum es diese warum man diese Bezeichnung benutzt kontextsensitiv oder einfacher Typ 1 das
3:41 sind Typ 1 Grammatiken also bevor wir mal weiter machen gucken wir uns mal Beispiele dafür
3:52 an ich schreibe ihn mal ein paar Produktionen hin welche von diesen vier Produktionen hier wäre wohl nicht zugelassen für eine Typ
4:43 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
4:54 anderen sind immer noch zugelassen für kontextsensitive Grammatiken das bedeutet kontextsensitiv grammaten können Grammatiken können immer noch
5:01 ziemlich kompliziert sein ja also hier kann es ihn z.B passieren sie haben schon abgeleitet die Zeichenkette a gefolgt von dem ter nichtterminalen
5:10 Symbol t gefolgt von BB und dann dürfen sie das einfach umschaffeln und durch vier andere Zeichen ersetzen wobei sie z.B aus
5:20 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
5:28 immer noch ziemlich kompliziert aber die einzige Regel von diesen Vieren die nicht erlaubt ist ist die
5:37 hier nicht erlaubt in kontextsensitiven Grammatiken oder damit ich nicht so viel schreiben muss in Typ 1 Grammatiken
6:00 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
6:10 leere Zeichenkette vorkommen kann und wenn sie mal ein bisschen scharf nachdenken dann werden Sie feststellen dass sie nachdem was wir dahineschrieben
6:17 haben mit kontextsensitiven Grammatiken keine leeren Zeichenketten erzeugen können denn um die leere Zeichenkette zu erzeugen muss ja auf der rechten Seite
6:26 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
6:32 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
6:40 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
6:50 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
7:01 leere Zeichenkette werden kann das nennt man die Sonderregel dann ma ich also hier so eine
7:15 Fußnote also dieses hier ist die Restriktion Fußnote
7:25 Ausnahme ist die sogenannte Sonderregel die besagt die Produktion S ist
7:45 erlaubt also die Regel für kontextsensitive Grammatiken ist die linke Seite darf niemals länger als die rechte sein
7:53 Ausnahme diese Produktion darf wenn Sie wollen dabei sein weil diese Produktion ja die Regel eigentlich verl
8:02 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
8:12 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
8:19 erklärt aber das ist jetzt eigentlich zu technisch um da drauf einzugehen so weil man mit dieser ein Einschränkung mit dieser
8:31 Restriktion immer noch ziemlich komplizierte Grammatiken machen kann und das komplizierte ist in diesem Fall das kontextsensitive das habe ich eben
8:40 vielleicht noch gar nicht so deutlich gesagt äh möchte man das noch einfach haben mit Kontext sensitiv meine ich dieses hier
8:47 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
8:55 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
9:03 ersetzen wenn T in einem bestimmten Kontext auftaucht nämlich wenn T eingebettet ist in ein a links und zwei BS
9:11 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
9:20 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
9:28 zulassen und nur noch solche Regeln wie diese hier zulassen wo Links nur ein Zeichen steht ganz simpel
9:37 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
9:46 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
9:57 ist dass die die linke Seite also Alpha in unserer Produktion nur aus einem Zeichen bestehen darf das heißt die linke Seite
10:07 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
10:15 jetzt sinnvollerweise kontextfrei weil es nicht mehr vom Kontext abhängt oder wie sie sich schon
10:23 gedacht haben Typ 2 Grammatik bevor or ich ihen es kommt noch eine weitere Kategorie in dieser
10:32 chomsk Hierarchie bevor ich ihn die letzte auch noch sage sollten wir uns mal folgendes [Musik]
10:37 überlegen natürlich ist jede kontextsensitive Grammatik eine phrasenstrukturgrammatik weil jede Grammatik ist eine
10:46 phrasenstrukturgrammatik steht ja da ne jede weil es keine weiteren Restriktionen gibt was interessanter ist ist jede kontextfreie Grammatik ist
10:54 natürlich auch automatisch eine kontextsensitive Grammatik weil nach unseren Regeln steht ja auf der linken
11:03 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
11:14 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
11:21 Sonderregel abgedeckt werden das heißt offensichtlich ist jede Typ 2 Grammatik auch eine Typ 1 Grammatik also das halt schon mal
11:36 fest offensichtlich ist jede Typ 2 Grammatik eine Typ 1
11:53 Grammatik und jede Typ 1 Grammatik eine Typ Null Grammatik das ist sowieso klar weil es bei bei Typ n0 ja keine Einschränkung
12:13 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
12:22 durch den Namen glaube ich auch klar werden warum man diese weitere Einschränkung noch
12:28 einführt der nächste einfachere Typ von Grammatiken der dann natürlich Typ 3 heißen wird muss bei denen muss folgende Regel
12:37 eingehalten werden erste Regel wie bei kontextfreien Grammatiken darf Links nur ein Zeichen stehen ein nichtterminales Zeichen aber die zweite Regel ist noch
12:46 wesentlich schärfer die besagt nämlich rechts sind nur folgende Dinge zugelassen also die rechte Seite ich schreib es erstmal hin ist aus
12:59 dieser Menge das bedeutet auf der rechten Seite einer Regel sind nur ganz bestimmte
13:07 Dinge erlaubt entweder steht rechts die leere Zeichenkette y oder ein Wort was aus zwei Zeichen besteht wobei das erste Zeichen Terminal
13:18 und das zweite nicht Terminal ist das ist eine sehr sehr strenge Regel die fast alle Grammatiken ausschließt und diese Grammatiken nennt man
13:29 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
13:36 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
13:45 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
13:55 schon Beispiele also hier sollte ich noch mal ergänzen diese diese eine die ich hier eingemarkert hatte die ist ja nicht
14:03 erlaubt in Typ 1 Grammatiken und was ich vorhin gesagt aber nicht aufgeschrieben habe diese drei hier sind nicht
14:15 erlaubt in kontextfreien Grammatiken oder in Typ 2 Grammatiken
14:34 diese Regel hier unten die wäre nach un nach dem was hier steht auch erlaubt in einer regulären Grammatik weil ein
14:47 terminales gefolgt von einem nichtterminalen Symbol darastehen muss also hier Terminal gefolgt von nicht Terminal also diese Regel ist sogar in
14:56 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
15:12 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
15:23 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
15:34 rechten Seite immer genau zwei Zeichen stehen müssen und das erste Zeichen muss nicht Terminal also ein kleiner Buchstabe und das zweite Zeichen
15:41 Terminal also ein großer sein all diese Dinger sind nicht
15:52 erlaubt in Typ 3 Grammatiken sie sehen das ist schon eine ziemlich starke Einschränkung da bleibt einem
16:04 kaum noch was übrig wie man überhaupt Regeln aufschreiben kann was es natürlich dann umgekehrt wieder leichter macht
16:12 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
16:22 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
16:42 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
16:52 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
17:00 also kann ich diesen Satz hier fortführen und kann sagen außerdem ist natürlich jede Typ dre Grammatik eine ty Z
17:23 Grammatik also was schon mal klar sein sollte hoffentlich ist durch diese diese einfü dieses
17:33 Einführen von Restriktionen habe ich nach und nach die Grammatiken einfacher gemacht und ich habe bestimmte Grammatiken
17:40 [Musik] ausgeschlossen zumindest erstmal anschaulich gesagt das wird dadurch einfacher was
17:48 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
17:56 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
18:04 was glaube ich relativ offensichtlich ist ist natürlich ist es wie bei Automaten so ich kann verschiedene Automaten für dieselbe Sprache angeben
18:11 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
18:18 jede Sprache die ich mit einer Typ 2 Grammatik erzeugen kann auch mit einer Typ 3 Grammatik erzeugen kann vielleicht geht das
18:24 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
18:31 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
18:40 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
18:49 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