Beispiel 4.3

[KatzeImSack]

also, meine Produktionen für L1:
S -> Sc|A, A -> aaaAbb|Eps

für L2:
S -> aS|B, B->bBccc|Eps

zur Zusatzfrage:
beweis muss ich mir noch überlegen...
(also "von haus aus bewiesen" ist es mal nicht, da kontextfreie sprachen nicht gegenüber Durchschnitt abgeschlossen sind...)

hat wer was anderes?

[schrankk]

hab genau so!! :)

und bzgl. Zusatzfrage: ich habe zuerst den Durchschnitt gebildet: L = \lbrace {a}^{n} {b}^{2/3*n} {c}^{2n} \rbrace Und weiters gibt es in meinem Skriptum (Version März 2008, Seite 47) den Beweis mit P.L. für k.f. Sprachen auf dem Beispiel L = \lbrace {a}^{kn} {b}^{ln} {c}^{mn} | {n} \geq 1 \rbrace für beliebige Konstanten {k},{l},{m} \geq 1 , dass L nicht k.f. ist!! ;)

vlg

[Bianconeri]

hab genau so!! :)

und bzgl. Zusatzfrage: ich habe zuerst den Durchschnitt gebildet: L = \lbrace {a}^{n} {b}^{2/3*n} {c}^{2n} \rbrace Und weiters gibt es in meinem Skriptum (Version März 2008, Seite 47) den Beweis mit P.L. für k.f. Sprachen auf dem Beispiel L = \lbrace {a}^{kn} {b}^{ln} {c}^{mn} | {n} \geq 1 \rbrace für beliebige Konstanten {k},{l},{m} \geq 1 , dass L nicht k.f. ist!! ;)

vlg
Ist der Durchschnitt der beiden Sprachen nicht Epsilon? Ich finde zumindest sonst keine gemeinsamen Wörter in den beiden Sprachen.

[schrankk]

Ist der Durchschnitt der beiden Sprachen nicht Epsilon? Ich finde zumindest sonst keine gemeinsamen Wörter in den beiden Sprachen.
Nein, ist er nicht!!

Z.B. für n=3 für Sprache L, die den Durchschnitt von L1 und L2 bildet, ergibt sich das Wort a^3 b^2 c^6. Dieses Wort wird in L1 gebildet, wenn n=1, m=6. Und in L2, wenn n=3, m=2.

vlg

[Bianconeri]

Nein, ist er nicht!!

Z.B. für n=3 für Sprache L, die den Durchschnitt von L1 und L2 bildet, ergibt sich das Wort a^3 b^2 c^6. Dieses Wort wird in L1 gebildet, wenn n=1, m=6. Und in L2, wenn n=3, m=2.

vlg
Ok hast du recht, danke. Dann ist deine Lösung wohl richtig, Grammatiken habe ich die selben.

[jperl]

hab genau so!! :)

und bzgl. Zusatzfrage: ich habe zuerst den Durchschnitt gebildet: L = \lbrace {a}^{n} {b}^{2/3*n} {c}^{2n} \rbrace Und weiters gibt es in meinem Skriptum (Version März 2008, Seite 47) den Beweis mit P.L. für k.f. Sprachen auf dem Beispiel L = \lbrace {a}^{kn} {b}^{ln} {c}^{mn} | {n} \geq 1 \rbrace für beliebige Konstanten {k},{l},{m} \geq 1 , dass L nicht k.f. ist!! ;)

vlg

kleine anmerkung:
dein l ist nicht größer gleich 1 (\frac{2}{3} < 1)

jperl

[georgfu]

bräuchte bitte einen ansatz, wie man systematisch auf den durchschnitt der beiden sprachen kommt.

danke =)

[Karotte]

Ja bitte, habs auch ned verstanden, wär nett wenn dus kurz erklären könntest =)

[DanyToss]

Durchschnitt: Einfach die ersten Worte ansehen:

Bei L1 kommt es auf a und b an, Rest kann was auch immer sein.
Bei L2 kommt es auf b und c an, Rest kann was auch immer sein.

Das heisst in L1 ist das erste Wort aus a und b: aaabb, dann aaaaaabbbb, usw ...

In L2 demnach: bccc, dann bbcccccc, bbbccccccccc, bbbbcccccccccccc, ...

Welches Wort liegt demnach als erstes im Durchschnitt? Natürlich das was bb hat: Bei L1 kann ich danach beliebig viele (6 Stück in dem Fall) c anhängen und bei L2 kann ich beliebig viele (3 Stück hier) a anhängen, und er erhalte: aaabbcccccc. Das kann in beiden Sprachen gemacht werden.

Analog ist das nächste, das was aus bbbb gemacht wird. (3x geht zwar in L2 aber in L1 nicht)

Nun muss man nur noch irgendeine Formel aufstellen, wie zB die gepostete (a müssen halbsoviele wie c sein, b is nun 2/3 von a oder 1/3 von c)

[Bianconeri]

kleine anmerkung:
dein l ist nicht größer gleich 1 (\frac{2}{3} < 1)

jperl
Mh da ist was dran. Hatte als Begründung eigentlich auch den Beweis aus dem Buch genommen aber l ist natürlich wirklich nicht größer gleich 1.
Stellt sich nur die Frage ob das nicht egal ist, weil ich denke, dass bei dem Beweis das >= 1 nur steht um zu verhindern, dass ein Symbol 0 mal auftritt. Und das kann es bei uns ja sowieso nicht weil ja n durch 3 teilbar sein muss.

[bsoykal]

Wie zeigen wir dass L1 und L2 kontextfrei sind ? mit PL oder ?

[jperl]

Mh da ist was dran. Hatte als Begründung eigentlich auch den Beweis aus dem Buch genommen aber l ist natürlich wirklich nicht größer gleich 1.
Stellt sich nur die Frage ob das nicht egal ist, weil ich denke, dass bei dem Beweis das >= 1 nur steht um zu verhindern, dass ein Symbol 0 mal auftritt. Und das kann es bei uns ja sowieso nicht weil ja n durch 3 teilbar sein muss.

naja einfach das l und auch alle andere variablen anpassen, sodass immer noch die gleichen wörter gebildet werden können.

sollte nicht allzu schwer sein. ;)

jperl

[bsoykal]

Sollen wir nicht zeigen dass L1 und L2 kontextfrei sind ?

[Bianconeri]

naja einfach das l und auch alle andere variablen anpassen, sodass immer noch die gleichen wörter gebildet werden können.

sollte nicht allzu schwer sein. ;)

jperl
Ok stimmt einfach a^(3*n/2) b^n c^3n nehmen dann passt es. Dabei muss n halt dann durch 2 teilbar sein.

[bsoykal]

????

[Bianconeri]

Sollen wir nicht zeigen dass L1 und L2 kontextfrei sind ?

Die kontextfreiheit von L1 und L2 haben wir eh schon gezeigt dadurch, dass wir eine kontextfreie Grammatik entwickelt haben. Die Grammatiken stehen ganz oben in diesem Thread und sind sicher richtig.

[bsoykal]

danke :) und letzte Frage ;

L =>(L1 n L2)
ist nicht kontextfrei oder?

[schrankk]

ich bin zwar immer todmüde montags und dienstags, aber jetzt hab die Beispiele nochmal angeschaut!

also bzgl. Zusatzfrage: es sieht in meinen Augen nicht mehr so schön aus, dass l=2/3 ist, und nicht unbedingt, da es <1 ist, und in Beweis zu P.L. in Skriptum nicht passt! Wie sieht denn ein Wort in L (Durchschnitt von L1 und L2) aus, wenn n=2? Also am Anfang 2 Symbole a, am Ende 4 Symbole c, und in der Mitte 4/3 Symbole b?? :rolleyes:

Meine erste Gedanke ist, dass man vl. einfach explizit die Bedingung für n ändern sollte (also nicht mehr einfach n=>0)... auf etwas wie n=0,3,6,9... :o

Die zweite Variante wäre es, den Durchschnitt umzuformulieren, auf etwas wie L={a^(3n) b^(2n) c^(6n) | n=>0}. Ist so der neue Durchschnitt äquivalent zu altem?!

Und die dritte Variante (auf bisschen ähnliche Weise zu zweite Idee), einfach n durch andere Konstante ersetzten, etwa n=3*d, d=>0.

P.S
ja, und wenn man angewiesene Beweis mit P.L. anschaut, wird dort k, l, m => 1 eigesetzt um sicher zu stellen, dass nicht die Länge von z = (k+l+m) * n => n ist. In unserem (alten) Fall ist k+l+m = 1+2/3+2 immer noch >1, und somit z = (k+l+m) * n => n auch gilt!! :thumb:
peace.

[jperl]

genau deswegen ja meine anmerkung zu den 2/3.

also ich habe deine variante 2.
der durchschnitt sollte passen.
weil ich ja eigentlich von L1 a^(3n) b^(2n) nehme und dann für L2 m = 2n habe. somit sind 3m = 3*2n = 6n.

was mich noch stört ist dass im beweis steht dass n>=1 und bei uns ist n>=0.

jperl

[schrankk]

was mich noch stört ist dass im beweis steht dass n>=1 und bei uns ist n>=0.
hab irgendwo in Skriptum gelesen, dass P.L. nur für "hinrechend große Wörter gilt". Also ich neheme an, Eps ist kein hinreichendgroßes!! Und um formalistischer zu sagen, steht in P.L. bzgl. Zerlegung, dass |vy| >= 1 gelten soll, was für keine Zerlegung des Leerwortes der Fall wird... :rolleyes:

[jperl]

hab irgendwo in Skriptum gelesen, dass P.L. nur für "hinrechend große Wörter gilt". Also ich neheme an, Eps ist kein hinreichendgroßes!! Und um formalistischer zu sagen, steht in P.L. bzgl. Zerlegung, dass |vy| >= 1 gelten soll, was für keine Zerlegung des Leerwortes der Fall wird... :rolleyes:

jepp, dann ist auch mein letzter zweifel aus dem weg geräumt.

jperl

[bsoykal]

Mein Vorschlag:

L={a^3k b^2k c^6k // k>=0}

Sei L kontextfrei ;

konstante k

lwl=(3+2+6)k>k
lvyl>=1
lvxyl<=k

Fall1 ;

lvxyla > 0
da lvxyl <=k sein soll
deswegen lvxylc=0

a^3k-m ---> u
a^m b^2k-n ---> vxy (2k>n)
b^n c^6k ---> z

wi = uv^ixy^iz
lw2lc=6k
lw2la>3k
lw2lb>2k .....................lw2l liegt nicht in der Sprache
------------------------------------------------------------------------------------------------------
Fall2 ;

lvxyla = 0

entweder

a^3k b^2k-n --> u (2k>n)
b^n c^6k-t ---> vxy
c^t ----> z (5k<t<=6t)

oder ..........................................

a^3k --> u
b^2k-n ---> vxy (2k>n)
b^n c^6k ----> z

lw2la= 3k
lw2lb>2k und lw2lc>6k
oder ....................lw2l liegt nicht in der Sprache
lw2lb>2k
lw2lc=6k

Wir erhalten in jedem Fall einen Wiederspruch.
L ist nicht kontextfrei.