Die Chomsky-Hierarchie
Christian Spannagel
https://www.youtube.com/watch?v=deDq4a8Vad8

Transkript (automatisch erstellt)

0:09 okay also noch mal den Zusammenhang zwischen Grammatik und Sprache ja schauen wir uns mal an
0:25 Grammatiken woraus besteht Grammatik generell aus welchen Elementen was brauch Grammatik zu
0:38 bilden ja genau man
0:46 brauch genau man braucht eine eine variablenmenge ne das sind diejenigen Elemente die ersetzt werden können so denkt man zumindest also Variablen bzw
0:59 nonter terminale oder nicht terminale dann ein Alphabet das sind die terminalsymbole oder die die letztlich dann auch aus
1:10 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
1:17 Regel haben wir a und BS verwendet oder Symbole aus dem man arithmetische Ausdrücke zusammenbasteln kann und so V Sigma was brauchen wir
1:26 noch P als Produktionssystem das ist das Regelsystem einer Grammatik ne und und S was ist s genau ein Startsymbol eine
1:40 startvariable oder ein Start nicht terminalsymbol das hier in V drin steckt ne okay so jetzt haben wir festgestellt es
1:54 gibt oder das wurde wurde erklärt dieomski Hierarchie es gibt vier verschiedene Typen von Grammatiken und die unterscheiden sich durch die Art der
2:04 Regeln in den Produktionssystemen so zunächst mal gibt's Typ Null
2:15 Grammatiken okay das sind einfach nach unserer Vorstellung jetzt mal alle möglichen Grammatiken da haben wir keine
2:24 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
2:37 Grammatiken wie heißen die noch Typ 1 Grammatiken oder ja genau SAS muss man auswendig wissen ne Typ 1 oder kontextensi
3:04 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
3:13 beschaffen sein kürzer gleich oder kürzer genau kleiner gleich ne
3:34 also wenn ich eine Regel hab der Form W1 geht nach W2 und das kann jetzt alles mögliche sein da können
3:44 nonterminal und terminale drin stecken dem W1 und W2 ganz egal ja wenn ich W1 nach W2 ableite dann muss
3:54 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
4:10 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
4:19 ne keine Doppellinie das das das ist jetzt keine a ableitungsschritt sondern das ist eine Regel die man verwenden kann beim Ableiten
4:33 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
4:44 länger und wenn ich von der startvariable losgehe startvariable hat der Länge 1 so dann kann ich nur Wörter ableiten
4:54 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
5:01 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
5:10 so okay so also die Ausnahme macht man gern gut jetzt kommt jetzt wird's immer interessanter sozusagen immer spezieller
5:20 aber auch immer interessanter Typ 2 wie heißen die auch richtig kontextfrei das sind die
5:30 kontextfreien Grammatiken so was muss für Kontext freie Grammatiken gelten wie müssen da
5:39 die Produktionsregeln beschaffen sein genau links darf nur eine Variable stehen sonst nichts ne und das ist auch
5:57 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
6:07 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
6:22 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
6:32 terminale stehen deswegen ist der Begriff variable auch ja der macht eigentlich ersten Sinn wenn man so will wenn man hier über kontextfreie Sprachen
6:41 spricht ne Variablen werden ersetzt bei kontextfreien Variablen durch Grammatiken durch irgendwas anderes und da können in W können auch wieder
6:50 Variablen drin stecken die ihrerseits wieder ersetzt werden können so warum heißen die eigentlich fi diese Grammatiken wo kommt denn der Begriff
7:11 her wo kommt der Begriff her kontextfrei ja ja ja also ich hol mal wegen der Aufzeichnung also was es hat keine
7:32 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
7:41 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
7:51 schreib mal nur die Produktionsregeln hin alles andere lass ich weg also machen wir mal a wird abgeleitet nach kein keine Ahnung
8:01 ne a ab oder a a a sowas und a ist vielleicht auch gleich die startvariable ne und oder vielleicht sogar nach BA und
8:20 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
8:28 oder a wird abgeleitet nach B und B wird abgeleitet nach ab oder B
8:40 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
8:50 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
8:57 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
9:09 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
9:22 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
9:35 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
9:47 das in dieser Sprache drin ist so und bei dem ersetzen ist es immer egal wo die Variablen stehen deswegen kontextfrei wenn ich meine
9:56 kontextsensitive Grammatik aufbaueer da kann ja folgendes drin stehen da könnte drin stehen dass das hier abgeleitet wird
10:06 nach Groß AA und das hier abgeleitet wird nach Groß BB ja und wenn A das Startsymbol ist
10:17 dann kann a vielleicht noch abgeleitet werden nach aa a oder so so und wenn ich jetzt mal so eine
10:25 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
10:35 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
10:43 mitersetzt wird ja also ich kann jetzt hier das ersetzen durch also das ganze hier ersetzen durch
10:54 BB dementsprechend spielt der Kontext hier eine Rolle also hier Links auf der linken Seite können nicht nur einzelne Variablen
11:03 stehen sondern ganze Kontexte die ersetzt werden deswegen Kontext sensitiv okay bei Kontext frei kann man einfach
11:15 Variablen ersetzen egal in welchem Kontext sie stehen ich ma das jetzt mal weg so okay also wir hatten jetzt hier Typ 1 da
11:25 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
11:34 jetzt aus bei Typ 3 oder regulär ne das sind die regulären
11:46 Sprache was gilt da wie können da nur die Regeln beschaffen sein
12:07 Typ 3 Sprache ist ja auch eine Typ 2 Sprache das heißt auf der linken Seite steht auf jeden Fall nur eine
12:13 Variable aber was steht auf der rechten Seite jetzt kommen nur noch die rechte Seite
12:27 einschränken was steht auf der rechten Seite
12:41 ja genau ich ma mal irgendeine Buchstaben ne also klein sag klein C groß D also kleiner Buchstabe gefolgt von einer
12:52 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
13:07 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
13:15 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
13:25 dem Wort in der Ableitung bisherigen Ableitung drin steckt indem ich die ein weglasse nach nichtsableite das kann man machen ein
13:35 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
13:45 Variable nach nichts ableite wird's kleiner okay bei diesen Regeln kann manchmal Ausnahmen machen und so es gibt aber noch eine schönere
13:52 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
14:03 stattfindet einfach nur nach einer einzelnen variblen äh chuldigung nach dem einzelnen terminalsymbol ne also nach dem
14:12 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
14:24 ä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
14:36 eine Regel damit würde es abbrechen mit dem könnte man folgendes machen ne a wird ersetzt durch
14:43 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
14:54 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
15:04 andere Variante hinschreibe die würde so aussehen a wird abgeleitet nach Klein a groß a oder nach Klein a zum
15:12 Abbrechen ja dann kann man folgendes machen a wird abgeleitet nach Klein a groß a und jetzt wenn ich das gleiche Wort
15:21 erzeugen will le ich n nach Klein a ab ne so genau also diese Variante der Definition regulärer Grammatiken dass nur diese
15:32 beiden Typen von Ableitung zugelassen sind sind einerseits konsistent hier oben mit der Förderung von Typ 1 sprachen von Typ 1 Grammatiken
15:41 Entschuldigung und außerdem sind die Ableitungen kürzer also macht Sinn das so zu machen okay
15:56 ähm so jetzt haben wir also vier verschiedene Typen von Grammatiken und jetzt ist die Frage
16:12 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
16:23 Grammatik ist eine Menge von variable eine Menge von Buchstab also im Alphabet und ein Produktionssystem mit Regeln und einem
16:34 stsymbol und daraus mit der Grammatik kann man Wörter erzeugen so was ist eine Sprache mal ganz formal gesprochen oder
16:45 allgemein gesprochen
16:56 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
17:06 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
17:21 und so weiter und so weiter ne ich kann alle möglichen Zeichenketten bilden und eine Sprache ist eine Teilmenge da draus
17:31 das jetzt Teilmenge nicht leider gleich ne Teilmenge aus Stern das bedeutet aber letztlich ist eine Sprache nichts anderes als eine
17:42 Menge von Wörtern mathematisch gesehen eine Menge eine Sprache hat keine Regeln eine Sprache hat kein
17:54 ableitungssystem eine Sprache ist kein Auto oder so sondern eine Sprache ist eine Menge von Wörtern
18:07 Punkt was ist jetzt eine Typ 3 Sprache eine Typ 3 Sprache
18:27 ja genau erzeugt ja ne jede dieser Grammatiken hier also jede Grammatik
18:36 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
18:45 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
18:52 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
19:02 haben sagen ach Mensch ich kann typrammatik basteln die mir die Sprache erzeugt genauso Typ 2 Sprache ne Typ 2 Sprache ist eine
19:15 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
19:24 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
19:35 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
19:45 angeben kann finde aber keine Typ 3 Grammatik so genauso bei Typ 1 ne es gibt tatsächlich Sprachen für die gibt es
19:57 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
20:05 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
20:17 nach unten kommt spezieller man wird umso effizienter lässt sich die Sprache mit Algorithmen behandeln hier oben wird's immer
20:27 schwieriger wenn die je breiter der Typ wird je allgemeiner es wird okay und das interessante also die interessanten Sprachen die eigentlich
20:38 interessanten Sprachen im Anwendungsfeld ja das sind diese Sprachen hier Typ 2 und Typ 3 die tauchen immer wieder auf in der inform informatischen
20:51 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
21:02 also dieerministische endliche Automaten sind diejenigen die Typ 3 Sprachen erkennen oder Typ 2 taucht immer auf arithmetische Ausdrücke haben wir schon
21:14 festgestellt lässt sich nicht durch einen deterministischen endlichen Automaten erzeugen ist also nicht den Typ 3 sondern ist der Typ zwe Sprache
21:26 ja okay