Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Formale Sprachen - Automaten und Formale Sprachen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 97 Zeilen
- Herzlich willkommen zum dritten Video in der Videoreihe Automaten und formale Sprachen. Wie ihr schon seht, geht's heute um formale Sprachen in einem
- bisschen anderen Format. Ich habe heute meine PowerPoint erstellt, da mir das ganze animieren in meinem Schnittprogramm zu doof wurde und das
- hier ein sehr theorielastiges Thema wird. Wir steigen aber auch direkt einmal ein. Also zu allererst, was sind Sprachen?
- Obviously, jeder kennt Sprachen, me wir sprechen den ganzen Tag. Wieso machen wir das? in erster Linie, um zu kommunizieren.
- Und egal mit wem ihr kommuniziert, solange ihr euch verstehen wollt, muss ja eure Sprache gewissen Regeln folgen. Wir kennen das als Rechtschreib und
- Grammatikregeln. Diese setzen sich so ein bisschen zusammen aus drei Punkten und zwar Lexik, Syntax und Semantik. Das ist
- jetzt um Thema Sprach und Verstehen relativ relevant. Ähm Lexic sind dabei die Symbole, die wir benutzen. Das kennen wir auch schon von den
- Automaten, z.B. im einabehabet. Das wäre hier unsere Lexik. Dann haben wir Syntax. Das sind im Grunde unsere Regeln und zwar wie wir
- die Wörter dann auch zusammensetzen dürfen. Wir können ja nicht einfach irgendwelche Buchstabeninander hängen, sondern machen das beim Automaten z.B.
- nach gewissen Regeln, dass unsere Eingabe akzeptiert wird. Aber nicht jede Eingabe ergibt dann auch noch Sinn und da kommt unsere Semantik ins Spiel.
- Unsere Semantik bestimmt nämlich, dass die Wörter nicht nur einfach richtig zusammengesetzt sind, dass ich z.B. im Deutschen silbenkorrekt bilde und die
- rechte Rechtschreibung benutze, sondern dass das Wort auch tatsächlich existiert. Wie weit ist das jetzt relevant für formale Sprachen?
- Dafür werde ich jetzt einmal natürliche und formale Sprachen vergleichen. Natürliche Sprachen ist im Grunde um das, was wir sprechen. Das haben wir
- gerade schon einmal geklärt. Das Problem an natürlichen Sprachen, wie z.B. Deutsch, Spanisch, Englisch ist aber, dass diese mehrde deutig sind.
- Das heißt, sie sind eben nicht kontextfrei und einziges Wort kann mehrere Bedeutungen haben. Beispiele in der
- deutschen Sprache, dafür wären z.B. die Wörterbank, das können wir von der Sitzbank, aber auch von der Bank, wo wir Geld abheben können oder vom Flügel,
- z.B. jetzt beim Vogel oder eben ders. Das Piano nennt man ja auch Flügel. Wir haben also keine eindeutigen Wörter. Dadurch ist die Sprache häufig
- fehleranfälliger und deutlich interpretierbarer. Das ist so in unserem Alltag gut, weil dadurch Sprache lebendig ist und sich weiterentwickeln
- kann. Gerade aber bei formaler Sprache wollen wir das nicht. Formale Sprache soll nämlich eindeutig und präzise sein. Und damit wir das erreichen können, hat
- formale Sprache ein eindeutiges Regelwerk. Ein Wort hat also immer nur eine Bedeutung
- und das sorgt dann dafür, dass eben auch Maschinen diese Sprache verstehen können. Die meisten von euch werden formale Sprachen wahrscheinlich auch
- schon kennen, entweder aus eurem Informatikalltag oder auch aus eurem tatsächlichen Alltag. Z.B. die Regeln, die wir in Mathe haben oder auch die
- Regeln, die wir aus Programmiersprachen kennen, z.B. Java sind schon formale Sprachen, da ein if ja immer nur eine Bedeutung hat und die Sprachen dadurch
- eindeutig und nicht mehrdeutig sind. Woraus besteht denn jetzt aber eine formale Sprache? Bei einer formalen Sprache ist es erstmal wieder ähnlich
- wie beim Automat. Wir können eine formale Sprache, aber auch in einen Automat umwandeln. Damit möchte ich mich heute nicht befassen.
- Zu allererst einmal hat eine formale Sprache ein Alphabet. Das kennen wir aus der Lexic. Wir haben also Symbole. Ich werde das jetzt auch direkt mal mit
- einem Beispiel verknüpfen, damit wir uns das gleich am Anschauen können, wie aus den Regeln dieser formalen Sprache dann auch tatsächlich ein Wort wird. Wir
- haben also die Symbole L, M, S und X. Man kann jetzt schon bisschen erahnen, welche Richtung das geht. Wir wollen hier nämlich Kleidergrößen erschaffen.
- Ein Wort besteht dann aus diesen Symbolen. Ich habe jetzt hier einfach mal ein Wort der Sprache erzeugt und zwar XXL. Natürlich haben wir jetzt auch
- keine Grammatik, also könnte ich auch sowas wie lxx erstellen. Das ist ja gerade noch nicht festgelegt. Dann hat unsere Sprache eben eine
- Grammatik, die aus Regeln besteht. Äh diese Regeln werden angegeben mit Terminalen und Nonterminale. Zeige ich euch gleich, keine Sorge. Wir haben eine
- ähnliche Menge von Produktionsregeln. Das ist wieder wichtig, denn wir können unsere formale Sprache in ein DA umwandeln und wir haben eine
- Startvariable S. Das möchte ich euch jetzt hier einmal zeigen. Links haben wir Nonminale. Das sind Symbole, die im späteren Wort
- gar nicht vorkommen sollen. Es sind aber sozusagen Platzhalter. Diese Nonterminale können wir dann, während wir das Wort bilden, quasi durch
- Terminale ersetzen. Die Terminale, die sehen wir hier schon. Wir haben ja jetzt unsere Kleidergrößen und da fällt mir auf, dass ich tatsächlich ein Symbol
- vergessen habe zu markieren. Das mache ich gleich noch mal. Und zwar ist unser S auch ein Terminalsymbol. Terminalesymbole, das sind diese
- Symbole, die dann später auch tatsächlich das Wort bilden. Äh, den rechten Teil des ganzen hier nennt man dann die Ableitung.
- Das heißt, äh wenn wir gleich einmal durchgehen und ein Wort bauen, dann leiten wir quasi aus diesen Nonterminalen das Wort ab. Deswegen
- einfache Ableitung. Wie wir jetzt hier schon sehen, gibt's Pfeile und wir beginnen jetzt in dem Fall beim Z. Da könnte ich jetzt auch
- äh was anderes draus machen. Das ist jetzt bei den Kleidergrßen aber nicht besonders sinnvoll, weil das eben schon vergeben ist. Ich beginne also mal beim
- Z und ich möchte jetzt eine valide Kleidergröße machen. Ich gehe also rüber und sage, ich möchte jetzt ein relativ großes T-Shirt haben. Mein Z wird also
- zum BL. Die Terminalen, die bleiben jetzt einfach stehen. Das heißt, das L ist gegeben und ich möchte jetzt aber ein noch viel
- größeres Shirt haben. Das B ist ja noch ein Nonterminal. Ein Wort muss aber nur aus Terminalen bestehen. Ich gehe also zum B, kann das B jetzt entweder durch
- nichts ersetzen, das ist wieder unser Ep, das kennen wir bereits, oder durch eine dieser drei Optionen durch ein X, ein XX oder ein XX. Das ist jetzt in dem
- Fall egal. Am Schluss habe ich ein Wort und zwar z.B. XL. Ich habe jetzt also mit diesen Produktionsregeln ein Wort dieser Sprache erschaffen. Das
- Ganze möchte jetzt einfach noch mal hier händisch zeigen, wie man das Ganze dann auch in einer Arbeit aufschreiben würde. Das Schöne ist, dass das jetzt ein
- relativ einfaches Beispiel ist, weshalb man es noch relativ anschaulich zeigen kann. Wir beginnen wieder bei unserem Z und haben dabei natürlich die
- Produktionsregeln im Kopf. Bestenfalls blende ich die auch noch mal irgendwie ein. Dann können wir uns ja wieder anschauen.
- Wir wollen von Z jetzt zu B. Schreiben wir also auf. Wir wollen jetzt BL. Jetzt müssen wir dieses B irgendwie
- ersetzen. Also schreiben wir z.B. auf XXL. Das wäre jetzt eine ziemlich einfache Folge. Wenn natürlich die Produktionsregeln
- komplexer werden, dann können hier auch ziemlich viele Pile dazwischen kommen. Werde ich euch aber auch gleich noch mal einmal kurz
- zeigen. Jetzt kommen wir zu regulärer versus irregulärer Grammatik. werden ja gerade schon geklärt, dass das Wort, das nach unseren Produktionsringen
- rauskommen muss, immer aus Terminalsymbolen bestehen muss. Das ist schon mal wichtig. Jetzt gibt es zwei Formen der regulären Grammatik und zwar
- die rechtsreguläre und die linksreguläre Grammatik. Einem von den beiden Regelsätzen muss das Ganze folgen, damit es eine reguläre Grammatik ist. Bei der
- äh rechtsregulären Grammatik haben wir immer ein Nonterminalsymbol links und das wird zu einem Terminalsymbol rechts oder einem Terminal und einem
- Nonminalsymbol. Das kennen wir schon von eben gerade. Wir haben z.B. am Start das Z und wenn unsere Kleidergröße jetzt z.B. einfach
- nur M ist und wir nicht weitermachen wollen, dann wird unser Zum M und das Wort ist quasi fertig. Wenn wir jetzt aber noch was dazu angeben wollen, z.
- Beispiel sx. Ob das jetzt Sinn ergibt oder nicht, ist erstmal egal. Dann machen wir ein Nonterminalsymbol. Haben wir wieder Z. Das wird zu einem S
- hier. Und wir setzen Nonterminal dazu, damit wir wieder mehrere Buchstaben anhängen können. Die linksreguläre Grammatik ist das, was wir gerade beim
- Beispiel gesehen haben. Wir haben das Z, das wird z.B. zum M oder wir haben eben das Z, das wird dann zum L rechts. Und weil wir z.B. XXL haben wollen, können
- wir dann hier rechts das neuen Tererminal hinsetzen, was dann wieder ersetzt wird. Wir stellen jetzt noch fest, dass Sprache regulär ist, wenn
- ihre Grammatik regulär ist, also nach diesen Regeln folgt, oder wenn die Grammatik so verändert werden kann, dass die Grammatik regulär wird. Und
- dazu möchte ich jetzt ein Beispiel zeigen, weil das nicht immer so direkt sichtbar ist. Jetzt werde ich erstmal auf ein Beispiel eingehen, wo die
- Grammatik erst einmal irregulär ist. Wir schauen uns einmal diese Produktionsregeln an. Das ist ein Beispiel von mir aus dem Unterricht.
- Ähm, ich lass euch kurz drauf gucken, vielleicht kennt ihr das auch schon. Äh, und ihr könnt mal kurz gucken, wo das Problem liegt.
- Und wir sehen hier auch schon ähm wir haben hier links das SK und V. Das sind ja unsere Nonminale und eben direkt bei der ersten Produktionsregel haben wir
- das Problem, S kann zu K werden. Das heißt, ein Nonterminal kann zu einem Nonminal werden und das ist weder bei der rechtsregulären als auch bei der
- linksregulären Grammatik möglich. Das heißt, wir müssen es jetzt irgendwie schaffen, dass unser S zu einem Terminal und einem
- Nonminalsymbol wird. Jetzt könnt ihr noch mal drüber nachdenken, wie wir das eventuell machen können, so dass unsere jetzt irreguläre Grammatik regulär wird
- und damit unsere Sprache auch regulär ist. Wenn ihr das Video jetzt kurz pausiert habt, dann kommt hier die Auflösung und
- die kleine Erklärung dazu. Äh, in dem Fall ist es jetzt sinnvoll, das Ganze einfach ein bisschen zusammen zuquetschen.
- Das ganze Beispiel hier ist ähm ein Beispiel zur hawaianische Sprache. Grob gesagt geht's dabei einfach darum, dass man eben gewisse Konsonanten hat, wie H,
- K, M, N, P und W. äh und diese zusammen mit den Vokalen A i Ou zusammentun kann. Wichtig ist, dass ein Konsonant immer nur alleine stehen
- kann äh und spätestens nach einem Konsonanten eben wieder ein Vokal folgen muss. Das ist aber theoretisch für die Produktionsregeln jetzt ist mal egal, da
- man diese ja auch erstmal ohne Kontext betrachten kann. Um jetzt eben diese Sprache regulär zu machen, äh haben wir jetzt in dem Fall
- versucht, das K hier allererstmal durch die Möglichkeiten von K zu ersetzen. Ich will das mal hier unten zeigen. K sieht man hier jetzt gar nicht mehr und wir
- haben hier einfach die Möglichkeiten von V eben mit rangehangen,
- also dass man eben direkt mit den Konsonanten KMNPw zu V kommt. Des weiteren hat aber gesagt, dass beliebig viele Vokale
- hintereinander folgen können. Es ist also nur relevant, dass nach einem konsonantenvokal kommt. Äh, das heißt, wir haben jetzt im Grunde auch direkt
- ein Loop drin, dass man quasi von AS wieder zu S kommt und quasi wieder ein A ranhängen kann. Das heißt, wir können z.B. schöne Kette von A ähm eben
- erzeugen. Das Ende ist jetzt hier in dem Fall gleich, wir enden hier auf äh einem Vokal, wenn wir eben zu V kommen, wenn wir das wollen.
- Gleichzeitig wird aber eben sichergestellt, dass in dem Fall jetzt nach einem Konsonant, also nach einem O, wir gehen zu V, hier gibt es eben nur
- Vokale, deswegen auch V, weil bei V hat man nur Vokale und die Konsonanten sind jetzt einfach in unser Start Produktionsriegel mit drin. Gerade hier
- empfehle ich noch mal einige weitere Beispiele anzugucken. Das ist ein kompliziertes Thema. Das ist sicherlich prüfungsrelevant, gerade im
- Aufgabenbereich 3, dass man eben eine irreguläre Grammatik irgendwie regulär machen muss oder erklären muss, warum eine Grammatik
- regulär oder vielleicht auch irregulär ist. Ähm, das kann auf jeden Fall dran kommen und da wird es sicherlich auch noch deutlich kompliziertere Beispiele
- für geben. Dann haben wir zum Schluss noch die kontextfreie Grammatik. Hier können wir uns jetzt aussuchen, ob ein Nonterminal zu einem Terminal oder
- nichtterminal wird. Und wir können auch sagen, dass das zu quasi unendlich vielen Terminal und Nonterminalen wird, egal in welcher Reihenfolge. Ein
- Beispiel dafür wäre jetzt das hier. Wir haben den Startzustand, ähm gehen wieder in den Startzustand, aber wir haben hier eben die Klammern.
- Und was jetzt dabei noch wichtig wäre, damit das Ganze auch endet, wäre hier wieder ein Epsilon. Das ganz wichtig, sonst endet das hier nie. Ähm im Grunde
- ist das hier einfach nur dafür da, um beliebig viele legale Klammerpaare zu bilden. Können es mal anschauen. S wird zu Klammer auf Klammer zu. Hier könnten
- wir jetzt also unendlich viele Klammer auf Klammer zu reinhauen. Wir könnten aber auch ähm rechts davon das jetzt entweder so lassen, dann können wir
- einfach Klammerpaare erschaffen oder wenn wir eben das erste Klammerpaar haben, können wir sagen, das hier wird zu nichts. Wird also ein leeres
- Klammerpaar. Wir gehen hier wieder rüber, zack und wieder hier rein und bilden daraus auch ein Klammerpaar. Ähm, hierbei fallen dann einfach die
- Regeln der regulären Grammatik weg und wir können einfach so viele Terminal und Nonminalsymbole zusammenklatschen, wie wir wollen.
- Das soll do erstmal gewesen sein. Nächstes Video hierzu wird es vermutlich nicht geben. Wir sehen uns hoffentlich trotzdem
- irgendwann. Bis dahin, ciao.
Zum Nachlesen
Formale GrammatikFormale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.
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 SpracheEine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, …