Fragen zu Vereinfachung von Sprachen und Sprachen vereinigen bzw. schneiden etc.

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.

Fragen zu Vereinfachung von Sprachen und Sprachen vereinigen bzw. schneiden etc.
Hi,

Ich sitze seit Stunden an ein paar Problemen allerdings finde ich nirgends im Netz ne gute Erklärung dazu.Hoffe mir kann hier jemand weiterhelfen.

Zum einen sind zwei Sprachen L1= (( ab vereinigt b)* a) , L2= ((ba vereinigt a)*) gegeben.

Diese soll ich nun miteinander schneiden und den neuen regulären Ausdruck dafür angeben…leider hab ich keine Ahnung wie so etwas geht :frowning: Regeln dafür hab ich auch keine gefunden.

Zum anderen habe ich diesen Ausdruck: c* vereinigt c* a (c* a c* a)* c* a c* gegeben …nun soll ich diesen vereinfachen…
das Ergebnis ist c* vereinigt a( c )* a nur leider weiß ich nicht wie man darauf kommt :frowning:

Hoffe mir kann jemand noch vor Dienstag antworten , dann hab ich darüber Prüfung hoff


Ich versuche mal den ersten Teil:
Sigma={a , b}
L1 ist die Sprache der Worte, die als letzten Buchstaben ein a haben und in denen keine zwei aufeinanderfolgenden Zeichen ‘a’ auftreten.
=> L1={w | existiert w’ aus Sigma*: (w=w’a UND für alle x,y,z aus Sigma*: (w’=xyz → y!=aa) )}

L2 ist die Sprache der Worte, die keine zwei aufeinanderfolgenden Zeichen ‘b’ beinhalten und (falls nicht leer) auf ‘a’ enden.
=> L2={w |w=leer ODER ( (existiert w’ aus Sigma*: (w=w’a)) UND (für alle x,y,z aus Sigma*: w=xyz → y!=bb) )}

Damit folgt (in der Mengenklammer sind alle logischen Bedingungen zu “ver-und-en”):
L1 Schnitt L2 = letzter Buchstabe a und weder zwei aufeinanderfolgende Buchstaben ‘a’ noch ‘b’ =
= {w | existiert w’ aus Sigma*: (w=w’a UND für alle x,y,z aus Sigma*: (w’=xyz → (y!=aa UND y!=bb)) )}
= ba(ba)* = (ba)*ba

Hier ein Bildchen um es zu verdeutlichen:

Beim ersten und beim letzten Graphen hab ich die Kanten, die zum Terminalzustand führen, vergessen. (Sind aber klar)

Ich hoffe jetzt mal, dass das alles so stimmt.

PS: Yves, wie macht man jetzt mathematische Symbole, warum kann man keine Grafiken mehr anhängen?


Die zweite Aufgabe:
c* vereinigt c* a (c* a c* a)* c* a c*
enthält (u.a.) das Wort cacacacac (alle *e =1)
dieses Wort ist nicht mehr in deinem Ergebnis.


bei der obigen Aufgabe soll (ba v a)(ba)* herauskommen laut Lösung
und im unteren Teil mussten wir so ne tolle Formel anwenden da kam das raus und jetzt muss ich das irgendwie vereinfachen :frowning: wie macht man sowas und wie geht man im oberen Teil mit \ ,vereinigung,* um? hängt man bei der Vereinigung zweier Sprachen einfach das L2 an das L1 hinten dran??wie das mit automaten geht weiß ich (außer das ) aber ich kann ja nicht jedes mal riesige automaten malen und ich erkenne dann auch nicht auf dem ersten Blick was das nun für einen regulären ausdruck ergibt :frowning:


stimmt, das einzelne ‘a’ halb ich übersehen…

Normalerweise (hab ich auch so gemacht) übersetzt man die regulären Ausdrücke in die zugehörigen Wortmengen und verundet die Eigenschaften logisch.
Beispiel:
L1= (( ab vereinigt b)* a) ={w| w=a ∨ ∃w_i∈∑: (w=w_1…w_n ∧ (w_i=a → w_i+1=b ) ∧ w_n=a)}
L2= ((ba vereinigt a)*) = {w| w=ε ∨ w=a ∨ ∃w_i∈∑: (w=w_1…w_n ∧ (w_i=b → w_i+1=a ))}

L1∩L2 = {w| (w=a ∨∃w_i∈∑: (w=w_1…w_n ∧ (w_i=a → w_i+1=b ) ∧ w_n=a)) ∧ (w=ε ∨ w=a ∨ ∃w_i∈∑: (w=w_1…w_n ∧ (w_i=b → w_i+1=a )))} =
= {w| w=a ∨ ∃w_i∈∑: (w=w_1…w_n ∧ (w_i=a → w_i+1=b ) ∧ w_n=a ∧ (w_i=b → w_i+1=a ))}=
= {w| w=a ∨ ∃w_i∈∑: (w=w_1…w_n ∧ (w_i ≠ w_i+1 ) ∧ w_n=a)} = (a ∪ ba)(ba)*
zum letzten ‘=’: w_1 hat nur die Wahl zwischen a oder b. Jenachdem ist damit die Wortlänge gerade oder ungerade.


bin jetzt durch zeichnen drauf gekommen(glaub das mach ich auch in der Prüfung …)… aber wie vereinfache ich ausdrücke…?denn das
c* vereinigt c* a (c* a c* a)* c* a c* ergibt wie gesagt vereinfacht (laut lösung)=c* vereinigt a( c )* a
Ich komm einfach nicht drauf.Das blöde ist halt das ich diese Formel aus dem Skript verwenden muss und nicht die Formel ausm Schöning glaub S.36/37 verwenden darf um aus einem Automaten einen regulären Ausdruck zu finden(habe ich schon gemacht da komm ich auf das richtige Ergebnis) sonder ich muss es wie gesagt so wie oben machen nur wenn ich nicht weiß wie man sowas vereinfacht :frowning:


und noch ne Frage :wink: wie ist ein L1 \ L2 zu lösen???(vielleicht mit Zeichnung…verstehs dann besser :wink: )


Das stimmt definitiv nicht. (vgl. mein Gegenbeispiel oben)
Bist du sicher, dass das richtig sein soll?


L1\L2= L1 ∩ ∑\L2 = L1 ∩ ¬L2
Also wie bei Schnitt, nur dass du die Eigenschaften mit ner Klammer drumrum negieren mußt.
Also {w| phi(w)}{w|rho(w)} = {w | phi(w) ∧ ¬rho(w)}

wenn du zeichnen möchtest, negiert man indem man alle Endzustände zu normalen Zuständen und vice versa macht.

Welche?


gibts so in ca. 30 min :wink: suchen gerade das Stromkabel vom Scanner :smiley:


So anbei alles eingescannt.Die vorher gepostete angabe bezog sich nur auf den übergang von S0 nach S2, den rechten teil des automaten mache ich gesondert .Kannst du mir anhand der beiliegenden Formel genau erklären wie man dort vorgeht?!Ich mache immer irgendetwas falsch …bei anderen Aufgaben habe ich das richtige Ergebnis raus nur bei dieser nicht…ich habe leider keine Ahnung was genau ich falsch mache :frowning:

Attachment:
Automat.jpg: https://fsi.cs.fau.de/unb-attachments/post_25789/Automat.jpg


Hier die eingescannte Formel

Attachment:
Unbenannt(1).jpg: https://fsi.cs.fau.de/unb-attachments/post_25790/Unbenannt(1).jpg


Mit so nem nichtdeterministische S*** habe ich in meiner Studienarbeit auch zu kämpfen…
Wenigstens scheint es nur einen Startzustand (S0) zu geben.
Ich bezeichne mit ⇒ das Kürzen von Zykeln. also einen Schritt von (Z) … (Z) nach (…)*
Also los:
Beobachtung 1: Wenn man rechts neben S0 einen Senkrechten Strich zieht, zerfällt der Graph über S0 (es laufen keine Kanten von Rechts nach Links und alle Kanten in die andere richtung gehen von
S0 aus). Also fangen wir links an.
S0 ist bereits Endzustand. Schreibe auf: ε (leeres Wort)
Verfolge die Kante b von S0 nach S1. Von dort kommt man nicht weg. Also kante (b:S0→S1) wegstreichen. Nichts aufschreiben.
Verfolge die Kante a von S0 nach S2. Kein Endzustand. Merke: (S0)a
Verfolge Kante b von S2 nach S1. Von dort kommt man nicht weg. Also Kante (b:S2→S1) wegstreichen.
Verfolge Kante c von S2 nach S2. Der Knoten (S2) war bereits erreicht. Merke: (S0)a(S2)c(S2) ⇒ (S0)a(S2)c*
Verfolge Kante a von S2 nach S0. Der Knoten (S0) war bereits erreicht (in diesem Zyklus!!!). Merke: (S0)a(S2)c*(S2)a(S0) ⇒ (aca)
Verfolge c von S0 nach S0. Der Konten (S0) war bereits erreicht. Merke (S0)a(S2)c*(S2)a(S0)c(S0) ⇒ (S0)a(S2)c*(S2)a(S0)c*(S0).
Nach S0 führen keine (unabgewanderten) Kanten mehr zurück. Also kompliziertere Umformung:
-Klammere äußere (S0)s ein, ersetzte innere durch ∪: (S0)a(S2)c*(S2)a ∪ c*
-Versterne die Neue Klammer: (S0)(a(S2)c*(S2)a ∪ c*)(S0)
S0 ist Endzustand. Schreibe auf (was du dir gemerkt hattest ohne die Zustände): (ac
a ∪ c*)* (Anmerkung: ∪ ist schwach bindend! Gemeint: ((aca) ∪ (c))*
Streiche Kanten (a:S0→S2) und (c:S0→S0)
Vergiss!
Verfolge die Kante a von S0 nach T1. Von dort kommt man nicht weg. Also kante (a:S0→T1) wegstreichen. Nichts aufschreiben.
Vergiss!
Verfolge die Kante c von S0 nach T0. T0 ist Endzustand. Schreibe auf: c Merke: (S0)c(T0)
Verfolge die Kante a von T0 nach T1. Von T1 kann man nicht weg, ist auch kein Endzustand also wieder Kante (a:T0→T1) streichen.
Verfolge die Kante c von T0 nach T0. Merke: (S0)c(T0)c(T0) ⇒ (S0)c(T0)c*(T0).
Streiche die Kante (c:T0→T0).
T0 ist Endzustand. Schreibe auf: cc*
Verfolge die Kante b von T0 nach T2. Merke: (S0)c(T0)c*(T0)b(T2)
Verfolge die Kante a von T2 nach T1. Alte blah. wegstreichen.
Verfolge die Kante c von T2 nach T2. Merke: (S0)c(T0)c*(T0)b(T2)c(T2) ⇒ (S0)c(T0)c*(T0)b(T2)c*(T2)
(!)Verfolge die Kante b von T2 nach T0. Merke: (S0)c(T0)c*(T0)b(T2)c*(T2)b(T0).
T0 war schonmal da und von T0 gehen keine weiteren Kanten mehr aus. Also kompliziertere Umformung:
- Suche letztes Auftreten von T0, einklammern: (S0)c(T0)c*(T0)b(T2)c*(T2)b.
- Zyklus versternen: (S0)c(T0)c*(T0)(bcb)(T0)
- Äuserste (T0)s einklammern, innere verunden: (S0)c(T0)c∪(bcb)*
- Zyklus versternen: (S0)c(T0)(c∪ (bcb)* )(T0)
T0 ist Endzustand. Schreibe auf: c(c
∪ (bcb) )*
Kante (c:S0 → T0) streichen. (Man sollte villeicht mal erwähnen: Kanten werden gestrichen, wenn es keinen Weg mehr zurück zum Kantenfußpunkt gibt)
Vergiss!
Es bleibt die Kante b von S0 nach T2. Merke: (S0)b(T2)
Verfolge die Kante c von T2 nach T2. Merke: (S0)b(T2)c(T2) ⇒ (S0)b(T2)c*(T2)
Verfolge die Kante a von T2 nach T1 nicht. (war ja gestrichen!)
Verfolge die Kante b von T2 nach T0. Merke: (S0)b(T2)c*(T2)b(T0).
Treibe denselben Rotz wie oben. Merke: (S0)b(T2)c*(T2)b(T0)(c∪ (bcb)* )(T0)
T0 ist Endzustand. Schreibe auf: bc
b(c∪ (bcb)* )*
Vergiss!
Dies war die letzte Kante.
Verunde, was auf dem Papier steht
ε ∪ (aca ∪ c)* ∪ c(c∪ (bcb)* )* ∪ bcb(c∪ (bcb) )*

(Optional: Radiere ε weg, weil es in (aca ∪ c)* enthalten ist…)


boah…


Meinst du damit das wenn er sofort danach in nen Endzustand läuft?weil die Kanten b und c laufen ja auch nicht wieder zurück


hmm also ich bekomme folgendes heraus:

((a(c)a) ∪ c)* ∪ ((b(c)b) ∪ c)* ∪ ((b(c)b) ∪ c)*

das Ergebnis laut Lösung ist:

((a(c)a) ∪ c)* ∪ ((b(c)b) ∪ c)⁺

ist ja fast richtig ergibt sich das ⁺ daraus das ich 2x mal das gleiche habe???


Ein weg ist ein Kantenzug also eine anzahl von Kanten k_i, s.d. Der Endpunkt von k_i der Fußpunkt von k_i+1 ist.
Was ich geschrieben habe meint besser verständlich: die Kante liegt in KEINEM Zyklus.

⁺ = ‘hoch +’ ? (wird im Firefox nicht richtig angezeigt)
Also mindestens ein auftreten:
Nein, das ergibt sich nicht aus 2x dem gleichen. zweimal das gleiche absorbiert sich einfach (da bleibt dann eines stehen, nicht keines!).

Hätte ich villeicht auch sagen sollen: * bindet bei mir eng: mein ac* ist dein a(c)*
Zur Musterlösung:
(aca ∪ c)* ∪ c(c∪ (bcb)* )* ∪ bcb(c∪ (bcb) )*

(aca ∪ c)* ∪ (c ∪ bcb)(c∪ (bcb) )*
≡ weil: (c∪ (bcb)* )* ≡ (ε ∪ c ∪ (bcb) ) ≡ (c ∪ (bcb) ) (Iteration nach außen ziehen)
(aca ∪ c)* ∪ (c ∪ (bcb) )⁺
≡ weil: ε ∈ (ac
a ∪ c*)*
(aca ∪ c)* ∪ ε ∪ (c ∪ (bcb) )⁺

(ac
a ∪ c*)* ∪ (c∪ (bcb) )⁺

(der Stern beim c ist auch optional)


Weil’s mir grad auffällt:

((a(c)a) ∪ c)* ∪ ((b(c)b) ∪ c)⁺

((a(c)a) ∪ c)* ∪ ((b(c)b) ∪ c)* ∪ ((b(c)b) ∪ c)*

Das liegt daran, dass ε* = ε ist.
Herzlichen Glückwunsch.


[ot]
Doch doch, das wird schon angezeigt. Wenn auch etwas klein. Du musst halt nur ne Schriftart installieren, die dieses Zeichen auch enthält. Unter Windows gibt’s z.B. Arial Unicode MS, das müsste bei Office dabei sein. Ob Linux und MacOS sowas auch haben, weiß ich nicht.
[/ot]


[OT] Krass! Jetzt wird es angezeigt! [/OT]