Vereinfachung regulärer Ausdrücke |
Tinchen1982
Grünschnabel
Dabei seit: 07.08.2016
Beiträge: 1
|
|
Vereinfachung regulärer Ausdrücke |
|
Meine Frage:
Hallo zusammen,
ich habe ein Problem darin reguläre Ausdrücke zu vereinfachen. Hier ein Beispiel:
b + epsilon +(b + epsilon)(b + epsilon)*(b+epsilon) soll äquivalent sein zu b*.
Ich verstehe leider überhaupt nicht, wie man aus dem ersten Teil b* korrekt heraus bekommt.
Meine Ideen:
Ich hatte, da mehrfach das + vorkommt, die Idee zunächst gehabt mit der Assoziativität ran zu gehen, jedoch bin ich mir bei dem Teilausdruck (b + epsilon)(b + epsilon)*(b + epsilon) nicht sicher, wie ich ihn richtig behandeln kann.
|
|
07.08.2016 12:13 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo Tinchen1982,
es handelt sich um 3 Alternativen: , und .
Benutzt man die erste Alternarive erhält man nur das Wort b. Bei der Zweiten nur das leere Wort. Die dritte Alternative ist wiederum eine Konkatenation aus 3 Alternativen. Wie die beiden Äußeren funktionieren haben wir ja bereits geklärt, da sie wie die ersten beiden Alternativen aufgebaut sind. Die Mittlere ist nun interessant, da hier zusätzlich ein Kleene-Stern zum Einsatz kommt. Angenommen wir wählen für die beiden Äußeren Alternativen jeweils , dann ist der mittlere Teil ein Kleene-Stern über . D.h. es ist eine beliebig lange Sequenz aus und . Eine Konkatenation von einem beliebigen Wort mir ergbit wieder das Wort. Wir sehen also, dass . Wählen wir also die dritte Alternative und dabei die erste und die letzte Alternative , dann erhalten wir , da
Gruß,
Karlito
|
|
08.08.2016 10:47 |
|
|
|