Frage:
Betrachten Sie die folgenden Sprachen, indem Sie jeweils folgendes ausführen: Geben Sie die Klassen der Myhill-Nerode Äquivalenzrelation an. Bestimmen Sie den Index von \( L_{i} \) und geben Sie für jedes Paar \( A, B \) von Äquivalenzklassen jeweils ein trennendes Wort \( x \in\{a, b\}^{*} \) an. Begründen Sie für jede Äquivalenzklasse, wieso es für die Wörter in ihr kein trennendes Wort gibt.
Zur Erinnerung: Ein Wort \( x \) ist ein trennendes Wort für zwei Äquivalenzklassen \( A \) und \( B \), wenn für \( v \in A \) und \( w \in B \) gilt: \( v x \) gehört zu der Sprache genau dann wenn \( w x \) nicht zu der Sprache gehört.
Ist \( L_{i} \) regulär? Falls ja, geben Sie den Myhill-Nerode DFA \( \mathcal{A}_{L_{i}} \) an.
a) \( L_{1}=\left\{w \in\{a, b\}^{*} \mid w\right. \) hat weder das Infix \( a a \) noch das Infix \( \left.b b .\right\} \)
b) \( L_{2}=\left\{w \in\{a, b, c\}^{*}|| w \mid \geq 2\right. \) und der zweitletzte Buchstabe von \( w \) ist ein \( \left.b .\right\} \)
Code:
