Frage: Wenn w in T * vorhanden ist, beweist, dass (w * w^R)^R = w * w^RNachweis (w * w^R)^R = w * w^R
Hallo, ich bin neu in Theorien von Algorithmen, und ich habe Probleme zu verstehen, wie das zu beweisen ist, wenn jemand mich auf die richtige Richtung hinweisen kann, die sehr geschätzt würde.
Anmerkung: R bedeutet, dass der String umgekehrt wird, ex: (abc)^R = cba
Auch Anmerkung: * bedeutet Verkettung so (abc * def) = abcdef
In allgemeinen Fall, versuchen Sie es mit Gruppentheorie (Sie haben sogar einen Hinweis : "auch Anmerkung: * bedeutet Verkettung so (abc * def) = abcdef"):
a, b, c, ... - (characters) - group's elements (generators in fact)
a * b == ab - (concatenation) - group's operation
ε - (empty string) - group's 1
a..z**-1 == z..a - rule for the item reversing; a**-1 == a
So weit, so gut, string Umkehren ist **-1 Betrieb, für jeden ab...yz Artikel haben wir:
(ab...yz)((ab..yz)^R) == ab..yz * zy ..ba == ab..yzzy..ba
since zz == z * z == ε (z == z**-1)
we have
ab..yzzy..ba ==
ab..yy..ba ==
ab..ba ==
ε
Ihr Satz ist ganz einfach dann: string Änderung **-1 Wende- und haben
(w * w**-1)**-1=(w**-1)**-1 * w**-1 == w * w**-1
Für diesen besonderen Fall die Gruppe, die wir gebaut haben, kann ein Overkill sein, jedoch kann es sehr nützlich sein, wenn die ähnlichen Probleme gelöst werden.
Quibble: Dies ist eine Halbgruppe und keine Gruppe. –
Ist es eine Hausaufgabe? – Raptor
Es folgt aus 2 Lemmata: 1) '(s^R)^R = s' (für jedes' s' in 'T *'). Und 2) '(u * v)^R = v^R * u^R 'für irgendein' u, v 'in' T * '. Können Sie diese beiden Lemmas beweisen und dann zeigen, wie das Ergebnis folgt? –
@JohnColeman Danke, das hat mir wirklich geholfen, den Beweis zu machen – Nightmare