Formale Sprachen: Reguläre Sprache
frankjuchim
https://www.youtube.com/watch?v=k9ceS7SREtY

Transkript (automatisch erstellt)

0:00 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
0:08 sind und wie sie sich auch vielleicht von anderen sprachen abgrenzen das gibt es in diesem video los geht's [Musik]
0:20 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
0:31 sind die eigentlich definiert und zwar gibt es von noam chomsky die chance die hierarchie und die sorgt dafür dass selbst die
0:39 formalen sprachen die ja von den natürlichen sprache irgendwie abgegrenzt sind das haben wir im letzten video kennen gelernt aber die formalen staaten
0:46 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
0:57 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
1:10 sprachen haben eine produktions vorschrift links steht immer ein nicht terminal- und rechts ein einzelnes terminal- oder ein terminal- mit einem
1:19 lichtsignal dann gibt es zwei mögliche grammatiken bei der regulären sprachen nämlich einmal eine links reguläre grammatik und eine rechts
1:29 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
1:37 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
1:45 kann ich auch mit einer rechts regulären com artikel ganz viel drüber geredet heute schauen wir uns die regulären sprachen wie
1:51 gesagt an los geht's wie ist eine produktions vorschrift aufgebaut beim regulären dramatik wie wahlrechts regulären grammatik die sieht dann so
2:02 aus und zwar haben wir ein nicht terminal- wird ersetzt durch fc nun also das leere wort ein nicht terminal- wird ersetzt
2:12 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
2:21 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
2:34 terminal- rechts vom terminal- das heißt wenn ich jetzt mein board weiter weiter wachsen lasse würde das immer nach rechts hin wachsen
2:43 und bei aller linkshänder martin wäre das halt getauscht der bitte das wort nach links hin wachsen
2:51 lassen der einzige unterschied zwischen einer rechts regulären links regulären grammatik erstmal der der für uns wichtig
2:59 so ein beispiel wir haben ja die leimbacher mit lalelu drei silben kennen wir alles noch die produktionsfläche sah genauso aus
3:10 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
3:21 terminal- gefolgt von einem nicht terminen oder halt nur einen termin damit ist die lautsprache eine rechts reguläre
3:32 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
3:42 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
3:53 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
4:05 unsere lang sprachen oder unserem land marken dann auch finden ja also wir haben unsere produktions vorschrift jetzt überlegen wir mal geld
4:13 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
4:21 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
4:31 das ist mir ein bisschen einfacher zu machen und übersichtlicher der akzeptierte genau das was da auch ansprachen oder antworten akzeptiert
4:39 wird in unserer sprache wichtig der abschluss ist immer ein und wir haben genau 37 aber wie analysiere ich jetzt das wort ich
4:51 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
5:00 erste produktions regieren wetten das läge werden von q1 in q2 gehen beziehungsweise unsere zweite produktions regel anwenden das haben wir
5:07 schon letzten video gemacht und dann würden wir beim new von gut 23 gehen beziehungsweise unsere dritte produktions regel anwenden wir hätten
5:16 dann eine zustand vor und wird q 100 123 gute reise endzustand wunderbar funktioniert alles ebenso funktioniert die ableitung drüben man sieht schon
5:25 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
5:33 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
5:41 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
5:50 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
5:58 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
6:05 akzeptiert und den kennen wir schon dann geht es weiter kontextsensitiv wir sind dann linear beschränkte touring maschinen vielleicht
6:14 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
6:21 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
6:31 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
6:38 sprachen dann schreibt gerne in die kommentare ansonsten sehen uns im nächsten video ich freue mich drauf und bis dann
6:44 [Musik]