0 Daumen
3,9k Aufrufe

Aufgabe:

A = {a, b}

Definieren Sie eine binäre Operation  : A ∗ × A ∗ → A ∗

Soll kommutativ, aber nicht assoziativ sein.
Anschließend beweisen.


Problem/Ansatz:

Jedoch weiß ich nicht wie ich zeigen soll, dass diese Operation assoziativ ist.
Bräuchte das Alphabet A neben den Teilmengen {a, b} nicht noch ein c um zu zeigen, dass diese assoziativ ist?

Ich bedanke mich im Voraus :)

Erklärung: * ist der Kleene-Stern

Die Menge aller möglichen Wörter/Zeichenkombinationen
Bsp.
A0 = {} = leere Menge
A 1 = {a, b}
A 2 = {aa, ab, ba, bb}
A* 0 = A0 mit A 1 mit A 2 bis An

Avatar von

Was genau soll denn mit dem Stern bei  A∗  gemeint sein ?

Vermutlich ist das der Kleene-Stern.

Richtig?

Die Menge aller möglichen Wörter/Zeichenkombinationen
Bsp.
A0 = {} = leere Menge
A 1 = {a, b}
A 2 = {aa, ab, ba, bb}
A* 0 = A0 mit A 1 mit A 2 bis An

Falls das weiterhilft

Genau Lu, es handelt sich um einen kleinen Stern über dem Alphabet A.

Ja, das ist wohl so gemeint. Den Begriff "Kleene-Stern" kannte ich allerdings nicht.

A∗  wäre also dann die Menge aller endlich langen Wörter (Buchstabenfolgen einer Länge n∈ℕ₀ ), welche nur aus den Buchstaben a und b gebildet werden können.

Ist vermutlich theoretische Informatik. Oder macht ihr das in Mathe?

Hierbei handelt es sich tatsächlich um eine Aufgabe der theoretischen Informatik. @Lu

Ok. Ich verschiebe unsere Diskussion dann später in die Stacklounge (Informatik). Gleiches Login wie hier.

"rumar hat eine Definition gewählt für kommutativ und assoziativ"

NEIN !

Meine Operation ist kommutativ, aber nicht assoziativ, wie ich auch schon gezeigt habe.

Sehr gut, dann präzisiere ich die Überschrift.

4 Antworten

+1 Daumen

Irgendeine Definition von Abstand von Wörtern habt ihr schon behandelt.

Du könntest vielleicht einen "Abstand" der Wörter (ein "Differenzwort") verwenden bzw. definieren.

aaa und bbb haben den "Abstand" bbb

aaa und aab haben den "Abstand" aab

aab und aaa haben den "Abstand" aab

usw.

Meine Definition

Definition: Differenzwort 

Wörter Buchstaben für Buchstaben vergleichen: Wenn gleich: Setze a, Wenn ungleich: Setze b. Das solange beide Wörter Buchstaben haben.

Falls du sie verwenden willst, erst mal kontrollieren, ob die verlangten Eigenschaften vorhanden sind.


Idee von hier https://www.mathelounge.de/665492/kommutativ-aber-nicht-assoziativ?show=665520#c665520

Avatar von

Danke für deine Antwort Lu,
habe ich richtig verstanden, dass die Differenz aus zwei Mengen das Differenzwort ergibt?
Beispiel mit Zahlen: {1,2,3} und {3,4,5} = {4,5}
Müsste dann nicht
(aab und aaa haben den "Abstand" aab)
aab und aaa haben den "Abstand" aaa sein?

Ich bitte um Verständnis falls ich mich blöd anstelle :P

Wenn gleich: Setze a, Wenn ungleich: Setze b.

War meine Definition. Damit arbeite ich bei

aab und aaa haben den "Abstand" aab , da b und a am Schluss nicht gleich sind, nehme ich b an dritter Stelle. 

Mir ist mittlerweile Ihre Definition klar geworden, dennoch ist mir nicht bewusst wie ich Ihre Definition nütze, um meine Aufgabe zu beantworten.

Sehe gerade, dass du in der Überschrift kommutativ / assoziativ geschrieben hast. Was bedeutet das?

Soll kommutativ, aber nicht assoziativ sein.

Das ist das Ziel bei meiner Definition. Ein Gegenbeispiel für "assoziativ" musst du allerdings noch finden.

+1 Daumen

Ich denke, ich hätte eine mögliche Operation:

Sind u und v zwei Wörter aus  A∗ , dann bildet man das neue Wort  w := u • v , indem man die beiden vorgegebenen Wörter in lexikographischer (alphabetischer) Reihenfolge aneinanderfügt.

Beispiele:

a • ab = aab

ab • a = aab

(abba • bba) • baa =  abbabba • baa =  abbabbabaa

abba • (bba • baa) = abba • baabba = abbabaabba

Avatar von

Vielen Dank Rumar!
Jedoch hätte ich eine Frage bezüglich der Anordnung der Wörter.
Darf man die Anordnung selbstständig bestimmen?
Laut Ihnen a • ab = aab, ab • a = aab Also unabhängig ob zuerst (a) oder (ab) steht.
Und würde diese Aussage bereits als Beweis gelten?

Verdammter Scheibenkleister ...

Sorry. Auf diese Rückfrage hatte ich schon (in Mathelounge) eine ausführliche Antwort geschrieben. Als ich sie absenden wollte, kam die Meldung, dass der Thread geschlossen und hierher verschoben worden sei. Und meine Mühe mit dem Kommentar war also für die Katz' !

Nun musste ich mich erst mal neu hier einloggen, neues Passwort setzen - aber eben: mein Kommentar ist weg !

In meinem Kommentar hatte ich klipp und klar dargestellt, weshalb meine Operation kommutativ, aber nicht assoziativ ist.

Ich überlasse es nun den schlauen Moderatoren, meinen Kommentar wieder hervorzuholen und hier zu publizieren. Und eine Entschuldigung wäre auch angemessen.

Tut mir leid das zu hören. Leider bin ich neu in diesem Forum, könnten Sie mir sagen, an wen ich mich wenden soll bzw. wo ich den Moderatoren finde?
Der Wechsel auf das Stocklounge-Forum war nicht meine Entscheidung, falls Sie dies meinen.

Naja, natürlich habe ich auch keine Ahnung, wer da rumgefummelt hat. Mir fällt es nur schwer zu verstehen, weshalb ein Thread, der erst seit Stunden eröffnet worden ist und an dem verschiedene Leute noch arbeiten, plötzlich in ein anderes Forum umgepflanzt wird. Kann mir das jemand erklären ?

Es ist einfach sehr ärgerlich, wenn Gedanken, die man während etwa zwanzig Minuten oder so sorgfältig formuliert hat, einfach verschwinden.

Ich kann Ihr Missverständnis vollkommen nachvollziehen. Fühle mich selber etwas frustriert da Ihre Antwort mir bis dahin am meisten geholfen hat und ich mich schon auf Ihren Kommentar gefreut habe.
Ich wäre Ihnen zwar sehr dankbar, wenn Sie mir dennoch einen Ansatz zur Erklärung geben könnten, kann aber vollkommen nachvollziehen, wenn Sie dies nicht machen wollen.

Das ist bei mir kein Missverständnis, sondern Missmut bzw. Ärger.

OK.

Natürlich muss man bei einer binären Operation zuerst mal zwischen  u • v  und  v • u  unterscheiden. Bei der von mir vorgeschlagenen Operation des Aneinanderfügens der Wörter u und v in lexikographischer Reihenfolge ist aber sofort klar, dass diese Operation kommutativ sein muss, denn bei zwei voeinander verschiedenen Wörtern u und v ist stets eindeutig bestimmt, welches im gesamten "Lexikon" aller Elemente (Wörter) aus  der Menge A*  weiter vorne und welches weiter hinten steht. Im Fall  u = v  ist die Reihenfolge sowieso einerlei (oder nicht einmal erkennbar).

Dass die Operation hingegen nicht assoziativ ist, kann man mit einem einzigen Gegenbeispiel zeigen. Ein solches Gegenbeispiel hatte ich in meinem ersten Beitrag schon angegeben. Dort ist eben, wenn man  t:= "abba" , u:= "bba" , v:= "baa" setzt,

         (t • u) • v ≠  t • (u • v)

(es gäbe bestimmt noch einfachere Beispiele - aber ich bin halt immer noch ABBA-Fan)

Ich danke Ihnen vielmals für Ihre Antwort!

0 Daumen
Bräuchte das Alphabet A neben den Teilmengen {a, b} nicht noch ein c um zu zeigen, dass diese assoziativ ist?

Nein. Übliche Definition von Assoziativität einer Verknüpfung "*" über einer Menge N ist, dass

        (a*b)*c = a*(b*c) für alle a,b,c ∈ N

ist. Nirgends wird gefordert, dass das nur für den Fall a ≠ c und b ≠ c gelten muss.

Avatar von 5,6 k

Habe ich richtig verstanden, dass demnach a=c bzw. b=c seien kann?
Und rein theoretisch a=h seien kann solange a,b,c,h ∈ N gilt?

Habe ich richtig verstanden, dass demnach a=c bzw. b=c seien kann?

Es stellt sich die Frage, was a, b, c und h sind.

"Gegeben ist das Alphabet ∑ = {a,b,c}".

Hier sind a, b und c Elemente des Alphabets. Insbesondere sind a, b und c keine Variablen und es ist a ≠ b.

"Eine Verknüpfung "+" auf ∑* heißt kommutativ, wenn

        a + b = b + a für alle a,b ∈ Σ*

gilt."

Hier sind a und b Variablen, die für Elemente aus ∑* stehen. Das wird durch "für alle a,b ∈ Σ*" deutlich. Insbesondere muss a + b = b + a auch dann gelten, wenn a und b für das selbe Element aus Σ* stehen, wenn also a = b ist.

0 Daumen

Definitiv nicht der Mittelwert der Wortlängen

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community