| Brayn |
Satz von Myhill Nerode
Hallo Ihr lieben,
Wir haben gerade den Satz von Myhill Nerode besprochen und ich verstehe irgenwie das vorgehen nicht. Ich habe Hier, in anderen Foren und bei YouTube schon nach Erklärungen gesucht aber mein Problem löst sich nicht. 
Mir geht es nicht darum, dass irgendjemand meine Aufgaben bzw. Übungen löst daher bin ich auch für neue Aufgaben offen. 
Nun zu meinem Problem:
Nehmen wir mal das Einsteigerbeispiel aus unserm Vorlesungsbegleitenden Buch:
![[latex]<br />
L = \left\{ a^n b^n\ |\ n\ \geq\ 1 \right\}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
L = \left\{ a^n b^n\ |\ n\ \geq\ 1 \right\}<br />
)
Außerdem heißt es:
![[latex]<br />
xR_My\ \Leftrightarrow \forall\ Woerter\ z\ \in \Sigma ^*\ gilt:<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
xR_My\ \Leftrightarrow \forall\ Woerter\ z\ \in \Sigma ^*\ gilt:<br />
)
![[latex]<br />
xz\ \in\ L\ \Leftrightarrow\ yz\ \in\ L<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
xz\ \in\ L\ \Leftrightarrow\ yz\ \in\ L<br />
)
![[latex]<br />
\left[ab\right] = L<br />
\left[a^2b\right] = \left\{ a^2b, a^3b^2, a^4b^3... \right\}<br />
\left[a^3b\right] = \left\{ a^3b, a^4b^2, a^45^3... \right\}<br />
...<br />
\left[a^kb\right] = \left\{ a^{k+i-1}b^i |\ i\ \geq 1 \right\}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\left[ab\right] = L<br />
\left[a^2b\right] = \left\{ a^2b, a^3b^2, a^4b^3... \right\}<br />
\left[a^3b\right] = \left\{ a^3b, a^4b^2, a^45^3... \right\}<br />
...<br />
\left[a^kb\right] = \left\{ a^{k+i-1}b^i |\ i\ \geq 1 \right\}<br />
)
Jetzt frage ich mich aber wie die darauf kommen. Denn nimmt man sich zwei Wörter w1 und w2 aus der Sprache z.B. w1 = aabb und Wort w2 = aaabbb und hängt ein x aus Sigma* z.B. a dran ergibt das doch:
aabba und aaabbba und beide sind nicht in der Sprache. Was mache ich da falsch?
Vielen Dank schonmal,
liebe Grüße Matthias |
