Grammatiken erklärt | Formale Sprachen 2024
Simplexity
https://www.youtube.com/watch?v=37PlCjW99yc

Transkript (automatisch erstellt)

0:00 heute geht's um formale Sprachen und deren Grammatiken wichtig ist dass es zu jeder Grammatik eine Sprache gibt aber nicht zu jeder Sprache eine Grammatik
0:08 das liegt daran dass es über einem Alphabet nur endlich viele Grammatiken gibt aber überabzielbar viele Sprachen aber fangen wir jetzt mal mit dem
0:15 wichtigen an und zwar besteht eine Grammatik aus einem viertupel in diesem stehen an erster Stelle die Variablen an zweiter Stelle das Alphabet danach
0:24 kommen die Produktionsregeln und als letztes die startvariable diese ist immer ein Element der Variable so dann fangen wir jetzt mit dem
0:32 interessanten Teil an und zwar den Produktionsregeln diese schreiben wir in mengenklammern man kann diese mengenklammern direkt ins Tupel
0:39 schreiben oder man definiert diese mit dem Repräsentanten P außerhalb schauen wir uns jetzt mal eine Grammatik für die Sprache L = A hoch n B hoch n mit n aus
0:48 den natürlichen Zahlen an l von G soll jetzt das gleiche wie l sein das gilt genau dann wenn g das gleiche ist wie V und V ist enthält nur die startvariab
1:00 sigσma ist das gleiche wie A B und EP dann haben wir natürlich unsere Produktion P die stehen außerhalb und unsere startvariable wenn wir uns unsere
1:10 Produktion P anschauen dann sehen wir s kann entweder in das leere Wort übergehen oder aber in ASB und dann könnten wir für das S jetzt da in dem
1:19 Fall auch das leere Wort einsetzen und somit belieb ich lange Ketten von diesem Wörtern aus der Sprache bilden damit haben wir jetzt eine Grammatik mit
1:28 welcher wir alle Wörter aus der Sprache bilden können und folglich gilt halt l von G ist das gleiche wie l Ableitungen von Wörtern sind auch noch mal sehr
1:35 relevant hier wenn es um Grammatiken geht also habe ich hier noch mal zwei Beispiele wie das geht wichtig ist hier das G für eine Grammatik unter dem Pfeil
1:44 zu schreiben also man sieht als erstes es geht in ASB über und man setzt im zweiten Schritt dann das EP für das S ein und somit erhalten wir das Wort ab
1:54 aus der Sprache die zweite Ableitung es geht nach ASB ist natürlich wieder unser Standard den wir vorhin auch hatten und jetzt setzen wir das Ganze also dieses s
2:04 geht nach ASB erneut ein und haben dann jetzt Aas s BB so im nächsten Schritt machen wir das ganze noch mal somit haben wir jetzt AAA s BBB und jetzt
2:15 macht man das ganze noch mal dann erhalten wir aa a S BBB und zu guute letzt setzen wir dann wieder unser EP ein um dann das Wort AAA BBB zu haben
2:27 das kann man zwar am Anfang so machen aber man sollte mit der Zeit immer die EPS Sonderregel verwenden welche besagt dass wenn eine Variable in ein leeres
2:36 Wort übergeht diese nicht mehr auf der rechten Seite stehen darf also die Variable also passen wir jetzt unsere Grammatik mal so an dass die EPS
2:44 Sonderregel erfüllt ist und wir immer noch die gleichen Wörter bilden können die letzte Sprache die wir jetzt noch verstehen müssen ist was die von einer
2:51 Grammatik erzeugte Sprache ist und wie wir das ganze notieren also wir sehen l von G hat eine komische Definition allerdings besagt diese nichts anderes
2:59 als dass unsere Sprache alle Wörter aus Sigma Stern beinhaltet die von einer stvariable aus abgeleitet werden können was ja auch Sinn ergibt wenn wir uns die
3:07 vorherige Grammatik zu a hoch n B hoch n wieder anschauen zum Ende hin habe ich dann noch eine Aufgabe mitgebracht und zwar welche Sprache wird hier erzeugt
3:16 ist die Aufgabe also ihr müsst das einfach herausfinden die Grammatik habe ich jetzt einfach mal so formal
3:21 hingeschrieben damit man das da stehen hat allerdings ist diese relativ irrelevant das Wichtige ist einfach die produktionsregel in dem Fall dass ihr
3:30 jetzt halt schaut äh welche Wörter jetzt gebildet werden können und was für eine Sprache man daraus schlussfolgern
3:42 kann genau die Lösung ist die leere Sprache ich hoffe euch hat das Video gefallen und dass es euch weitergeholfen hat und danke fürs zuschauen