Reguläre Sprache und reguläre Ausdrücke

Question

Gegeben sind zwei Sprachen \(L_1,L_2\) über dem Alphabet \(\Sigma=\{a,b\}\). Die Sprache \(L_1\) sei die Sprache deren erstes und letztes Zeichen übereinstimmen, die Sprache \(L_2\) die Sprache der Wörter, auf denen auf jedes b ein a folgt. Nun soll ich reguläre Ausdrücke zu folgenden Sprachen angeben:

$$(1) L_1\cup L_2\\(2)L_1\cdot L_2\\(3)L_1\cap L_2\\(4)L_2\backslash L_1\\(5)L_1^c\\(6)L_2^c$$

Meine Frage dazu lautet, wie genau ich da vorgehen muss? Ich denke, dass es hilfreich wäre, wie die Sprachen \(L_1\) und \(L_2\) als reguläre Ausdrücke aussehen. Oder stehe ich da gerade ganz auf dem Schlauch und muss ganz anders vorgehen?

Sollte meine Idee prinzipiell richtig sein, so sehen meine regulären Ausdrücke wie folgt aus:

$$L_1:=((a\cdot (a\cup b)^*\cdot a)\cup (b\cdot (a\cup b)^* \cdot b))\\L_2:=(b^*\cdot (a\cdot b)^*)^*$$

Answer 1

Ich denke, dass es hilfreich wäre, wie die Sprachen L1 und L2 als reguläre Ausdrücke aussehen.

Ja.

und muss ganz anders vorgehen?

Du "musst" gar nichts ;) Du könntest Dir auch zwei DFAs/NFAs konstruieren (da es sich um reguläre Sprachen handelt, ist das ohne Probleme möglich) und die Automaten entsprechend zusammenbauen. Daraus ließe sich dann wiederum ein regulärer Ausdruck bauen usw.. Grundsätzlich empfehle ich Dir, dass Du bei Deinem ersten Gedanken bleibst!

so sehen meine regulären Ausdrücke wie folgt aus

Wie habt ihr reguläre Ausdrücke definiert? Meiner Nomenklatur folgend wären

\((a(a|b)^*a)|(b(a|b)^*b)\) und

\((a^*|(ba)^*)^*\Longleftrightarrow (a|(ba))^*\)

reguläre Ausdrücke, was im Grunde nur eine andere Schreibweise Deiner Variante ist. Wo genau ist jetzt Dein Problem? Für den zweiten Ausdruck musst Du z. B. nur Deine beiden regulären Ausdrücke hintereinanderhängen. Entsprechend sind die übrigen Operatoren anwendbar (z. B. "|" bei "\(\cup\)").

Comments

L₂ = (a|(ba))*