Regulären Ausdruck für eine Sprache angeben

Question

Frage:

Geben Sie einen regulären Ausdruck für die folgende Sprache über ∑ = {a,b} an:

L = {w ∈ {a,b}* | w enthält kein bb als Teilwort}

Wie gehe ich hier vor?

r = (ab)*

Das würde bedeuten, dass das Wort w entweder komplett leer wäre, oder aber in dieser Form unendlich lang möglich wäre, oder? : ababababab....

also immer ab nebeneinander im Paar. Wäre das so eine korrekte Lösung?

In der Musterlösung ist folgende Lösung angegeben:

r = (1+b)(a^+b)*a*

Sind meine Deutungen so richtig:

(1+b) => leeres Wort oder b

gefolgt von:

(a^+b)* => entweder keinmal oder n mal mindestens ein a gefolgt von einem b

gefolgt von

keinem oder unendlich vielen a's.

Also wäre ein mögliches Wort w1 = baaaba

Also wurde in dieser Musterlösung dafür gesorgt, dass mindestens ein a zwischen 2 b's sind.

Gibt es aber noch andere Lösungen?

Liebe Grüße

Comments

Bei der Sprache

L = {w∈ ∑* | ∃k ∈ ℕ: #a(w) + #b(w) = 2k}

#a(w) bedeutet Anzahl der a's im Wort w

Wäre dies ein passender, regulärer Ausdruck?

r = (c(a+b)c(a+b)c(a+b)c(a+b)c)*

Dieses Paar (a+b) taucht 4mal auf, es würde auch reichen, wenn es nur 2mal auftaucht, oder? Denn egal, ob pro Klammer entweder ein a ist oder ein b ist, insgesamt sind es immer 4, also immer teilbar durch 2.

Answer 1

L = {w ∈ {a,b}* | w enthält kein bb als Teilwort}

r = (ab)*

Es ist \(aa\in L\)  aber \(aa\) past nicht auf den regulären Ausdruck \(r\).

(1+b) => leeres Wort oder b

Das leere Wort wird üblicherweise mit \(\varepsilon\) bezeichnet, nicht mit \(1\). Aber letztendlich ist für die Bedeutung von Notation ausschließlich die Definition von regulären Ausdrücken in deinen Unterlagen maßgeblich. Schau dort nach.

(a^+b)* => entweder keinmal oder n mal mindestens ein a gefolgt von einem b

Oben hast du das \(+\) als oder aufgefasst und jetzt auf ein mal als gefolgt von. Schau in deinen Unterlagen nach, welche Verwendung korrekt ist.

Comments

In meinen Unterlagen steht:

...Wir benutzen auch das Makro 1:= 0*

J(1) = {ε}

---

Oswald, bei folgender Sprache:

L = {vw | v ∈ {a,b}*, w ∈ {c}*, |vw| ist gerade}

Wenn ich dafür einen regulären Ausdruck angeben soll.

Da dachte ich an

r1 = ( c* ((a+b)*c*) (a+b)* )*

Meine Absicht ist, dass entweder aus dem Tupel (a,b) a oder b geschrieben wird, und dann ein c. Dann ist die Anzahl = 2. Bei (a+b)*c*. Ist denn meine Interpretation von (a+b)*c* so richtig, dass möglicherweise entweder ein a oder ein b gelesen wird, und dann möglicherweie ein c?

Oder heißt es bei (a+b)*, dass man daraus auch abbbbaaba ableiten könne, bevor überhaupt erst das c* gelesen wird?

Und: ich darf ja z.B. keinen regulären Ausdruck z.B. mit (a+b)^+ angeben, oder? Denn die Sprache L hat ja definiert, dass v ∈ {a,b}*, w ∈ {c}*

Laut meinen Unterlagen bedeutet (a+b) = Wort a oder Wort b.

(ab) heißt Wort a gefolgt von Wort b.

(a)* heißt: Wort a wird 0 oder mehrere Male wiederholt.

Wenn jetzt (a+b)*, heißt das dann für mich, die Reihenfolge muss nicht beachtet werden, und daraus kann man dann z.B. abbbbaaba ableiten. Was auch logisch ist, wenn man sich die Maschine dafür aufmalt. Dan hat man einen Startzustand, der gleichzeitig Endzustand ist, mit einem Pfeil auf sich selbst, wo dran steht: a,b

Dann frage ich mich aber, wie ich korrekt einen regulären Ausdruck für die Sprache L angeben kann.

---

L = {vw | v ∈ {a,b}*, w ∈ {c}*, ...}

Jedes Wort aus L

1. beginnt mit einem a oder
2. beginnt mit einem b oder
3. es hat weder ein a, noch ein b.
   

---

...Wir benutzen auch das Makro 1:= 0*

Was ist 0*?

J(1) = {ε}

Ist das eine Identitätsgleichung, eine Definitionsgleichung oder eine Bestimmungsgleichung?

---

Sorry, das soll L(1) heißen, und L steht für eine Sprache!

Unter der Definition: Semantik regulärer Ausdrücke.

---

Oswald,

heißt das dann, dass z.B.

dieser reguläre Ausdruck:

(a+b)*aaa(a+b)*

Kann ich damit z.B. dieses Wort ableiten:

babaabab aaa abbbbaa

ja, oder? Natürlich ohne die Leerzeichen vor und nach aaa, nur damit visualisiert wird, dass die 3 a's die aus der Mitte des regulären Ausdrucks sind.

Mich irritiert das, denn:

der reguläre Ausdruck: (b*a*)*

Ist das nicht das selbe wie (a+b)* ?

Also bzw., worauf ich hinaus will:

mit (a+b)* kann ich doch z.B. aaabbb generieren. Mit (b*a*)* kan ich das nicht, weil falls ein oder mehrere b's vorkommen, sie vor a stehen müssen.

Aber wenn ich mit (a+b)* z.b. bb generiere, dann kann ich mit (b*a*)* auch bb generieren, denn ich sorge einfach dafür, dass nur b* und nicht a* zutrifft.

Ist das so richtig? Oder muss, wenn ich mit (b*a*)* 2 b's generiere, auch zwangsläufig 2 a's darauf folgen? Muss die Anzahl dieses Paars immer identisch sein, oder geht auch z.B. bbbaa?