Zeigen Sie, dass die in i angegebenen Klassen alle paarweise verschieden sind.

Question

Frage:

Text erkannt:

(a) Rudolf bekommt die Aufgabe, alle Myhill-Nerode Klassen der folgenden Sprache \( L \) über dem Alphabet \( \Sigma=\{a, b\} \) anzugeben:
\( L=\left\{a^{3 n+2} b^{2 m} \mid n, m \in \mathbb{N}\right\} \)
Um ihn zu motivieren verspricht der Weihnachtsmann ihm einen Futtersack pro angegebener Klasse. Rudolf muss beweisen, dass alle seine angegebenen Klassen paarweise verschieden sind, denn es gibt für zwei gleiche Klassen keine zwei Futtersäcke.
Rudolf möchte natürlich sicher sein, die maximale Menge an Futtersäcken zu bekommen und möchte beweisen, dass er tatsächlich alle Klassen gefunden hat. Er hat jedoch in der letzten Woche lieber für seinen großen Flug trainiert als am Unterricht teilzunehmen und hat das Kapitel über den Satz von Myhill-Nerode zum großen Teil verpasst. Können Sie ihm helfen?
i. Geben Sie alle Myhill-Nerode Klassen der Sprache \( L \) an. Verwenden Sie für jede Klasse den längenlexikographisch kleinsten Repräsentanten.
ii. Zeigen Sie, dass die in i angegebenen Klassen alle paarweise verschieden sind.
iii. Zeigen Sie, dass jedes \( w \in\{a, b\}^{*} \) in einer der in i angegebenen Klassen enthalten ist.

Code:

Answer 1

Geben Sie alle Myhill-Nerode Klassen der Sprache \( L \) an.

\([aaa]\), \([aaaa]\), \([aaaab]\) \([aabbbb]\), \([aabbbbb]\)

Verwenden Sie für jede Klasse den längenlexikographisch kleinsten Repräsentanten.

Oops, das habe ich vergessen.

Zeigen Sie, dass die in i angegebenen Klassen alle paarweise verschieden sind.

Zu je zwei Klassen \(K_1\) und \(K_2\) gibt es Wörter \(w_1\in K_1 \)  und \(w_2\in K_2\) und ein Wort \(w\in \Sigma^{*}\), so dass \(v_1w\in L \iff v_2w\notin L\).