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 Äquivalenzklassen der Nerode-Relation dieser Sprache angeben. Ich schrieb:
[epsilon] = {epsilon}
[a^n | n element N+] = {w | w element {a,c}* und |w|a = n}
[b^n | n element N+] = {w | w element {b,c}* und |w|b = n}
[a^n b^m c^l | n, m, l element N+] = {w c^l | l = |w|a + |w|b + c und c element Z}
[c] = {xw | x element {a,b} und w element {c}*}
Bei der c) musste man mit der Nerode-Relation beweisen, dass L nicht regulär ist. Ich schrieb: "Eine Sprache ist genau dann regulär, wenn der Nerode-Index von 
Quertriche>L endlich ist. Das ist hier jedoch nicht der Fall, da beispielsweise bereits [a^n | n element N+] unendlich viele Äquivalenzklassen darstellt (für jedes n element N eine Äquivalenzklasse). Somit ist L nicht regulär.
