0 Daumen
51 Aufrufe

Frage:

Das Alphabet Σ sei {a, b}. Welche der folgenden regulären
Ausdrücke sind äquivalent.
a) (a + b)∗a(b + a)∗b(a + b)∗ + ϵ
b) (a + b)∗ + (ab)∗ + (a + b)∗
c) (a + b)∗aa∗(a + b)∗b(b + a)∗
d) (ab)∗ab(b + a)∗

Code:

Ich weiß leider nicht wie das geht, für Hilfe bin ich dankbar

von

1 Antwort

0 Daumen

Du hast die regulären Ausdrücke \(\alpha, \beta, \gamma, \delta\) gegeben. Jetzt könntest du zu den Sprachen \(L(\alpha); L(\beta); L(\gamma); L(\delta)\) jeweils (vollständige) minimale DEAs \(M_\alpha = L(\alpha);\dots;M_\delta = L(\delta)\) bauen und diese dann auf Äquivalenz überprüfen. Da minimale DEAs zu einer Sprache einzigartig sind, kann man ganz einfach "ablesen", ob zwei min DEA äquivalent sind und demnach auch ihre beiden zugehörigen regulären Ausdrücke.

Es kann also nicht passieren, dass du zwei äquivalente Sprachen hast und die beiden zugehörigen minimalen DEAs unterschiedlich sind. (Ausnahme: unterschiedliche Bezeichnung der Zustände)

Alternativ könntest du auch anhand der Struktur der regulären Ausdrücke die zugehörigen Sprachen bestimmen und dann auf Äquivalenz vergleichen: Z.B ist \(\mathcal{L}\left(\mathtt{(ab)^*ab(b + a)^*}\right)=\{(ab)^i.ab.(ba)^j\mid i,j\geq 0\}\), also die Sprache enthält ab als Teilwort und beliebige Wiederholungen von ab davor und ba danach.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community