Praxis zu Grammatiken - Automaten & Formale Sprachen 11
Informatik - simpleclub
https://www.youtube.com/watch?v=aGWYtdoBF2M

Transkript (automatisch erstellt)

0:00 Na ihr habt wohl immer noch nicht genug von Grammatiken! Das hab ich mir gedacht.
0:03 Deswegen schauen wir uns heute ne konkrete Aufgabe dazu an und machen die durch! Los geht’s!
0:09 Also, dann starten wir direkt mit der Aufgabe. Wir haben jetzt in der Klausur folgende Grammatik gegeben.
0:18 Zuerst sollen wir drei Wörter angeben die nicht erkannt werden. Also Wörter durch die wir nicht durch ableiten kommen.
0:26 Wir sehen schnell, dass Wörter nicht erkannt werden, wenn sie nicht mit b anfangen. Also zum Beispiel cbba, caab oder c.
0:35 Natürlich gibt’s noch ganz viele andere wie abc, abb oder ab. Also eigentlich unendlich viele , die nicht erkannt werden.
0:42 So nächste Aufgabe: jetzt sollen wir auch noch drei Wörter angeben, die von der Grammatik erkannt werden.
0:48 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.
0:59 Nice oooooooone! Dann gleich weiter zur nächsten Aufgabe!
1:02 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.
1:13 Zuerst starten wir natürlich mit dem S, da das ja die Startvariable ist. Von dem S kommen wir erstmal nur zu bA.
1:20 Jetzt kommt im Wort nur ein a dran. Also gehen wir vom großen A zu aSA.
1:25 Da in der Aufgabenstellung eine Linksableitung verlangt wird, schauen wir uns das große S vor dem großen A an.
1:32 Weil? Richtig, du Schlauberger!
1:34 Weil es weiter links steht! Vom S kommen wir jetzt wieder nur auf bA.
1:38 In unserem Wort kommen als nächstes zwei a. Also gehen wir von dem linken großen A zu aaB.
1:46 Als nächstes kommt ein b und danach wieder as. Also gehen wir vom großen B zu bA.
1:53 So jetzt kommen wieder zwei a. Also gehen wir vom großen linken A wieder zu aaB.
1:58 Jetzt kommt als nächstes ein c. Deswegen gehen wir vom großen B zu einem c.
2:03 Das sieht doch gut aus! Jetzt bleibt noch ein kleines a übrig.
2:07 Also gehen wir vom großen A zu einem a. Und schon haben wir eine Linksableitung des Wortes!
2:13 Good one! Jetzt stellen wir uns noch die Frage ob die Grammatik kontextfrei oder regulär ist.
2:18 Naa, was sagt ihr? Sie ist auf jeden Fall kontextfrei, da links vom Pfeil immer genau eine Variable drinsteht.
2:26 Regularität trifft nicht zu, da rechts vom Pfeil ja nicht immer genau ein Symbol auf genau eine Variable folgt.
2:31 Schaut euch dafür ruhig nochmal das Video zu den Grammatiken und das Video zu Regularität und Kontextfreiheit an!
2:37 Fassen wir nochmal zusammen: Bei der Ableitung müsst ihr erstmal drauf achten ob eine Rechts- oder eine Linksableitung
2:42 gefordert ist. Es wird also entweder die Variable ganze rechts oder die Variable ganz links zuerst abgeleitet.
2:49 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.
2:54 Falls nicht, liegt es nicht in der Sprache. Also dann!
2:59 Fröhliches Schaffen! Pfiadi und Servus!