|
Autor |
Beweis von zuständen |
|
Nash
Ehemals Aktiv  Dabei seit: 26.05.2003 Mitteilungen: 153
 | Themenstart: 2004-03-07
|
Beweisen sie "~", bei z1~z2 sich um eine Äquivalenzrelation handelt.
mit z meine ich Zustände
Zustände sind äquivalent, wenn sie die selbe ausgabe haben.
also:für alle p p ist elem. von X* => g1(p,z1)=g2(p,z2)
nur gibt es unendlich viele wörter...
Das heißt ich muss refelxivität,symmetrie und transitivität nachweisen
also
R:z1~z1
S:z1~z2->z2~z1
T:z1~z2 und z2~z3->z1~z3
Beweis
R:g1(p,z1)=g1(p,z1)
gilt immer,ist trival :-)
S:g1(p,z1)=g2(p,z2)->g2(p,z2)=g1(p,z1)
das ist auch trival
T:
g1(p,z1)=g2(p,z2) und g2(p,z2)=g3(p,z3)->g1(p,z1)=g3(p,z3)
das ist auch trival
"=" bezeichnet die wortgleichheit,wörter sind gleich wenn sie zeichen für zeichen übereinstimmen und die selbe länge haben.
das war doch hier alles kein richtiger beweis,weil es selbst verständlich ist.... :-?
helft mir weiter
|
Profil
|
lochi
Senior  Dabei seit: 19.08.2002 Mitteilungen: 1484
Wohnort: Allgäu
 | Beitrag No.1, eingetragen 2004-03-07
|
Hallo Nash,
gehe ich recht in der Annahme, dass deine Zustände Zustände eines endlichen Automaten mit Ausgabe sind?
Dann hast du schon recht, das ist (fast) trivial. Im Wesentlichen nutzt du die Äquivalenzeigenschaften von = (auf Worten) aus, um das direkt auf ~ zu übertragen. Wenn du dann noch "trivial" durch etwas Formalismus ersetzt, dann wird das perfekt.
Beispiel:
Zu zeigen: z_1\.\~z_2 => z_2\.\~z_1
Beweis: Wegen z_1\.\~z_2 gilt: \forall p\el X^\*\.: g_1(p,z_1)=g_1(p,z_2).
Wegen Symmterie von = gilt dann auch: \forall p\el X^\*: g_1(p,z_2)=g_1(p,z_1)
Damit ist nach Definition z_2\.\~z_1
Manchmal wollen so Übungen halt stur mit Formalismus gelöst werden. In deinem Beweis hast du bereits immer die Definitionen eingesetzt und dadurch ist das ganze von selbst trivial geworden, weil das ganze an dem Beweis ist, dass man die Definition einsetzt.
Jetzt alles klar?
Lochi
|
Profil
|
Nash hat die Antworten auf ihre/seine Frage gesehen. Nash hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]
|