Theoretische Informatik (1): Alphabet, Grammatik und Sprachen
Franneck
https://www.youtube.com/watch?v=_Jrr2o8nDfQ

Transkript (automatisch erstellt)

0:00 so moin moin meine lieben Freunde willkommen zu einer neuen Videoreihe theoretische Informatik und ja damit begrüße ich euch schon mal zur
0:07 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
0:15 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
0:24 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
0:35 was haben wir jetzt sprachen mit Informatik zu tun fragt man sich vielleicht am Anfang des Semesters wenn man das Fach
0:43 belegt wir brauchen später bestimmte Regeln sage ich mal für unsere Automaten die wir z.B haben und diese
0:53 Regeln werden wir gleich sehen kann man durch die eine oder andere Sache bestimmen und dafür brauchen wir jetzt erstmal ein Alphabet
1:03 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
1:12 zwei verschiedene Sigmas es gibt einmal σma Stern und einmal also hier oder oder σma plus was ist jetzt der Unterschied bei sig stn
1:25 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
1:34 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
1:45 ähm ein Alphabet wie fange ich am besten an ich fange erstmal mit Alphabet an danach kommen wir auf Wörter und dann auf
1:53 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
2:06 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
2:16 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
2:27 zusammensetzen also wortelement σma dann die Länge von W was mit was man mit dem Betrag bestimmen kann ist auch [Musik]
2:39 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
2:48 man kann auch z.B die Anzahl an bestimmten terminalen also einfach merken terminale sind einfach Buchstaben die im Alphabet drin
2:56 sind es heißt aber halt terminale z.B wie oft ist ein a in dem Wort drin kann man so z.B
3:04 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
3:16 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
3:27 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
3:38 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
3:51 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
4:03 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
4:11 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
4:22 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
4:37 gehangen so war ja das leere Wort wie gesagt stellt das vor als wäre das ja als würde Space Taste
4:45 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
4:56 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
5:10 zusammen so jetzt kommen wir vielleicht mal auf Grammatiken eine Grammatik wird meistens mit G abgekürzt eine Grammatik ist ein
5:20 Vierer turpel aus ich schreibbe die Buchstaben kurz hin danach schreibe ich hin was die denn sind so V sind unsere
5:32 Variablen so hier V dann haben wir einmal das Alphabet sigσma P sind
5:42 ja unsere Produktionsvorschriften bzw Ableitung Produktion schreibe ich mal hin und S ist unsere
5:57 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
6:09 auch endlich und was ich noch mal anmerken will oder habe ich das gerade schon gemacht ich habe es jetzt schon wieder vergessen
6:15 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
6:24 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
6:36 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
6:44 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
6:52 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
7:03 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
7:21 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
7:30 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