Beweis regulärer Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Es seien [mm] \alpha [/mm] und [mm] \beta [/mm] zwei reguläre Ausdrücke über einem Alphabet.
Gilt allgemein die Äquivalenz [mm] (\alpha^\* \circ \beta^\*)^\* \equiv [/mm] ( [mm] \alpha [/mm] | [mm] \beta)^\* [/mm] |
Hallo Matheraum,
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
mir ist bei dieser Aufgabe die Vorgehensweise unklar.
Ich würde mich sehr freuen, wenn mir jemand ein Tipp geben könnte, wie man bei diesem Beweis startet.
Im Voraus vielen Dank.
Viele Grüße,
BugCrasher
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:47 Di 24.03.2009 | | Autor: | bazzzty |
> Es seien [mm]\alpha[/mm] und [mm]\beta[/mm] zwei reguläre Ausdrücke über
> einem Alphabet.
> Gilt allgemein die Äquivalenz [mm](\alpha^\* \circ \beta^\*)^\* \equiv[/mm]
> ( [mm]\alpha[/mm] | [mm]\beta)^\*[/mm]
> ..
> mir ist bei dieser Aufgabe die Vorgehensweise unklar.
>
> Ich würde mich sehr freuen, wenn mir jemand ein Tipp
> geben könnte, wie man bei diesem Beweis startet.
Hallo BugCrasher!
Du willst ja die Äquivalenz zweier Mengen zeigen, also zeigst Du einfach die Inklusion in beide Richtungen.
[mm]L_1=(\alpha^\* \circ \beta^\*)^\*[/mm]
[mm]L_2=( \alpha | \beta)^\*[/mm]
Die eine Richtung ist sehr einfach:
[mm]x\in L_1 \Rightarrow x\in L_2[/mm]
Tipp: Was wäre denn nicht in [mm] L_2?
[/mm]
Die andere Richtung ist vielleicht nicht ganz so klar:
[mm]x\in L_2 \Rightarrow x\in L_1[/mm]
Tipp: Zerlege x geeignet.
|
|
|
| |
|
Hallo bazzzty,
vielen Dank für Deine schnelle Hilfe.
Ich glaube Deine Anmerkungen haben mir schon etwas weitergeholfen.
1. x [mm] \in [/mm] L1 [mm] \Rightarrow [/mm] x [mm] \in [/mm] L2
Ich denke dies kann ich in Worten begründen.
Die Sprache welche durch den Ausdruck [mm] (\alpha|\beta)^\* [/mm] "entsteht", besteht aus einer beliebigen Folge von [mm] \alpha [/mm] und/oder [mm] \beta [/mm] inklusive dem leeren Element. Mit diesem Ausdruck können also alle denkbaren Kombinationen erstellt werden.
(z.B. [mm] \alpha\alpha\alpha\beta\beta)
[/mm]
Daher muss gelten: x [mm] \in [/mm] L1 [mm] \Rightarrow [/mm] x [mm] \in [/mm] L2
Mir ist aber unklar, wie ich dies "sauber" mathematisch begründen kann.
2. x [mm] \in [/mm] L2 [mm] \Rightarrow [/mm] x [mm] \in [/mm] L1
Die Sprache L welche durch den Ausdruck [mm] (\alpha^\*\circ\beta^\*)^\* [/mm] entsteht, habe ich versucht mit einem Beispiel zu verstehen:
Beispiel:
[mm] ((\alpha^0\cup \alpha^1 \cup \alpha^2 ...)(\beta^0\cup \beta^1 \cup \beta^2 ...))^0 \cup ((\alpha^0\cup \alpha^1 \cup \alpha^2 ...)(\beta^0\cup \beta^1 \cup \beta^2 ...))^1 \cup ((\alpha^0\cup \alpha^1 \cup \alpha^2 ...)(\beta^0\cup \beta^1 \cup \beta^2 ...))^1 [/mm] ...
Damit damit können auch alle Kombinationen von [mm] \alpha [/mm] und [mm] \beta [/mm] "abgedeckt" werden.
Allerdings ist dies kein ordentlicher Beweis.
Leider ist mir noch unklar, wie dies sauber mathematisch korrekt dargestellt werden kann.
Ich kenne noch die Umformung:
[mm] (\alpha|\beta)^\* [/mm] = [mm] ((L(\alpha) \cup L(\beta))^\*
[/mm]
Komme damit aber leider auch nicht weiter.
Wenn Du mir nochmal einen Hinweis geben könntest, würde ich mich sehr freuen 
Viele Grüße und vielen Dank,
BugCrasher
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 26.03.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
