Regulärer Ausdruck - Automaten & Formale Sprachen 6
Informatik - simpleclub
https://www.youtube.com/watch?v=SewleITxvcg

Transkript (automatisch erstellt)

0:00 Jo Bro was ist regulärer Ausdruck? Regulärer Ausdruck beschreibt Sprache Bro. Allet klar Danke!
0:04 Also jut! Ein Regulärer Ausdruck ist nix anderes als eine Beschreibungsmöglichkeit von formalen
0:19 Sprachen. Also genauso wie wir das schon von unsren Automaten kennen.
0:23 Mit den regulären Ausdrücken beschreiben wir halt irgendne Sprache aus einem vorgegeben Alphabet.
0:28 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,
0:37 aber eigentlich meint man dasselbe. Schauen wir uns mal an, wie so ein fresher regulärer Ausdruck aussehen könnte:
0:42 Zum Beispiel so: 01* Ah jo und die 0 steht für Gefahr oder was?
0:48 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
0:56 beliebig vielen 1en. Das wäre die definierte Sprache also.
1:00 Wie man erkennt, stammt der Ausdruck aus dem Alphabet 0 und 1. Der Stern bei der 1 ist übrigens der sogenannte Kleene Stern.
1:07 Werden darauf aber gleich genauer eingehen. Zuerst ist wichtig zu merken: Reguläre Ausdrücke beschreiben Sprachen.
1:14 Die Ausdrücke müssen dazu aus Zeichen des Alphabets bestehen. Alright gehen wir mal genauer auf so nen Ausdruck ein.
1:21 Wie kann man den jetzt beschreiben: Ein regulärer Ausdruck besteht immer aus den Zeichen eines definierten Alphabets.
1:27 Bei uns jetzt 0 und 1. Dabei kann ein Ausdruck auf folgenden Operationen basieren.
1:32 Erstens der Alternative: Die Alternative ist im Prinzip einfach ein Oder.
1:37 Gekennzeichnet durch ein plus oder so nen senkrechten Strich. Zweitens die Verkettung: Die Verkettung ist einfach das UND was jeder
1:45 von euch kennt. Beim regulären Ausdruck kann man entweder ein „Mal-Zeichen“ schreiben oder man klatscht
1:50 die Zeichen einfach direkt zusammen. So wie bei unserem Beispiel.
1:53 Als drittes gibt es noch die Wiederholung: Die Wiederholung soll einfach zeigen, dass das Zeichen öfter verwendet werden kann.
2:00 Dazu wird eben dieser Stern genommen. Wird auch als Kleensche Hülle bezeichnet und heißt vereinfacht wir dürfen das Zeichen
2:06 oder Wort beliebig oft wiederholen. Okay zurück zum Thema: Reguläre Ausdrücke werden dann wie folgt
2:13 definiert: 1. Das Leere Wort und die Leere Menge sind reguläre Ausdrücke.
2:18 2. Für 0 Element dem Alphabet ist 0 ein regulärer Ausdruck
2:22 Und 3. Sind 0 und 1 reguläre Ausdrücke so auch (0+1), (01) und (0)* reguläre Ausdrücke.
2:31 Ah jo interessant: Ausdrücke können logischerweise auch geklammert werden.
2:36 So kann man beispielsweise sowas kreieren: 0*(10*10*)* What soll das denn sein?
2:44 Gehen wir den Kollegen mal durch und schauen welche Sprache damit beschrieben wird. Wir können offensichtliche beliebig viele 0er schreiben.
2:51 Danach folgt ein Wort bestehend aus einer 1, beliebig vielen 0en, wieder einer 1 und wieder beliebig vielen 0en.
2:58 Das ganze Wort können wir beliebig oft wiederholen. Das heißt 0en können wir dahinballern wie wir bock haben.
3:04 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.
3:12 Beispiele dafür wären: - 01010 - 0010101010 - 01000010
3:19 Nice easy peasy. Drehen wir den Spieß mal um.
3:22 Sagen wir mal wir haben das gleiche Alphabet und folgende Sprache: Die Menge der Wörter die keine zwei aufeinanderfolgenden 0en enthalten.
3:30 Okay also wir müssen vermeiden 2 0en hintereinander zu bekommen. Dann können wir zum Beispiel sowas basteln: (0+e) (11*0)* 1*
3:44 Zuerst schreiben wir eine 0 oder das leere Wort Das verketten wir mit einer 1 danach beliebig viele 1en und eine 0.
3:53 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.
4:00 Und fertisch is der Lack! So können wir entweder Sprachen aus Ausdrücken ableiten oder ein Ausdruck aus einer Sprache
4:07 definieren. Okidokiliy.
4:09 Für reguläre Ausdrücke gelten die ganz normalen mathematischen Gesetze zur Vereinfachung Unter anderem das Kommutativgesetz oder auch das Distrbutivgesetz.
4:17 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,
4:27 ignorieren wir den das neutrale Element ganz einfach. Wie wenn man 0 zu irgendwas addiert.
4:31 Verknüpfen wir das neutrale Element mit der Verkettung, so bekommen wir logischerweise das neutrale Element raus.
4:37 Wie wenn man mit 0 mal nimmt. Nice!
4:41 In der Praxis werden reguläre Ausdrücke oft verwendet um Zeichenkette zu Suchen und zu ersetzen.
4:46 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
4:54 aber nicht noch näher eingehen. Wichtig zu wissen ist noch: Zu jedem regulären Ausdruck existiert ein
4:59 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.
5:08 Das ist aber ein anderes Thema. Vorher fassen wir nochmal zusammen: Ein regulärer Ausdruck beschreibt eine formale
5:13 Sprache. So nen Ausdruck besteht immer aus den Zeichen des definierten Alphabets.
5:18 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
5:28 möglichen Ausdruck kreieren. Reguläre Ausdrücke können wir mit gewissen Gesetzen vereinfachen.
5:33 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
5:41 das mit den Automaten verknüpfen können, dann schaut euch das nächste Video dazu an. Bis dahin haut rein
5:46 Bis gleich.