Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #343

Aufgabe mit Lösung Sprache (gleicher Rest bei Division) ist regulär

Beweise, dass die folgende Sprache \(L\) regulär (eine Typ-3-Sprache) ist:\[ L = \{ w \in \{a,b\}^* ~:~ |w|_a ~\text{mod}~ 2 = k ~\text{UND}~ |w|_b ~\text{mod}~ 2 = k \} \]

Lösungstipps

Um zu beweisen, dass eine Sprache regulär ist, muss ein deterministischer endlicher Automat gefunden werden. Denn für jede reguläre Sprache lässt sich ein DEA konstuieren.

Zur Erinnerung: Ein DEA \(A\) ist ein 5-Tupel \(A = (Z, \Sigma, \delta, z_0, E) \). Gib diesen 5-Tupel an. Für die Überführungsfunktion \( \delta \) kann auch ein Graph angefertigt werden.

Lösung

Lösung anzeigen

Die Sprache \(L\) ist eine unendliche Sprache, deren Wörter \(w\) aus den Buchstaben \(a\) und \(b\) bestehen. Die bestimmende Eigenschaft dieser Sprache ist, dass die Anzahl \(|w|_a\) der Buchstaben \(a\) den gleichen Rest \(k\) ergibt, wie die Anzahl \(|w|_b\) der Buchstaben \(b\), wenn diese durch zwei geteilt werden. Die Sprache besteht beispielsweise aus folgenden Wörtern:1\[ L = \{\varepsilon, aa, bb, aabb, aaaabb, ~... \} \]

Es sind mindestens zwei Zustände notwendig, nämlich einen Zustand \(z_0\) für den gleichen Rest und einen Zustand \(z_1\) für den ungleichen Rest. Die Zustandsmenge ist:2\[ Z = \{ z_0, z_1 \} \]mit \(z_0\) als Anfangszustand. Die Überführungsfunktion \(\delta: Z \times \Sigma \rightarrow Z\) sieht folgendermaßen aus:3\[ \delta(z_0, \varepsilon) = z_0 \] \[ \delta(z_0, a) = \delta(z_0, b) = z_1 \] \[ \delta(z_1, a) = \delta(z_1, b) = z_0 \]

Die Menge \(E\) der Endzustände ist:4\[ E = \{ z_0 \} \]

Der angegebene Automat \(A = (Z, \Sigma, \delta, z_0, E) \) akzeptiert die betrachtete Sprache \(L\). Also muss die Sprache regulär sein.

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?