Komplizierte Funktion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:33 Fr 06.06.2008 | | Autor: | Leader |
| Aufgabe | Sei A = {0,1} und <.> : A* [mm] \to \IN [/mm] mit [mm] <\varepsilon> [/mm] = 0 und <aw> = [mm] 2^a 3^{} [/mm] für a [mm] \in [/mm] A und w [mm] \in [/mm] A*.
Sei nun f(x) = [mm] \begin{cases} 1, & falls \exists n \ge 1: k = <0^n 1^n 0^n> \\ 0, & sonst \end{cases} [/mm]
Schreiben Sie für die Funktion f ein WHILE-Programm. |
Hallo,
ich versteh die obige Funktion nicht (insbesondere verstehe ich nicht, was <.> berechnen soll). Kann mir das mal jemand erklären? Ich wüsste sonst nicht, wie ich das While-Programm schreiben soll.
Was würde zum Beispiel <001100> liefern? So wie ich das bisher sehe wohl [mm] 3^{<00>} 3^{<11>} 3^{<00>}, [/mm] bloß das wäre ja dann wohl ein unendlicher rekursiver Aufruf von [mm] 3^{} [/mm] oder?
Vielen Dank für eure Hilfe!
LG, Leader.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:34 Fr 06.06.2008 | | Autor: | rainerS |
Hallo!
> Sei A = {0,1} und <.> : A* [mm]\to \IN[/mm] mit [mm]<\varepsilon>[/mm] = 0
> und <aw> = [mm]2^a 3^{}[/mm] für a [mm]\in[/mm] A und w [mm]\in[/mm] A*.
>
>
> Sei nun f(x) = [mm]\begin{cases} 1, & falls \exists n \ge 1: k = <0^n 1^n 0^n> \\ 0, & sonst \end{cases}[/mm]
>
>
> Schreiben Sie für die Funktion f ein WHILE-Programm.
Ist hier x und k identisch?
> ich versteh die obige Funktion nicht (insbesondere verstehe
> ich nicht, was <.> berechnen soll). Kann mir das mal jemand
> erklären? Ich wüsste sonst nicht, wie ich das
> While-Programm schreiben soll.
Die Vorschrift ist doch eindeutig: wenn zwischen den spitzen Klammern gar nichts steht, dann ist der Wert 0. Ansonsten ist es eine rekursive Definition: du nimmst das erste Zeichen a heraus, berechnest den Wert der Klammer ohne das erste Zeichen ($<w>$) und berechnest dann [mm] $2^a 3^{}$.
[/mm]
> Was würde zum Beispiel <001100> liefern? So wie ich das
> bisher sehe wohl [mm]3^{<00>} 3^{<11>} 3^{<00>},[/mm] bloß das wäre
> ja dann wohl ein unendlicher rekursiver Aufruf von [mm]3^{}[/mm]
> oder?
Das ist nicht richtig, aber unendlich wäre die Rekursion auch dann nicht. Nach der Definition ist
[mm] <001100> = 2^0 * 3^{<01100>} [/mm]
Das kannst du in 6 Schritten selbst ausrechnen.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:36 Fr 06.06.2008 | | Autor: | Leader |
Vielen Dank, jetzt weiß ich Bescheid.
LG,
Leader.
|
|
|
|
