Zum Inhalt springen
L

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

Regulärer Ausdruck - Automaten & Formale Sprachen 6

Informatik - simpleclub5:50 131.928 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 54 Zeilen
Herunterladen
  1. Jo Bro was ist regulärer Ausdruck? Regulärer Ausdruck beschreibt Sprache Bro. Allet klar Danke!
  2. Also jut! Ein Regulärer Ausdruck ist nix anderes als eine Beschreibungsmöglichkeit von formalen
  3. Sprachen. Also genauso wie wir das schon von unsren Automaten kennen.
  4. Mit den regulären Ausdrücken beschreiben wir halt irgendne Sprache aus einem vorgegeben Alphabet.
  5. Dabei können unterschiedliche Ausdrücke ein und dieselbe Sprache beschreiben. Wie wenn man beim Tabu ein Wort beschreiben muss, jeder erklärt es ein bisschen anders,
  6. aber eigentlich meint man dasselbe. Schauen wir uns mal an, wie so ein fresher regulärer Ausdruck aussehen könnte:
  7. Zum Beispiel so: 01* Ah jo und die 0 steht für Gefahr oder was?
  8. Nope der Ausdruck bedeutet: Zuerst eine 0 und dann beliebig viele Einsen. Oder anders ausgedrückt: Wörter die zuerst eine 0 haben, gefolgt von
  9. beliebig vielen 1en. Das wäre die definierte Sprache also.
  10. Wie man erkennt, stammt der Ausdruck aus dem Alphabet 0 und 1. Der Stern bei der 1 ist übrigens der sogenannte Kleene Stern.
  11. Werden darauf aber gleich genauer eingehen. Zuerst ist wichtig zu merken: Reguläre Ausdrücke beschreiben Sprachen.
  12. Die Ausdrücke müssen dazu aus Zeichen des Alphabets bestehen. Alright gehen wir mal genauer auf so nen Ausdruck ein.
  13. Wie kann man den jetzt beschreiben: Ein regulärer Ausdruck besteht immer aus den Zeichen eines definierten Alphabets.
  14. Bei uns jetzt 0 und 1. Dabei kann ein Ausdruck auf folgenden Operationen basieren.
  15. Erstens der Alternative: Die Alternative ist im Prinzip einfach ein Oder.
  16. Gekennzeichnet durch ein plus oder so nen senkrechten Strich. Zweitens die Verkettung: Die Verkettung ist einfach das UND was jeder
  17. von euch kennt. Beim regulären Ausdruck kann man entweder ein „Mal-Zeichen“ schreiben oder man klatscht
  18. die Zeichen einfach direkt zusammen. So wie bei unserem Beispiel.
  19. Als drittes gibt es noch die Wiederholung: Die Wiederholung soll einfach zeigen, dass das Zeichen öfter verwendet werden kann.
  20. Dazu wird eben dieser Stern genommen. Wird auch als Kleensche Hülle bezeichnet und heißt vereinfacht wir dürfen das Zeichen
  21. oder Wort beliebig oft wiederholen. Okay zurück zum Thema: Reguläre Ausdrücke werden dann wie folgt
  22. definiert: 1. Das Leere Wort und die Leere Menge sind reguläre Ausdrücke.
  23. 2. Für 0 Element dem Alphabet ist 0 ein regulärer Ausdruck
  24. Und 3. Sind 0 und 1 reguläre Ausdrücke so auch (0+1), (01) und (0)* reguläre Ausdrücke.
  25. Ah jo interessant: Ausdrücke können logischerweise auch geklammert werden.
  26. So kann man beispielsweise sowas kreieren: 0*(10*10*)* What soll das denn sein?
  27. Gehen wir den Kollegen mal durch und schauen welche Sprache damit beschrieben wird. Wir können offensichtliche beliebig viele 0er schreiben.
  28. Danach folgt ein Wort bestehend aus einer 1, beliebig vielen 0en, wieder einer 1 und wieder beliebig vielen 0en.
  29. Das ganze Wort können wir beliebig oft wiederholen. Das heißt 0en können wir dahinballern wie wir bock haben.
  30. Aber 1en kommen immer nur in gerader Anzahl vor. Das heißt die Sprach enthält eine Menge von Wörtern mit gerader Anzahl von 1ern.
  31. Beispiele dafür wären: - 01010 - 0010101010 - 01000010
  32. Nice easy peasy. Drehen wir den Spieß mal um.
  33. Sagen wir mal wir haben das gleiche Alphabet und folgende Sprache: Die Menge der Wörter die keine zwei aufeinanderfolgenden 0en enthalten.
  34. Okay also wir müssen vermeiden 2 0en hintereinander zu bekommen. Dann können wir zum Beispiel sowas basteln: (0+e) (11*0)* 1*
  35. Zuerst schreiben wir eine 0 oder das leere Wort Das verketten wir mit einer 1 danach beliebig viele 1en und eine 0.
  36. Das können wir dann so oft wiederholen wie wir bock haben. Am Ende schreiben wir nochmal so viele 1er wie wir wollen, damit wir keine zwei 0er bekommen.
  37. Und fertisch is der Lack! So können wir entweder Sprachen aus Ausdrücken ableiten oder ein Ausdruck aus einer Sprache
  38. definieren. Okidokiliy.
  39. Für reguläre Ausdrücke gelten die ganz normalen mathematischen Gesetze zur Vereinfachung Unter anderem das Kommutativgesetz oder auch das Distrbutivgesetz.
  40. Aber auch der Kleene Stern folgt einem Gesetz: Haben wir ein neutrales Element wie die Leere Menge oder das leere Wort verknüpft durch die Alternative mit einem regulären Ausdruck,
  41. ignorieren wir den das neutrale Element ganz einfach. Wie wenn man 0 zu irgendwas addiert.
  42. Verknüpfen wir das neutrale Element mit der Verkettung, so bekommen wir logischerweise das neutrale Element raus.
  43. Wie wenn man mit 0 mal nimmt. Nice!
  44. In der Praxis werden reguläre Ausdrücke oft verwendet um Zeichenkette zu Suchen und zu ersetzen.
  45. Zum Beispiel auch um in Dokumenten nach bestimmten Wörtern zu suchen. Dafür gibt es in der Praxis jede Menge Syntax für die Definition, darauf wollen wir jetzt
  46. aber nicht noch näher eingehen. Wichtig zu wissen ist noch: Zu jedem regulären Ausdruck existiert ein
  47. endlicher Automat, der dann die Sprache akzeptiert, die vom Ausdruck beschrieben wurde. Das heißt man kann so ein Automaten aus einem regulären Ausdruck konstruieren.
  48. Das ist aber ein anderes Thema. Vorher fassen wir nochmal zusammen: Ein regulärer Ausdruck beschreibt eine formale
  49. Sprache. So nen Ausdruck besteht immer aus den Zeichen des definierten Alphabets.
  50. Der Ausdruck kann drei Operationen enthalten: Die Alternative, die Verkettung und die Wiederholung. Aus regulären Ausdrücken können wir die Sprache ableiten oder aus der Sprache einen
  51. möglichen Ausdruck kreieren. Reguläre Ausdrücke können wir mit gewissen Gesetzen vereinfachen.
  52. In der Praxis werden die Dinger eingesetzt um zum Beispiel ein bestimmten Text in einem Dokument zu suchen Wenn ihr jetzt noch wissen wollt, wie wir
  53. das mit den Automaten verknüpfen können, dann schaut euch das nächste Video dazu an. Bis dahin haut rein
  54. Bis gleich.

Zum Nachlesen

Regulärer AusdruckEin regulärer Ausdruck (englisch regular expression, Abkürzung RegExp oder Regex) ist in der theoretischen Informatik eine Zeichenkette, … Reguläre SpracheIn der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge oder erkennbare Sprache eine formale Sprache, die einigen Einschränkungen … Formale SpracheEine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, … 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 …