Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Beweis von zuständen
Autor
Kein bestimmter Bereich J Beweis von zuständen
Nash
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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.

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-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]