Theoretische Informatik (2): Chomsky Hierarchie
Franneck
https://www.youtube.com/watch?v=4WTOz26DZ9w

Transkript (automatisch erstellt)

0:00 so willkommen meine lieben Freunde zum nächsten Video heute haben wir die homsky Hierarchie diese unterteilt sich in vier Teil Gebiete und diese bauen ja
0:12 sag ich mal so gesehen aufeinander auf denn ganz unten haben wir einmal die Typ nullprache das ist die allgemeine jede Sprache ist Standard
0:22 oder jede Grammatik so gesehen ist standardmäßig oder automatisch Typ Null wenn dann die Grammatik weitere Einschränkungen hat ist sie weder Typ 1
0:30 2 oder 3 aber schon mal festhalten sieeh ist zumindest Typ 0 wenn schon nicht das andere dann haben wir eine Typ 1 Grammatik diese nennt sich Kontext
0:40 sensitiv die Eigenschaft von Kontext sensitiven Grammatiken ist dass wenn wir z.B u nach v ableiten dass V nicht kürzer also nicht kleiner u sein darf da
0:55 werden wir gleich ein Beispiel reinsehen da wird das klarer dann haben wir bei der Typ 2 das ist die kontextfreie Grammatik dort ist wichtig zu beachten
1:04 dass z.B aus einer Variable groß a ein Terminal klein a werden kann und dann haben wir die Typ 3 Grammatik das ist die reguläre bei der regulären Grammatik
1:16 kann entweder aus einer Variable ein Terminal werden oder aus einer Variable wird ein Terminal und eine weitere variable wichtig ist dass es halt auch
1:26 genau in dieser Reihenfolge ist erst Terminal und dann die Variable so habe ich alles mal aufgeschrieben könnt ihr euch kurz
1:33 notieren und Pause machen so dann haben wir jetzt ein Beispiel oder zwei Beispiele besser gesagt als erstes haben wir jetzt die
1:43 Sprache mache ich kurz noch was wir als σma haben wir haben die Sprache a auch n n gröer= 1 und die zu Verfügung stehen Buchstaben sind A B oder C in unserem
1:56 Fall hier brauchen wir natürlich nur a so wir wissen schon mal dass wir mindestens ein a im Wort haben weil das n größer g= 1 ist das heißt unsere
2:09 ableitungsschritte wären von der startvariable entweder halt ein a bilden oder wenn wir mehrere a bilden wollen ein a plus die startvariable noch mal
2:19 z.B könnten wir ja das Wort AAA bilden nämlich aus S wird as daraus wird AA S und daraus wird
2:34 AAA das wäre z.B mE ein Beispiel und jetzt müssen wir uns anschauen was für eine was für ein Typ hat denn diese Sprache so Typ Null ist standardmäßig
2:45 gesetzt kann man sich hier neben schreiben sie ist zumindest Typ ull dann gucken wir uns ein was ist die Regelung bei Typ 1 gewesen nämlich dass das Wort
2:53 nicht kürzer wird schauen wir uns an kann das Wort denn kürz werden wenn unser Wort mit der Länge 1 starten die Länge niemals unter
3:04 ein sein darf laut unserer Regelung kann das Wort nicht kürzer werden das heißt sie ist auch schon mal vom Typ 1 und wie man dann sieht das baut halt
3:13 aufeinander auf was in Typ 1 für Regelung sind die sind auch in Typ was in Typ 0 vorhanden ist ist auch in Typ 1 vorhanden an Regeln die Regeln die in
3:22 Typ 1 vorhanden sind sind auch in Typ 2 vorhanden die Typ 2 vorhanden sind sind Typ 3 vorhanden das heißt ja umso höher die Zahl ums mehr Regelung hat man
3:31 Einschränkungen hat man so jetzt gucken wir uns an was ist die Regelung für Typ 2 gewesen dass man aus einer Variable ein terminalzeichen ableiten kann haben
3:42 wir das bei unserer ja haben wir hier z.B das heißt wir haben auch Typ 2 und Typ 3 war dass man entweder KIS geldb aus einer Variable
3:55 ein Terminal macht oder aus einer Variable ein Terminal gefolgt von einer Variablen das trifft h auch zu das heißt wir haben eine Typ 3
4:07 Grammatik machen wir noch mal ein Beispiel das könnt ihr euch kurz angucken können ihr kurz Pause machen und vielleicht mal selber
4:14 Beilen so dann mache ich jetzt weiter wir haben jetzt wieder das gleiche Alphabet wir haben unsere Sprache nehme ich mit a W a das heißt ein a dann kommt
4:27 unser Wort und wieder ein a über Sigma Stern das heißt selbst wenn wir das leere Wort haben ist unser Wort mindestens AA lang
4:37 ähm so vom Typ Null ist sie wieder standardmäßig gesetzt und jetzt können wir uns kurz vielleicht die Ableitung überlegen die
4:45 wir haben dann daran erkennt man das meist dann sehr gut was für ein ja sag ich mal Typ die Grammatik hat so wir fangen mit S an daraus wird ein
4:56 ab nenne ich das mal das B ist eine Variable das A ist ja standardmäßig am Anfang und aus dem B können wir entweder ab
5:06 bilden BB oder CB oder halt was wir am Ende wieder haben müssen das einzelne a wo wenn ihr euch jetzt fragt wo kommt das
5:17 kleine A B und C her das sind halt unsere Buchstaben in unserem Alphabet so das sind dann die ableitungsschritte die wir zur Verfügung
5:25 hätten und an diesen können wir jetzt wieder rausgucken was haben wir denn jetzt hier Typ ein war ja das Wort wird nicht
5:34 kürzer das Wort kann nicht kürzer werden weil wir mindestens die Länge 2 haben wenn wir jetzt z.B das Wort AA
5:49 bilden wollen gehen wir ja von S nach ab nach AA könnten wir jetzt z.B von ab dann machen wir
6:00 z.B ABB können wir das Wort jetzt irgendwie kürzer machen als diese Länge die wir jetzt haben nein es geht nicht sie bleibt entweder gleich lang also die
6:10 dre wenn wir jetzt aus dem B das kleine a machen oder es wird länger wenn wir aus großen B z.B KLE C groß B machen das heißt sie ist auch schon mal vom Typ
6:22 1 da das nicht kürzer wird Typ 2 W wir aus einem aus einer Variable ein Terminal bilden können also ja Typ 2 auch und Typ 3 war das
6:36 entweder Terminal undvariable oder variable Terminal undvariable und Terminal manchmal verdrehe ich die Wörter wirklich dann noch mal vielleicht
6:45 wenn ich mich verhaspel noch mal bisschen nachdenken die kleinen Buchstaben sind terminale also Buchstaben die großen sind Variablen
6:52 also ist diese z.B hier auch vom Typ 3 und ja das war's für dieses Video wenn ihr was nicht verstanden habt schreibt in die Kommentare ich würde sagen se uns
7:00 nächstes Mal euch bin raus tschüssi