Reguläre Ausdrücke < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:14 Mo 02.08.2010 | | Autor: | Pacapear |
Hallo zusammen!
Ich versuche grade diese regulären Ausdrücke zu verstehen und hab mir dazu mal den Wikipedia-Artikel ![[]](/images/popup.gif) Reguläre Ausdrücke angeguckt.
Also wenn ich das richtig verstanden habe, dann werden reguläre Ausdrücke immer über einem gegebenen Alphabet definiert.
Und dann gibt es da ja diese komischen Syntax-Regeln, irgendwie versteh ich die nicht.
Also als erstes ist da ja das leere-Menge-Symbol, das soll ja ein regulärer Ausdruck sein.
Aber irgendwie seh ich da keinen Zusammenhang zu einem gegebenen Alphabet ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
Und dann die zweite Defintion, da steht:
"Für alle [mm] a_i [/mm] aus dem gegebenen Alphabet ist [mm] \mathbf{a_i} [/mm] ein regulärer Ausdruck und [mm] \mathbf{a_i} [/mm] soll die Repräsentation eines Zeichens aus dem zugrunde liegenden Alphabet sein.
Das versteh ich überhaupt nicht...
Wenn ich jetzt z.B. das Alphabet [mm] \{a,b\} [/mm] habe, und als [mm] a_i [/mm] nehme ich jetzt a, was ist denn dann die Repräsentation [mm] \mathbf{a_i} [/mm] davon, die dann der reguläre Ausdruck ist?
Und dann gibts ja dann noch die letzte Bedingung, dass wenn ich zwei reguläre Ausdrücke x und y habe, dass dann deren Alternative x|y und deren Verkettung (xy) auch wieder reguläre Ausdrücke sind.
Aber wie sehen diese Ausdrücke überhaupt aus, was ist x|y und (xy)?
Unten steht zwar, wie die Sprachen von diesen regulären Ausdrücken aussehen, aber nicht, wie die regulären Ausdrücke selbst aussehen
Die Semantik versteh ich denk ich einigermaßen, aber bei den Repräsentanten, da hängts wieder.
Da steht ja:
für alle [mm] a_i \in \Sigma [/mm] gilt [mm] \mathcal{L}(\mathbf{a}_i)=\{a_i\}
[/mm]
Jeder Repräsentant eines Zeichens aus dem Alphabet spezifiziert die Sprache, die nur dieses Zeichen enthält.
Diesen Repräsentanten, den versteh ich wieder nicht. Wenn die Sprache, die durch diesen komischen Reräsentanten entsteht, aus genau dem Zeichen besteht, den der Repräsentant präsentiert, warum kann ich dann nicht direkt das Zeichen als regulären Ausdruck nehmen
Unten steht dann auch nochmal was dazu, aber irgendwie verwirrt mich das noch mehr.
Da steht:
"Es wird jedoch nicht immer optisch zwischen einem regulären Ausdruck und der zugehörigen Sprache unterschieden, sodass man statt [mm] \mathbf{a} [/mm] auch $a$ als regulären Ausdruck für die Sprache [mm] \{a\} [/mm] verwendet."
Also wenn ich optisch nicht zwischen der Sprache und dem regulären Ausdruck unterscheide, dann heißt das für mich, dass ich für die Sprache und für den Ausdruck beidesmal dasselbe schreibe, aber die nehmen ja dann für regulären Ausdruck und Repräsentant das gleiche Zeichen, aber Repräsentant ist doch nicht gleich Sprache, oder ![[haee]](/images/smileys/haee.gif "[haee]")
Ich hoffe ihr könnt mir ein bisschen helfen.
LG Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:38 So 08.08.2010 | | Autor: | rainerS |
Hallo Nadine!
> Hallo zusammen!
>
> Ich versuche grade diese regulären Ausdrücke zu verstehen
> und hab mir dazu mal den Wikipedia-Artikel
> Reguläre Ausdrücke
> angeguckt.
>
> Also wenn ich das richtig verstanden habe, dann werden
> reguläre Ausdrücke immer über einem gegebenen Alphabet
> definiert.
Richtig.
Ein regulärer Ausdruck definiert eine Menge von Zeichenketten, die aus den einzelnen Zeichen des Alphabets bestehen; diese Menge ist dann eine Sprache.
> Und dann gibt es da ja diese komischen Syntax-Regeln,
> irgendwie versteh ich die nicht.
>
> Also als erstes ist da ja das leere-Menge-Symbol, das soll
> ja ein regulärer Ausdruck sein.
> Aber irgendwie seh ich da keinen Zusammenhang zu einem
> gegebenen Alphabet
Dieses Symbol bedeutet denjenigen regulären Ausdruck, der die leere Sprache definiert, also diejenige Sprache, die überhaupt keine Zeichenketten enthält - also eine leere Menge ist.
Das ist nützlich als Grenzfall, genauso wie in der Mengenlehre, in der die Leere Menge auch immer als Grenzfall vorkommt.
> Und dann die zweite Defintion, da steht:
> "Für alle [mm]a_i[/mm] aus dem gegebenen Alphabet ist [mm]\mathbf{a_i}[/mm]
> ein regulärer Ausdruck und [mm]\mathbf{a_i}[/mm] soll die
> Repräsentation eines Zeichens aus dem zugrunde liegenden
> Alphabet sein.
> Das versteh ich überhaupt nicht...
> Wenn ich jetzt z.B. das Alphabet [mm]\{a,b\}[/mm] habe, und als [mm]a_i[/mm]
> nehme ich jetzt a, was ist denn dann die Repräsentation
> [mm]\mathbf{a_i}[/mm] davon, die dann der reguläre Ausdruck ist?
Die einfachsten (nichtleeren) Zeichenketten sind diejenigen, die aus genau einem Zeichen bestehen. Für jedes Zeichen des Alphabets gibt es genau so eine Zeichenkette.
In deinem Beispiel wären das die beiden Zeichenketten "a" und "b" (ich schreibe Zeichneketten die Unterscheidung halber in Gänsefüßchen). Die Sprache, die nur die Zeichenkette "a" enthält, ist die Menge
[mm] $\{$ "a" $\}$
[/mm]
und das Symbol [mm]\mathbf{a}[/mm] bezeichnet den regulären Ausdruck, der genau diese Menge von Zeichenketten definiert.
Analog definiert der reguläre Ausdruck [mm]\mathbf{b}[/mm] die Sprache [mm] $\{$ "b" $\}$ [/mm] .
Du siehst, das Zeichen a kommt in drei Bedeutungen vor:
- als Teil des Alphabets: a ,
- als Zeichenkette, die nur aus diesem Zeichen besteht: "a" ,
- als regulärer Ausdruck, der die Sprache aus nur dieser Zeichenkette beschreibt: [mm]\mathbf{a}[/mm] , der Repräsentant dieses Zeichens.
Das ist die Bedeutung des Satzes:
> für alle [mm]a_i \in \Sigma[/mm] gilt
> [mm]\mathcal{L}(\mathbf{a}_i)=\{a_i\}[/mm]
> Jeder Repräsentant eines Zeichens aus dem Alphabet
> spezifiziert die Sprache, die nur dieses Zeichen enthält.
> Unten steht dann auch nochmal was dazu, aber irgendwie
> verwirrt mich das noch mehr.
> Da steht:
>
> "Es wird jedoch nicht immer optisch zwischen einem
> regulären Ausdruck und der zugehörigen Sprache
> unterschieden, sodass man statt [mm]\mathbf{a}[/mm] auch [mm]a[/mm] als
> regulären Ausdruck für die Sprache [mm]\{a\}[/mm] verwendet."
>
> Also wenn ich optisch nicht zwischen der Sprache und dem
> regulären Ausdruck unterscheide, dann heißt das für
> mich, dass ich für die Sprache und für den Ausdruck
> beidesmal dasselbe schreibe, aber die nehmen ja dann für
> regulären Ausdruck und Repräsentant das gleiche Zeichen,
> aber Repräsentant ist doch nicht gleich Sprache, oder
>
Korrekt. Genaugenommen müsstest du immer die Unterscheidung zwischen den drei verschiedenen Objekten machen. Wenn du aber einmal daran gewöhnt bist und weisst, was du tust, ist es nicht mehr nötig die unterschiedlichen Symbole zu verwenden. Dann schreibst du in allen drei Fällen einfach nur a, weil es dir aus dem Kontext klar ist, was gemeint ist.
Das ist wie in anderen Gebieten der Mathematik: irgendwann machst du dir keine Gedanken mehr darüber, ob das Zeichen + die Addition reeller Zahlen oder die Vektorraumaddition bedeutet, weil es für dich offensichtlich ist, was gemeint ist.
> Und dann gibts ja dann noch die letzte Bedingung, dass wenn
> ich zwei reguläre Ausdrücke x und y habe, dass dann deren
> Alternative x|y und deren Verkettung (xy) auch wieder
> reguläre Ausdrücke sind.
> Aber wie sehen diese Ausdrücke überhaupt aus, was ist
> x|y und (xy)?
> Unten steht zwar, wie die Sprachen von diesen regulären
> Ausdrücken aussehen, aber nicht, wie die regulären
> Ausdrücke selbst aussehen
Genauso, wie es da geschrieben ist. Beispiel: aus den regulären Ausdrücken [mm] $\mathbf{a}$ [/mm] und [mm] $\mathbf{b}$, [/mm] die die Sprachen [mm] $\{$ "a" $\}$ [/mm] bzw. [mm] $\{$ "b" $\}$ [/mm] beschreiben, entstehen die regulären Ausdrücke
[mm]\mathbf{a}|\mathbf{b}[/mm] Sprache: [mm] $\{$ "a", "b" $\}$
[/mm]
[mm] (\mathbf{ab} )[/mm] Sprache: [mm] $\{$ "ab" $\}$
[/mm]
Viele Grüße
Rainer
|
|
|
|
