Äquivalenz von Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Gegeben sind die [mm] \Sigma-Sprachen [/mm] L und M. Zeigen Sie, dass (L [mm] \cup [/mm] M)* = (L*M*)*. |
Hallo,
ich habe einen solchen Beweis mit Sprachen noch nie durchgeführt, sondern nur mit mathematischen Mengen, meine Idee wäre daher, zu zeigen, dass die erste Menge Teilmenge der zweiten ist und umgekehrt. Dann wäre folgendes zu zeigen:
1. (L [mm] \cup [/mm] M)* [mm] \subseteq [/mm] (L*M*)*
2. (L*M*)* [mm] \subseteq [/mm] (L [mm] \cup [/mm] M)*
Weiter bin ich auch nicht wirklich gekommen. Ich kann keine Schlussfolgerungen daraus ziehen, weil wegen dem Stern-Operator unendlich viele Möglichkeiten bestehen.
Man könnte auch die beiden Mengen als regulären Ausdruck formulieren. Wenn man festlegt, dass v [mm] \in [/mm] L und w [mm] \in [/mm] M, dann lassen sich alle Wörter der Sprache (L [mm] \cup [/mm] M)* mit dem Ausdruck (v+w)* und Wörter der Sprache (L*M*)* mit dem Ausdruck (v*w*)* beschreiben. Ich kann schon erkennen, dass mit beiden Ausdrücken die selbe Sprache beschrieben wird, mir fehlt aber der Ansatz wie man das mathematisch formulieren soll. Eine einfache Erklärung reicht wahrscheinlich nicht aus.
Daher würde ich mich freuen, wenn mir jemand sagt wie man dabei prinzipiell vorgeht. Danke im Voraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Mi 02.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
