Kleene Stern angewandt auf Mengen Beweise oder Widerlege

Neue Frage »

11.04.2012, 22:03	Auf diesen Beitrag antworten »
Iwant2bacomputerscientist	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


12.04.2012, 22:12	Auf diesen Beitrag antworten »
Karlito	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
14.04.2012, 08:06	Auf diesen Beitrag antworten »
Iwant2bacomputerscientist	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, 09:11	Auf diesen Beitrag antworten »
Iwant2bacomputerscientist	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?
Anzeige

14.04.2012, 10:13	Auf diesen Beitrag antworten »
Iwant2bacomputerscientist	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, 11:18	Auf diesen Beitrag antworten »
Karlito	Hallo, Kontaktenation ist richtig Beim Durchschnitt würde ich sagen deine Begründung ist falsch (das habe ich mir vorher nicht angeschaut, da es nicht mit in der Aufgabenstellung stand). Epsilon ist doch in beiden Mengen enthalten, also ist es doch kein Gegenbeispiel... Vereinigung ist richtig. Um Durchschnitt und Stern zu beweisen muss man meines Erachtens nach eine Art Strukturelle Induktion anwenden: Man schaut sich die Definition des Kleene Sterns an und beweist die Teilmengenbeziehung in beide Richtungen. Zu unterscheiden wären also die Fälle: und $[latex] L ^ {n+1} [/latex]$ . Für $[latex] (A \cap B)^* = A^* \cap B^[/latex]$ wäre also zu Zeigen, dass für jedes $[latex] w \in (A \cap B)^[/latex]$ gilt, dass es auch in $[latex] A^* \cap B^*[/latex]$ enthalten ist und andersrum. In Anlehnung an Wikipedia zeigt man das also erst für $[latex] w = \epsilon[/latex]$ und dann für $[latex] w = x \circ y \in L^{n+1}[/latex]$ mit $[latex] x \in L^n[/latex]$ und $[latex] y \in L[/latex]$ . Ich hoffe das liefert Dir einen guten Ansatz. VG, Karlito Edit: - Irgendein Wort mit $[latex]\epsilon[/latex]$ konkateniert ergibt immer das Wort selbst. D.h. $[latex] \epsilon \circ \epsilon = \epsilon[/latex]$
15.04.2012, 11:44	Auf diesen Beitrag antworten »
Iwant2bacomputerscientist	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, 13:36	Auf diesen Beitrag antworten »
Karlito	Könntest du deine Lösung noch posten? VG, Karlito
19.05.2012, 21:07	Auf diesen Beitrag antworten »
Iwant2bacomputerscientist	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:29	Auf diesen Beitrag antworten »
Iwant2bacomputerscientist	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*

Neue Frage »

Antworten »

Kleene Stern angewandt auf Mengen Beweise oder Widerlege

Verwandte Themen