Nerode Relation

Aufrufe: 746     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: 39.12K

 

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

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.
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: 30.55K

 

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Cauchy wurde bereits informiert.