Servus, ich schrieb vor 3 Monaten an der uni eine Theoretische-Informatik-Prüfung und es kann sein, dass bei dieser Aufgabe enorm Punkte unrechtmäßig abgezogen wurden. Bei allen 3 Aufgabenteilen bekam ich leider nur jeweils 0-0.75 Punkte von insgesamt 21, obwohl ich der Meinung bin, dass es viel mehr sein müssten. Bin auf jedem sehr dankbar, der sich das mal durchliest und seine Meinung abgibt:
Bei der a) ging es darum, mit Pumping-Lemma zu beweisen, dass die Sprache pc^i, wobei p element {a,b}+, i element N+, |p|a > 0, |p|b > 0 und anzahl as + anzahl bs = i, nicht regulär ist. Ich schrieb: "Sei n element N, wähle w=a^l b^m c^p mit w element L, |w| >= n, l > 0, m > 0 und p > 0 und l+m=p. Dann ist x=a^l b^i, y=b^m-i-j, z=b^j c^p eine beliebige Zerlegung mit i+j<m. Wir wählen k=0. Dann ist a^l b^i b^j c^p nicht element L, da l+i+j < l+m = p gilt, also |p|a + |p|b < i und nicht mehr |p|a + |p|b = i gilt. Somit gilt NICHT(PUMP(L)), sodass L nicht regulär ist.
Bei der b) musste man die
…