Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
An die MIU-Checker
Hi allerseits ich hab ein paar Fragen zur MIU - Aufgabe und C-rekursiven Folgen…
-
bei der ersten Teilaufgabe soll man die C-Rekursion verifizieren. Ich hab dazu die Transfermatrix aufgestellt und das charakteristische Polynom berechnet, daraus kann man ja (so wie ich das verstanden hab) leicht die C-Rekursion ablesen, nur komm ich da immer auf was falsches :-/ stimmt der Ansatz überhaupt oder welche anderen Methoden gibts da?
-
Seh ich das richtig, dass ich die erzeugende Funktion nur aus dem regulären Ausdruck krieg?
-
Bei der vorletzten Aufgabe soll man eine andere Darstellung von μn zeigen, wie kommt man auf die?
4 . Für die Coderate hab ich 1 raus … hat das noch jemand?
bei dem char. polynom kommt ja λ³ - 3λ² + 3λ - 2 raus.
Man nehme die Potenz der char. Fkt als Index für die Rekursion:
μn-3 - 3μn-2 + 3μn-1 - 2μn = 0
bisschen hübscher hingeschrieben:
μn-3 = 3μn-2 - 3μn-1 + 2μn
Naja der Strehl kann die auch irgendwie aus dem charakteristischen Polynom herleiten. Das unter dem Bruchstrich bekomm ich auch noch hin, aber was er mit Koeffizientenvergleich meint, weiß ich auch nicht.
steht eigentlich alles in Strehls Musterlösung. Er macht da Partialbruchzerlegung der erzeugenden Funktion.
Strehl hat log 2 zur Basis 3
http://www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Uebungen05/u9loesung.pdf
hmmm ich hab da die Matrix hoch 3 genommen bevor ich das ausgerechnet hab … weiß auch nicht wieso… sowas stand irgendwie in den Folien … aber so isses klar …
hmmm ja das hat mich auch gewundert, wie das gehen soll …
Danke für den Link, hab ich wohl irgendwie übersehen :red:
das mit dem Koeffizientenvergleich ist glaube ich so gemeint:
man hat die Rekursionsgleichung der Wortlaengen gegeben:
μ(n) = 3μ(n-1) - 3μ(n-2) + 2μ(n-3) (n>=3); μ(0)=μ(1)=0: μ(2) = 1;
…und weiss die erzeugende Funktion ist immer:
f(z) = Summe[ μ(n)*z^n ]
…auch mit f(z) kann man die Rekursionsgleichung schreiben, man braucht bloss die richtigen koeffizienten, die man aber aus der rekursionsgleichung sieht…
f(z) - z^2 = 3zf(x) -3z^2f(z) +2z^3f(z)
links macht man - z^2 wegen n>=3, rechts laufen die indexe hinterher, doch durch die koeffizienten (ich denke die meint auch der Strehl?) z^1, z^2, und z^3 wird das ausgeglichen.
Man loese die Gleichung nach f(z) auf und die erzeugende Funktion steht da.
naja so denke ich mir das jedenfalls. konnte damit auch schon die erzeugende funktion fuer fibonacci herleiten.
Und wenns fuer MIU und Fibonacci geht, dann stimmts sicher fuer alle c-rekursionen (Physikerinduktion).
Ergaenzung: in der Musterloesung bezieht sich der Koeffizientenvergleich auf diese a0, a1, a2. das ist also in meinem vorherigen Post in der linken Seite der Gleichung zu sehen. Und da weiss ich auch nicht welche Koeffizienten man vergleichen soll (vermutlich meint er einfach nur diejenigen der ersten folgenglieder?), aber jedenfalls folgen die koeffizienten ai aus der rekursionsgleichung und das ergibt die erzeugende funktion.
Es gibt ja auch noch die Möglichkeit die erzeugende Funktion zu bestimmen, indem man dieses LGS aus der Musterlösung löst. Kann mir mal bitte jemand zeigen, wie man das macht. Ich komme irgendwie nie auf das korrekte Ergebnis.
Und was genau sagt mir eigentlich diese erzeugende Funktion? Ich kann doch damit die Rekursionsgleichung für µ(n) aufstellen, nachdem ich die Partialbruchzerlegung durchgeführt habe, oder?
Danke!
nachdem mich das heute schonmal jemand per mail gefragt hab, post ich es halt hier auch nochmal:
Gehen tut es um die Beispielsprache aus dem Script, in der Wörter ohne “aa” über dem Alphabet {a,b.c} akzeptiert werden sollen
Also mein Automat hat nur zwei Zustände (siehe Bild im Anhang).
L0 = bL0 + cL0 + aL1 + e
L1 = bL0 + cL0 + e = (b+c)L0 + e
L1 in L0 eingesetzt:
L0 = bL0 + cL0 + a( (b+c)L0 + e) + e = bL0 + cL0 + abL0 + acL0 + a + e
= (b + c + ab + ac)L0 + a + e
jetzt den Arden losgelassen:
(b + c + ab + ac)*(a+e)
die erzeugende Funktion ergibt sich aus folgenden Regeln:
x → z (x ist beliebiges Symbol der Sprache - z.B. a)
x* → 1/ 1-z
e → 1
(b + c + ab + ac) liefert z + z + zz + zz = 2z + 2z²
(…)* liefert 1 / (1- (…)) also
(b + c + ab + ac)* liefert 1 / (1 -(2z + 2z²))
(a+e) liefert z + 1
1 / (1 -(2z + 2z²)) * (z+1) = (z+1) / ( 1 - 2z -2z²)
Das gleiche mit der Transfermatrix:
vom Zustand z0 aus kommt man mit 2 Symbolen in den Zustand z0 (b oder c) oder mit einem Symbol in den Zustand z1
also erste Zeile 2 1
vom Zustand z1 aus kommt man mit 2 Symbolen in den Zustand z0 (b oder c) oder mit keinem Symbol in den Zustand z1
zweite Zeile 2 0
Matrix ist also
2 1
2 0
das char. Polynom bestimmen (ich schreib y für lambda)
(y - 2) 1
2 y
davon die Determinante:
(y-2)y - (21) = y² -2y - 2
Rekursionsgleichung ist also mü_n+2 = 2mü_n+1 + 2mü_n
Anfangswerte: mü_0 = 1 (in der Sprache liegt genau 1 Wort - das leere - mit Länge 0)
Anfangswerte: mü_1 = 3 (in der Sprache liegen 3 Wörter - a oder b oder c - mit Länge 1)
die restlichen mü ergeben sich aus der Rekursionsgleichung
mü_2 = 23 + 21 = 8
also wissen wir schonmal, dass bei der erzeugenden Funktion 1 - (2z + 2z²) unter dem Bruchstrich stehen wird.
Über dem Bruchstrich wird sowas in der Art a0 + a1z stehen.
Außerdem muss gelten Summe(mü_n * z^n) = erzeugende Funktion.
also muss Summe(mü_n * z^n) * (1 - (2z + 2z²)) = a0 + a1z sein
mü_0 haben wir ausgerechnet ist 1. also haben wir als ersten Summanden 1z0
als zweiten mü_1z1 = 3z1
dritter Summand ist mü_2z² = 8*z²
Nun der Koeffizientenvergleich:
wir haben also 1 + 3z + 8z² + … und multiplizieren das mit (1-2z-2z²)
kommt raus: 1(1-2z-2z²) + 3z(1-2z-2z²) + 8z²(1-2z-2z²) + …
= 1 - 2z - 2z² + (3z -6z² -6z³) + (8z² - 16z³ - 16z4) + …
jetzt sieht man, dass sich die Summanden alle aufheben bis auf 1+z
also steht über dem Bruchstrich 1+z
also
(1+z) / ( 1-2z-2z²)
Attachment:
automat.jpg: https://fsi.cs.fau.de/unb-attachments/post_19284/automat.jpg
Mit Hilfe der Partialbrauchzerlegung und der restlichen Rechnerei schafft man es aus der Rekursionsgleichung mit Hilfe der erzeugenden Funktion eine diskrete Formel für mü_n herzubekommen, die nicht mehr rekursiv ist und keine mü_n+1 oder sowas enthält. Das ist der große Witz bei dem ganzen Kram, dass man es schafft sowas rekursives in etwas nicht rekursives umzuwandeln. Und das geht eben mit allen regulären Sprachen.