0 Daumen
70 Aufrufe

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

von
{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

1 Antwort

0 Daumen
 
Beste Antwort

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.

von 2,9 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community