Informatiker Board | formale Sprachen | Vereinfachung regulärer Ausdrücke

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Vereinfachung regulärer Ausdrücke

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Vereinfachung regulärer Ausdrücke

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Tinchen1982
Grünschnabel

Dabei seit: 07.08.2016
Beiträge: 1

Vereinfachung regulärer Ausdrücke

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie Tinchen1982 in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo Tinchen1982,

es handelt sich um 3 Alternativen: [latex]b[/latex]

, $[latex]\varepsilon[/latex]$ und $[latex](b + \varepsilon)(b + \varepsilon)^*(b+\varepsilon)[/latex]$ .

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 $[latex]\varepsilon[/latex]$ , dann ist der mittlere Teil ein Kleene-Stern über $[latex]b+\varepsilon[/latex]$ . D.h. es ist eine beliebig lange Sequenz aus [latex]b[/latex]

und $[latex]\varepsilon[/latex]$ . Eine Konkatenation von einem beliebigen Wort mir $[latex]\varepsilon[/latex]$ ergbit wieder das Wort. Wir sehen also, dass $[latex](b+\varepsilon)^* \equiv b^*[/latex]$ . Wählen wir also die dritte Alternative und dabei die erste und die letzte Alternative $[latex]\varepsilon[/latex]$ , dann erhalten wir [latex]b*[/latex]

, da $[latex](\varepsilon)(\varepsilon+b)^*(\varepsilon) \equiv (\varepsilon+b)^* \equiv b^* [/latex]$

Gruß,

Karlito

08.08.2016 10:47

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Vereinfachung regulärer Ausdrücke