Verständnisfrage Wörter und Sprachen

Question

Frage:

Vereinfacht soll dieser Ausdruck :

 {a}{ε, aa}*{ab, b} ∪ {b}

Lösung ist folgende:

1.Schritt: {a}{aa}{ab,b}∪{b}

2.Schritt:{a}⁺{b} ∪ {b}

3.Schritt [a}* ∪ {b}

Ich verstehe nicht im 1.Schritt wie von {ε,aa}* auf {aa} vereinfacht wurde.

KleeneStern ist ja so definiert das es die Menge aller Wörter über ein Alphabet Sigma mit dem leeren Wort ist wie kommt man dadurch auf {aa}? Wenn ich * auflöse dann hab ich doch ε, aa,aaaa,aaaa usw.

im zweiten Schritt ist dann {a}{aa}{ab,b} auf {a}⁺{b} vereinfacht wurden. Wie kommt man auf das  ⁺

Hier lautet die Definition alle Wörter über ein Alphabet Sigma ohne das leere Wort.

Comments

Ist denn der Schritt von 2. zu 3. korrekt?

---

Ja

ich habe noch von der anderen Übungsgruppe dies bekommen.

{a} {aa}* {ab,b} ∪ {b}

= {a} {aa}* {ε,a} {b} ∪ {b}

={a}⁺ {b} ∪ {b}

= {a}*{b}

Im zweiten Schritt wurde {ab,b} ja als {ε,a} {b} aufgefasst weil epsilon konkatiniert mit b = {b} ergibt und a konkateniert mit b {ab} das verstehe ich noch aber dann im nächsten Schritt wie lässt sich die Zeile mit den plus erklären und dann am Ende von + auf * zurück.

Ist die Begründung vielleicht das die Konkatenation {a} {aa}* {ε,a} einfach weil durch das leere Wort es immer noch a... bleibt. Wenn ja dann würde nur der letze Schritt fehlen

Answer 1

Man kann allenfalls {ε, aa}* = {aa}* vereinfachen. Ich nehme an, der Stern ist verloren gegangen.

Comments

Vielleicht so:

{a}{ε, aa}*{ab, b} ∪ {b} =

{a}{aa}*{ab, b} ∪ {b} =

{a}{aa}*{ab} ∪ {a}{aa}*{b} ∪ {b} =

{aa}⁺{b} ∪ {a}{aa}*{b} ∪ {b} =

{a}⁺{b} ∪ {b} =

{a}*{b}.

---

Ich verstehe den Teil

{a}{aa}*{ab} ∪ {a}{aa}*{b} ∪ {b} =

{aa}⁺{b} ∪ {a}{aa}*{b} ∪ {b} =

{a}⁺{b} ∪ {b} =

bei dir nicht so genau kannst du mir da genauer sagen was wie man darauf kommt da das Endergebnis mit dem übereinstimmt.

---

Ich verstehe den Teil

{a}{aa}*{ab} ∪ {a}{aa}*{b} ∪ {b} =

{aa}⁺{b} ∪ {a}{aa}*{b} ∪ {b} =

{a}⁺{b} ∪ {b} =

bei dir nicht so genau...

Es ist zum Beispiel

{a}{aa}*{ab} = {aa}*{aa}{b} = {aa}⁺{b}.

Weiter ist

{aa}⁺{b} ∪ {a}{aa}*{b} = {ε, a}{aa}⁺{b} = {a}⁺{b}.