Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Wörter und Sprachen - Automaten und formale Sprachen 1

Informatik - simpleclub5:44 243.697 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 78 Zeilen
Herunterladen
  1. Geil Geil Geil Leude heute gibts ein bissl Theorie! #ohno
  2. Aber keine Angst Freunde das ist super easy und extrem wichtig! Also Aufgepasst, ab gehts nach dem Intro mit Sprachen und Wörtern
  3. yipi! Also dann!
  4. Was ne Sprache ist wisst ihr ja :) Allgemeine Sprachen wie Deutsch,
  5. Englisch, Französisch usw. werden ja hauptsächlich verwendet damit wir mit unseren Dudes und internationalen Dudes auch kommunizieren können.
  6. Aber in Computern läuft das ein bisschen anders. Bei dem kommen wir mit Deutsch, Französisch usw. nicht sehr weit.
  7. Deswegen gibt es die formalen Sprachen. Diese werden für die Verarbeitung von Daten und Informationen für den Computer verwendet.
  8. Das Konzept der formalen Sprachen kommt aus der Theoretischen Informatik. Jap Theorie hat keiner gern, aber die ist ganz wichtig für die Abstraktion von Prozessen
  9. und Informationsverarbeitung in Computern. Okay dann schau mer mal aus was die so zusammengesetzt ist.
  10. Der Grundbaustein ist ein Alphabet, also so wie wir das schon kennen. Ein Alphabet ist eine endliche und vorallem nichtleere Menge von Zeichen oder Symbolen.
  11. Dat kann dann im Prinzip alles sein, zum Beispiel: Ein Alphabet aus kleinbuchtstaben, ein Alphabet aus 0en und 1en, ein Alphabet aus irgendwelchen komischen Symbolen.
  12. Formal wird das Alphabet meistens mit dem großen Sigma gekennzeichnet, also dem komischen E da.
  13. Merkt euch: Das Alphabet gibt an welche Zeichen oder Symbole wir verwenden dürfen. Haben wir ein Alphabet definiert, sagen wir mal ein Alphabet mit Kleinbuchstaben a-z.
  14. Können wir aus den einzelnen Zeichen Wörter bilden. Wie: a,
  15. ab, abcc, hammer, eselbananenpampe….
  16. :D Also alle Kombinationen mit kleinen Buchstaben. Wörter sind eine endliche Folge von Symbolen aus einem Alphabet.
  17. Wichtig ist: Bildet man Wörter aus einem Alphabet dürfen sie nur den Symbolen in diesem Alphabet entsprechen.
  18. So gehört zu dem Alphabet {0,1} nur Folgen mit 0 und 1, also zum Beispiel 00, 01,
  19. 01101, 010 usw. Sowas wie 12,
  20. 123 oder ähnliches sind keine Wörter aus dem Alphabet. Es gibt aber noch ein Wort, welches in jedem Alphabet zu finden ist.
  21. Das so genannte Leere Wort, wird geschrieben mit dem griechischen Buchstaben Epsilon. Das Leere Wort hat ein Länge von 0.
  22. Alle anderen Wörter besitzen ein Länge größer gleich 1. Die Länge eines Worts wird mit den Betragsstrichen gekennzeichnet, also diesen geraden Strichen.
  23. Wörter werden auch als Zeichenkette, Zeichenfolge oder Zeichenreihe bezeichnet. Diese Wörter können durch die Konkatenation miteinander verknüpft werden.
  24. Nehmen wir jetzt unser Alphabet mit Kleinbuchstaben, also a,b,c bis z und bilden daraus die zwei Wörter: v = hammer
  25. w= eselbananenpampe können wir die miteinander verknüpfen: Man erhält die Kombination aus v und w,
  26. also vw = hammereselbananenpampe die Länge setzt sich dann zusammen, aus der Länge von v und der Länge von w
  27. Also |v|
  28. + |w|
  29. = 22 Am besten ihr schreibt euch auf: Wörter sind eine endliche Folge von Symbolen
  30. aus einem Alphabet Nice!
  31. Aus Wörtern können nun Sprachen gebildet werden. Sprachen sind Teilmengen der Kleeneschen Hülle eines Alphabets.
  32. Klingt kompliziert, bedeutet aber einfach nur, dass eine Sprache eine beliebige Menge von gewissen Wörtern aus einem Alphabet ist.
  33. Geil Geil Geil Leude heute gibts ein bissl Theorie! #ohno
  34. Aber keine Angst Freunde das ist super easy und extrem wichtig! Also Aufgepasst, ab gehts nach dem Intro mit Sprachen und Wörtern
  35. yipi! Also dann! Was ne Sprache ist wisst ihr ja :)
  36. Allgemeine Sprachen wie Deutsch, Englisch, Französisch usw. werden ja hauptsächlich
  37. verwendet damit wir mit unseren Dudes und internationalen Dudes auch kommunizieren können. Aber in Computern läuft das ein bisschen anders.
  38. Bei dem kommen wir mit Deutsch, Französisch usw. nicht sehr weit. Deswegen gibt es die formalen Sprachen.
  39. Diese werden für die Verarbeitung von Daten und Informationen für den Computer verwendet. Das Konzept der formalen Sprachen kommt aus der Theoretischen Informatik.
  40. Jap Theorie hat keiner gern, aber die ist ganz wichtig für die Abstraktion von Prozessen und Informationsverarbeitung in Computern.
  41. Okay dann schau mer mal aus was die so zusammengesetzt ist. Der Grundbaustein ist ein Alphabet, also so wie wir das schon kennen.
  42. Ein Alphabet ist eine endliche und vorallem nichtleere Menge von Zeichen oder Symbolen. Dat kann dann im Prinzip alles sein, zum Beispiel: Ein Alphabet aus kleinbuchtstaben, ein Alphabet
  43. aus 0en und 1en, ein Alphabet aus irgendwelchen komischen Symbolen. Formal wird das Alphabet meistens mit dem großen Sigma gekennzeichnet, also dem komischen
  44. E da. Merkt euch: Das Alphabet gibt an welche Zeichen oder Symbole wir verwenden dürfen.
  45. Haben wir ein Alphabet definiert, sagen wir mal ein Alphabet mit Kleinbuchstaben a-z. Können wir aus den einzelnen Zeichen Wörter bilden.
  46. Wie: a, ab, abcc,
  47. hammer, eselbananenpampe…. :D Also alle Kombinationen mit kleinen Buchstaben.
  48. Wörter sind eine endliche Folge von Symbolen aus einem Alphabet. Wichtig ist: Bildet man Wörter aus einem Alphabet dürfen sie nur den Symbolen in diesem
  49. Alphabet entsprechen. So gehört zu dem Alphabet {0,1} nur Folgen mit 0 und 1, also zum Beispiel
  50. 00, 01, 01101, 010 usw.
  51. Sowas wie 12, 123 oder ähnliches sind keine Wörter aus dem Alphabet.
  52. Es gibt aber noch ein Wort, welches in jedem Alphabet zu finden ist. Das so genannte Leere Wort, wird geschrieben mit dem griechischen Buchstaben Epsilon.
  53. Das Leere Wort hat ein Länge von 0. Alle anderen Wörter besitzen ein Länge größer gleich 1.
  54. Die Länge eines Worts wird mit den Betragsstrichen gekennzeichnet, also diesen geraden Strichen. Wörter werden auch als Zeichenkette, Zeichenfolge oder Zeichenreihe bezeichnet.
  55. Diese Wörter können durch die Konkatenation miteinander verknüpft werden. Nehmen wir jetzt unser Alphabet mit Kleinbuchstaben, also a,b,c bis z
  56. und bilden daraus die zwei Wörter: v = hammer w= eselbananenpampe
  57. können wir die miteinander verknüpfen: Man erhält die Kombination aus v und w, also vw = hammereselbananenpampe
  58. die Länge setzt sich dann zusammen, aus der Länge von v und der Länge von w Also |v| + |w| = 22
  59. Am besten ihr schreibt euch auf: Wörter sind eine endliche Folge von Symbolen aus einem Alphabet
  60. Nice! Aus Wörtern können nun Sprachen gebildet werden.
  61. Sprachen sind Teilmengen der Kleeneschen Hülle eines Alphabets. Klingt kompliziert, bedeutet aber einfach nur, dass eine Sprache eine beliebige Menge
  62. von gewissen Wörtern aus einem Alphabet ist. Nehmen wir zum Beispiel ein Alphabet A bestehend aus drei Zeichen a b und c
  63. Können wir folgende Sprachen bilden: S1 = {aa,bb,cc,aab,cab,a} Das bedeutet diese Sprache enthält nur diese 6 Wörter.
  64. Haben wir jetzt ein Wort wie “abc”, wissen wir es ist nicht in der Sprache S1. Aber man kann auch Sprachen anders definieren:
  65. S2 = {a^n b^n c^n | n element N } Das heißt es sind Wörter erlaubt wie:
  66. abc, aabbcc, aaabbbccc usw.
  67. Beim erstellen von Sprachen kann man alle möglichen Bedingungen stellen. Zum Beispiel Anzahl von unterschiedlichen Buchstaben in den Wörtern soll gleich sein,
  68. die Anzahl von a’s soll durch 2 teilbar sein usw. oder was euch sonst noch einfällt :P
  69. Merkt euch: Eine Sprache ist eine beliebe Menge von Wörtern aus einem Alphabet. Sprachen können unterschiedlich definiert
  70. werden. Wichtig zu beachten ist:
  71. Bei so einer Sprache gibt es noch keine Informationen über ihre Bedeutung. Also eine Kombination aus 01 oder abc kann alles mögliche bedeuten.
  72. Auch das Wort eselbananenpampe muss nicht das bedeuten was wir vielleicht denken. Um Wörter einer Sprache zu erkennen verwendet man endliche Automaten, aber was das ist könnt
  73. ihr euch im nächsten Video reinziehen. Bevor ihr das tut, fassen wir aber nochmal zusammen:
  74. Formale Sprachen werden für die Informationsverarbeitung in Computern verwendet Ein Alphabet gibt dabei an welche Zeichen oder Symbole man verwenden darf.
  75. Aus so nem Alphabet kann man Wörter bilden. Wörter werden auch als Zeichenreihen bezeichnet und sind eine endliche Folge von Symbolen aus einem Alphabet.
  76. Man kann Sprachen auf unterschiedliche Weise bilden. Sie beinhalten eine beliebige Menge von Wörtern aus einem Alphabet.
  77. Wollt ihr jetzt wissen wie wir Wörter einer Sprache erkenne können, dann geht zum nächsten Video in der Reihe...Oder schaut auf unsre Lernplattform und guckts euch um.
  78. Bis dahin haut rein und Ciao!

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, … 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, … Alphabet (Informatik)Sie stellen das Zeicheninventar für Wörter zur Verfügung und bilden damit die Grundlage für formale Sprachen. Man muss unterscheiden zwischen dem Alphabet aus … Ω-reguläre SpracheIn der theoretischen Informatik bezeichnet die Klasse der ω-regulären Sprachen eine bestimmte Menge formaler Sprachen aus unendlichen Wörtern.