Seite 1 von 1

[epsilon] als Startwert Myhill-Nerode-Relation

BeitragVerfasst: 29 Nov 2013, 18:03
von jens.heinen
Hallo,

beim Durchlesen von Kapitel 15 ist mir folgende Stelle aufgefallen :

Now define the DFA M: = (Q, 'E, 6, s, F), where
s = [epsilon]
(Seite 105)

Wieso wähle ich hier die Äquivalenzklasse mit epsilon als neuen Startwert ? Ist das nur Definitionssache oder erfüllt das einen bestimmten Zweck ?

Danke im Voraus

LG

Re: [epsilon] als Startwert Myhill-Nerode-Relation

BeitragVerfasst: 01 Dez 2013, 22:48
von Dominik.Kirst
Hallo Jens,

diese Wahl für den Startzustand ist die einzig sinnvolle!
Die Transitionsfunktion 'd ist so konstruiert, dass ein Zustand genau die Klasse der Wörter repräsentiert, die bis zu diesem Zustand gelesen wurden. Da bis zum Startzustand genau 'e und eventuelle Schleifen gelesen werden (die dann zu 'e äquivalent sind) ist die Klasse von 'e der korrekte Startzustand.
Überleg dir fürs bessere Verständnis vielleicht, was passieren würde, wenn wir als Startzustand eine Klasse wählen würden, die 'e nicht enthält!

Liebe Grüße,
Dominik =)

Re: [epsilon] als Startwert Myhill-Nerode-Relation

BeitragVerfasst: 02 Dez 2013, 22:47
von jens.heinen
Achso stimmt, das ist wirklich das einzig sinnvolle ^^

Vielen Dank

Grüße
Jens