Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Die Chomsky-Hierarchie
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 113 Zeilen
- okay also noch mal den Zusammenhang zwischen Grammatik und Sprache ja schauen wir uns mal an
- Grammatiken woraus besteht Grammatik generell aus welchen Elementen was brauch Grammatik zu
- bilden ja genau man
- brauch genau man braucht eine eine variablenmenge ne das sind diejenigen Elemente die ersetzt werden können so denkt man zumindest also Variablen bzw
- nonter terminale oder nicht terminale dann ein Alphabet das sind die terminalsymbole oder die die letztlich dann auch aus
- denen die Wörter der Sprache zusammengesetzt werden die von der Grammatik erzeugt wird und damit hat wir auch bislang bei Automaten zu tun in der
- Regel haben wir a und BS verwendet oder Symbole aus dem man arithmetische Ausdrücke zusammenbasteln kann und so V Sigma was brauchen wir
- noch P als Produktionssystem das ist das Regelsystem einer Grammatik ne und und S was ist s genau ein Startsymbol eine
- startvariable oder ein Start nicht terminalsymbol das hier in V drin steckt ne okay so jetzt haben wir festgestellt es
- gibt oder das wurde wurde erklärt dieomski Hierarchie es gibt vier verschiedene Typen von Grammatiken und die unterscheiden sich durch die Art der
- Regeln in den Produktionssystemen so zunächst mal gibt's Typ Null
- Grammatiken okay das sind einfach nach unserer Vorstellung jetzt mal alle möglichen Grammatiken da haben wir keine
- Einschränkung schauen wir uns mal nicht näher an jetzt weil die jetzt unseren Fall noch zu allgemein sind gehen wir mal in die Typ 1
- Grammatiken wie heißen die noch Typ 1 Grammatiken oder ja genau SAS muss man auswendig wissen ne Typ 1 oder kontextensi
- tief so was gilt denn für diese für diesen Typ von Grammatik für die Regeln wie müssen die alle Regeln in dem Produktionssystem dieser Grammatik
- beschaffen sein kürzer gleich oder kürzer genau kleiner gleich ne
- also wenn ich eine Regel hab der Form W1 geht nach W2 und das kann jetzt alles mögliche sein da können
- nonterminal und terminale drin stecken dem W1 und W2 ganz egal ja wenn ich W1 nach W2 ableite dann muss
- gelten die Länge von W1 ist kleiner gleich der Länge von W2 acho wenn man able wenn man tatsächlich ein ein ein Wort ableitet ja
- konkretes Wort oder herleitet dann nimmt man ein Doppelpfeil hier ist es jetzt aber die produktionsregel die hat ein ein einzelpfeil also ein mit einer Linie
- ne keine Doppellinie das das das ist jetzt keine a ableitungsschritt sondern das ist eine Regel die man verwenden kann beim Ableiten
- so okay so das heißt wenn ich ein Wort ein Ausdruck habe den ich ableite dann kann der nicht kürzer werden beim Ableiten wird immer
- länger und wenn ich von der startvariable losgehe startvariable hat der Länge 1 so dann kann ich nur Wörter ableiten
- die mindestens die Länge ein haben es gibt immer noch so eine Ausnahmeregel bezüglich des leerren Worts manchmal W wir das lehere Wort in einer Sprache mit
- drin haben dann kann man es auch einfach extra dazu nehmen ja das ist jetzt kein sonderlich schwieriger Fall man lässt es einfach weg und nimmt später dazu oder
- so okay so also die Ausnahme macht man gern gut jetzt kommt jetzt wird's immer interessanter sozusagen immer spezieller
- aber auch immer interessanter Typ 2 wie heißen die auch richtig kontextfrei das sind die
- kontextfreien Grammatiken so was muss für Kontext freie Grammatiken gelten wie müssen da
- die Produktionsregeln beschaffen sein genau links darf nur eine Variable stehen sonst nichts ne und das ist auch
- das ja soll ich sagen das was man natürlicherweise empfindet wenn man solche Grammatiken baut ne dass man eigentlich immer nur so gerne eine
- Variable hätte die abgeleitet wird also V irgendeine V n ich jetzt mal nicht weil hier oben V heißt meine Menge sagen wir mal groß a wird abgeleitet nach
- irgendwas links darf also nur eine Variable oder ein nichtterminal stehen jetzt hier bei Typ 1 da dürfen auf der linken Seite auch theoretisch nur
- terminale stehen deswegen ist der Begriff variable auch ja der macht eigentlich ersten Sinn wenn man so will wenn man hier über kontextfreie Sprachen
- spricht ne Variablen werden ersetzt bei kontextfreien Variablen durch Grammatiken durch irgendwas anderes und da können in W können auch wieder
- Variablen drin stecken die ihrerseits wieder ersetzt werden können so warum heißen die eigentlich fi diese Grammatiken wo kommt denn der Begriff
- her wo kommt der Begriff her kontextfrei ja ja ja also ich hol mal wegen der Aufzeichnung also was es hat keine
- Bedeutung was rechts steht nee das hat schon eine Bedeutung danach leite ich ja ab aber es hat keine Bedeutung in welchem Kontext die Variable steht wenn
- ich ableite also wenn ich jetzt gerade hier so ein Wort ableite ne machen mal ein Beispiel für eine Grammatik okay ich finde jetzt ich
- schreib mal nur die Produktionsregeln hin alles andere lass ich weg also machen wir mal a wird abgeleitet nach kein keine Ahnung
- ne a ab oder a a a sowas und a ist vielleicht auch gleich die startvariable ne und oder vielleicht sogar nach BA und
- groß B wird abgeleitet nach also das ist ein oder Zeichen dazwischen ist klar ne es gibt drei Regeln a wird abgeleitet nach AAB oder a wird abgeleitet nach AAA
- oder a wird abgeleitet nach B und B wird abgeleitet nach ab oder B
- so jetzt ist völlig gleich in welchem Kontext a vorkommt als Variable ich kann a immer ersetzen dadurch oder dadurch oder dadurch also wenn ich jetzt anfange
- abzuleiten ich ma mal eine Ableitung von A und jetzt mache ich ein Doppelpfeil jetzt leite ich mal ein konkretes Wort ab a kann ich ableiten nach
- AAB so und jetzt kann ich mir diese Variable hier wieder schnappen und ableiten denn der Kontext bleibt natürlich stehen a und z.B nach Groß BA
- und dann klein B ja jetzt habe ich dieses a abgeleitet nach BA und mir war wurscht was links oder rechts neben dem A steht danach musste ich nicht
- gucken genauso bei dem B ich kann jetzt dieses B hier ersetzen durch z.B klein B dann hätte ich jetzt hier ab B ab abgeleitet bin fertig kann nichts mehr
- machen es ist keine Variable mehr in diesem Ausdruck das heißt dieses Wort ist in der von der Grammatik erzeugten Sprache ich habe jetzt ein Wort erzeugt
- das in dieser Sprache drin ist so und bei dem ersetzen ist es immer egal wo die Variablen stehen deswegen kontextfrei wenn ich meine
- kontextsensitive Grammatik aufbaueer da kann ja folgendes drin stehen da könnte drin stehen dass das hier abgeleitet wird
- nach Groß AA und das hier abgeleitet wird nach Groß BB ja und wenn A das Startsymbol ist
- dann kann a vielleicht noch abgeleitet werden nach aa a oder so so und wenn ich jetzt mal so eine
- Ableitung mache also ich leite a ab nach A ja dann könnte ich jetzt zwar das hier nehmen dieses a wieder und da einsetzen
- aber ich könnte auch z.B das hier nehmen diese Regel und bei dieser Regel ist entscheidend dass um die Variable herum ein bestimmter Kontext ist der
- mitersetzt wird ja also ich kann jetzt hier das ersetzen durch also das ganze hier ersetzen durch
- BB dementsprechend spielt der Kontext hier eine Rolle also hier Links auf der linken Seite können nicht nur einzelne Variablen
- stehen sondern ganze Kontexte die ersetzt werden deswegen Kontext sensitiv okay bei Kontext frei kann man einfach
- Variablen ersetzen egal in welchem Kontext sie stehen ich ma das jetzt mal weg so okay also wir hatten jetzt hier Typ 1 da
- wird nimmt die Wortlänge zu oder bleibt gleich bei Typ 2 ist es so ähm dass auf der linken Seite nur eine Einzel variable stehen kann wie sieht's
- jetzt aus bei Typ 3 oder regulär ne das sind die regulären
- Sprache was gilt da wie können da nur die Regeln beschaffen sein
- Typ 3 Sprache ist ja auch eine Typ 2 Sprache das heißt auf der linken Seite steht auf jeden Fall nur eine
- Variable aber was steht auf der rechten Seite jetzt kommen nur noch die rechte Seite
- einschränken was steht auf der rechten Seite
- ja genau ich ma mal irgendeine Buchstaben ne also klein sag klein C groß D also kleiner Buchstabe gefolgt von einer
- Variable die die die Regeln haben alle diese Form Terminal nicht Terminal okay ähm ja jetzt kann man wenn man nur solche Regeln hat hört das ja nie auf ne
- jetzt gibt's zwei Varianten wie man reguläre Grammatiken definieren kann eine haben sie in dem Video gesehen da wird auch noch erlaubt dass man
- Variablen ableitet zum Leeren Wort zu nichts also wegnimmt ne das wäre die möglichit damit Ende der Prozess des ableitens indem ich die Variable die in
- dem Wort in der Ableitung bisherigen Ableitung drin steckt indem ich die ein weglasse nach nichtsableite das kann man machen ein
- bisschen Bauchschmerzen hat man da dabei weil Typ bei Typ 1 ja gefordert ist dass die Wortlänge mindestens mal gleich bleiben muss und wenn ich jetzt eine
- Variable nach nichts ableite wird's kleiner okay bei diesen Regeln kann manchmal Ausnahmen machen und so es gibt aber noch eine schönere
- Definition und ich würde Sie bitten oder empfehlen die zu nehmen man kann auch folgendes machen man kann auch noch Regeln hinzufügen wo eine Ableitung
- stattfindet einfach nur nach einer einzelnen variblen äh chuldigung nach dem einzelnen terminalsymbol ne also nach dem
- einzelnen Buchstaben aus dem Alphabet so das ist äquivalent ne also wenn sie z.B diese Ableitung hier nehmen also angenommen wir haben reguläre Sprache
- äh reguläre Grammatik die folgendermaßen aussieht reguläre Grammatik die folgendermaßen aussieht ich leite a nach Klein a groß a ab oder EP ja das WD so
- eine Regel damit würde es abbrechen mit dem könnte man folgendes machen ne a wird ersetzt durch
- AA und dieses große a wird noch mal ersetzt durch klein a groß a und jetzt Gicht das ganze abbrechen nem ich groß a nach EPS ableite nach dem Leeren Wort
- dann steht da AA so es ist eigentlich ein Schritt zu viel bei der anderen Variante hat man den Vorteil also wenn ich jetzt die
- andere Variante hinschreibe die würde so aussehen a wird abgeleitet nach Klein a groß a oder nach Klein a zum
- Abbrechen ja dann kann man folgendes machen a wird abgeleitet nach Klein a groß a und jetzt wenn ich das gleiche Wort
- erzeugen will le ich n nach Klein a ab ne so genau also diese Variante der Definition regulärer Grammatiken dass nur diese
- beiden Typen von Ableitung zugelassen sind sind einerseits konsistent hier oben mit der Förderung von Typ 1 sprachen von Typ 1 Grammatiken
- Entschuldigung und außerdem sind die Ableitungen kürzer also macht Sinn das so zu machen okay
- ähm so jetzt haben wir also vier verschiedene Typen von Grammatiken und jetzt ist die Frage
- Sprachen was ist eine Sprache also eine Grammatik hier ist ist so ein viertuuppel sagt man auch ja wenn man es formal definieren würde also
- Grammatik ist eine Menge von variable eine Menge von Buchstab also im Alphabet und ein Produktionssystem mit Regeln und einem
- stsymbol und daraus mit der Grammatik kann man Wörter erzeugen so was ist eine Sprache mal ganz formal gesprochen oder
- allgemein gesprochen
- ja ja genau sehr schön eine Teilmenge aus der Menge aller Zeichenketten ja wenn ich so ein Alphabet habe σma dann bedeutet σ Stern ich kann alle
- möglichenchte alle möglichen Zeichenketten ne also wenn σma A und B ist klein a klein B dann ist σ stn alles das leere Wort a b AA ab B a BB AAA ab a
- und so weiter und so weiter ne ich kann alle möglichen Zeichenketten bilden und eine Sprache ist eine Teilmenge da draus
- das jetzt Teilmenge nicht leider gleich ne Teilmenge aus Stern das bedeutet aber letztlich ist eine Sprache nichts anderes als eine
- Menge von Wörtern mathematisch gesehen eine Menge eine Sprache hat keine Regeln eine Sprache hat kein
- ableitungssystem eine Sprache ist kein Auto oder so sondern eine Sprache ist eine Menge von Wörtern
- Punkt was ist jetzt eine Typ 3 Sprache eine Typ 3 Sprache
- ja genau erzeugt ja ne jede dieser Grammatiken hier also jede Grammatik
- erzeugt ja eine bestimmte Menge von Wörtern das ist die von der Grammatik erzeugte Sprache ich kann mit einer Grammatik eine Menge von Wörtern
- erzeugen andere nicht alle Wörter die von der Grammatik erzeugt werden nehme ich zusammen als Menge und sag das ist die von der Grammatik erzeugte Sprache
- so eine Typ 3 Sprache eine Sprache ist dann eine Typ 3 Sprache wenn eine Typ 3 ammatik existiert die sie erzeugt wenn Sie irgendeine Sprache
- haben sagen ach Mensch ich kann typrammatik basteln die mir die Sprache erzeugt genauso Typ 2 Sprache ne Typ 2 Sprache ist eine
- Sprache für die eine Typ 2 Grammatik existiert ich kann Typ 2 Grammatik angeben die diese Sprache erzeugt und jetzt der Witz ist natürlich
- es gibt jetzt Sprachen das heiß es gibt Mengen von Wörtern die kann ich eine Typ 2 Grammatik angeben aber keine Typ 3 Grammatik also spannende sozusagen zu
- begründen dass es unmöglich ist bei eine bestimmte Menge von Wörtern eine Typ 3 Grammatik anzugeben dann ist die Sprache von Typ 2 ne wenn ich Typ 2 Grammatik
- angeben kann finde aber keine Typ 3 Grammatik so genauso bei Typ 1 ne es gibt tatsächlich Sprachen für die gibt es
- keine 2 Grammatik und damit auch keine Typ 3 Grammatik jede Typ 3 Grammatik ist eine Typ 2 Grammatik wenn ich keine Typ 2 Grammatik angeben kann kann ich auch
- keine Typ 3 Grammatik angeben aber vielleicht kann ich Typ 1 Grammatik angeben damit habe ich eine Typ 1 Sprache und man kann sagen je weiter man
- nach unten kommt spezieller man wird umso effizienter lässt sich die Sprache mit Algorithmen behandeln hier oben wird's immer
- schwieriger wenn die je breiter der Typ wird je allgemeiner es wird okay und das interessante also die interessanten Sprachen die eigentlich
- interessanten Sprachen im Anwendungsfeld ja das sind diese Sprachen hier Typ 2 und Typ 3 die tauchen immer wieder auf in der inform informatischen
- Alltag ja also Typ 3 reguläre Sprachen das damit Beschäftigung ist auch noch reguläre Ausdrücke beispielsweise oder Automaten so wie wir reguläre Automaten
- also dieerministische endliche Automaten sind diejenigen die Typ 3 Sprachen erkennen oder Typ 2 taucht immer auf arithmetische Ausdrücke haben wir schon
- festgestellt lässt sich nicht durch einen deterministischen endlichen Automaten erzeugen ist also nicht den Typ 3 sondern ist der Typ zwe Sprache
- ja okay
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.
Kontextfreie SpracheKontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären …
Reguläre GrammatikEine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie. Die von solchen Grammatiken erzeugten Sprachen heißen …