Äquivalenzrelation < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Die Notwendige Bedingung zur Äquivalenz Zweier Zustände bei Automaten |
Hallo
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich hatte eine Prüfung in Formale Sprache-Automatentheorie
geschrieben
Da war die Frage nennen Sie die Notwendige Bedingungung 2 äquivalenten Zustände.
Ich weiss das bei gleicher Eingabe, die gleiche Ausgabe erfolgen muss. Ich war der Meinung Alle p Element X^* ->
g1(p,z1)= g2(p,z2). Das war leider das falsche.
Kann mir jemand helfen.
Wenn ich da bitten dürfte: kann ich auch gleich die hinreichende Bedingung bekommen?
Danke
|
|
| |
|
> Die Notwendige Bedingung zur Äquivalenz Zweier Zustände bei
> Automaten
> Hallo
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Ich hatte eine Prüfung in Formale Sprache-Automatentheorie
> geschrieben
>
> Da war die Frage nennen Sie die Notwendige Bedingungung 2
> äquivalenten Zustände.
>
> Ich weiss das bei gleicher Eingabe, die gleiche Ausgabe
> erfolgen muss. Ich war der Meinung Alle p Element X^* ->
> g1(p,z1)= g2(p,z2). Das war leider das falsche.
Ich bin mit Deiner Schreibweise etwas unsicher, vermute aber, dass Du sagen willst: zwei Zustände [mm] $z_{1,2}$ [/mm] können nur dann äquivalent sein, wenn die Maschine in [mm] $z_1$ [/mm] bzw. [mm] $z_2$ [/mm] gestartet dieselben Inputs [mm] $p\in X^{\star}$ [/mm] akzeptiert.
Falls ja: dies ist eigentlich die Definition der Äquivalenz zweier Zustände und daher sowohl hinreichend als auch notwendig.
Eine (offenbar sehr schwache) notwendige Bedingung für Äquivalenz von [mm] $z_1$ [/mm] und [mm] $z_2$ [/mm] wäre zum Beispiel, dass sie beide akzeptierende oder beide verwerfende Zustände sind ("compatibility condition").
> Kann mir jemand helfen.
> Wenn ich da bitten dürfte: kann ich auch gleich die
> hinreichende Bedingung bekommen?
Eine hinreichende Bedingung für Äquivalenz von [mm] $z_1$ [/mm] und [mm] $z_2$ [/mm] wäre, dass alle Inputs [mm] $p\in X^{\star}$ [/mm] ausgehend von [mm] $z_1$ [/mm] bzw. [mm] $z_2$ [/mm] zu äquivalenten Zuständen führen ("propagation condition").
Die Kombination dieser beiden Bedingungen wird bekanntlich zum Beweis der Korrektheit des bekannten Minimierungsalgorithmus für endliche Automaten verwendet.
|
|
|
| |
|
Hallo
Ich habe deine Erklärung nicht ganz verstanden,weil mir das wörtchen (schwach) stört
Ich stelle die Frage nochmal nur anders ausgedrückt.
Man nehme einen Automaten mit n Zuständen.
Von den n Zuständen nimmt man 2 beliebige Zustände und gibt jeweils das gleiche Wort ein und bekommt jeweils die gleiche Ausgabe
notwendige Bedingung ist: gleiche Überführungsfungtion für z1 und z2
hinreichende Bedingung ist gleiche Ergebnisfunktionür z1 und z2
Sind meine Erklärungen für die notwendige Bedingung und hinreiuchende Bedingung richtig
Bitte um Antwort
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 So 09.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
