Beim Lernen sind mir ein paar Sachen im F2-Skript aufgefallen:
Seite 27 ganz unten: Dort müsste es doch heissen [img]
http://mokrates.de/cgi-bin/texstring?x=%5Csum_%7Bl=0%7D%5Ej%202%5E%7Bi_l%7D[/img] statt [img]
http://mokrates.de/cgi-bin/texstring?x=%5Csum_%7Bl=0%7D%5Ej%20m_%7Bi_l%7D%5Ccdot%202%5E%7Bi_l%7D[/img], oder?
Seite 30: dort müsste es [img]
http://mokrates.de/cgi-bin/texstring?h%5Ccirc%20i=f[/img] statt
[img]
http://mokrates.de/cgi-bin/texstring?i%5Ccirc%20h=f[/img]
heissen, oder?
Und dann wird auf Seite 37 von Abzählungen von
[img]
http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BR%7D%5Em[/img]
gesprochen (ich nehme an, da ging es früher mal um Abzählungen von
[img]
http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BN%7D%5Em[/img]).
Und noch eine Frage zu Seite 33:
[img]
http://mokrates.de/cgi-bin/texstring?D_1[/img] ist doch noch nichtmal endlich erzeugt (weil jedes endlich erzeugte Monoid regulär ist), oder?
tschüs
Georg
1) S.27. Aufgrund des nachfolgenden Beispiels würde ich ja sagen. f ist dann für alle x mit 1 <= x <= 2^k -1 eine nicht leere Teilmenge von M und für x = 0 bzw. x >= 2^k die leere Menge.
2) S.30. Dass kann man wohl so und so definieren, kommt also darauf an, welches Mathebuch du gerade liest. In den deutschen Standardlehrbüchern ist glaube ich die Variante h*i = f gängiger. (Um h(i(x)) = f(x) fuer alle x zu verdeutlichen. i*h entspricht eher der Leserichtung im Diagramm.)
3) S.37. Die definierte Ordnung ist doch in Ordnung, oder? Nur hier den Begriff "Abzählung" zu benutzen ist vielleicht nicht ganz so gut, denn (anders als bei den Wörtern der vorherigen Seite, bei denen insb. nur Endliche viele Buchstaben zur Auswahl stehen) kann man hier ja nicht "abzählen" (im Sinner einer Bijektion von den Natürlichen Zahlen), da man bspw. zu zwei Vektoren stets einen finden kann, der noch dazwischen liegt.
4) S.33. Klingt überzeugend [img]
http://www.fb18.de/gfx/25.gif[/img]
Cheers,
Frank
Seite 27 ganz unten: Dort müsste es doch heissen [img]http://mokrates.de/cgi-bin/texstring?x%20=%20%5Csum%5Climits_%7Bl=0%7D%5Ej%202%5E%7Bi_l%7D[/img] statt [img]http://mokrates.de/cgi-bin/texstring?x=%5Csum%5Climits_%7Bl=0%7D%5Ej%20m_%7Bj_l%7D%5Ccdot%202%5E%7Bj_l%7D[/img] ?
Ja, das war falsch, richtig wäre jedoch etwas Anderes, nämlich::
[img]
http://mokrates.de/cgi-bin/texstring?$$%0Af(x)%20:=%20%5Ccases%7B%5C%7Bm_%7Bi_0%7D,%20%5Cdots,%20m_%7Bi_j%7D%5C%7D%20%20&%20falls%0A$x=%5Csum%5Climits_%7Bl=0%7D%5E%7Bj%7D%5Bm_%7Bi_l%7D%5Cin%20M'%5D%5Ccdot%202%5E%7Bi_l%7D$%5Ccr%0A%5Cemptyset%20&%20sonst%7D%20$$[/img]
Nur so wird der Faktor vor der entsprechenden Zweierpotenz genau dann 1, wenn der Index [img]
http://mokrates.de/cgi-bin/texstring?i_l[/img] des Wortes
[img]
http://mokrates.de/cgi-bin/texstring?m_%7Bi_l%7D[/img] derjenige ist, für den [img]
http://mokrates.de/cgi-bin/texstring?m_%7Bi_l%7D%5Cin%20M'[/img] gilt.
Eine Zahl wird so also zunächst in die Binärdarstellung umgeformt, und dann bestimmen diejenigen 1-en,
die in den Positionen 0 bis k-1 (v.r.n.l.) liegen, welche Elemente von M in M' vorkommen.
Von [img]
http://mokrates.de/cgi-bin/texstring?%5Bx%5D_2[/img] bleiben dabei alle höheren Stellen als k-1 unberücksichtigt.
Danke für den Fehler-Hinweis!
zu Punkt 2. hatte Azure Recht, bei den anderen zwei antworte ich später, sonst wird's zu lang.
M.J.
Und dann wird auf Seite 37 von Abzählungen von [img]http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BR%7D%5En[/img]
gesprochen (ich nehme an, da ging es früher mal um Abzählungen von [img]http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BN%7D%5En[/img]).
Ok, Abzählung sind's wirklich nicht, aber die Ordnungen und deren Erweiterungen gehen noch gut so verallgemeinert.
Streichen Sie also in dem Text oben auf Seite 37:
Oftmals ben"otigt man Abz"ahlungen und Ordnungen auf [img]http://mokrates.de/cgi-bin/texstring?%5Cmathbb%7BR%7D%5En[/img] …
einfach das "Abz"ahlungen und", dann passt's schon.
auch hier wieder Dank dem/der aufmerksamen Leser{in},
M.J.
Und noch eine Frage zu Seite 33:
ist doch noch nichtmal endlich erzeugt (weil jedes endlich erzeugte Monoid regulär ist), oder?
Beinahe richtig: Was soll das heissen, "jedes endlich erzeugte Monoid ist regulär"? Diesen Satz zitieren Sie wie/bzw wo?
Die Menge aller Elemente des Monoides, hier ist das die Dycksprache(!), hat eine syntaktische Rechtskongruent von endlichem Index genau dann,
wenn sie regulär ist. OK, und das ist ein Satz im Skript. Aber das ist ja nicht (von jedem) sofort zu sehen, und es ist doch eh' einfacher
[img]
http://mokrates.de/cgi-bin/texstring?D_1%20%5Ccap%20%5C%7Ba%5C%7D%5E*%5C%7Bb%5C%7D%5E*%20=%20DUP%20[/img] zu bilden, und DUP war schon als nichtregulär kennzeichnet, oder nicht?
M.J.
Und noch eine Frage zu Seite 33:
ist doch noch nichtmal endlich erzeugt (weil jedes endlich erzeugte Monoid regulär ist), oder?
Beinahe richtig: Was soll das heissen, "jedes endlich erzeugte Monoid ist regulär"? Diesen Satz zitieren Sie wie/bzw wo?
Wenn [img]
http://mokrates.de/cgi-bin/texstring?%24%24M%3D%5C%7Ba_1%2C%5Cldots%2Ca_n%5C%7D%5Csubseteq%20%5CSigma%5E*%24%24[/img], dann ist doch
[img]
http://mokrates.de/cgi-bin/texstring?%24%24(a_1%2B%5Cldots%2Ba_n)%5E%2B%24%24[/img] ein rationaler Ausdruck fuer [img]
http://mokrates.de/cgi-bin/texstring?%24%24M%5E%2B%24%24[/img]. Damit ist doch jedes endlich erzeugte Monoid regulaer.
Die Menge aller Elemente des Monoides, hier ist das die Dycksprache(!), hat eine syntaktische Rechtskongruent von endlichem Index genau dann,
wenn sie regulär ist. OK, und das ist ein Satz im Skript. Aber das ist ja nicht (von jedem) sofort zu sehen, und es ist doch eh' einfacher
[img]http://mokrates.de/cgi-bin/texstring?D_1%20%5Ccap%20%5C%7Ba%5C%7D%5E*%5C%7Bb%5C%7D%5E*%20%3D%20DUP%20[/img] zu bilden, und DUP war schon als nichtregulär kennzeichnet, oder nicht?
Genau. Man weiss also, dass die Dyck-Sprache nicht regulaer ist und damit nicht endlich erzeugt.
2) S.30. Dass kann man wohl so und so definieren, kommt also darauf an, welches Mathebuch du gerade liest. In den deutschen Standardlehrbüchern ist glaube ich die Variante h*i = f gängiger. (Um h(i(x)) = f(x) fuer alle x zu verdeutlichen. i*h entspricht eher der Leserichtung im Diagramm.)
Genau, aber auf Seite 29 (2.38) ist es so definiert, dass es nicht passt.
3) S.37. Die definierte Ordnung ist doch in Ordnung, oder? Nur hier den Begriff "Abzählung" zu benutzen ist vielleicht nicht ganz so gut,
Genau das meinte ich. Die Ordnung ist in Ordnung.
Aber die Auswahl der richtigen 2er-Potenzen wird doch schon durch die Indizes i0 bis il erreicht.
Richtig, nur mit dem Iversonschen Prädikat wirds überdeutlich.
Wenn [img]http://mokrates.de/cgi-bin/texstring?%20%3D%20%5C%7Ba_1%2C%5Cdots%20a_n%5C%7D%20%5Csubseteq%20%5CSigma%5E*[/img], dann ist doch [img]http://mokrates.de/cgi-bin/texstring?(a_1%20%2B%20%5Cdots%20%2B%20%20a_n)%5E*[/img] ein rationaler Ausdruck fuer [img]http://mokrates.de/cgi-bin/texstring?M%5E%2B[/img]. Damit ist doch jedes endlich erzeugte Monoid regulaer.
Endlich erzeugte Monoide (und Gruppen) sind solche, die über endlichem Alphabet von Erzeugenden gebildet sind.
Endlich präsentierte Monoide (und Gruppen) sind solche, zu deren Definition (=Präsentation) endlich viele definierende Relationen ausreichen.
Jedes Monoid M ist Quotient eines freien Monoides [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*%20[/img] (ausführlicher notiert als [img]
http://mokrates.de/cgi-bin/texstring?%20%5B%5CSigma%5E*%2C%20%5Ccirc%5D[/img]) modulo einer Thue-Kongruenz [img]
http://mokrates.de/cgi-bin/texstring?%5Cmathop%7B%25%0A%20%20%20%20%20%20%20%20%20%20%20%20%5CLongleftrightarrow%7D%5Climits%5E%7B%5C%2C*%7D%7D_%7B%5C!S%7D[/img] (reflexive, transitive, symmetrische Ersetzungsrelation á la Chomsky-Typ-0 Grammatik), die von einem endlichen Thue-System beschrieben wird.
Man schreibt das so: M= [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*%20%2F%20%5Cmathrel%7B%5Cmathop%7B%25%0A%20%20%20%20%20%20%20%20%20%20%20%20%5CLongleftrightarrow%7D%5Climits%5E%7B%5C%2C*%7D%7D_%7B%5C!S%7D[/img] .
Die Dycksprache über dem Klammerpaar {a,b} ist selbst ein Monoid (das sogenannte bizyklische Monoid) und ist
1. endlich generiert und auch
2. endlich präsentiert (durch das Thue-System: { (ab,[img]
http://mokrates.de/cgi-bin/texstring?%5Clambda[/img]) } und NICHT regulär.
Es gibt sogar endlich generierte und endlich präsentierte Monoide, deren Elemente (=Kongruenzklassen im Quotientenmonoid) nicht einmal kontextfrei sind!
Aber alles das geht weit über Grundstudiumsstoff hinaus!
Genau, aber auf Seite 29 (2.38) ist es so definiert, dass es nicht passt.
Richtig definiert in Zeilen 11,12 [img]
http://mokrates.de/cgi-bin/texstring?(f%5Ccirc%20g)(x)%20=f(g(x))[/img] nur auf Grund einer früheren Änderung blieb es auf S. 30, Z. -4 falsch! Dort muss tats"achlich [img]
http://mokrates.de/cgi-bin/texstring?h%5Ccirc%20i%20=f[/img] stehen!
Danke auch dafür, M.J.
PS. (das ist hier echt mühsam mit dem LaTeX, das bei Klick auf Bestätigung die image_Information immer ganz unten einfügt, und nicht dort wo der Cursor ist. Auch ist kein schnelles cut-and-paste von der LaTeX-Vorschau möglich….)
Aber alles das geht weit über Grundstudiumsstoff hinaus!
Irgendwie gibt mir das Hoffnung ^^
PS. (das ist hier echt mühsam mit dem LaTeX, das bei Klick auf Bestätigung die image_Information immer ganz unten einfügt, und nicht dort wo der Cursor ist. Auch ist kein schnelles cut-and-paste von der LaTeX-Vorschau möglich….)
Ich nehme an, sie benutzen den LaTeX-Button in der Symbolleiste? Man kann auch einfach, ohne die Finger von der Tastatur zu nehmen, [LATEX]Latex-Code[/LATEX] schreiben, dann erscheint die Grafik genau an der Stelle. Braucht dann aber JavaScript.
Man kann auch einfach, ohne die Finger von der Tastatur zu nehmen, [ LATEX]Latex-Code[/LATEX] schreiben, dann erscheint die Grafik genau an der Stelle. Braucht dann aber JavaScript
Oh, danke!
Nebenbei: wie schreibe ich hier nun [ LATEX] ohne den Zwischenraum zwischen [ und LATEX, so wie Sie das ja taten? Ich hab das in den FAQ's oder den Anleitungen so schnell nicht gefunden…
wie haben Sie denn den Text von UncleOwen zitiert?
durch CopyPaste?
wenn Sie auf den Zitieren-Button unter dem jeweiligen Beitrag drücken,
sehen sie die Schreibweise:
\ [ LATEX \ ] Latex-Code \ [ /LATEX \ ]
Endlich erzeugte Monoide (und Gruppen) sind solche, die über endlichem Alphabet von Erzeugenden gebildet sind.
Ja, so hatte ich das auch gemeint. Nach Definition 2.43 ist ein Monoid M' endlich erzeugt, wenn es eine endliche Menge M gibt mit
[img]
http://mokrates.de/cgi-bin/texstring?%20M'%3DM%5E*[/img]. (Oder werfe ich hier zwei Begriffe durcheinander?)
Und ich meinte: Wenn D_1 endlich erzeugt wäre, müsste es eine solche Menge M mit [img]
http://mokrates.de/cgi-bin/texstring?M%5E*%3DD_1[/img] geben. Dann könnte man aber, wenn man die Elemente von M mit a_1,…,a_n bezeichnet, einen Rationalen Ausdruck für D_1 angeben, nämlich [img]
http://mokrates.de/cgi-bin/texstring?(a_1%2B%5Cldots%2Ba_n)%5E*[/img]
(vorher hatte ich + geschrieben, muss aber ein Stern sein).
(Rest des Postings, konnte ich nicht quoten, wegen der Bilderobergrenze von 8 Bildern)
Das geht auch über das hinaus, was ich gemeint habe :)
Ist das M=[img]
http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*%20%2F%20%5Cmathrel%7B%5Cmathop%7B%25%0D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5CLongleftrightarrow%7D%5Climits%5E%7B%5C%2C*%7D%7D_%7B%5C!S%7D[/img] eigentlich als Isomorphie zu verstehen (so, dass jedem Wort eine Kongruenzklasse entspricht) oder ist dann [img]
http://mokrates.de/cgi-bin/texstring?D_1[/img] die Kongruenzklasse, in der auch [img]
http://mokrates.de/cgi-bin/texstring?%5Clambda[/img] enthalten ist (letzteren Fall würde ich verstehen, aber dann ist [img]
http://mokrates.de/cgi-bin/texstring?D_1[/img] nicht das Monoid [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*%2F%20%5Cmathrel%7B%5Cmathop%7B%25%0D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5CLongleftrightarrow%7D%5Climits%5E%7B%5C%2C*%7D%7D_%7B%5C!S%7D[/img], oder? Wie ist das gemeint?)
tschüs
Georg
Endlich erzeugte Monoide (und Gruppen) sind solche, die über endlichem Alphabet von Erzeugenden gebildet sind.
Das können auch endliche Mengen statt Alphabete sein, und von frei erzeugten Monoiden wurde an dieser Stelle der Def. ohnehin (noch) nicht gesprochen!
Ja, so hatte ich das auch gemeint. Nach Definition 2.43 ist ein Monoid M' endlich erzeugt, wenn es eine endliche Menge M gibt mit
. (Oder werfe ich hier zwei Begriffe durcheinander?)
Und ich meinte: Wenn D_1 endlich erzeugt wäre, müsste es eine solche Menge M mit geben.
Def 2.43 sagt (oder sollte das zumindest sagen), wenn M endlich ist, dann ist [img]
http://mokrates.de/cgi-bin/texstring?M%5E*[/img] endlich erzeugt und nicht, dass jedes endlich erzeugte Monoid so aussehen muss!
Jedes Monoid ist isomorph zu einem Qotientenmonoid [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*%2F%20%5Cequiv%20[/img] und ist endlich erzeugt, wenn [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma[/img] endlich ist und endlich repräsentiert, wenn die Kongruenzrelation [img]
http://mokrates.de/cgi-bin/texstring?%20%5Cequiv[/img] von endlich vielen Relationen generiert wird.
Die Dycksprache über dem Klammerpaar {a,b} ist selbst ein Monoid (das sogenannte bizyklische Monoid) und ist
1. endlich generiert und auch
2. endlich präsentiert (durch das Thue-System: { (ab,) } und NICHT regulär.
Noch ein kleiner Lapsus: Das sogenannte bizyklische Monoid ist gerade
[img]
http://mokrates.de/cgi-bin/texstring?%20%5C%7Ba%2Cb%5C%7D%5E*%20%2F%20%5Cmathrel%7B%5Cmathop%7B%5CLongleftrightarrow%7D%5Climits%5E%7B%5C%2C*%7D%7D_%7B%5C!S%7D%0A[/img], wobei [img]
http://mokrates.de/cgi-bin/texstring?%5Cmathrel%7B%5Cmathop%7B%5CLongleftrightarrow%7D%5Climits%5E%7B%5C%2C*%7D%7D_%7B%5C!S%7D%20%3D%20%5C%7B(x%2Cy)%5Cin%20%5C%7Ba%2Cb%5C%7D%5E*%5Ctimes%20%5C%7Ba%2Cb%5C%7D%5E*%20%7C%20%5Cforall%7Bu%2Cv%20%5Cin%20%5C%7Ba%2Cb%5C%7D%5E*%7D%3Auxv%5Cin%20D_1%20%5Cmathop%7B%5Cleftrightarrow%7D%20uyv%5Cin%20D_1%5C%7D%20[/img],
Die Menge [img]
http://mokrates.de/cgi-bin/texstring?D_1%20[/img] ist tatsächlich die Kongruenzklasse [img]
http://mokrates.de/cgi-bin/texstring?%20%5B%5Clambda%5D_%7B%5Cmathrel%7B%5Cmathop%7B%5CLongleftrightarrow%7D%5Climits%5E%7B%5C%2C*%7D%7D_%7B%5C!S%7D%0A%7D%20[/img] des bizyklischen Monoides.
Aber wir wollen hier doch keinen Mathematiker-Plausch halten oder?
Trotzdem schön, das sich jemand so für Details interessiert,
good luck, M.J.
Ah, dann ist mir das klar.
[img]
http://www.fb18.de/gfx/24.gif[/img] Das ist schön. Zur allgemeinen Beruhigung: Ich habe irgendwo zwischendrin den Faden verloren. Für die Art schnelle Auffassungsgabe fehlt mir wohl jegliches Talent - ich würde mir jetzt erstmal ein schönes Buch raussuchen und dann so Hundert Seiten dazu und drumherum lesen und *dann* würde ich vielleicht sagen können, dass es mir klar ist…. [img]
http://www.fb18.de/gfx/28.gif[/img]
Vorher muss ich aber erst noch für meine Prüfungen lernen [img]
http://www.fb18.de/gfx/25.gif[/img]
Cheers,
Frank
Also ich hab mir das auch nur plausibel gemacht:
Wenn man sich die Grammatik [img]
http://mokrates.de/cgi-bin/texstring?%5Clambda%5Clongrightarrow%20ab[/img] vorstellt (das entspricht dem Thue-System (ab,[img]
http://mokrates.de/cgi-bin/texstring?%5Clambda[/img]), wenn ich die Beschreibung richtig verstanden habe) und diese Produktion vorwaerts und rueckwaerts und immerwieder anwendet, bekommt man aus Woertern in D_1 wieder Woerter in D_1. Andererseits leuchtet es ein, dass man durch wiederholtes Anwenden auf das Wort [img]
http://mokrates.de/cgi-bin/texstring?%5Clambda[/img] alle Woerter aus D_1 bekommen kann.
Und ganz [img]
http://mokrates.de/cgi-bin/texstring?%5CSigma%5E*[/img] zerfaellt dann in solche Kongruenzklassen, innerhalb derer man die Produktion anwenden kann (ohne aus der Klasse rauszukommen). Die anderen Klassen zeichnen sich naemlich dadurch aus, wieviele a's bzw. b's vorne bzw. hinten noch gebraucht werden, um ein richtiges D_1-Wort zu bekommen. Und daran aendert das Anwenden obiger Produktion nichts.
Und da [img]
http://mokrates.de/cgi-bin/texstring?%5Clambda%5Cin%20D_1[/img] ist, ist [img]
http://mokrates.de/cgi-bin/texstring?%5B%5Clambda%5D%3DD_1[/img].
