reguläre Ausdrücke für eine Sprache

Question

Frage:

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

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

Eine angegebene Lösung ist: r1 = (c*(a+b)c*(a+b)c*)* + c*

Ich habe zwei Fragen:
ist diese Möglichkeit von mir auch korrekt:

c(a+b)*ab(a+b)*cc

Und: Muss c mindestens einmal vorkommen, oder kann man bei r1 c auch komplett weglassen?

(a+b) heißt doch a oder b, oder? Das heißt, ich müsste mindestens zweimal (a+b) im regulären Ausdruck haben, damit die Anzahl am ende durch 2 teilbar ist.

Answer 1

c(a+b)*ab(a+b)*cc

Das ist nicht korrekt. Es ist ε ∈ L, aber jedes Wort aus der durch deinen regulären Ausdruck beschriebenen Sprache endet mit cc.

Muss c mindestens einmal vorkommen

Es genügt, wenn das Wort w die Bedingung

        ∃k ∈ ℕ: #a(w) + #b(w) = 2k

erfüllt.

(a+b) heißt doch a oder b, oder?

Für die Bedeutung von Ausdrücken ist die Definition in deinen Unterlagen einzig maßgebliche Quelle.

Das heißt, ich müsste mindestens zweimal (a+b) im regulären Ausdruck haben, damit die Anzahl am ende durch 2 teilbar ist.

Nein. Die Sprache L wird auch durch den regulären Ausdruck

        (((c*a)+(c*b))((c*a)+(c*b)))*c

beschrieben. In diesem kommt kein einziges mal (a+b) vor.

Comments

Dankeschön.

Darf ich diesen Ausdruck: c(a+b)*ab(a+b)*cc

in diesen umändern: (c(a+b)*ab(a+b)*cc)* und dann wäre er korrekt?

Gilt immer, dass ε ∈ L, oder nur in diesem Falle? Wenn letzteres, woran erkenne ich das?

---

(c(a+b)*ab(a+b)*cc)* und dann wäre er korrekt?

Nein. Es ist aa ∈ L aber alle nicht-leeren Wörter, die auf den Ausdruck (c(a+b)*ab(a+b)*cc)* passen, beginnen mit einem c.

Gilt immer, dass ε ∈ L, oder nur in diesem Falle?

Ja, es gilt immer, dass ε ∈ { w ∈ ∑* | ∃k ∈ ℕ: #a(w) + #b(w) = 2k} ist.

Dass erkennst du daran, dass

        ε ∈ ∑*

ist, und dass

        ∃k ∈ ℕ: #a(ε) + #b(ε) = 2k

gilt.

---

Wie komme ich darauf, dass aa ∈ L ist?

r2 = (c(a+b)*ab(a+b)*cc)*

Folgerst du das aus r2?

---

Wie komme ich darauf, dass aa ∈ L ist?

Die Sprache L ist definiert als die Sprache

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

Es ist aa ∈ ∑* und #a(aa) + #b(aa) = 2·1. Also ist aa ∈ L.

Folgerst du das aus r2?

Natürlich nicht. r2 beschreibt ja überhaupt nicht die Sprache L.

---

Achso. Dann wäre auch aaaa ∈ L und aaaaaa ∈ L usw., also alle geraden Anzahl von a.

---

Ja, diese Wörter sind ebenfalls in L enthalten.