Die Mathe-Redaktion - 10.12.2018 14:36 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 757 Gäste und 18 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Beweis: Algebra der Wörter ist ein Monoid
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Beweis: Algebra der Wörter ist ein Monoid
Inf0rmatiker
Junior Letzter Besuch: im letzten Monat
Dabei seit: 14.11.2018
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-11-14 17:40


Hallo,

komme bei folgender Aufgabe nicht weiter:



Mein Ansatz: ich weiß nur, dass ein Monoid folgende Eigenschaften hat:
Abgeschlossenheit, Assoziativität und ein neutrales Element.

Wäre super, wenn mir jemand helfen könnte.

Viele Grüße




  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 1800
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-11-14 17:45


Hallo,

2018-11-14 17:40 - Inf0rmatiker im Themenstart schreibt:

Mein Ansatz: ich weiß nur, dass ein Monoid folgende Eigenschaften hat:
Abgeschlossenheit, Assoziativität und ein neutrales Element.


Das ist korrekt, aber vielleicht zu einfach formuliert.
Womit genau hast du Probleme?

Kannst du Abgeschlossenheit zeigen?
Was ist hier das neutrale Element?






  Profil  Quote  Link auf diesen Beitrag Link
Inf0rmatiker
Junior Letzter Besuch: im letzten Monat
Dabei seit: 14.11.2018
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-11-14 22:56


2018-11-14 17:45 - PrinzessinEinhorn in Beitrag No. 1 schreibt:
Hallo,

2018-11-14 17:40 - Inf0rmatiker im Themenstart schreibt:

Mein Ansatz: ich weiß nur, dass ein Monoid folgende Eigenschaften hat:
Abgeschlossenheit, Assoziativität und ein neutrales Element.


Das ist korrekt, aber vielleicht zu einfach formuliert.
Womit genau hast du Probleme?

Kannst du Abgeschlossenheit zeigen?
Was ist hier das neutrale Element?

Ich hab noch Probleme damit, etwas formal zu beweisen.

Das neutrale Element im Zusammenhang mit der Multiplikation 1(?)

Wobei ich mir hier auch nicht sicher bin, da mich der Satz "wobei · der binäre Konkatenationsoperator und fed-Code einblenden
das Leerwort ist", verwirrt.







  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1949
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-11-14 22:59

\(\begingroup\)
Hier gibt es keine Multiplikation und keine $1$.

Was ist die zweistellige Verknüpfung der Struktur und was wird wohl deren neutrales Element sein?


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 1800
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-11-15 07:26

\(\begingroup\)
2018-11-14 22:56 - Inf0rmatiker in Beitrag No. 2 schreibt:

Das neutrale Element im Zusammenhang mit der Multiplikation 1(?)

Wobei ich mir hier auch nicht sicher bin, da mich der Satz "wobei · der binäre Konkatenationsoperator und fed-Code einblenden
das Leerwort ist".


Das liegt daran, dass du die Definition nicht sorgfältig wiedergibst.

Die Verknüpfung auf der Menge $\Sigma^\ast$ is gegeben durch $\circ$. Was hier die Konkatenation zweier Wörter bedeutet. Daher das "hintereinanderschreiben" von zwei Wörtern.

Daher:

$\circ: \Sigma^\ast\times\Sigma^\ast\to\Sigma^\ast$, $(w, v)\mapsto w\circ v=wv$

Wobei $wv$ hier eben nicht Multiplikation bedeutet.
Wir haben zwei Wörter $w,v\in\Sigma^\ast$. Diese bestehen aus Buchstaben aus dem Alphabet $\Sigma$. Wie dieses Alphabet aussieht, wissen wir nicht. Es ist auch nicht wichtig.
Jedenfalls hat $w$ und $v$ dann so eine Form:

$w=w_1w_2\dotso w_n$

$v=v_1v_2\dotso v_m$

Dann ist $wv=w_1w_2\dotso w_nv_1\dotso v_m$

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Inf0rmatiker
Junior Letzter Besuch: im letzten Monat
Dabei seit: 14.11.2018
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-11-15 14:26

\(\begingroup\)
2018-11-15 07:26 - PrinzessinEinhorn in Beitrag No. 4 schreibt:
2018-11-14 22:56 - Inf0rmatiker in Beitrag No. 2 schreibt:

Das neutrale Element im Zusammenhang mit der Multiplikation 1(?)

Wobei ich mir hier auch nicht sicher bin, da mich der Satz "wobei · der binäre Konkatenationsoperator und fed-Code einblenden
das Leerwort ist".


Das liegt daran, dass du die Definition nicht sorgfältig wiedergibst.

Die Verknüpfung auf der Menge $\Sigma^\ast$ is gegeben durch $\circ$. Was hier die Konkatenation zweier Wörter bedeutet. Daher das "hintereinanderschreiben" von zwei Wörtern.

Daher:

$\circ: \Sigma^\ast\times\Sigma^\ast\to\Sigma^\ast$, $(w, v)\mapsto w\circ v=wv$

Wobei $wv$ hier eben nicht Multiplikation bedeutet.
Wir haben zwei Wörter $w,v\in\Sigma^\ast$. Diese bestehen aus Buchstaben aus dem Alphabet $\Sigma$. Wie dieses Alphabet aussieht, wissen wir nicht. Es ist auch nicht wichtig.
Jedenfalls hat $w$ und $v$ dann so eine Form:

$w=w_1w_2\dotso w_n$

$v=v_1v_2\dotso v_m$

Dann ist $wv=w_1w_2\dotso w_nv_1\dotso v_m$

Dann ist das leere Wort das neutrale Element?
fed-Code einblenden

Die () sollten nicht dabei sein.

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 1800
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-11-15 14:44

\(\begingroup\)
Ja, $\epsilon$ ist das neutrale Element.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Inf0rmatiker
Junior Letzter Besuch: im letzten Monat
Dabei seit: 14.11.2018
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2018-11-15 15:06

\(\begingroup\)
2018-11-15 14:44 - PrinzessinEinhorn in Beitrag No. 6 schreibt:
Ja, $\epsilon$ ist das neutrale Element.

Und wie muss ich jetzt vorgehen, um zu zeigen, dass die gegebene Algebra ein Monoid ist?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1949
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-11-15 15:13

\(\begingroup\)
Du musst zeigen, dass alle Axiome erfüllt sind.

Die Axiome zum neutralen Element hast du ja schon mehr oder weniger gezeigt. Das könntest du noch etwas schöner schreiben.

Fehlt also noch, dass $\circ$ eine innere Verknüpfung und dass sie assoziativ ist.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Inf0rmatiker
Junior Letzter Besuch: im letzten Monat
Dabei seit: 14.11.2018
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2018-11-15 15:47

\(\begingroup\)
2018-11-15 15:13 - DerEinfaeltige in Beitrag No. 8 schreibt:
Du musst zeigen, dass alle Axiome erfüllt sind.

Die Axiome zum neutralen Element hast du ja schon mehr oder weniger gezeigt. Das könntest du noch etwas schöner schreiben.

Fehlt also noch, dass $\circ$ eine innere Verknüpfung und dass sie assoziativ ist.

Wie meinst du das mit dem schöner schreiben? Ausführlicher?

Zur Assoziativität: laut Aufgabe, sollte ich diese durch die Definition der Konkatenation zeigen.

Definition Konkatenation: fed-Code einblenden
fed-Code einblenden

Nur, wie kann ich dadurch Assoziativität beweisen?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1949
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-11-15 16:02

\(\begingroup\)
$w\circ\epsilon=w$ ist erst einmal nur eine zu beweisende Behauptung.
Schöner wäre es daher, es anhand eurer Definition der Konkatenation tatsächlich vorzurechnen.


Assoziativität kannst du ebenfalls zeigen, indem du mit eurer genannten Definition nachweist/nachrechnest, dass $(u\circ v)\circ w=u\circ (v\circ w)$ gilt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Inf0rmatiker
Junior Letzter Besuch: im letzten Monat
Dabei seit: 14.11.2018
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2018-11-15 17:01

\(\begingroup\)
2018-11-15 16:02 - DerEinfaeltige in Beitrag No. 10 schreibt:
$w\circ\epsilon=w$ ist erst einmal nur eine zu beweisende Behauptung.
Schöner wäre es daher, es anhand eurer Definition der Konkatenation tatsächlich vorzurechnen.


Assoziativität kannst du ebenfalls zeigen, indem du mit eurer genannten Definition nachweist/nachrechnest, dass $(u\circ v)\circ w=u\circ (v\circ w)$ gilt.

Beim formalen Beweisen hab ich eben noch Probleme...denn für v und w Zahlen einsetzen und Beispiele aufschreiben, reicht nicht als Beweis, oder?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 1800
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-11-15 17:05

\(\begingroup\)
Wie gesagt sind $v$ und $w$ keine Zahlen, sondern Wörter.
Und nein. Ein Beweis durch ein Beispiel funktioniert nicht.
Du kannst eine Aussage mit einem Beispiel widerlegen.

Wie habt ihr Konkatenation definiert?
Schreibe die Definition mal auf.

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Inf0rmatiker
Junior Letzter Besuch: im letzten Monat
Dabei seit: 14.11.2018
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2018-11-15 19:20

\(\begingroup\)
2018-11-15 17:05 - PrinzessinEinhorn in Beitrag No. 12 schreibt:
Wie gesagt sind $v$ und $w$ keine Zahlen, sondern Wörter.
Und nein. Ein Beweis durch ein Beispiel funktioniert nicht.
Du kannst eine Aussage mit einem Beispiel widerlegen.

Wie habt ihr Konkatenation definiert?
Schreibe die Definition mal auf.



Die Definition laut Skript lautet:

Seien x, y Wörter, wir schreiben x · y für die Konkatenation von x und y: Sei x = a1a2 · · · ai, y = b1b2 · · · bj,
dann gilt x·y = a1a2 · · · aib1b2 · · · bj
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1949
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2018-11-16 09:44

\(\begingroup\)
Das sieht doch brauchbar aus, auch wenn deine obige Definition mit den Klammern mir besser gefällt, da man dort einfacher das leere Wort darstellen kann.

Beliebiges Wort $u = (u_1u_2\dots u_{n_u})$.
Leeres Wort $\epsilon = ()$.


Für die Assoziativität musst du nun drei beliebige Worte $u,v,w$ konkatenieren.

Einmal erst $u$ und $v$ zu $uv$ und dann $uv$ mit $w$.
Einmal erst $v$ und $w$ zu $vw$ und dann $u$ mit $vw$.

Mit etwas Glück (sprich: wenn du es richtig machst) kommt in beiden Fällen so etwas wie $uvw = (u_1u_2\dots u_{n_u}v_1v_2\dots v_{n_v}w_1w_2\dots w_{n_w})$ heraus.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Inf0rmatiker hat die Antworten auf ihre/seine Frage gesehen.
Inf0rmatiker wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]