Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Sprachen
Hi,
weiss jemand, wie bei Sprachen genau der Schnitt, die Vereinigung und Konkatenation ausschaut?
Folgendes Beispiel: L1 = ΣabΣ , L2 = ΣbaΣ
Konkatenation würd ich sagen ist einfach zusammenhängen: L1 * L2 = ΣabΣbaΣ*
Schnitt: L1 ∩ L2 = ?
Sind das alle Wörter, die ba und ab enthalten, also z.B. bab oder aba? Und zählen hier auch Wörter mit abba oder baba usw.? Wie würde die Sprache dann ausschaun?
Vereinigung: L1 ∪ L2 = ?
Danke schon mal, falls es jemand weiss 
Naja, und wenn ich schon dabei bin, noch eine kleine Frage:
Gibt es ein System, eine Regel, ein Irgendwas (ausser genaues Hinschaun 
) wie man auf die regulären Ausdrücke kommt?
Ich kenn das zwar, dass man sich solche Formeln aufstellt, z.B. L1 = aL1 + bL2 + λ usw. und dann die Formeln irgendwie ineinander einsetzt, aber da komm ich immer auf andere, als hier oder im Wiki stehen. Vielleicht mach ichs auch einfach falsch und es geht nur durch scharfes Schaun.
Aber vielleicht kennt ja jemand ein Schema
Schnitt: Da würde ich sagen, daß sind alle Worte bei denen sowohl ein a auf ein b als auch ein b auf ein a folgt; da sollten dann aba, bab, abba und baab dabei sein.
Vereinigung: Das sind dann alle Worte die ab ODER ba enthalten, wobei das oder nicht exclusiv ist.
Bei den regulären Ausdrücken würde ich mich nicht so sehr aufs scharfe hinschauen verlassen.
Mit Arden’s Lemma klappts eigentlich immer. Das muesste dann das sein, was du meinst.
Bei den reg. Ausdrücken gibts halt immer viele versch. Lösungen.
Könnte jemand das “Arden Lemma” mal formulieren bzw einen guten Link angeben, wo man es nachlesen kann?
Du stellst zum geg. Automaten ein Gleichungssystem auf, mit L ist Zustand und a,b sind Eingaben.
z.B.:
- L_0 = bL_0 + aL_1 + ε
- L_1 = aL1 + bL_2 + ε
- L_2 = bL_0 + ε
d.h. in 1) : von Zust. L_0 kommst du mit Eingabe b wieder in L_0 , mit a in L_1 und ε bedeutet dass L_0 akzeptiert.
u.s.w.
dann setzt du die 3) in die 2) ein:
L_1 = aL_1 + bbL_0 + b + ε
Arden’s Lemma besagt nun: L = AL + B
dann ist L = A*B
Hier ist aL_1 dein AL und der Rest ist B
=> 4) L_1 = a*(bbL_0+b+ε)
ausmultiplizieren und weiter mit der nächsten.
Am Ende sollte ein regulärer Ausdruck da stehen.
Ich hoffe das hilft dir weiter.
Gruß,
emeran
Herzlichen Dank 
@emeran: ja, genau: Ardens Lemma hab ich gemeint. Aber nach deiner herrlichen Erklärung hab ichs noch besser verstanden. Super.
Sehr schön, so hab ich mir das vorgestellt (die Erklärung mein ich, vom Lemma hat ich keinen Schimmer). Also Danke Dir emeran.
Aber ein paar Fragen kommen mir doch noch in den Sinn:
Meinst du mit * soviel wie Konkatenation oder schon den Kleene-Abschluss?
Ausmultiplizieren geht so: A*(B+C+D) → AB + AC + A*D ?
Eigentlich doch eher dumm die Fragen. Ich beantwort sie lieber gleich selbst :red: :
Kleene-Abschluss natürlich und Ausmultiplizieren so wie ichs gedacht hab.
Also krieg ich für die Sprache L_0 den regulären Ausdruck: (b+aabb)(aab + aa + ∈)
Den regulären Ausdruck bekomm ich auch raus. Aber, soweit ich weiss, kann man aus aa* immer a+ machen.
So sollte er sein.
@schmetterling:
Was meinst du mit a+ ?
P.S.: trefft ihr euch diese Woche nochmal in der Uni und kann ich da evtl auch mal vorbeischaun?
a* heisst a beliebig oft oder garnix
a+ heisst a mindestens einmal
Das mit aa* → “a+” ist schon klar. Nur hätte das hier zur Verwechslung mit dem “oder-+” geführt.
Des stimmt. Dachte nur, ich erwähns mal
Schönen Abend noch 
ich träum heut nur noch von thi und entdecke hoffentlich im Schlaf die Lösung aller thi-Probleme 
Seid ihr euch mit dem plus sicher? Bei Regulären Ausdrücken (nicht gnu-regexps) bedeutet das + nämlich “oder”, wie zum Beispiel bei der Fibonacci Rekursion aus dem Thi3-Script.
Angeblich soll der Stehl schonmal explodiert sein weil jemand + im regexp-Sinn also aa* verwendet hat.
Also als exponent heisst + aa* sonst ist es natürlich oder ^^