Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Formale Sprachen: Reguläre Sprache
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 45 Zeilen
- hallo und herzlich willkommen zurück zu diesem neuen video es geht wieder um formale sprachen heute um reguläre sprachen was genau regulärer sprachen
- sind und wie sie sich auch vielleicht von anderen sprachen abgrenzen das gibt es in diesem video los geht's [Musik]
- los geht's und zwar bevor wir richtig einsteigen in den regulären sprachen und damit auch in die formale sprachen wollen wir einmal ganz kurz wissen wie
- sind die eigentlich definiert und zwar gibt es von noam chomsky die chance die hierarchie und die sorgt dafür dass selbst die
- formalen sprachen die ja von den natürlichen sprache irgendwie abgegrenzt sind das haben wir im letzten video kennen gelernt aber die formalen staaten
- untereinander auch noch mal verteilt sind und zwar nicht durch die regeln wie wörter gebildet werden und für uns von interesse sind vor allen
- dingen sprachen vom typ 2 und typ nämlich genau diese beiden also die reguläre sprachen und die kontext frei entspannen die regulären
- sprachen haben eine produktions vorschrift links steht immer ein nicht terminal- und rechts ein einzelnes terminal- oder ein terminal- mit einem
- lichtsignal dann gibt es zwei mögliche grammatiken bei der regulären sprachen nämlich einmal eine links reguläre grammatik und eine rechts
- reguläre grammatik was da genau der unterschied ist das schauen wir uns gleich an ganz wichtig ist aber für euch ja es gibt keinen unterschied aber
- rechts regulär oder links regulär die gleichen wörter können gebildet werden ja also jedes wort das sie mit einer links regulären grammatik bilden kann
- kann ich auch mit einer rechts regulären com artikel ganz viel drüber geredet heute schauen wir uns die regulären sprachen wie
- gesagt an los geht's wie ist eine produktions vorschrift aufgebaut beim regulären dramatik wie wahlrechts regulären grammatik die sieht dann so
- aus und zwar haben wir ein nicht terminal- wird ersetzt durch fc nun also das leere wort ein nicht terminal- wird ersetzt
- durch ein terminal- das ist bei allen gleich bei rechts und links regulär und jetzt kommt der unterschied zwischen rechts und links regulär es kann ein
- nicht terminal- ersetzt wenn durch eine terminalgebäude von einem nicht termin oder beides ja was ist jetzt drängt regulär naja hier steht das nicht
- terminal- rechts vom terminal- das heißt wenn ich jetzt mein board weiter weiter wachsen lasse würde das immer nach rechts hin wachsen
- und bei aller linkshänder martin wäre das halt getauscht der bitte das wort nach links hin wachsen
- lassen der einzige unterschied zwischen einer rechts regulären links regulären grammatik erstmal der der für uns wichtig
- so ein beispiel wir haben ja die leimbacher mit lalelu drei silben kennen wir alles noch die produktionsfläche sah genauso aus
- und diese sprache die wir in den letzten video hatten na ja die hat auf der linken seite immer einen nicht terminal- und auf der rechten seite immer einen
- terminal- gefolgt von einem nicht terminen oder halt nur einen termin damit ist die lautsprache eine rechts reguläre
- reguläre sprache also eine rechts reguläre grammatik aber es stellt sich die frage wann ist denn so eine sprache eigentlich regulär und das kannst du dir
- ganz einfach merken und jetzt kommen wir zurück zur automaten theorie eine sprache ist genau dann regulär wenn es einen gibt der diese sprache erkennt und
- natürlich anders es gibt genau dann ein wenn es eine sprache ist die regulär ist also es ist ein in beide richtung die beziehung das heißt ja wir müssen für
- unsere lang sprachen oder unserem land marken dann auch finden ja also wir haben unsere produktions vorschrift jetzt überlegen wir mal geld
- kann es auch selber kunst das video pausieren an dieser stelle wie würde ich dann den laden alle tomaten sozusagen erstellen vielleicht passiert ja melden
- jetzt hier sonst komplett ist die lösung nämlich genauso ich habe jetzt ein endlich der automaten gefunden ich habe jetzt mehr genommen ja
- das ist mir ein bisschen einfacher zu machen und übersichtlicher der akzeptierte genau das was da auch ansprachen oder antworten akzeptiert
- wird in unserer sprache wichtig der abschluss ist immer ein und wir haben genau 37 aber wie analysiere ich jetzt das wort ich
- würde jetzt das wort love you auf der cd die man eben zu überprüfen und zwar bekommen wir erst als nach wir würden von q 0 den q1 gehen beziehungsweise die
- erste produktions regieren wetten das läge werden von q1 in q2 gehen beziehungsweise unsere zweite produktions regel anwenden das haben wir
- schon letzten video gemacht und dann würden wir beim new von gut 23 gehen beziehungsweise unsere dritte produktions regel anwenden wir hätten
- dann eine zustand vor und wird q 100 123 gute reise endzustand wunderbar funktioniert alles ebenso funktioniert die ableitung drüben man sieht schon
- eine sehr sehr enge verbindung und verzweigung des ganzen und am ende können wir sagen dass die leihe sprache auf jeden fall regulär ist jetzt kommen
- wir mal zurück zum bild vom anfang und zwar das bild wo wir sagen wir haben regulärer sprachen wir haben kontext freisprachen kontextsensitive und rico
- sieht auch zählbar was das genau ist naja da müssen wir noch mal gucken aber wir können auf jeden fall sagen dass eine sprache regulär ist genau dann wenn
- es um der gibt oder näher als der gleiche da können wir schon mal auf jeden fall eine verbindung herstellen wie ist das
- bei den kontext freien da müssen wir noch mal gucken das kommt im nächsten video aber da kann ich nur sagen da gibt es auch einen automaten der genau das
- akzeptiert und den kennen wir schon dann geht es weiter kontextsensitiv wir sind dann linear beschränkte touring maschinen vielleicht
- hast du schon mal von touring maschinen gehört von alan turing wahrscheinlich auf jeden fall und repressiv auf zählbare sind dann touring maschinen die
- der nicht weniger beschränkt sind dass wir den typ einsparen wobei type-0 dann schon eine sehr freie sprache ist was genau kontext frei ist und wann und
- welche automat das akzeptiert das schauen wir uns im nächsten video an hast du erst mal noch fragen zu diesem thema nämlich zum thema reguläre
- sprachen dann schreibt gerne in die kommentare ansonsten sehen uns im nächsten video ich freue mich drauf und bis dann
- [Musik]
Zum Nachlesen
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 …
Formale GrammatikFormale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.
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.