Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Theoretische Informatik (2): Chomsky Hierarchie
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 41 Zeilen
- 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
- sag ich mal so gesehen aufeinander auf denn ganz unten haben wir einmal die Typ nullprache das ist die allgemeine jede Sprache ist Standard
- 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
- 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
- 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
- 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
- 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
- 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
- genau in dieser Reihenfolge ist erst Terminal und dann die Variable so habe ich alles mal aufgeschrieben könnt ihr euch kurz
- notieren und Pause machen so dann haben wir jetzt ein Beispiel oder zwei Beispiele besser gesagt als erstes haben wir jetzt die
- 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
- 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
- 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
- z.B könnten wir ja das Wort AAA bilden nämlich aus S wird as daraus wird AA S und daraus wird
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Grammatik machen wir noch mal ein Beispiel das könnt ihr euch kurz angucken können ihr kurz Pause machen und vielleicht mal selber
- 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
- 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
- ähm so vom Typ Null ist sie wieder standardmäßig gesetzt und jetzt können wir uns kurz vielleicht die Ableitung überlegen die
- 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
- 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
- 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
- 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
- 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
- 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
- bilden wollen gehen wir ja von S nach ab nach AA könnten wir jetzt z.B von ab dann machen wir
- 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
- 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
- 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
- entweder Terminal undvariable oder variable Terminal undvariable und Terminal manchmal verdrehe ich die Wörter wirklich dann noch mal vielleicht
- wenn ich mich verhaspel noch mal bisschen nachdenken die kleinen Buchstaben sind terminale also Buchstaben die großen sind Variablen
- 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
- nächstes Mal euch bin raus tschüssi
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.
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 …
SprachklasseDer amerikanische Publizist und Sprachtheoretiker Noam Chomsky hat die von intelligenten Wesen erkennbaren oder klassifizierbaren Sprachen in vier abstrakte …