Grundlagen der Informatik, Lehrvideo; Grammatiken formaler Sprachen - mit Übungsteil
Ulrich Greveler
https://www.youtube.com/watch?v=kwPkwLzB_us

Transkript (automatisch erstellt)

0:00 [Musik] hallo liebe Zielgruppe ich begrüße Sie zu einem weiteren Lehrvideo aus der
0:11 Reihe Grundlagen der Informatik heute zum Thema Grammatiken es geht um Grammatiken für formale Sprachen wir abstrahieren also
0:21 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
0:30 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
0:41 studiere schreibe und es gibt ein beliebiges Objekt z.B Informatik und so wird ein Satz gebildet ich studiere informatikkt wir haben hier gleich
0:50 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
1:00 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
1:09 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
1:18 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
1:28 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
1:39 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
1:49 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
1:58 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
2:07 dann wäre ich in diesem Beispiel auch fertig denn dann sind keine weiteren Variablen übrig durch schrittweises anwenden dieser Regeln kann ich
2:14 schließlich jede beliebige natürliche dezimalgeschriebene Zahl erzeugen das Prinzip haben Sie wahrscheinlich auf Anhieb erfasst auch wenn sie das noch
2:22 gar nicht kannten wir benötigen aber auch eine saubere mathematische Formalisierung damit immer klar ist welche Wörter erzeugt werden und welche
2:30 nicht das Erzeugen eines Wortes geschieht durch eine schrittweise Ableitung jeder ableitungsschritt wird durch einen rechtsfil mit doppeltem
2:37 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
2:50 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
2:59 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
3:08 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
3:17 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
3:28 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
3:37 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
3:46 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
3:56 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
4:05 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
4:13 terminalzeichen zu schreiben oder sogar das Wort Epsilon und alle diese Paare bilden eine Relation die wir mit dieser pfeilschreibweise sehr gut ausdrücken
4:22 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
4:32 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
4:44 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
4:54 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
5:03 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
5:12 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
5:20 Ableitungen von einem Wort seinem Nachfolger wieder seinem Nachfolger und so weiter bis zum endenwt dann haben wir eine Ableitung von W
5:30 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
5:39 von der startvariablen abgeleitet werden können es muss also irgendeine Ableitung existieren wohl gemerkt wenn ein abgeleitetes Wort noch Variablen enthält
5:50 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
5:59 geklammerten Terme mit den vier Grundrechenarten erzeugen auch das ist eine Sprache und für die gibt es übrigens keinen endlichen Automaten oder
6:06 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
6:16 zweite Variable schreiben wir OP in spitzenklammern das steht für Operation und unsere terminalsymbole bestehen aus einem kleinen a den beiden
6:25 klammersymbolen und den vier Grundrechenarten hier geschrieben plus minus Stern für mal und Slash für geteilt durch dann kommen noch die
6:33 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
6:42 mathematischer Notation wir halten das hier einfach damit das Beispiel überschaubar bleibt die Regeln sehen nur vor dass die startvariable e ersetzt
6:51 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
7:01 durch die vier Symbole unserer Grundrechenarten wir führen no gleich eine Konvention ein damit die Regeln sehr kurz geschrieben werden können wenn
7:08 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
7:17 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
7:24 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
7:34 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
7:43 Klammer auch eine geschlossene Klammer existiert die Anzahl stimmt überein und auch die Reihenfolge ist korrekt das liegt daran dass diese Grammatik es
7:51 vorsieht dass Klammer nur dann in ein Wort eingetragen werden wenn sie gleich paarweise vorkommen wir zeigen nun einmal etwas ausführlich die
7:59 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
8:10 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
8:19 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
8:28 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
8:38 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
8:50 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
8:59 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
9:08 festlegen sind große Buchstaben immer Variablen und kleine Buchstaben immer terminale also aus σma mit dieser einfachen Festlegung vermeiden wir es
9:19 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
9:27 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
9:40 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
9:48 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
9:57 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
10:07 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
10:16 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
10:26 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
10:36 AAA BBB bei Grammatiken werden verschiedene Typen unterschieden wir sprechen von der komsk hierierarchie Typ 0 Typ 1 Typ 2 Typ 3 die bisherigen
10:47 Beispiele waren sogenannte kontextfreie oder Typ 2 Grammatiken diese spielen auch die größte Rolle in der Informatik eine Grammatik heißt dabei kontextfrei
10:56 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
11:06 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
11:15 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
11:22 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
11:31 Reihenfolge nebeneinander stehen solche nichtkontextfreien Grammatiken sind dann vom Typ Null oder vom Typ 1 was diese beiden Typen dann noch unterscheidet
11:40 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
11:47 entweder das leere Wort steht oder nur terminalsymbole stehen oder nur terminalsymbole stehen gefolgt von einer einzigen Variablen sie können sich das
11:57 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
12:05 terminalzeichen da sind mit dieser Einschränkung können nur noch reguläre Sprachen erzeugt werden deswegen nennen wir diese Grammatiken auch reguläre
12:14 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
12:24 Grammatiken die wie bereits erwähnt eine wichtige Rolle in der Informatik stehen gibt es noch besondere maschinenlesbare Schreibweisen z.B die bakusnuer Form
12:34 diese kann verwendet werden um die Syntax von Programmiersprachen festzulegen hier schreibt man anstatt eines Pfeiles beispielsweise die Zeichen
12:42 doppelpt doppelpkt gleich sie sehen h ein Beispiel für die syntaxdefinition einer Postanschrift in bakusnauerform neben der bakusnauerform
12:51 BNF gibt es auch die ebnf die erweiterte bakusnauerform die einige Erleichterungen enthält so kann ich mit geschweiften Klammern dort beliebig
13:01 viele Wiederholungen spezifizieren und sie sehen hier eine ebnf Darstellung der Sprache der ganzen Zahlen hier noch mit optionalem Minuszeichen als
13:13 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
13:21 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
13:32 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
13:42 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
13:54 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
14:03 dass sie eine korrekte Lösung haben die sich deutlich von dieser unterscheidet nun sollen sie einmal eine Grammatik selbst lesen und die Sprache
14:11 bestimmen die von dieser Grammatik erzeugt wird und die Sprache schreiben Sie bitte schön sauber in intentionaler Schreibweise auf die Grammatik besteht
14:20 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
14:31 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
14:40 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
14:49 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
15:01 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
15:09 von der Null nur dann eine ein erzeugen wenn wir auch rechts von der Null eine ein erzeugen das war auch schon die letzte
15:18 Übungsaufgabe und das Ende des Lehrvideos ist erreicht ich hoffe ich konnte zu ihrem Verständnis von Grammatiken formaler Sprachen beitragen
15:25 vielleicht sehen wir uns schon bald wieder bei einem weiteren Lehrvideo aus der Reihe Grundlagen der Informatik bis dahin verabschiede ich mich auf
15:32 wiederschauen [Musik]