Standardnummerierung < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:01 So 15.11.2009 | | Autor: | stefan00 |
| Aufgabe | Es sei [mm] $\Sigma$={a,b} [/mm] ein Alphabet, und [mm] $a:\{1,2\} \to \Sigma$ [/mm] sei diejenige Ordnungsfunktion, die $a(1)=$a und $a(2)=$b erfüllt. Ferner sei [mm] $\nu_\Sigma:\IN \to \Sigma^\*$ [/mm] die zugehörige Standardnummerierung.
Es sei die Funktion [mm] $f:\Sigma^\* \to \Sigma^\*$ [/mm] definiert durch $f(w):=w$aba für alle $w [mm] \in \Sigma^\*$. [/mm] Zeigen Sie: [mm] $\nu_\Sigma^{-1}f\nu_\Sigma(n)=8 \cdot [/mm] n+9$, für alle [mm] $n\in\IN$. [/mm] |
Hallo,
wenn ich nun bei obiger Aufgabe aba einmal lexikographisch aufzähle, dann habe ich ja: [mm] $\epsilon$; [/mm] a,b; aa,ab,ba,bb; aaa,aab,aba,...;...
D.h. die 9 in obiger Formel ($8n+9$) würde sich daraus erklären, dass aba an 9. Stelle der obigen Aufzählung steht, richtig? Jede Kombination aus $w$ mit $w$aba würde also diese Standardnummerierung ergeben, aber wie gehe ich nun weiter vor? Ich habe ja noch die Formel der Ordnungsfunktion [mm] $\sigma$: $\sigma(\epsilon):=0$,
[/mm]
[mm] $\sigma(a_{i_k}a_{i_{k-1}}...a_{i_1}a_{i_0}):=i_kn^k+i_{k-1}n^{k-1}+...+i_1n+i_0$, [/mm] aber wie muss ich das nun einsetzen?
Vielen Dank für die Hilfe.
Gruß, Stefan.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:39 Mo 16.11.2009 | | Autor: | felixf |
Hallo Stefan!
> Es sei [mm]\Sigma[/mm]={a,b} ein Alphabet, und [mm]a:\{1,2\} \to \Sigma[/mm]
> sei diejenige Ordnungsfunktion, die [mm]a(1)=[/mm]a und [mm]a(2)=[/mm]b
> erfüllt. Ferner sei [mm]\nu_\Sigma:\IN \to \Sigma^\*[/mm] die
> zugehörige Standardnummerierung.
> Es sei die Funktion [mm]f:\Sigma^\* \to \Sigma^\*[/mm] definiert
> durch [mm]f(w):=w[/mm]aba für alle [mm]w \in \Sigma^\*[/mm]. Zeigen Sie:
> [mm]\nu_\Sigma^{-1}f\nu_\Sigma(n)=8 \cdot n+9[/mm], für alle
> [mm]n\in\IN[/mm].
>
> Hallo,
> wenn ich nun bei obiger Aufgabe aba einmal lexikographisch
> aufzähle, dann habe ich ja: [mm]\epsilon[/mm]; a,b; aa,ab,ba,bb;
> aaa,aab,aba,...;...
> D.h. die 9 in obiger Formel ([mm]8n+9[/mm]) würde sich daraus
> erklären, dass aba an 9. Stelle der obigen Aufzählung
> steht, richtig? Jede Kombination aus [mm]w[/mm] mit [mm]w[/mm]aba würde also
> diese Standardnummerierung ergeben, aber wie gehe ich nun
> weiter vor? Ich habe ja noch die Formel der
> Ordnungsfunktion [mm]\sigma[/mm]: [mm]\sigma(\epsilon):=0[/mm],
>
> [mm]\sigma(a_{i_k}a_{i_{k-1}}...a_{i_1}a_{i_0}):=i_kn^k+i_{k-1}n^{k-1}+...+i_1n+i_0[/mm],
> aber wie muss ich das nun einsetzen?
Nun, dein Wort sei $w = [mm] a_{i_k} \cdots a_{i_0}$, [/mm] es gilt also [mm] $\nu_\Sigma(n) [/mm] = w$, also [mm] $\nu_\Sigma^{-1}(w) [/mm] = [mm] i_kn^k+i_{k-1}n^{k-1}+...+i_1n+i_0 [/mm] = n$. Wenn du jetzt $a b a$ anhaengst steht da [mm] $a_{i_k} \cdots a_{i_0} a_1 a_2 a_1$, [/mm] und es gilt [mm] $\nu_\Sigma^{-1}(a_{i_k} \cdots a_{i_0} a_1 a_2 a_1) [/mm] = [mm] i_k n^{k+3} [/mm] + [mm] i_{k-1} n^{k+2} [/mm] + [mm] \dots [/mm] + [mm] i_1 n^4 [/mm] + [mm] i_0 n^3 [/mm] + 1 [mm] \cdot n^2 [/mm] + 2 [mm] \cdot n^1 [/mm] + 1 [mm] \cdot n^0$. [/mm] Hier ist $n = 2$. Rechne nach, dass dies gleich $8 n + 9$ ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:04 Di 17.11.2009 | | Autor: | stefan00 |
Hallo Felix,
> Wenn du jetzt [mm]a b a[/mm] anhaengst steht da [mm]a_{i_k} \cdots a_{i_0} a_1 a_2 a_1[/mm],
> und es gilt [mm]\nu_\Sigma^{-1}(a_{i_k} \cdots a_{i_0} a_1 a_2 a_1) = i_k n^{k+3} + i_{k-1} n^{k+2} + \dots + i_1 n^4 + i_0 n^3 + 1 \cdot n^2 + 2 \cdot n^1 + 1 \cdot n^0[/mm].
> Hier ist [mm]n = 2[/mm]. Rechne nach, dass dies gleich [mm]8 n + 9[/mm] ist.
ja, das ist erschreckend einleuchtend, vielen Dank für die Hilfe. Jetzt hab ichs begriffen.
Schöne Grüße, Stefan.
|
|
|
|
