Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Reguläre und kontextfreie Sprachen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 90 Zeilen
- 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
- an diesen Beispielen sehr viel verstehen kann hinsichtlich des Unterschieds zwischen regul Sprachen oder regulären Grammatiken und
- kontextfreien Sprachen kontextfreien Grammatiken so nehmen wir erst mal die erste Sprache hier oben und zwar nehmen wir mal na
- 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
- 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
- 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
- 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
- mit Grammatik meine ich es genügt jetzt mal die Produktionsregeln hinzuschreiben okay eigentlich müsste ich noch die variablenmenge etc P Sigma hinschreiben
- und so aber für uns reicht es mal Produktionssystem okay beginnen wir mit einer startvariablen S wohin würd man die
- ableiten was würden Sie vorschlagen ja klein a groß a können wir machen ne
- wir erzeugen erstmal das kleine a also a brauchen wir mindestens und dann groß a wofür brauchen wir groß a
- jetzt genau erstmal benutzen wir das doch um weitere as zu erzeugen ne also wir können jetzt hier beliebig viele weitere as
- erzeugen oder klein a groß B genau so und das B benutzen wir
- wie mhm genau
- so ging es noch kürzer wie denn diei genau wir könnten noch a als startvariable nehmen mache ich jetzt mal
- 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
- 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
- diese Grammatik ja genau das ist eine reguläre Grammatik ja sie hat nur Regeln der Form
- terminalsymbol und variable also terminalsymbol nicht terminalsymbol oder nur ein einzelnes terminalsymbol das heißt das ist der
- speziellste Typ von Grammatik der geht jatim Kön wirugen nurter die mit AA Anfang im Moment weil die oh sie haben
- 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
- erzeugen aber das auch blödsin also machen wir mal weg machen wir so ne okay gut jetzt sind wir richtig okay
- 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
- also a ist unsere startvariable leiten wir mal ein Wort ab nehmen wir mal wir wollen mal dieses Wort hier ableiten
- AA AAB BBB okay dieses Wort a a BBB wollen wir mal ableiten womit beginnen wir mit der startvariable
- so welche Regel wenden wir jetzt an genau klein a groß a und dann als nächsten
- Schritt KLE a KLE a groß B also dieses a wird abgeleitet zu ab ne dieses a leite ich ab zu
- ab okay und dann genau jetzt wenn ich diese Regel so oft an bis ich fast so viele BS hab
- gerne hätte wie ich haben möchte a a b BB und am Schluss ersetze ich
- 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
- die ich gerne mal zweite Sprache erstmal die ich gerne mir anschauen würde und was ist die folgende
- L2 a hoch n B hoch n mit n größer = 1 also wodurch unterscheidet sich diese Sprache von der Sprache
- 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
- 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
- Grammatik und jetzt schreiben wir nur die Produktionsregeln hin ja können wir wieder mit a anfangen ne von mir aus egal
- 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
- 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
- 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
- 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
- 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
- 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
- so von welchem Typ ist diese Grammatik ja
- 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
- 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
- kontextfrei wenn jetzt hier links noch was stehen würde noch was anderes mehr als eine Variable dann wä es kontextsensitiv okay
- kriege ich für diese Sprache eine reguläre grammatikin das Ziel ist jetzt ein Feeling hinzubekommen ja für Unterschied
- 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
- Grammatik erzeugen warum nicht wir schauen uns mal die Ableitung hier an bei L1 das war eine reguläre
- 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
- Charakteristikum einer Ableitung bei einer regulären Grammatik ja
- 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
- 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
- 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
- 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
- die Variable weiter hinten solangee bis sie die Variable durch ein einzelnes terminalsymbol ersetzen das ist der Abschluss der Ableitung
- 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
- anders als dass die Variable immer am Ende ist warum können Sie mit einer regulären Grammatik nicht die Sprache L2
- erzeugen ja ja gut sie bauen hier das Wort von der Mitte auf müsste aber nicht sein ne
- warum kann man das nicht von vorne aufbauen was würde denn passieren wenn ich jetzt anfange ich will 3 a und 3 BS
- 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
- 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
- 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
- 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
- weitere variable ableiten regulären Grammatik aber jetzt kommt ich habe kein Gedächtnis
- 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
- 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
- nur kontextfreie grammatikin so jetzt zum Abschluss noch sind gleich fertig Zusammenhang hier oben hierfür haben wir schon mal einen
- Automaten konstruiert ne einen deterministischen Automaten wie könnte der Aussehen der die Sprache erzeugt Steig wir mal hier jetzt haben wir so
- ein Anfangszustand q0 ich lese ein
- a jetzt gehe ich den nächsten Zustand den nenne ich jetzt mal ach komm den nenne ich mal
- 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
- lesen kleines a kommen in Groß a so es ist nicht ganz analog na macht aber nichts jetzt lese ich
- hier klein mit dem kleinen B komme ich in Groß B ne das kann man noch analoger machen okay so
- 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
- nzustand sehen Sie den Zusammenhang zwischen dem deterministischen Automaten und der regulären Grammatik ich lese immer ein Zeichen und bin in dem Zustand
- 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
- 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
- her erzeuge und ich kann genauso wenig diese Sprache hier durch eine reguläre Grammatik erzeugen wie durch einen
- deterministischen Automaten erkennen wir hatten auch festgestellt a hoch n B hoch n kann ich nicht durch den deterministischen Automaten erkennen
- 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
- heißt das hängt ganz eng zusammen die regulären Sprachen und die deterministischen Automaten und die regulären
- 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
- erzeugt die regulären Sprachen sind genau die Sprachen die auch von deterministischen Automaten erkannt werden
- 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
- kann sie auch nicht durch eine reguläre Grammatik erzeugen das heißt deterministische Automaten hängen ganz eng zusammen mit
- 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
- kontextfreien Sprachen brauche ich ein Gedächtnis ich muss ein Gedächtnis zu meinem Automaten hinzufügen und das werden oder zu meiner Grammatik
- 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
- 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
- exkursionswoche
Zum Nachlesen
Kontextfreie SpracheKontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären …
Lineare Sprache... Informatik. So sind sie hier speziell eine Klasse formaler Sprachen und stellen dabei eine echte Teilklasse der Typ-2-Sprachen der Chomsky-Hierarchie dar.
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 …
Chomsky-HierarchieSie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …