Informatiker Board | Druckvorschau: Satz von Myhill Nerode

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Satz von Myhill Nerode (http://www.informatikerboard.de/board/thread.php?threadid=1859)

Geschrieben von Brayn am 30.05.2014 um 00:00:

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. unglücklich

Mir geht es nicht darum, dass irgendjemand meine Aufgaben bzw. Übungen löst daher bin ich auch für neue Aufgaben offen. smile

Nun zu meinem Problem:
Nehmen wir mal das Einsteigerbeispiel aus unserm Vorlesungsbegleitenden Buch:
$[latex] L = \left\{ a^n b^n\ |\ n\ \geq\ 1 \right\} [/latex]$

Außerdem heißt es:
$[latex] xR_My\ \Leftrightarrow \forall\ Woerter\ z\ \in \Sigma ^*\ gilt: [/latex]$

$[latex] xz\ \in\ L\ \Leftrightarrow\ yz\ \in\ L [/latex]$

$[latex] \left[ab\right] = L \left[a^2b\right] = \left\{ a^2b, a^3b^2, a^4b^3... \right\} \left[a^3b\right] = \left\{ a^3b, a^4b^2, a^45^3... \right\} ... \left[a^kb\right] = \left\{ a^{k+i-1}b^i |\ i\ \geq 1 \right\} [/latex]$

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