1. Welt
  2. Quests
  3. #1455
Alexander Fufaev

Sprache (gleicher Rest bei Division) ist regulär

aus dem Bereich: Quests
Mehr dazu

Deine Aufgabe ist...

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 \} \]

Allgemeine 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 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.

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 7
Gäste online: 7
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.