Probleme mit regulären Ausdrücken

Neue Frage »

Auf diesen Beitrag antworten »
der_Stefan Probleme mit regulären Ausdrücken

Hat jemand Beispiele und Erklärungen zu den regulären Ausdrücken? Damit habe ich Verständnisprobleme bei meinem Studium (Wirtsch-Informatik).



Vielleicht würden mir viele Beispiele beim Verständnis helfen (reguläre Ausdrücke mit entsprechenden Mengen, welche diese beinhalten).

Ich meine solche Sachen wie

"...1. Der Ausdruck a^*b^* steht für die Menge der Zeichenketten, die aus endlichen vielen (einschließlich 0) gefolgt von endlich vielen $b$ (einschließlich 0) aufgebaut sind...."

Mit Google bin ich auch nicht wirklich fündig geworden.

Irgendwie hab ich da keinen Blick...
 
Auf diesen Beitrag antworten »
Tobias

Die formale induktive Definition der regulären Ausdrücke findest du hier:
http://de.wikipedia.org/wiki/Regul%C3%A4rer_Ausdruck

Ich will dir mal ein paar Beispiele zeigen. Zu jedem regulären Ausdruck ist es erstmal wichtig zu erkennen, ob ein Wort in der Sprache dieses regulären Ausdrucks liegt.

[latex]a^\ast[/latex]
Hier sind Wörter der Form a, aaaaaa, aaaaaaaaaaaa aber auch das leere Wort Epsilon gemeint. Also kannst du den Buchstaben a beliebig oft aneinanderhängen (auch 0-mal) und erhältst immer ein Wort, das in der Sprache von [latex]a^\ast[/latex] ist.


[latex](ab)^\ast[/latex]
Der Stern bezieht sich auf ab. Also kannst du ab beliebig oft hintereinander hängen:
ab, abababababababab, ...

[latex]ab^\ast[/latex]
Der Stern bezieht sich nur auf b. Die gesuchten Wörter beginnen alle mit einem a und enden auf beliebig vielen b's:
a, abbbbb, abbbbbbbbbb, ...

[latex]a+b[/latex]
Das + steht für "oder". Ich darf mir aussuchen, welche Seite ich nehme. Die möglichen Wörter sind hier: a, b

[latex]a^\ast+b^\ast[/latex]
Hier sind alle Wörter drin, die aus [latex]a^\ast[/latex] oder [latex]b^\ast[/latex] kommen. a's und b's dürfen aber nicht vermischt werden:
a, b, aaaaaa, bbbbbbb, aaa, bbbbbb, ...

[latex](a+b)^\ast[/latex]
Du darfst beliebig viele a's oder b's aneinanderhängen. Der Stern bezieht sich hier auf a+b, d.h. du kannst in Gedanken erstmal beliebig viele (a+b) aneinanderhängen und dann in jedem (a+b) auswählen. Das Ergebnis sind alle möglichen Wörter, die man aus den Buchstaben a und b bauen kann:
(a+b)(a+b)(a+b) = abb oder aaa oder bbb oder bab, ...


Jetzt kannst du dich an größeren Ausdrücken versuchen, wie z.B.:

[latex](a + b + c)^\ast ab c^\ast[/latex]

Welche Wörter sind wohl in der Sprache dieses regulären Ausdrucks?
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
leeres Wort
ab
aaaaaa
cccccc
bbbbb
abc
abcabcabcabc
acccacacacacacacacacaccacbccc
Auf diesen Beitrag antworten »
der_Stefan

Danke!!!

Ich wünschte, unser TI Prof. würde mal was so in der Art erklären wie du!

OK, mal sehen ob ich richtig liege...

leeres Wort
Nein, nur der Kleenesche Abschuss kann ja das leere Zeichen enthalten, oder also zBsp. a* oder b* oder c*

ab
Nein, aab oder bab oder cab wäre möglich, nicht aber nur ab (also vor dem ab muss mindestens noch ein a, b oder c kommen. c am Ende muss nicht unbedingt enthalten sein (Kleenesche Abschuss von c)

aaaaaa
Nein ein b muss mindestens vorhanden sein.

cccccc
Nein, denn ein b muss mind. vorhanden sein.

bbbbb
Nein, es muss mindestens ein a vorkommen

abc
Nein. aabc wäre möglich.

abcabcabcabc
Ja, ist möglich.

acccacacacacacacacacaccacbccc
Nein, denn vor dem b müsste ein a stehen.

was ist 9.?
Auf diesen Beitrag antworten »
Tobias

Warum ist das leere Wort denn nicht in [latex](a+b+c)^\ast[/latex]?
 
Auf diesen Beitrag antworten »
der_Stefan

Ich hab mir das so gedacht:
(a+b+c) beliebig oft hintereinander. So in der Art hattest du's ja auch beschrieben. Daher dachte ich, dass die Menge mindestens entweder ein a, ein b oder ein c beinhalten muss (nicht leer sein kann).

Also heißt das jetzt, der Ausdruck [latex](a+b+c)^\ast[/latex] kann auch leer sein?
Das würde natürlich vieles ändern.
Dann würde ich meine Antworten noch mal überdenken!
Auf diesen Beitrag antworten »
Tobias

Der Stern bleibt der Stern (und damit der Kleene'sche Abschluss), egal ob er an einem a hängt oder an einem (a + b + c).
Auf diesen Beitrag antworten »
der_Stefan

[latex](a + b + c)^\ast ab c^\ast[/latex]


leeres Wort
Nein, nur der Kleenesche Abschuss kann ja das leere Zeichen enthalten, oder also zBsp. a* oder b* oder c*

ab
Wird akzeptiert.

aaaaaa
Nein ein a und ein b müssen mindestens vorhanden sein.

cccccc
Nein ein a und ein b müssen mindestens vorhanden sein.

bbbbb
Nein ein a und ein b müssen mindestens vorhanden sein.

abc
Wird akzeptiert

abcabcabcabc
Ja, ist möglich.

acccacacacacacacacacaccacbccc
Nein, denn vor dem b müsste ein a stehen.



Stimmt's jetzt?
Auf diesen Beitrag antworten »
Tobias

Jawoll. Daumen hoch

Vielleicht noch ein Nachtrag:

Für zwei reguläre Ausdrücke [latex]\phi, \psi[/latex] schreibt man manchmal auch [latex]\phi \vee \psi[/latex] statt [latex]\phi + \psi[/latex].

Statt [latex]\psi \psi^\ast[/latex] schreibt man kurz [latex]\psi^+[/latex].

Hier noch eine Aufgabe für dich:

[latex]a \in \Sigma[/latex] sei ein Buchstabe und [latex]\psi[/latex] sei ein beliebiger regulärer Ausdruck.

1.) Ist [latex]\varepsilon \in L(a^+)[/latex]?

2.) Wann ist [latex]\varepsilon \in L(\psi^+)[/latex]?
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »