Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Theoretische Informatik (1): Alphabet, Grammatik und Sprachen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 44 Zeilen
- so moin moin meine lieben Freunde willkommen zu einer neuen Videoreihe theoretische Informatik und ja damit begrüße ich euch schon mal zur
- Videoreihe ich hoffe ihr versteht es wenn nicht schreibt immer drunter am besten auch die Stelle im Video was genau nicht verstanden habt und dann
- werde ich mich bemühen dass ich zumindest dann in den Kommentaren ja euch verständlich rüberbringe sofern ich die Antwort natürlich auch kenne so wir
- fangen heute mit einer kleinen Einführung ein in die formalen Sprachen das werden wir für die nächsten Videos brauchen wir hört schon vale Sprachen
- was haben wir jetzt sprachen mit Informatik zu tun fragt man sich vielleicht am Anfang des Semesters wenn man das Fach
- belegt wir brauchen später bestimmte Regeln sage ich mal für unsere Automaten die wir z.B haben und diese
- Regeln werden wir gleich sehen kann man durch die eine oder andere Sache bestimmen und dafür brauchen wir jetzt erstmal ein Alphabet
- ein Alphabet das heißt σma das ist dieses Zeichen hier das ist ja in der Mathematik eigentlich das Summenzeichen und es gibt's so gesehen
- zwei verschiedene Sigmas es gibt einmal σma Stern und einmal also hier oder oder σma plus was ist jetzt der Unterschied bei sig stn
- hat man das leere Wort dabei das ist hier so ein und bei sig Plus hat man halt ja man hat kein Epsilon so einfach kann man sich
- das merken ähm das leere Wort ist einfach als würdet ihr auf die Leertaste drücken so kann man sich das im Prinzip vorstellen
- ähm ein Alphabet wie fange ich am besten an ich fange erstmal mit Alphabet an danach kommen wir auf Wörter und dann auf
- Grammatiken würde ich sagen ähm ein Alphabet hat eine endliche Länge und was noch wichtig zu sagen ist ein leeres Wort ist nicht die leere Menge
- das ist nicht das Gleiche möchte ich noch mal vielleicht jetzt erwähnen an der Stelle dann haben wir ein Wort ein Wort wird bei mir jetzt meistens als W
- abgekürzt das ist aber auch eigentlich egal ein Wort ist ein ist Teil oder kann sich aus den terminalen das sind die einzelnen Buchstaben des Alphabetes
- zusammensetzen also wortelement σma dann die Länge von W was mit was man mit dem Betrag bestimmen kann ist auch [Musik]
- endlich ist vielleicht auch noch mal wichtig zum anzumerken wie man z.B also jetzt mit Betrag vom W kann man die Länge des Wortes bestimmen
- man kann auch z.B die Anzahl an bestimmten terminalen also einfach merken terminale sind einfach Buchstaben die im Alphabet drin
- sind es heißt aber halt terminale z.B wie oft ist ein a in dem Wort drin kann man so z.B
- aufschreiben dann gibt es auch noch konkar Nation ich mache jetzt erstmal ein beispielwort z.B wenn unser Wort a a b b ist wollen wir hier bei der
- ersten beim ersten hier wissen wie lang ist unser Wort das heißt wie viele Buchstaben umfasst das Wort nämlich vier beim zweiten W wissen wie
- viele a haben wir im Wort wir haben zwei im Wort und jetzt fügen wir z.B ein anderes Wort zu nennen wir das mal W STR und das ist
- BBA und jetzt kann man z.B auch Wörter aneinander hängen das nennt sich konkatenieren so schreibe ich es mal kurz so auf also die Länge von WW ist
- gleich die Länge von W plus die Länge von W Strich das wäre dann das Wort aneinander gehangen schreibe es jetzt mal in Schwarz auf wäre alt AA BB b b a
- das heißt die zwei verschiedeneen Wörter wurden aneinander gehängt man kann auch das eine dasselbe wort natürlich aneinander hängen dazu eine kleine
- Anmerkung wenn man das Wort hoch n0 nimmt dann ist es das leere Wort wenn man das Wort hoch n nimmt dann wird das n mal aneinander
- konkateniert wenn wir jetzt gleich mal n= 2 wählen haben wir unser Wort AAB b b also a a b a ab b b heißt zweimal aninander
- gehangen so war ja das leere Wort wie gesagt stellt das vor als wäre das ja als würde Space Taste
- drücken haben wir schon geklärt was die verschiedenen Sigmas auf sich haben da haben wir jetzt gerade gesehen was ist erstmal ein Wort an
- sich ein Wort ist halt also setzt sich aus den terminalen des Alphabetes zusammen z.B hier wäre das jetzt es setzt sich aus A und B
- zusammen so jetzt kommen wir vielleicht mal auf Grammatiken eine Grammatik wird meistens mit G abgekürzt eine Grammatik ist ein
- Vierer turpel aus ich schreibbe die Buchstaben kurz hin danach schreibe ich hin was die denn sind so V sind unsere
- Variablen so hier V dann haben wir einmal das Alphabet sigσma P sind
- ja unsere Produktionsvorschriften bzw Ableitung Produktion schreibe ich mal hin und S ist unsere
- startvariable so da haben wir die vier Sachen mal gesehen die Menge an Variablen sind auch eine endliche Menge dann die terminale in ein Alphabet sind
- auch endlich und was ich noch mal anmerken will oder habe ich das gerade schon gemacht ich habe es jetzt schon wieder vergessen
- genau habe ich schon gesagt ja das leere Wort ist nicht die leere Menge das kann ich noch mal wiederholen wenn man also vielleicht denkt man sich leeres Wort
- leere Menge ist halt beides so gesehen nichts in anführungstrichen mal ganz salop gesagt nicht das Gleiche so und dann gibt es jetzt eine Sprache eine
- Sprache setzt sich aus der Grammatik zusammen das heißt die Grammatik setzt sich aus den vier Sachen zusammen unter anderem auch dem Alphabet und die
- Sprache setzt sich aus der Grammatik zusammen das wird dann l von G genannt also wenn die Grammatik g heißt dann l von G l steht für language g steht für
- grammar ja so einfach mal Erklärung und dann kann man z.B machen dass unser Wort aus Element Sigma Sternes das heißt wir können das leere
- Wort dabei haben und z.B können wir jetzt eine Regel aufstellen z.B die Anzahl an A ist g=ich zweimal die Anzahl an BS das
- wäre jetzt z.B eine Regel die man dafür aufgestellt hat und ja das war jetzt als kleine Anleitung würde ich sagen W ich sagen se uns bei der nächsten Folge
- wieder da rede ich kurz die homski Hierarchie und danach geht's dann sage ich mal schon mehr los W ich sagen bis zum nächsten Mal tschüssi
Zum Nachlesen
Formale SpracheEine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, …
Formale GrammatikFormale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.
Wort (theoretische Informatik)Wörter oder Worte sind die Elemente einer formalen Sprache. Sie sind deshalb wichtig für mathematische Modellierungen, für die Theorie der Programmiersprachen, …
Chomsky-HierarchieSie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …