Fachrat Informatik - Forum

ich glaube das würde so etliche leute hier im forum brennend heiss interessiern (mich eingeschlossen)
aber anscheinend sind alte klausuren mangelware sonst hätte wohl schon wer auf den selben thread weiter unten geantwortet

hat eventuell wer
zu den themen:
- entfernung von epsilon produktionen in kontextfreienspr.
-pumping lemma
-diese komische R(i,j,k) Produktions geschichte
-und evtl. zu den abschluss eigenschaften von Sprachen

schön gelöste Hausübungen anzubieten ??!!

Nun, in der letzten Aufgabe der letzten Hausübung hatten wir ja einen "Vorgeschmack" auf eine typische Klausuraufgabe bekommen. Ausschluss von Sprachen mithilfe bekannter Sprachen ist natürlich Pflicht.
Da muss ich noch was tun.

huups
da iss mir nen kleines malör passiert

das hab ich grade aus unserer letzten ü-stunde ausgegraben :

zu HÜ 10 (1.a)

L1= {a^i b^j /j >= i} ist kfr. unter ausnutzung der abschlusseigenschaften

{a^i b^i b^k /i,k >= 0} = {a^i b^i / i >= 0}o b^*

{a^i b^i } ist kfr. (mit Kellerautomat beweisbar und b* ist reg. also natürlich auch kfr.

laut abschlusseigenschaften von kfr. sprachen ist L1 Kfr.

zu 1b)
zz. ....(siehe ü-blatt)... ist kfr.

L~ := {a^k b^l c^m /k,l,m >= 0}

L' := a* b* c* b* a* (reg.)
L" := {ww^r(gespiegelt) / w elem. {a b c }* }

L2 = {ww^r /w elem. L~}

L2 = L' geschnitten mit L" also Kfr. (da reg geschn. mit kfr.)

X elem. L' geschn. L" => x elem. L" => x= x^r .