0 Daumen
1,2k Aufrufe

Aufgabe:

Zu zeigen mit dem Satz von Milhill und Nerode dass die folgende Sprache nicht regulär ist und entsprechend begründen:

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

Avatar von

Ich habe den Satz gefunden: https://de.wikipedia.org/wiki/Satz_von_Myhill-Nerode#Satz und die Fragestellung korrigiert

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Mit Satz von Myhill und Nerode die Irregularität von Sprache \(L_3 = \{a^{n³} | n ≥ 1 \} \subseteq \{a\}^*\) zeigen

Um mit dem Satz von Myhill und Nerode zu zeigen, dass eine Sprache \(L\) nicht regulär ist, muss man beweisen, dass es eine unendliche Anzahl von Äquivalenzklassen bezüglich der rechtsinvarianten Äquivalenzrelation gibt. Eine rechtsinvariante Äquivalenzrelation \(\sim_L\) auf \(\Sigma^*\) ist definiert durch: Für alle \(x, y \in \Sigma^*\),

\(x \sim_L y \Leftrightarrow \forall z \in \Sigma^*\,(xz \in L \Leftrightarrow yz \in L).\)

Das bedeutet, zwei Strings sind äquivalent, wenn das Hinzufügen eines beliebigen Suffixes \(z\) zu beiden den gleichen Effekt hat — entweder liegen beide resultierenden Strings in \(L\) oder beide nicht.

Ein Kernpunkt des Satzes von Myhill und Nerode ist, dass eine Sprache \(L\) genau dann regulär ist, wenn die Anzahl der Äquivalenzklassen der Äquivalenzrelation \(\sim_L\) endlich ist.

Um zu beweisen, dass die Sprache \(L_3 = \{a^{n³} | n ≥ 1 \} \subseteq \{a\}^*\) nicht regulär ist, zeigen wir, dass es unendlich viele Äquivalenzklassen bezüglich \(L_3\) gibt. Dazu konstruieren wir für jedes \(n \in \mathbb{N}\) einen String \(x_n = a^{n³}\), und zeigen, dass für alle \(n \neq m\) die Strings \(x_n\) und \(x_m\) in verschiedenen Äquivalenzklassen sind.

Annahme: Wir haben zwei verschiedene natürliche Zahlen \(n\) und \(m\) mit \(n > m\). Wir betrachten die Strings \(x_n = a^{n³}\) und \(x_m = a^{m³}\). Nun wählen wir ein geeignetes Suffix \(z\), um zu zeigen, dass diese Strings nicht äquivalent sind. Ein geeignetes \(z\) ist \(a^{(3n^2 + 3n + 1) - n^3} = a^{2n^2 + 3n + 1}\), da dies genau die Differenz zu \(n^3\) ist, um \(x_nz = a^{n³}a^{2n^2 + 3n + 1} = a^{n^2(2n + 2) + 3n + 1}\) zur nächsten Kubikzahl \(a^{(n+1)³}\) zu ergänzen.

Nun prüfen wir, ob das Hinzufügen von \(z\) zu \(x_n\) und \(x_m\) uns gleichermaßen in \(L_3\) landen lässt:

- \(x_nz = a^{n³}a^{2n^2 + 3n + 1} = a^{(n+1)³}\) liegt sicher in \(L_3\), da \((n+1)³\) eine Kubikzahl ist.
- Um zu sehen, ob \(x_mz = a^{m³}a^{2n^2 + 3n + 1}\) in \(L_3\) ist, bemerken wir, dass, da \(n \neq m\), \(m³ + 2n^2 + 3n + 1\) keine Kubikzahl ist (es sei denn unter sehr speziellen Umständen, die nicht generell für alle \(n\) und \(m\) gelten).

Folglich ist \(x_mz\) nicht in \(L_3\) für eine allgemeine Wahl von \(n\) und \(m\) mit \(n > m\), da die resultierende Potenz keine Kubikzahl sein wird, was erforderlich wäre, um in \(L_3\) zu sein.

Da wir für jedes Paar von natürlichen Zahlen \(n\) und \(m\) mit \(n \neq m\) ein Suffix \(z\) finden können, sodass \(xz\) und \(yz\) unterschiedlich bezüglich ihrer Zugehörigkeit zu \(L_3\) sind, folgt, dass \(x_n\) und \(x_m\) in verschiedenen Äquivalenzklassen sind. Da es unendlich viele natürliche Zahlen gibt, folgt, dass es auch unendlich viele Äquivalenzklassen gibt. Nach dem Satz von Myhill und Nerode bedeutet dies, dass \(L_3\) nicht regulär ist.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community