Informatiker Board | Theoretische Informatik | Kleene Stern angewandt auf Mengen Beweise oder Widerlege

Informatiker Board » Themengebiete » Theoretische Informatik » Kleene Stern angewandt auf Mengen Beweise oder Widerlege » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 10 Beiträge
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*
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
Karlito	Könntest du deine Lösung noch posten? VG, Karlito
Iwant2bacomputerscientist	Vielen Dank Karlito, Das war ein guter Ansatz. Ich habe die Aufgabe jetzt gelöst. Nochmals Danke für Deine Hilfe VG
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]$
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?
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?
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?
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
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