4.2

[Auron]

G1= ( {S,A}, {a,b,c}, {S=> Sc | A, A=> aAbb | \varepsilon}, S)

G2= ( {S,A}, {a,b,c}, {S=> aS | A, A=> bAcc | \varepsilon}, S)

Zusatzfrage: Weil kontextfreie Sprachen über \cap nicht abgeschlossen sind.

[tonico]

Ergänzung: L1 ∩ L2 = {anb2nc4n|n >= 0}

Edit: Der Schnitt zweier kontextfreier Sprachen könnte wieder Kontextfrei sein, z.B. bei regulären Sprachen. Im Allgemeinen is dies nicht der Fall.

[MADyn]

Startpunkt S am Ende in den beiden Grammatiken net vergessen

[axestr]

Hallo!

Die Zusatzfrage kann man mit dem PL für reg. Gram. begründen.

L=\{a^nb^{2n}c^{4n}| n \ge 0\}.

Sei n die Konstante aus dem PL und w=a^nb^{2n}c^{4n} \in L,
|w|=7>=n. Wegen dem PL muss eine Zerlegung uxwyv existieren, sodass
z_i=ux^iwy^iv \in L für alle i>=0, mit |xwy| <= n, |xy|>0.

Sein nun |xwy|_a > 0 . Wegen |xwy| <= n folgt, dass |xwy|_c=0 (also innerhalb von a^nb^{2n} liegen muss).
Dann müssen aber alle c in v liegen, also |v|_c=4n konstant sein. Da aber mit wachsendem i auch |z|_c wächst ist dies ein f.A., also muss |xwy|_a = 0 sein.

Sein nun |xwy|_a = 0 . Dann liegen alle a's in u (da |xy|>0), also müsste |u|_a=n konstant sein, was für wachsende i wiederum ein Widerspruch ist, als f.A.

Als gilt das PL nicht, also ist die G. nicht kontextfrei.

Lg, Axel.