Nerode Relation

Aufrufe: 69     Aktiv: 04.12.2021 um 01:28

0
Ich weiss, das hat nicht direkt mit Mathematik zu tun aber ich denke, dass ich hier dennoch eine Antwort erhalten werde.
Kann mir jemand erklearen worauf sich die Bedingungen n>=2 und xn-1 beziehen?
Muss die Anzahl der Woerter in der Sprache min. 2 sein und das Vorletzte Wort aus 0 bestehen oder muss die Wortlaenge min. 2 betragen und das vorletzte Zeichen eine 0 sein? Vielen lieben Dank schonmal!

Diese Frage melden
gefragt

Student, Punkte: 16

 
Kommentar schreiben
2 Antworten
1
Über die Anzahl der Worte in $L$, also $|L|$, ist nichts gesagt. Das andere hängt davon ab, ob $x_i$ Zeichen oder Worte sein sollen. Das geht aus dem, was Du gepostet hast, nicht hervor.
Wenn $x_i$ ein Wort ist, dann wäre Deine erste Variante halbwegs zutreffend. "Halbwegs" weil es nicht um die Anzahl der Worte in $L$ geht, sondern in jedem einzelnen Wort. Ein Wort würde dann mind. aus zwei Teilworten bestehen. Das erscheint aber nicht sinnvoll,  da "Anzahl Teilworte" in einem String nicht wohldefiniert ist.
Daher vermute ich, dass $x_i$ Zeichen sind, also $x_i\in \{0,1\}$, und dann trifft Deine zweite Variante zu.

Ist, wie gesagt, eine Vermutung. Das ganze ist ein schönes Beispiel was passiert, wenn nicht alle auftretenden Größen präzise definiert sind.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 20.67K

 

Ich denke auch eher, dass es das 2. ist, leider ist die Konsistenz der genutzten Buchstaben und deren Kontext im Skript eher loechrig. Danke fuer die schnelle Antwort!   ─   gr33nte4 03.12.2021 um 13:43

Gerne. Ja, wenn sich diese lückenhaften Definitionen durch das ganze Skript ziehen, wird es mühselig.   ─   mikn 03.12.2021 um 13:44

Kommentar schreiben

0
Hier muss nichts weiter präzise definiert werden, denn das Sternchen an der Menge $\{0,1\}^*$ ist der Kleenesche *-Operator, der mit Sicherheit irgendwo im Skript definiert wurde. Man nennt das auch KIeenesche Hülle. Diese enthält alle Wörter (beliebiger Länge!) über das zugrundeliegende Alphabet, in diesem Fall $\{0,1\}$. Das wiederum bedeutet, dass $x_1\dots x_n\in\{0,1\}^*$ ein Wort der Länge $n$ bestehend aus den Zeichen $0$ und $1$ ist. Folglich bezeichnet $x_i$ jeweils ein Zeichen. Damit ergibt sich für die Bedingungen sofort, dass in der Sprache jedes Wort über $\{0,1\}$ enthalten ist, das sowohl mindestens aus 2 Zeichen besteht ($n\geq 2$) als auch an der vorletzten Stelle eine 0 hat ($x_{n-1}=0$). 

Ich gehe einfach mal davon aus, dass die Definitionen nicht richtig verstanden wurden und deswegen diese Verwirrung auftritt. Daher unbedingt nochmal nachschlagen, was es mit der Kleeneschen Hülle auf sich hat. Denn wenn man das verstanden hat, ergibt sich (siehe oben) sofort, wie die Sprache $L$ zu interpretieren ist.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 17.97K

 

Die Kleenesche Hülle ist mir bekannt dem Frager wohl auch). Z.B. ist 1011001 in $\{0,1\}`$. An der Stelle "das wiederum bedeutet" gehe ich nicht weiter mit. Das bedeutet es eben nur, wenn die Bedeutung von x_i definiert ist. Ist sie aber in diesem Moment nicht.
Woher weiß man nun, ob $x_1=1, x_2=01, x_3=10, x_4=0, x_5=1$ oder $x_1=101, x_2=10, x_3=0, x_4=1$ ist? Ich sehe nicht woraus das hervorgeht.
  ─   mikn 04.12.2021 um 00:22

Kommentar schreiben