Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Grundlagen der Informatik, Lehrvideo; Grammatiken formaler Sprachen - mit Übungsteil
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 101 Zeilen
- [Musik] hallo liebe Zielgruppe ich begrüße Sie zu einem weiteren Lehrvideo aus der
- Reihe Grundlagen der Informatik heute zum Thema Grammatiken es geht um Grammatiken für formale Sprachen wir abstrahieren also
- vom Prinzip der Grammatik für natürliche Sprachen in der deutschen Sprache wissen wir beispielsweise dass ein Satz so aufgebaut werden kann Subjekt predikat
- Objekt wobei es noch viele weitere Strukturen für korrekte deutsche Sätze gibt für das Subjekt kann z.B ich du RCS stehen das Prädikat kann sein laufe
- studiere schreibe und es gibt ein beliebiges Objekt z.B Informatik und so wird ein Satz gebildet ich studiere informatikkt wir haben hier gleich
- festgelegt dass am Ende eines Satzes ein Punkt kommt das Prinzip wenden wir nun für die Informatik an wobei Sprachen hier wieder ganz allgemein sind es
- können beliebige bitstrings sein also auch binäre Zahlen es können ask Zeichen sein oder beliebige andere zeichenvorräte als Beispiel wollen wir
- einmal die Syntax festlegen für dezimalgeschriebene natürliche Zahlen wobei wir kein leeres Wort haben möchten und auch keine führende Nullen also 0
- ist eine natürliche Zahl 17 ist eine natürliche Zahl aber nicht 03 5 so legen wir es jetzt einfach mal fest in Analogie zu der Grammatik für natürliche
- Sprachen beginnen wir hier mit einer startvariablen S und gewisse Regeln z.B dürfen wir s durch die ull ersetzen das wird durch diesen fil spezifiziert wir
- dürfen es auch ersetzen durch zZ also zwei neue Variablen Z steht dabei für eine Ziffer außer der Null sod dass wir neun weitere Regeln brauchen die wir
- aber schon in einer Zeile schreiben können z kann ersetzt werden durch 1 kann ersetzt werden durch 2 und so weiter kann ersetzt werden durch 9 das Z
- kann ersetzt werden durch ige Ziffern gefolgt von einem weiteren Z und damit das nicht ewig so weitergeht kann ich das Z auch durch Epsilon ersetzen und
- dann wäre ich in diesem Beispiel auch fertig denn dann sind keine weiteren Variablen übrig durch schrittweises anwenden dieser Regeln kann ich
- schließlich jede beliebige natürliche dezimalgeschriebene Zahl erzeugen das Prinzip haben Sie wahrscheinlich auf Anhieb erfasst auch wenn sie das noch
- gar nicht kannten wir benötigen aber auch eine saubere mathematische Formalisierung damit immer klar ist welche Wörter erzeugt werden und welche
- nicht das Erzeugen eines Wortes geschieht durch eine schrittweise Ableitung jeder ableitungsschritt wird durch einen rechtsfil mit doppeltem
- Strich dargestellt so wird aus S eben zZ das erste Z kann ich durch 4 ersetzen daraus wird also 4Z dann kann ich eine weitere Regel anwenden die aus z2z macht
- und ich erhalte 42z schließlich kann ich z durch ersetzen und erhalte 42 oder eben die natürliche Zahl 42 und bin fertig denn
- es gibt keine weiteren Variablen mehr die erste Regel kann ich auch verwenden um direkt aus S eine Null zu machen und erhalte die Zahl 0 in ihrer dezimalen
- Darstellung und genauso kann ich in drei Schritten aus der startvariablen S die Zahl 7 erhalten das möchten wir nun genauer formalisieren eine Grammatik ist
- ein viertupel bestehend aus einer Menge V von Variablen die darf nicht leer sein wir brauchen ein Alphabet Sigma das enthält die Zeichen aus denen später die
- Wörter Zusam gesetzt sind die werden nicht weiter ersetzt deswegen nennen wir sie auch terminalzeichen oder kurz terminale eine Menge P die enthält diese
- Regeln mit der wir aus einem Zwischenstand den nächsten Zwischenstand oder das Finale Wort erzeugen und wir brauchen ja eine startvariable S mit der
- dieser Vorgang beginnt die Schnittmenge aus V und σma ist die leere Menge es muss also immer klar sein ob ein Symbol für eine Variable steht oder für ein
- terminalzeichen das erste Objekt dieses Paares steht dann auf der linken Seite vom PIL und das kann eben aus Variablen aber auch aus terminalzeichen bestehen
- insgesamt darf es aber nicht leer sein also nicht das leere Wort darstellen auf der rechten Seite haben wir dann wieder die Möglichkeit Variablen oder
- terminalzeichen zu schreiben oder sogar das Wort Epsilon und alle diese Paare bilden eine Relation die wir mit dieser pfeilschreibweise sehr gut ausdrücken
- können nun definieren wir wie das Ersetzen eines teilwortes durch etwas anderes abläuft für zwei Wörter u und v die jeweils aus Variablen und
- terminalzeichen bestehen oder auch einer Mischung daraus also aus u kann V abgeleitet werden falls sowohl u als auch V ein Präfix und ein Postfix
- enthält und dieser mittlere Teil einer Regel aus der Grammatik entspricht der Präfix heißt hier x der Postfix heißt z und in der Mitte ist ein Y das wir durch
- y Strich ersetzen dabei Mitte bitte nicht wörtlich nehmen X oder z kann sogar leer sein sodass wir natürlich auch ganz am Anfang oder ganz am Ende
- etwas ersetzen können aber es wird eben eine Regel benötigt die uns erlaubt y durch y STR zu ersetzen und so erhalten wir ein neues Wort was möglicherweise
- immer noch Variablen enthält oder vielleicht auch nur noch aus terminalen besteht nun können wir definieren dass wenn wir eine solche Folge haben von
- Ableitungen von einem Wort seinem Nachfolger wieder seinem Nachfolger und so weiter bis zum endenwt dann haben wir eine Ableitung von W
- zu WN und die von einer Grammatik erzeugte Sprache sind eben alle Wörter die nur noch aus terminalzeichen bestehen also aus σma Stern sind und die
- von der startvariablen abgeleitet werden können es muss also irgendeine Ableitung existieren wohl gemerkt wenn ein abgeleitetes Wort noch Variablen enthält
- gehört es nicht zur erzeugten Sprache hier nun ein anderes Beispiel das zeigt wie praktisch Grammatiken sind wir können damit die Menge aller korrekt
- geklammerten Terme mit den vier Grundrechenarten erzeugen auch das ist eine Sprache und für die gibt es übrigens keinen endlichen Automaten oder
- kein regulären Ausdruck der diese Sprache spezifizieren würde wir haben nur zwei Variablen die startvariable heißt hier e für Expression und die
- zweite Variable schreiben wir OP in spitzenklammern das steht für Operation und unsere terminalsymbole bestehen aus einem kleinen a den beiden
- klammersymbolen und den vier Grundrechenarten hier geschrieben plus minus Stern für mal und Slash für geteilt durch dann kommen noch die
- Regeln und E wird als startvariable festgelegt nur als Hinweis das kleine a steht dann gedanklich für beliebige Zahlen oder auch andere Variablen in
- mathematischer Notation wir halten das hier einfach damit das Beispiel überschaubar bleibt die Regeln sehen nur vor dass die startvariable e ersetzt
- werden kann durch ein kleines a oder auch durch einen Ausdruck e Operation e oder durch ein geklammertes E die operations variable können wir ersetzen
- durch die vier Symbole unserer Grundrechenarten wir führen no gleich eine Konvention ein damit die Regeln sehr kurz geschrieben werden können wenn
- auf der linken Seite sich die Variable wiederholt können wir einfach auf der rechten Seite mit einem senkrechten Strich die alternativen aufführen das
- ist eine gewisse Ähnlichkeit zu diesem alternativsymbol bei regulären Ausdrücken so lässt sich die Menge der Regeln so schreiben wie man es unten
- rechts sieht ein mögliches erzeugtes Wort aus der Sprache sehen Sie oben rechts so kann ich A + A in Klammern mal nehmen mit A- a in Klammern und das kann
- geteilt werden durch ein doppelt geklammertes a dieses Wort gehört zur erzeugten Sprache und wir erkennen auch recht schnell dass zu jeder geöffneten
- Klammer auch eine geschlossene Klammer existiert die Anzahl stimmt überein und auch die Reihenfolge ist korrekt das liegt daran dass diese Grammatik es
- vorsieht dass Klammer nur dann in ein Wort eingetragen werden wenn sie gleich paarweise vorkommen wir zeigen nun einmal etwas ausführlich die
- ableitungsschritte für diese Grammatik um das erzeugte Wort aus dem Beispiel zu erzeugen wir können aus e unmittelbar ableiten e ob e daraus e ob e ob e
- daraus geklammert e ob e ob e dann können wir das erste e und anschließend das zweite e durch ein a ersetzt und auch die erste Operation anschließen
- durch ein Plus ersetzen dann wird die zweite Operation durch das Sternsymbol für Multiplikation ersetzt und das geht so weiter bis nach einer Folge von
- Schritten schließlich das zu erzeugende Wort abgeleitet ist hier nur ein paar prägnante kurze Beispiele wir wollen die Sprache erzeugen die aus a hoch I b hoch
- K mit jeweils positiven i und K besteht also z.B aabbb oder AAB das können wir mit diesen fünf Regeln erledigen die wir in drei Zeilen schreiben können und zwar
- darf man groß s durch groß ab ersetzen man darf das große a durch ein kleines a ersetzen oder durch ein kleines a gefolgt von einem großen a und auch das
- B dürfen wir durch ein kleines B oder ein kleines B gefolgt von einem großen B ersetzen hier greift auch eine weitere Konvention soweit wir nichts anderes
- festlegen sind große Buchstaben immer Variablen und kleine Buchstaben immer terminale also aus σma mit dieser einfachen Festlegung vermeiden wir es
- dass wir immer eine Menge von Variablen explizit angeben müssen hier sind die variabelen also s A und B in Großbuchstaben und nun können wir die
- Grammatik anwenden aus S abgeleitet werden groß ab B daraus klein a gro B daraus klein a klein B groß B und daraus schließlich klein a klein B klein B und
- wir erhalten ein Wort was nur noch aus terminalen besteht dieses Wort gehört also zur Sprache die von der Grammatik erzeugt wird und noch ein bisschen hin
- und her überlegen erkennt man auch schnell dass genau die Sprache erzeugt wird die oben angegeben wurde also alle Wörter die mindestens ein A und
- mindestens ein B enthalten und sortiert sind im zweiten Beispiel haben wir nun eine Teilmenge aus dem ersten Beispiel auch diese Wörter bestehen aus a und aus
- BS aber es müssen immer gleich viele a und BS sein das geht sogar mit einer Grammatik die aus nur zwei Regeln besteht so können wir s direkt ersetzen
- durch das Wort ab oder durch a groß s B weil durch wiederholtes Anwenden der zweiten Regel wächst immer links vom s ein kleines a und rechts vom s ein
- kleines B sodass die gesamtanz Zahl der A und BS gleich bleibt wenden wir die zweite Regel zweimal und danach die erste Regel an erhalten wir das Wort
- AAA BBB bei Grammatiken werden verschiedene Typen unterschieden wir sprechen von der komsk hierierarchie Typ 0 Typ 1 Typ 2 Typ 3 die bisherigen
- Beispiele waren sogenannte kontextfreie oder Typ 2 Grammatiken diese spielen auch die größte Rolle in der Informatik eine Grammatik heißt dabei kontextfrei
- wenn eine Einschränkung erfüllt ist so dürfen auf der linken Seite der Regeln nur einzelne Variablen stehen ich ersetze also später immer eine Variable
- durch etwas anderes die Variable hat also keinen Kontext und kann an jeder Stelle so ersetzt werden und das ist der Grund für diese Benennung aber wir
- dürfen natürlich auch Grammatiken definieren die einen Kontext berücksichtigen z.B so eine Regel haben dass ein großes a nur dann durch ein
- kleines a setzt werden kann wenn links vom großen a bereits ein kleines a steht oder auch das variable CB umsortiert werden können wenn sie in der
- Reihenfolge nebeneinander stehen solche nichtkontextfreien Grammatiken sind dann vom Typ Null oder vom Typ 1 was diese beiden Typen dann noch unterscheidet
- behandeln wir aber heute nicht wir können die kontextfreien Grammatiken noch weiter einschränken wenn wir auf der rechten Seite nur erlauben dass dort
- entweder das leere Wort steht oder nur terminalsymbole stehen oder nur terminalsymbole stehen gefolgt von einer einzigen Variablen sie können sich das
- dann so vorstellen dass das zu erzeugen Wort dann von links nach rechts wächst weil immer ganz rechts eine Variable ersetzt wird bis nur noch
- terminalzeichen da sind mit dieser Einschränkung können nur noch reguläre Sprachen erzeugt werden deswegen nennen wir diese Grammatiken auch reguläre
- Grammatiken es gilt auch die Umkehrung das heißt zu jeder regulären Sprache gibt es eine reguläre Grammatik die diese erzeugt für die kontextfreien
- Grammatiken die wie bereits erwähnt eine wichtige Rolle in der Informatik stehen gibt es noch besondere maschinenlesbare Schreibweisen z.B die bakusnuer Form
- diese kann verwendet werden um die Syntax von Programmiersprachen festzulegen hier schreibt man anstatt eines Pfeiles beispielsweise die Zeichen
- doppelpt doppelpkt gleich sie sehen h ein Beispiel für die syntaxdefinition einer Postanschrift in bakusnauerform neben der bakusnauerform
- BNF gibt es auch die ebnf die erweiterte bakusnauerform die einige Erleichterungen enthält so kann ich mit geschweiften Klammern dort beliebig
- viele Wiederholungen spezifizieren und sie sehen hier eine ebnf Darstellung der Sprache der ganzen Zahlen hier noch mit optionalem Minuszeichen als
- brefix es folgt nun ein kleiner Übungsteil sie können das Video wieder anhalten bevor die Lösung eingeblendet wird das müssen sie dann tun bevor die
- Zahlen 1 2 3 über den Bildschirm gelaufen sind in der Aufgabe sollen sie nun selbst eine Grammatik angeben und zwar zur Erzeugung der Sprache aller
- Wörter über ab die genau ein a enthalten sie haben nun Gelegenheit über die Lösung nachzudenken und hier ist eine mögliche Lösung eine Grammatik mit drei
- Regeln aus der startvariable S kann groß B KLE a groß B werden groß B ist also eine Variable und aus Groß B kann klein B groß B oder EPS werden und so wird
- erzwungen dass genau ein a enthalten ist und links und rechts davon eine beliebige Anzahl BS möglich wird es gibt aber viele andere Lösungen gut möglich
- dass sie eine korrekte Lösung haben die sich deutlich von dieser unterscheidet nun sollen sie einmal eine Grammatik selbst lesen und die Sprache
- bestimmen die von dieser Grammatik erzeugt wird und die Sprache schreiben Sie bitte schön sauber in intentionaler Schreibweise auf die Grammatik besteht
- aus vier Regeln aus der startvariable S kann B0 B oder 0 werden mit einer variablen B und aus B kann 1 b oder 1 werden und nun folgt auch schon die
- Lösung die Sprache besteht offenbar aus bitstrings also aus Wörtern die nur aus Nullen und Einsen bestehen und entweder wir erhalten das Wort ull oder wir
- erhalten ein Wort was genau eine Null enthält wobei links und rechts davon mindestens eine 1 steht das können wir intentional aufschreiben die Sprache
- besteht aus allen 1 hoch i 0 1 hoch K aus der Menge der Wörter über 01 wobei i und K größer 0 sind oder beide gleich n0 sind letzteres brauchen wir für den
- Sonderfall dass wir genau die Null erzeugen aber wohl gemerkt das Wort 10 oder 01 gehört nicht zur erzeugten Sprache wir können hier nämlich links
- von der Null nur dann eine ein erzeugen wenn wir auch rechts von der Null eine ein erzeugen das war auch schon die letzte
- Übungsaufgabe und das Ende des Lehrvideos ist erreicht ich hoffe ich konnte zu ihrem Verständnis von Grammatiken formaler Sprachen beitragen
- vielleicht sehen wir uns schon bald wieder bei einem weiteren Lehrvideo aus der Reihe Grundlagen der Informatik bis dahin verabschiede ich mich auf
- wiederschauen [Musik]
Zum Nachlesen
Formale GrammatikFormale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.
Chomsky-HierarchieSie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …
Kontextfreie GrammatikIn der Theorie der formalen Sprachen ist eine kontextfreie Grammatik (englisch context-free grammar, CFG) eine formale Grammatik, die nur solche …
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 …