0 Daumen
691 Aufrufe

Hallo Community,

Die Frage ist nach " Geben Sie einen endlichen Automaten an, der L entscheidet. "
Lediglich ist mein Problem, dass ich nicht auf die endgültige Lösung komme.

L = {w ∈{a,b}∗ ||w|a + 2·|w|b ≡ 1 (mod 7)}

Mein Versuch war: Ich kam zuM Ergebnis, dass es doch nicht ganz richtig ist.




Bitte und dankeschön

Edit: Muss ich mit dem DFA wirklich die komplette Bedingung der Sprache auch in der DFA wieder geben?

Avatar von
L = {w ∈{a,b}∗ ||w|a + 2·|w|b ≡ 1 (mod 7)}

Die Sprache ist uneindeutig dargestellt. Gib mal bitte ein paar Beispiele für Wörter oder (besser noch) eine klare Definition der Sprache.

Ich kam zuM Ergebnis, dass es doch nicht ganz richtig ist.

Dass was nicht ganz richtig ist? Hast Du mal einen Automatenentwurf (bitte posten)?

L = {w ∈{a,b}* ||w|a + 2·|w|b ≡ 1 (mod 7)} ist eine reguläre Sprache - Ich weiß  nicht, weshalb es durch das Kopieren ein "Multiplikator" wurde aber es soll ein Sternchen sein. Verzeihe mir aber es gibt leider keine andere Eingabe dieser Sprache, die ist so als Übungsaufgabe ( keine Abgabeaufgabe ) gestellt. Lediglich die Aufgabe "Geben Sie einen endlichen Automaten an, der L entscheidet" wird noch angegeben.

Allerdings meinte mein Kollege, dass es falsch, weil b einen Zustand überspringen soll.

blob.png
Edit: Danke für die Antwort!

1 Antwort

+1 Daumen

Zustände sind 0 bis 6.

Anfangszustand ist 0, akzeptierender Zustand ist 1.

Ziel ist es, dass wenn nach Lesen des Wortes w der Automat im Zustand n  ist, die Beziehung

        |w|a + 2|w|b ≡ n (mod 7),

gelten soll. In diesem Fall ist

        |w|a + 2|w|b = 7m + n für ein m ∈ ℕ

Diese Beziehung zwischen gelesenem Wort und Zustand gilt am Anfang (w = ε, n = 0, Anfangszustand ist 0). Sie kann auch aufrecht erhalten werden:

Ist der Automat nach Lesen des Wortes w im Zustand n und liest das Zeichen a, dann wurde insgesamt das Wort wa gelesen. Es ist

        |wa|a = 1 + |w|a und

        |wa|b = |w|b

Also ist

        |wa|a + 2|wa|b = 1 + |w|a + 2|w|b = 1 + 7m + n für ein m ∈ ℕ

und somit

        |wa|a + 2|wa|b ≡ n+1 (mod 7).

Folgezustand sollte also (n+1) mod 7 sein. Wird stattdessen ein b gelesen, dann ist aus gleichem Grund

        |wb|a + 2|wb|b = |w|a + 2|w|b + 2 = 2 + 7m + n ≡ n+2 (mod 7).

In diesem Fall sollte (n+2) mod 7 der Folgezustand sein.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community