www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Komplexität & Berechenbarkeit" - Standardnummerierung
Standardnummerierung < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Standardnummerierung: Tipp
Status: (Frage) beantwortet Status 
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.

        
Bezug
Standardnummerierung: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Standardnummerierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]