Reguläre Sprache in regulären Ausdruck verwandeln

[Ninjafighter]

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.

Für L2 auch ein NFA gezeichnet. Ich habe keine Ahnung, ob es richtig ist und hoffentlich auch relativ gut erkennbar.

 

[httpdigest]

Das geht ganz einfach mit Quantifizierer, siehe: https://docs.oracle.com/javase/tutorial/essential/regex/quant.html
Du benötigst den "X, exactly n times" und den "X, zero or more times" Quantifier. Damit würde dein regulärer Ausdruck dann sagen (ich will ihn dir nicht gleich sofort hinschreiben, sondern nur "beschreiben"): "Zuerst kommt immer a oder b und dann beliebig häufig jeweils immer 3 mal a oder b".

 

[Ninjafighter]

Danke für die Antwort. Doch ich verstehe es immer noch nicht :/
Also (a|b) (aaa|bbb)* ?

Könntest du mir den Satz "X, exactly n times" und den "X, zero or more times" Quantifier nochmal erklären? Was heißt X, exactly n times und X, zero oder more times? Ich verstehe schon, was es auf deutsch heißt aber kann es mir nicht erklären.

Edit: Wir dachten zu erst an: (a|b) ( aa| ab| ba| bb) (a|b)

 

[temi]

Könntest du mir den Satz "X, exactly n times" und den "X, zero or more times" Quantifier nochmal erklären?

Ich nehme an, es handelt sich um die Quantifizierer aus der ersten Tabelle des o.g. Links https://docs.oracle.com/javase/tutorial/essential/regex/quant.html

2. Zeile und 4. Zeile => "Meaning"

 

[httpdigest]

Ein Beispiel für die Verwendung von "X, exactly n times" mit `n`=2, wobei `X` hier einfach ein beliebiger regulärer Teilausdruck ist, wäre z.B.: X{2}.
Das ist einfach nur eine kürzere Schreibweise für XX.
Ein Beispiel für die Verwendung von "X, zero or more times" wäre: X*.
Jetzt solltest du aber wirklich zumindest L2 schon spielend hinbekommen.
Ich weiß nicht, was man da noch mehr erklären kann, steht ja auch eigentlich alles in der Tabelle in dem Link.

 

[httpdigest]

Also (a|b) (aaa|bbb)*

Nein. Im Prinzip würde dieser Ausdruck schon Wörter der richtigen Länge generieren, aber es sollen ja nicht immer Sequenzen von genau drei aufeinander folgenden a's oder b's sein.

Edit: Wir dachten zu erst an: (a|b) ( aa| ab| ba| bb) (a|b)

Das kann doch gar nicht funktionieren... Dieser reguläre Ausdruck ist doch gar nicht in der Lage, Wörter beliebiger Länge zu generieren, da keine Wiederholungen drin sind. Er kann doch nur Wörter der exakten Länge 4 generieren. Oder hast du irgendwo ein * vergessen?

Okay, lass uns vielleicht nochmal L2 in Prosa aber etwas strukturierter beschreiben:
Zuerst kommt ein a oder ein b, gefolt von: {beliebig vielen Wiederholungen von: {genau drei Wiederholungen von: {a oder b}}}.
Damit habe ich aber eigentlich schon zu viel Vorarbeit geleistet.

 

[Ninjafighter]

Danke für die Hilfe httpdigest.