Informatiker Board | Theoretische Informatik | Probleme mit regulären Ausdrücken

Informatiker Board » Themengebiete » Theoretische Informatik » Probleme mit regulären Ausdrücken

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Probleme mit regulären Ausdrücken

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

der_Stefan
Grünschnabel

Dabei seit: 28.09.2007
Beiträge: 4

Probleme mit regulären Ausdrücken

Zitatantwort auf diesen Beitrag erstellen

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...

29.09.2007 02:04

Nehmen Sie der_Stefan in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

29.09.2007 12:24

Nehmen Sie Tobias in Ihre Freundesliste auf

der_Stefan
Grünschnabel

Dabei seit: 28.09.2007
Beiträge: 4

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.?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von der_Stefan: 29.09.2007 20:59.

29.09.2007 20:57

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Warum ist das leere Wort denn nicht in $[latex](a+b+c)^\ast[/latex]$ ?

29.09.2007 21:13

der_Stefan
Grünschnabel

Dabei seit: 28.09.2007
Beiträge: 4

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!

30.09.2007 02:00

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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).

30.09.2007 11:11

der_Stefan
Grünschnabel

Dabei seit: 28.09.2007
Beiträge: 4

$[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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von der_Stefan: 30.09.2007 11:47.

30.09.2007 11:46

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Jawoll.

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]$ ?

30.09.2007 13:12

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Probleme mit regulären Ausdrücken