 Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
|
|
| Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
     |
Meine Frage:
Sei E (sigma) ein Alphabet und A,B (sind) Teilmengen von E* formale Sprachen. Beweisen oder widerlegen Sie!
(A U B)*= A* U B*
(A ° B)*=A* ° B*
(A*)*= A*
Meine Ideen:
Zuerst dachte ich das ich die mathematische Mengenlehre hier anwenden kann, aber ich weiß nicht so recht was ich mit dem Kleene Stern machen soll. Ich weiß, dass der Kleene Stern auf eine beliebig oft iterierte Konkatenation hinweist, aber ich weiß nicht wie ich hier anfangen soll. Bitte um Hilfe
|
|
11.04.2012 22:03 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
 |
|
Hallo,
mit Mengenbeweisen bist du nicht schlecht beraten. Aber im speziellen hier bei dieser Aufgabe ist es günstig, erstmal nach Gegenbeispielen zu suchen. Du wirst sehr schnell feststellen, dass es nur einen Beweis zu führen gilt.
Konstruiere eine minimale Beispielsprache und erstelle die ersten Paar Wörter aus den jeweiligen Mengen.
Bei dem Beweis bin ich auch noch am schauen, wie man den am besten führt. Sollte eigentlich simpel sein, aber ich tu mich schwer mit sowas. Kannst ja erstmal Posten was dein zwischenergebnis ist (die Gegenbeispiele). Den Beweis schauen wir uns dann gemeinsam an.
VG,
Karlito
|
|
|
12.04.2012 22:12 |
|
|
|
|
Hallo Karlito,
vielen Dank für den Tipp, also ich habe mir ein Beispiel für die Vereinigung ausgedacht:
Sei Sigma die Menge der natürlichen Zahlen.
Sei A={1,2} und B={7,8}
(A U B)* = { e (leere Wort), 1, 2,7,8,11,12,17,18,21,22,27,28,71,72,77, 78,81,82,87, 88, 111,112,117,118,121,122,127,128,171,172,177,178,181,182,187,188, ... }
A* U B* = {e(leere Wort),1,2,7,8,11,12,21,22,77,78,87,88,112,121,122,211,212, 221,222,777,787, ..}
=> 71 ist Element (A U B)* aber nicht Element A* U B*.
Wäre das so richtig?
|
|
|
14.04.2012 08:06 |
|
|
|
|
Bei der Aufgabe:
( A [Durchschnitt] B)* = A* [Durchschnitt] B*
Annahme die Aussage ist falsch:
Sei A={1,2} und B={7,8}
Dann ist : A [Durchschnitt] B = leere Menge
Dann ist: ( A [Durchschnitt] B)* = [leeres Wort] oder?
A* und B* wie oben, aber A* [Durchschnitt] B* wäre dann ja auch das leere Wort. Also
hätte ich hier ein Widerspruch zur Annahme und die Aussage wäre richtig. Oder?
|
|
|
14.04.2012 09:11 |
|
|
|
|
Bei der Aufgabe:
(A°B)*= A* ° B* , mit ° ist die Konkatenation gemeint.
Falsche Aussage! Denn
Sei A= {1,2} und B={5,6}
A°B={15,26} , (A°B)*= { leere Wort, 15,26, 1515, 1526,2615,2626,151515,151526,152615,152626,261515,261526,262615,262626, ...}
A*°B*={leere Wort (2 Mal hintereinander(weiss gar nicht, ob das geht)), 15,26,1155,1256,2165,2266,111555,112556,121565,122566,221655,222656,211665,
212666 ...}
z.B der String 1515 ist Element (A°B)*, aber nicht Element A*°B*
Ist das richtig?
|
|
|
14.04.2012 10:13 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
|
14.04.2012 11:18 |
|
|
|
|
Vielen Dank Karlito,
Das war ein guter Ansatz. Ich habe die Aufgabe jetzt gelöst.
Nochmals Danke für Deine Hilfe
VG
|
|
|
15.04.2012 11:44 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Könntest du deine Lösung noch posten?
VG,
Karlito
|
|
|
15.04.2012 13:36 |
|
|
|
|
Hallo Ihr Lieben,
also hier kommt die Lösung zu (A*)*=A*
z.z. (A*)*=A*
Zuerst kommt ein Zwischenbeweis:
z.z. (A*)^n = A* (mit vollständiger Induktion)
Induktionsanfang: n=1 : (A*)^1=A* dies ist eine wahre Aussage
Induktionsvoraussetzung: (A*)^n = A*
Induktionsschritt: n --> n+1
Induktionsbeweis:
(A*)^n+1 = (A*) ^n ° A* wobei ich ° für die Multiplikation verwende
Ind.Vor. = A* ° A*
= {vw I v Element A*, w Element A*} wobei I für ein
senkrechten Strich steht
={ v1 v2 ...vn w1 w2 ...wm I n,m >=0, vi, wi ElementA} (1,2,n,m,i
sind Indizes)
={z1 z2 ... zn+m I n+m>=0, zi Element A}
= A* q.e.d vom Zwischenbeweis.
(A*)*= (A*)^1 U (A*)^2 U (A*)^3 U .... wobei U für
Vereinigung steht
wegen des Zwischenbeweises
= A* U A* U A* U ....
= A* q.e.d
|
|
|
19.05.2012 21:07 |
|
|
|
|
Jetzt kommt,Lösung zur Aussage mit dem Durchschnitt
(A (Durchschnitt) B)* =A* (Durchschnitt) B* dies ist eine falsche Aussage
Gegenbeispiel: Sei A={1,0} und B={10}
A* (Durchschnitt) B* = { e, 1, 0, 10, ...} (Durchschnitt) { e, 10, 1010, ... }
= { e, 10, 1010, ... }
= (10)*
(A (Durchschnitt) B )* = O/ * = { e } wobei O/ die Leere Menge ist
Daraus folgt
(A(Durchschnitt)B )*=O/*= { e } ist nicht gleich (10)*= A* (Durchschnitt) B*
|
|
|
19.05.2012 21:29 |
|
|
|
