Hallo, ich grüble jetzt schon mehrere Tage über dieser Aufgabe. Mein Problem ist, ich komme nicht auf L2, kann mir vielleicht jemand sagen, wie das zu lösen ist.
L1 = {w element {a,b}* | w enthält doppelt so viele a's wie b's}
L1 ist nicht regulär(kann durch uvw gezeigt werden)
sei L2 = L1 geschnitten {a}* {b}*
Frage:
geben sie L2 an,
geben sie einen kellerautomaten an, der L2 mit
leeren keller akzeptiert.
Ist L2 nicht schlicht "a^2n b^n"?
L1 = {w element {a,b}* | w enthält doppelt so viele a's wie b's}
sei L2 = L1 geschnitten {a}* {b}*
Dann gilt also
L2 = {w element {a,b}* | w enthaelt doppelt so viele as wie bs und w wird beschrieben durch a*b*}
= {a^2k b^k | k natuerliche Zahl}
Wenn ich das richtig sehe, dann ist L2 die Menge aller Wärter aus a*b*, die doppelt so viele a's wie b's enthält.
L2= {w = a^(2n) b^n | n ? N}
Ein Kellerautomat müste in etwa so aussehen.
Startzustand, der gleichzeitig Endzustand ist.
Kante mit "aa" zu Zustand 2 (Z2), wobei ein x aufn Keller geschrieben wird.
Von Z2 aus eine Kante zu Z2, mit "aa", wobei wiederum x aufn Keller geschrieben wird.
Eine Kante von Z2 mit "b" zu Z3, wobei x vom keller gelesen wird.
Eine Kante von Z3 mit "b" zu Z3, wobei x vom Keller gelesen wird.
Eine Kante von Z3 mit Lambda zum Endzustand Z4, wobei das Kellerbodensymbol gelesen wird.
Mist, waren andere schneller [img]
http://www.fb18.de/gfx/25.gif[/img]
Hab eigntlich ne andere Frage, aber ich wollte dafür kein neues Topic erstellen.
Und zwar wüsste ich gerne den Unterschied zwische der normalen Vereinigung von Mengen und der disjunkten Vereinigung.
Ein Beispiel:
M1:={a,b,c,d,e,f}
M2:={x,y,z,a,b}
u=Vereinigung
u+=disjunkte Vereinigung
M1uM2={a,b,c,d,e,f,x,y,z} <- das versteh ich ja
Muss ich bei der disjunkten Vereinigung Sysbole umbenennen, die in beiden Mengen vorkommen?
Etwa M2_neu:={x,y,z,a1,b1}
Dann vereinigen, sodass
M1u+M2=M1uM2_neu={a,b,c,d,e,f,x,y,z,a1,b1}?
Sehe ich das so richtig?
wenn ich mal erinnern versuche,
dann bedeutet
M1 u+ M2 = M1 u M2 mit dem zusatz: M1 und M2 sind disjunkt,
also dürftest du für deine mengen
gar nicht M1 u+ M2 hinschreiben, da sie nicht disjunkt sind,
falls falsch bitte korrigieren
wenn ich mal erinnern versuche,
dann bedeutet
M1 u+ M2 = M1 u M2 mit dem zusatz: M1 und M2 sind disjunkt,
also dürftest du für deine mengen
gar nicht M1 u+ M2 hinschreiben, da sie nicht disjunkt sind,
falls falsch bitte korrigieren
Also müsste ich die Mengen erst disjunkt machen (M2_neu) und dann disjunkt vereinigen, quasi M1u+M2_neu oder?
falls
1.
meine theorie stimmt
und
2. du unbedingt dieses u+ verwenden möchtest (wozu eigentlich?)
wär das wohl ein weg, aber was ist dann die aussage?
spannender ist das zum beispiel bei:
reelle zahlen = {0} u+ {positive reelle zahlen} u+ {negative reeele zahlen}
da spart diese schreibweise den zusatz der disjunktheit
falls
1.
meine theorie stimmt
und
2. du unbedingt dieses u+ verwenden möchtest (wozu eigentlich?)
u+ weil das im F2-Skript dieses Symbol ist bzw. ein u mit nem plus drin.
wär das wohl ein weg, aber was ist dann die aussage?
wieder mal F2… Beispiel Vereinigung zweier kontextfreier Sprachen L1 u L2. Die daraus resultierende Grammatik ist
G=(V1u+V2,…) Um diese Menge zu bestimmen muss ich ja wissen wie ich evtl. in beiden vorkommende Nonterminale behandeln soll).
spannender ist das zum beispiel bei:
reelle zahlen = {0} u+ {positive reelle zahlen} u+ {negative reeele zahlen}
da spart diese schreibweise den zusatz der disjunktheit
?
Das letzte versteh ich zwar nicht, aber trotzdem danke
u+ weil das im F2-Skript dieses Symbol ist bzw. ein u mit nem plus drin.
wieder mal F2… Beispiel Vereinigung zweier kontextfreier Sprachen L1 u L2. Die daraus resultierende Grammatik ist
G=(V1u+V2,…) Um diese Menge zu bestimmen muss ich ja wissen wie ich evtl. in beiden vorkommende Nonterminale behandeln soll).
das wär ein nicht schlechter hinweis bei der frage gewesen ;)
ja da denke ich da ist gemeint das die beiden mengen disjunkt
sein sollen, und dann macht es sinn, die elemente eben
passend umzubenennen, richtig
spannender ist das zum beispiel bei:
reelle zahlen = {0} u+ {positive reelle zahlen} u+ {negative reeele zahlen}
da spart diese schreibweise den zusatz der disjunktheit
?
kann man dann ignorieren, ich meinte etwas ausführlicher:
"reelle zahlen = {0} u+ {positive reelle zahlen} u+ {negative reeele zahlen}"
<=gleichbedeutend=>
"reelle zahlen = {0} u {positive reelle zahlen} u {negative reeele zahlen}
mit zusatz: alle drei mengen auf der rechten seite sind paarweise disjunkt"
wenn ich mal erinnern versuche,
dann bedeutet
M1 u+ M2 = M1 u M2 mit dem zusatz: M1 und M2 sind disjunkt,
also dürftest du für deine mengen
gar nicht M1 u+ M2 hinschreiben, da sie nicht disjunkt sind,
falls falsch bitte korrigieren
Im F2-Skript, S. 13 steht:
waehrend A \u+ B deren
disjunkte Vereinigungbezeichnet, d.h. A und B waren schon disjunkt oder werden, durch
Umbenennung der Elemente einer Menge, dazu gemacht.
Also sieht das Umbenennen in a1, b1 in einer der Mengen ok aus.
Problem ist nur, wo vermerkt man das, wenn man es tut (tun musste)?
Also doch besser: erst disjunkt machen dann u+ verwenden, wenn man's ueberdeutlich machen möchte.
