Reguläre und kontextfreie Sprachen
Christian Spannagel
https://www.youtube.com/watch?v=TjuGaawXTbQ

Transkript (automatisch erstellt)

0:11 so ich würde gerne mal zwei m Aufgaben rausgreifen ja zur Erzeugung von Z zur Angabe von Grammatiken die vorgegebene Sprachen erzeugen weil man
0:24 an diesen Beispielen sehr viel verstehen kann hinsichtlich des Unterschieds zwischen regul Sprachen oder regulären Grammatiken und
0:33 kontextfreien Sprachen kontextfreien Grammatiken so nehmen wir erst mal die erste Sprache hier oben und zwar nehmen wir mal na
0:45 L1 ist GLE die Menge aller a hoch m B hoch n mit mn grö= 1 ja so das ist eine relativ einfache Sprache noch wenn man
1:04 da ja bisschen überlegt findet man relativ schnell eine Grammatik gucken un aber trotzdem an welche Wörter sind in der Sprache also beispielsweise das
1:14 einfachste Wort das man bilden kann ist ab genau so ab ne oder a ab oder ab b b b oder a a b b ganz
1:34 egal wie viele a und wie viele BS Hauptsache mindestens eins von jedem und erst kommen alle a dann kommen alle BS so jetzt machen wir eine Grammatik und
1:47 mit Grammatik meine ich es genügt jetzt mal die Produktionsregeln hinzuschreiben okay eigentlich müsste ich noch die variablenmenge etc P Sigma hinschreiben
1:55 und so aber für uns reicht es mal Produktionssystem okay beginnen wir mit einer startvariablen S wohin würd man die
2:17 ableiten was würden Sie vorschlagen ja klein a groß a können wir machen ne
2:27 wir erzeugen erstmal das kleine a also a brauchen wir mindestens und dann groß a wofür brauchen wir groß a
2:42 jetzt genau erstmal benutzen wir das doch um weitere as zu erzeugen ne also wir können jetzt hier beliebig viele weitere as
2:50 erzeugen oder klein a groß B genau so und das B benutzen wir
3:13 wie mhm genau
3:22 so ging es noch kürzer wie denn diei genau wir könnten noch a als startvariable nehmen mache ich jetzt mal
3:34 nicht zeig ih auch gleich warum also wir könnte auch einfach mit Al stad variable beginnen und die die die Regel hier oben weglassen da kann ich trotzdem ein
3:44 kleines a und dann beliebig viele BS erzeugen oder erstmal beliebig viele a mindestens eins und dann auf B übergehen okay so welcher von welchem Typ ist
3:54 diese Grammatik ja genau das ist eine reguläre Grammatik ja sie hat nur Regeln der Form
4:10 terminalsymbol und variable also terminalsymbol nicht terminalsymbol oder nur ein einzelnes terminalsymbol das heißt das ist der
4:19 speziellste Typ von Grammatik der geht jatim Kön wirugen nurter die mit AA Anfang im Moment weil die oh sie haben
4:33 recht genau richtig ja ah s haben recht sogar falsch ne wir erzeugen nur Wörter mit AA okay wir könnten es hier oben noch ab
4:44 erzeugen aber das auch blödsin also machen wir mal weg machen wir so ne okay gut jetzt sind wir richtig okay
4:56 stattviable a wir hatten ein a zu viel sehr gut okay gut trotzdem reguläre Grammatik ne okay jetzt leiten wir mal ein Wort ab
5:09 also a ist unsere startvariable leiten wir mal ein Wort ab nehmen wir mal wir wollen mal dieses Wort hier ableiten
5:17 AA AAB BBB okay dieses Wort a a BBB wollen wir mal ableiten womit beginnen wir mit der startvariable
5:30 so welche Regel wenden wir jetzt an genau klein a groß a und dann als nächsten
5:56 Schritt KLE a KLE a groß B also dieses a wird abgeleitet zu ab ne dieses a leite ich ab zu
6:07 ab okay und dann genau jetzt wenn ich diese Regel so oft an bis ich fast so viele BS hab
6:19 gerne hätte wie ich haben möchte a a b BB und am Schluss ersetze ich
6:30 die Variable noch durch das kleine B hier und dann bin ich fertig okay lass wir mal so stehen jetzt gucken wir uns die zweite Grammatik an
6:49 die ich gerne mal zweite Sprache erstmal die ich gerne mir anschauen würde und was ist die folgende
6:55 L2 a hoch n B hoch n mit n größer = 1 also wodurch unterscheidet sich diese Sprache von der Sprache
7:20 L1 also das W aus derache ein nur die ander genau wir nehmen die Wörter raus aus L1 wo nur die wo die Anzahl der A und BS
7:35 gleich groß ist genau also ab a a BB a a a b b b und so weiter ne nur gleich viele a und gleich viele BS so machen wir mal eine
7:50 Grammatik und jetzt schreiben wir nur die Produktionsregeln hin ja können wir wieder mit a anfangen ne von mir aus egal
8:00 wohin leiten wir das ab ja klein a groß a und dann klein groß B genau ja super ne kürzer geht's nicht jetzt kann ich die startvariable zu ab
8:19 ableiten sie haben sogar die Regel ver vermieten sehr schön ja K klein ab ableiten oder siezeugen erstmal beliebig viele a und BS am
8:30 und dann der Mitte das ab jetzt leiten wir mal folgendes ab machen wir mal leiten wir mal das hier ab a AAB BBB wie würde diese Ableitung Aussehen a geht
8:40 zunächst mal nach na ja ist klar ne klein a groß a b klein B als nächstes wird die Regel noch mal angewendet klein a dann kriege ich klein
8:52 a groß a klein B für das A und das kleine B am Rande nicht vergessen das hatten wir ja auch schon erzeugt vorher und jetzt schließe
9:01 ich ab mit dem letzten ab kann ja so beliebig viele a und BS von außen nach innen Schachteln klein a klein a klein a klein B klein B klein B
9:13 so von welchem Typ ist diese Grammatik ja
9:25 fast wie sieht uns wie sind unsere Regeln aus auf der Link nee kontextfrei genau auf der linken Seite von Regeln steht immer nur eine
9:36 Variable ich habe zwei Regeln a geht nach AAB oder a geht nach Klein ab so das sind zwei Regeln und links steht immer nur eine Variable das heißt
9:49 kontextfrei wenn jetzt hier links noch was stehen würde noch was anderes mehr als eine Variable dann wä es kontextsensitiv okay
10:01 kriege ich für diese Sprache eine reguläre grammatikin das Ziel ist jetzt ein Feeling hinzubekommen ja für Unterschied
10:20 zwischen regulär und kontextfrei ich krieg sie hab recht Krieg keine reguläre Grammatik hin ich kann die Sprache L2 nicht mit einer en
10:29 Grammatik erzeugen warum nicht wir schauen uns mal die Ableitung hier an bei L1 das war eine reguläre
10:42 Grammatik ne die hat nur die Form klein a groß a also Terminal variable oder nur Terminal so sieht eine Ableitung aus was ist das
10:52 Charakteristikum einer Ableitung bei einer regulären Grammatik ja
11:01 genau die Variable steht immer am Ende geht gar nicht anders ja sie haben eine Variable die leiten sie immer ab nach kleinbchstabe und große variable
11:14 und jetzt können Sie im nächsten Schritt diese Variable wieder ableiten nach nach terminalsymbo und variable sie haben nirgendwo den Fall wo variable und
11:23 terminalsymbol abgeleitet wird dann wäre die Variable irgendwann mal in der Mitte hier die ist immer am Ende ne sie können diese Variable nehmen und ersetzen aber
11:31 Sie können es immer nur durch irgendwas ersetzen wo die Variable wieder hinten steht und zwar in jedem Schritt kommt ein terminalsymbol dazu und dann bleibt
11:42 die Variable weiter hinten solangee bis sie die Variable durch ein einzelnes terminalsymbol ersetzen das ist der Abschluss der Ableitung
11:50 dann deswegen sagt man dazu reguläre Grammatik ja weil sozusagen eine gewisse Regelmäßigkeit auch hier in der Ableitung vorhanden ist geht gar nicht
12:01 anders als dass die Variable immer am Ende ist warum können Sie mit einer regulären Grammatik nicht die Sprache L2
12:20 erzeugen ja ja gut sie bauen hier das Wort von der Mitte auf müsste aber nicht sein ne
12:29 warum kann man das nicht von vorne aufbauen was würde denn passieren wenn ich jetzt anfange ich will 3 a und 3 BS
12:45 machen ich hät eine reguläre Grammatik ja genau man weiß nicht wenn man wenn man die dre a erzeugt hat von vorne ja
12:55 die Variable ist ja immer hinten wenn ich die dre a erzeugt habe also angenommen h jetzt hier irgendeine reguläre Grammatik ne da würde ich jetzt
13:03 hier erstmal AA erzeugen dann noch mal AAA dann noch mal a a a dann vielleicht B ne jetzt muss ich doch wissen wie viele
13:15 BS ich noch ableiten darf aber das kriege ich nicht reinodiert in die reguläre Grammatik ich weiß nicht ich kann jetzt immer nur ein ein Buchstabe
13:23 weitere variable ableiten regulären Grammatik aber jetzt kommt ich habe kein Gedächtnis
13:31 wie viele as ich schon abgeleitet habe was ich überhaupt schon gemacht habe keine Ahnung ich denke nur lokal da hinten an am am am
13:42 Ende das heißt ich kriege keine reguläre Grammatik hin für diese Sprache das heißt die Sprache ist definitiv nicht regulär die ist kontextfrei ich krieg
13:51 nur kontextfreie grammatikin so jetzt zum Abschluss noch sind gleich fertig Zusammenhang hier oben hierfür haben wir schon mal einen
14:02 Automaten konstruiert ne einen deterministischen Automaten wie könnte der Aussehen der die Sprache erzeugt Steig wir mal hier jetzt haben wir so
14:10 ein Anfangszustand q0 ich lese ein
14:17 a jetzt gehe ich den nächsten Zustand den nenne ich jetzt mal ach komm den nenne ich mal
14:25 a jetzt kann ich beliebig viele A's lesen klein a und komme wieder in den großzustand groß a also kommen Zustand groß a lesen kleines a kommen in Groß a
14:35 lesen kleines a kommen in Groß a so es ist nicht ganz analog na macht aber nichts jetzt lese ich
14:50 hier klein mit dem kleinen B komme ich in Groß B ne das kann man noch analoger machen okay so
14:59 jetzt lese ich mit dem klein B komme ich in großzustand Groß B ja jetzt kann ich hier mit klein B groß B weiterhin lesen lesen lesen und am Ende bin ich jeem
15:12 nzustand sehen Sie den Zusammenhang zwischen dem deterministischen Automaten und der regulären Grammatik ich lese immer ein Zeichen und bin in dem Zustand
15:24 den man sozusagen als Variable interpretieren könnte ne so dann lese ich immer wieder Zeichen Zeichen Zeichen Zeichen habe kein Gedächtnis was ich
15:33 bislang gemacht habe ich lese Zeichen für Zeichen ich arbeite das Wort von vorne her ab genauso wie ich bei der regulären Grammatik das Wort von vorne
15:42 her erzeuge und ich kann genauso wenig diese Sprache hier durch eine reguläre Grammatik erzeugen wie durch einen
15:55 deterministischen Automaten erkennen wir hatten auch festgestellt a hoch n B hoch n kann ich nicht durch den deterministischen Automaten erkennen
16:03 weil wenn ich die ersten as erkannt habe bin ich in irgendeinem Zustand oder weiß ich gar nicht wie viel BS mus ich noch erkennen das
16:12 heißt das hängt ganz eng zusammen die regulären Sprachen und die deterministischen Automaten und die regulären
16:20 Grammatiken reguläre Sprachen sind diejenigen die von regulären Grammatiken erzeugt werden ne das ist reguläre Sprache die wird von regulären Grammatik
16:28 erzeugt die regulären Sprachen sind genau die Sprachen die auch von deterministischen Automaten erkannt werden
16:41 können habe ich eine Sprache die nicht regulär ist wie diese hier kann ich sie nicht durch einenerministischen endlichen Automaten erkennen und ich
16:49 kann sie auch nicht durch eine reguläre Grammatik erzeugen das heißt deterministische Automaten hängen ganz eng zusammen mit
16:56 regulären Sprachen und regulären Grammatiken wenn ich von hier nach da gehe wenn ich von hier nach da gehe in die Welt der
17:03 kontextfreien Sprachen brauche ich ein Gedächtnis ich muss ein Gedächtnis zu meinem Automaten hinzufügen und das werden oder zu meiner Grammatik
17:15 hinzufügen letztlich habe ich das Gedächtnis dadurch hinzugefügt dass jetzt m von außen nach innen arbeite oder ich brauche ein Automaten der ein
17:21 extra Gedächtnis hat der sich gemerkt hat was schon alles passiert ist und das sind die kellerautomaten damit beschäftigen wir uns dann nach der
17:29 exkursionswoche