theoretische examenvraag DM

[flupke]

Zoals sommige misschien nog niet weten, is de kans groot da sabineke een theoretisch vraagske stelt bij deterministische modellen, een grote kanshebber (ik voel het gewoon) is:

-Als in M q1 bereikbaar is uit q0, dan is ook in M^ de toestanq [q1] bereikbaar uit [q0].

-Als in M q1 niet bereikbaar is uit q0, dan is ook in M^de toestand [q1] niet bereikbaar uit [q0].

Juist/fout + bewijs/tegenvoorbeeld?

Het eerste is volgens mij juist, het bewijs volgt uit het feit dat eta een IO-homomorfisme is.

Het tweede zou ik hetzelfde zeggen, maar ik vind het raar dat sabine 2 keer dezelfde redenering zou vragen om op te schrijven, dus zou moeten lukken dat dit hetzelfde antwoord is.

Iemand die kan helpen, ben ik eeuwige dankbaarheid verschuldigd! (mja, ik overdrijf graag)

Thanks in advance

[Stijn]

Ik denk dat ik da uit het ongerijmde zou bewijzen

bvb 1ste : stel dat q1 niet bereikbaar is vanuit q0 in de gereduceerde, maar wel in M

uwen M en M^ moeten dezelfde functie M(q0) realiseren, dus als nen toestand q1 bestaat die bereikbaar is vanuit q0 in M dan bestaat er ook een w element van X* waarvoor delta*(q0,w) = q1

als ge die w nu aanlegt aan uw gereduceerde moet ge in toestand q1 komen, anders realiseren ze niet alletwee dezelfde fie, dus q1 moet wel bereikbaar zijn => contradictie => q1 is bereikbaar

maar idd, 2de kunde dan compleet analoog doen?

ook al, als ge M reduceert naar M^ dan gaat ge per definitie de niet bereikbare toestanden overboord smijten ? mss dat ze da wil horen?

any more input?

ik ben u minstens 2 weken dankbaar ! ( ik ben realistischer :p )

[quick]

ook al, als ge M reduceert naar M^ dan gaat ge per definitie de niet bereikbare toestanden overboord smijten ? mss dat ze da wil horen?

Reduceren heeft toch niets te maken met nt- bereikbare toest. weg?
Pas als je op zoek gaat naar minimale M dat je eerst nt-ber. gaat weggooien en dan reduceren.

[...]

-Als in M q1 niet bereikbaar is uit q0, dan is ook in M^de toestand [q1] niet bereikbaar uit [q0].

Juist/fout + bewijs/tegenvoorbeeld?

Het tweede zou ik hetzelfde zeggen, maar ik vind het raar dat sabine 2 keer dezelfde redenering zou vragen om op te schrijven, dus zou moeten lukken dat dit hetzelfde antwoord is.

Iemand die kan helpen, ben ik eeuwige dankbaarheid verschuldigd! (mja, ik overdrijf graag)

Thanks in advance

Ni zo moeilijk.
Neem de volgende situatie:


Hier is duidelijk dat q1 niet bereikbaar is uit q0, maar dat q1 en q2 dezelfde gedragsfunctie hebben.
Bij reductie worden deze dan ook samengenomen, dus is [q1] wel bereikbaar uit [q0].

Greetz

[flupke]

thanks!

[...]

Aja en voor da eerste: gemakkelijk bewijs:
  [tex] \exists w:\;\;\delta(q0,w)=q1   \quad\quad\text{\footnotesize (Das dus gegeven)}\\
  \Rightarrow \hat{\delta}([q0],w) = [\delta(q0,w)] = [q1]  [/tex]
Met da laatste gewoon toepassing vd definitie van hat(delta).