Reguläre Sprache in regulären Ausdruck verwandeln: Bsp. L2 = w ∈ { a, b }* | |w|a + |w|b ≡ 1 mod 3 }

Question

Hallo Community,

ich bin auf ein Problem gestoßen, an dem ich nicht mehr weiter komme.

L2 = w ∈ { a, b }* | |w|a + |w|b ≡ 1 mod 3 }
L3 = w ∈ { a, b, c }* | |w|a + |w|b ≡ 1 mod 3 }

Durch die Bedingung weiß ich, dass die Gesamtzahl der Elemente in dem Wort einen Rest von 1 haben sollen, also 1, 4, 7, 10, 13, 16 etc.

Nur weiß ich nicht, wie ich beide in einen regulären Ausdruck bringen soll.

Zuerst dachte ich an ((a|b)| ...... ) aber mir es fühlt sich nach dem falschen Weg an.

Würde mich auf Hilfe freuen.

Answer 1

L2 = w ∈ { a, b }* | |w|a + |w|b ≡ 1 mod 3 }
L3 = w ∈ { a, b, c }* | |w|a + |w|b ≡ 1 mod 3 }

Es gibt hier mehr schliessende als öffnende geschweifte Klammern.

Was ist mit den Pipes | gemeint?

Was ist w ?

|w|a + |w|b ≡ 1 mod 3

Wie kann das links von ≡ eine ganze Zahl geben?

Answer 2

Da ist wohl jeweils eine Klammer vergessen worden. Außerdem ist es etwas unglücklich formuliert. Du hast recht mit der Angabe der möglichen Zahlen.

Die Betragsstriche heißen hier Anzahl der Buchstaben a oder b des Wortes w.

Diese sollen addiert bei mod 3 identisch zu 1 sein. Also die Anzahl der as und bs zusammen bei mod 3 = 1 sein.

Regex L2:

(a|b)((a|b){3})*

Regex L3:

c*(a|b)c*((a|bc*){3})*

Grüße

Felix