Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Grammatiken erklärt | Formale Sprachen 2024
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 26 Zeilen
- 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
- das liegt daran dass es über einem Alphabet nur endlich viele Grammatiken gibt aber überabzielbar viele Sprachen aber fangen wir jetzt mal mit dem
- wichtigen an und zwar besteht eine Grammatik aus einem viertupel in diesem stehen an erster Stelle die Variablen an zweiter Stelle das Alphabet danach
- kommen die Produktionsregeln und als letztes die startvariable diese ist immer ein Element der Variable so dann fangen wir jetzt mit dem
- interessanten Teil an und zwar den Produktionsregeln diese schreiben wir in mengenklammern man kann diese mengenklammern direkt ins Tupel
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- ist die Aufgabe also ihr müsst das einfach herausfinden die Grammatik habe ich jetzt einfach mal so formal
- hingeschrieben damit man das da stehen hat allerdings ist diese relativ irrelevant das Wichtige ist einfach die produktionsregel in dem Fall dass ihr
- jetzt halt schaut äh welche Wörter jetzt gebildet werden können und was für eine Sprache man daraus schlussfolgern
- 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
Zum Nachlesen
Formale GrammatikFormale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.
Kontextfreie GrammatikIn der Theorie der formalen Sprachen ist eine kontextfreie Grammatik (englisch context-free grammar, CFG) eine formale Grammatik, die nur solche …
Ableitung (Informatik)Eine formale Grammatik ist ein mathematisches Modell, das eine Menge solcher ableitbaren Wörter festlegt. Diese Menge nennt man eine formale Sprache. Das …
Chomsky-HierarchieSie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …