Finde zwar den rat. Ausdruch für (a), allerdings komm ich da mit der Kleene-Sache nich ganz drauf. Gehe ich da richt ran, wenn n=2, i=1, j=2? Dann gilt R hoch 2 und tiefgestellt 1,2.
Kann ich dann einfach schreiben, dass R hoch 2 und tiefgestellt 1,2 = R hoch 1 und tiefgestellt 1,2 mal R hoch 0 und tiefgestellt 2,2? Ich klomm nur so auf die Lösung.
kommt drauf an wie der automat ausssieht,
wenn du 2 zustände hast, z1 start und z2 endzustand,
dann ist
L(A) = R^2_1,2 = R^1_1,2 vereinigt R^1_1,2 * (R^1_2,2)^* * R^1_2,2
usw., da muss man ziemlich viel kleinkram ausrechnen,
wenn du einen konkreten automaten hast und eine herleitung
nach Kleene dazu, kannst sie mir als email schicken,
dann sag ich dir ob sie richtig ist ;)
Kann mir Jemand das Grundprinzip von Kleene erklären?! Die Definitionen aus dem Skript sind mir nicht verständlich?!
die sollte aber schon verständlich sein, das ist eine wichtige fähigkeit,
solche kryptischen zeichen lange genug anzuschauen,
bis man jede einzelheit nach und nach versteht,
schaff ich aber auch nicht immer ;)
was genau willst du denn wissen?,
der satz besagt, dass Akz(E) = Rat(E), das ist verständlich?
ich nehme mal an du meinst die richtung
Akz(E) teilmenge Rat(E)
(jede sprache eines FA lässt sich als rationaler ausdruck darstellen)
das zeigt man indem man aus jedem DFA/ NFA den rationalen
ausdruck für die akzeptierte sprache konstruiert,
und zwar mit dem angegebenen verfahren,
das verfahren arbeitet rekursiv,
R^k_i, j ist die reguläre menge (also praktisch schon ein rationaler ausdruck),
die alle wörter enthält, die der automat bilden kann,
und zwar von zustand i aus nach zustand j,
wobei zwischendurch nur die ersten k zustände besucht werden,
demnach ist L(A) des automaten die vereinigung aller dieser
mengen, die bei einem startzustand anfangen, bei einem
endzustand aufhören und beliebige zwischenzustände besuchen,
formal: vereinigung über R^n_1, j für alle endzustände j,
das ganze funktioniert, wenn R^k_i, j für alle relevanten
i, j,k eine reguläre menge ist,
dies wird per induktion bewiesen,
der induktionsanfang ist einfach für alle i, j und für k=0
der induktionsschritt zeigt, das für alle i, j gilt:
R^k_i, j = R^k-1_i, j vereinigt R^k-1_i,k * (R^k-1_k,k)^* * R^k-1_k,j
und zwar wird das argumentativ bewiesen:
R^k_i, j = von i nach j über die ersten k zustände
= (von i nach j über die ersten k-1 zustände) oder
(von i nach j über den k.ten und die ersten k-1 zustände)
= R^k-1_i, j vereinigt
(von i nach j über den k.ten und die ersten k-1 zustände)
= R^k-1_i, j vereinigt
((von i nach k über die ersten k-1 zusände) und danach
(beliebig oft: von k nach k über die ersten k-1 zustände) und danach
(von k nach j über die ersten k-1 zustände))
= R^k-1_i, j vereinigt R^k-1_i,k * (R^k-1_k,k)^* * R^k-1_k,j
dies ist eine reguläre menge also fertig
