Beweis, dass eine Sprache nicht regulär ist (Myhill und Nerode)

Question

Zu zeigen ist, dass die folgende Sprache nicht regulär ist, indem man den Satz von Myhill und Nerode anwendet.

L_3 = {an³ | n ≥ 1 } ⊆ {a}*

Ich komme gar nicht weiter, egal wie oft ich mir die Definition auf Wikipedia oder sonst wo anders durchlese.

Definition vom Satz Myhill und Nerode: https://de.wikipedia.org/wiki/Satz_von_Myhill-Nerode#Satz

Comments

{an³ | n ≥ 1 }

Was soll das bedeuten?

---

Oh, hab es nicht richtig geschrieben.

ich meinte:

L_3 = {a^n³ | n ≥ 1 } ⊆ {a}*

Also: a hoch n hoch 3

Answer 1

Es ist 2³ - 1³ = 7.

1. Das Präfix a wird durch das Suffix aaaaaaa zu einem Wort aus L_3 ergänzt.
2. Das Präfix aa wird durch das Suffix aaaaaa zu einem Wort aus L_3 ergänzt.
3. Das Präfix aaa wird durch das Suffix aaaaa zu einem Wort aus L_3 ergänzt.
4. Das Präfix aaaa wird durch das Suffix aaaa zu einem Wort aus L_3 ergänzt.
5. Das Präfix aaaaa wird durch das Suffix aaa zu einem Wort aus L_3 ergänzt.
6. Das Präfix aaaaaa wird durch das Suffix aa zu einem Wort aus L_3 ergänzt.
7. Das Präfix aaaaaaa wird durch das Suffix a zu einem Wort aus L_3 ergänzt.

Keines der genannten Präfixe wird durch zwei der genannten Suffixe zu einem Wort aus L_3 ergänzt.

Also hat die Nerode-Relation einen Index von mindestens 7.

Überlege dir, warum die Nerode-Relation einen Index von mindestens 19 hat.

Überlege dir, warum die Nerode-Relation einen Index von ∞ hat.