+1 Daumen
411 Aufrufe

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.

Avatar von
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

1 Antwort

+1 Daumen

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

Avatar von

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}.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community