Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Praxis zu Grammatiken - Automaten & Formale Sprachen 11
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 30 Zeilen
- Na ihr habt wohl immer noch nicht genug von Grammatiken! Das hab ich mir gedacht.
- Deswegen schauen wir uns heute ne konkrete Aufgabe dazu an und machen die durch! Los geht’s!
- Also, dann starten wir direkt mit der Aufgabe. Wir haben jetzt in der Klausur folgende Grammatik gegeben.
- Zuerst sollen wir drei Wörter angeben die nicht erkannt werden. Also Wörter durch die wir nicht durch ableiten kommen.
- Wir sehen schnell, dass Wörter nicht erkannt werden, wenn sie nicht mit b anfangen. Also zum Beispiel cbba, caab oder c.
- Natürlich gibt’s noch ganz viele andere wie abc, abb oder ab. Also eigentlich unendlich viele , die nicht erkannt werden.
- So nächste Aufgabe: jetzt sollen wir auch noch drei Wörter angeben, die von der Grammatik erkannt werden.
- Da nur Wörter erkannt werden, die mit b anfangen, muss das auf jeden Fall gelten. Möglich wäre zum Beispiel baac, baabb oder babaaca.
- Nice oooooooone! Dann gleich weiter zur nächsten Aufgabe!
- Als nächstes sollen wir eine Linksableitung des Wortes babaabaaca angeben. Wir müssen jetzt also durch die Anwendung der Regeln versuchen auf das Wort zu kommen.
- Zuerst starten wir natürlich mit dem S, da das ja die Startvariable ist. Von dem S kommen wir erstmal nur zu bA.
- Jetzt kommt im Wort nur ein a dran. Also gehen wir vom großen A zu aSA.
- Da in der Aufgabenstellung eine Linksableitung verlangt wird, schauen wir uns das große S vor dem großen A an.
- Weil? Richtig, du Schlauberger!
- Weil es weiter links steht! Vom S kommen wir jetzt wieder nur auf bA.
- In unserem Wort kommen als nächstes zwei a. Also gehen wir von dem linken großen A zu aaB.
- Als nächstes kommt ein b und danach wieder as. Also gehen wir vom großen B zu bA.
- So jetzt kommen wieder zwei a. Also gehen wir vom großen linken A wieder zu aaB.
- Jetzt kommt als nächstes ein c. Deswegen gehen wir vom großen B zu einem c.
- Das sieht doch gut aus! Jetzt bleibt noch ein kleines a übrig.
- Also gehen wir vom großen A zu einem a. Und schon haben wir eine Linksableitung des Wortes!
- Good one! Jetzt stellen wir uns noch die Frage ob die Grammatik kontextfrei oder regulär ist.
- Naa, was sagt ihr? Sie ist auf jeden Fall kontextfrei, da links vom Pfeil immer genau eine Variable drinsteht.
- Regularität trifft nicht zu, da rechts vom Pfeil ja nicht immer genau ein Symbol auf genau eine Variable folgt.
- Schaut euch dafür ruhig nochmal das Video zu den Grammatiken und das Video zu Regularität und Kontextfreiheit an!
- Fassen wir nochmal zusammen: Bei der Ableitung müsst ihr erstmal drauf achten ob eine Rechts- oder eine Linksableitung
- gefordert ist. Es wird also entweder die Variable ganze rechts oder die Variable ganz links zuerst abgeleitet.
- Dann wendet ihr die Regeln an und versucht so auf das Wort zu kommen. Falls es möglich ist, liegt das Wort in der Sprache.
- Falls nicht, liegt es nicht in der Sprache. Also dann!
- Fröhliches Schaffen! Pfiadi und Servus!
Zum Nachlesen
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 …
Kontextfreie GrammatikIn der Theorie der formalen Sprachen ist eine kontextfreie Grammatik (englisch context-free grammar, CFG) eine formale Grammatik, die nur solche …
Kontextfreie SpracheKontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären …