Induktionsbeweise Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:30 Mo 13.07.2009 | | Autor: | RalU |
| Aufgabe | Für folgende Induktive Definitionen sollen Induktionbeweise geführt werden.
Aufgabe 1:
Die Länge einer Zeichenkette x [mm] \in \summe [/mm] * ist folgendermaßen definiert:
(IA) [mm] |\epsilon|=_{def}0
[/mm]
(IS) für x [mm] \in \summe [/mm] * und a [mm] \in \summe [/mm] gilt |xa|=_{def}=|x|+[1]
Zeigen Sie mit Hilfe dieser Definition durch vollständige Induktion über die Länge von z, dass für beliebige x, z [mm] \in \summe [/mm] * gilt: |xz|=|x|+|z|.
2. Aufgabe:
Die Spiegelung [mm] w^{R} [/mm] eines Wortes w [mm] \in \summe [/mm] * kann induktiv wie folgt definiert werden:
(IA) Für [mm] w=\epsilon [/mm] ist [mm] w^{R}=_{def} \epsilon
[/mm]
(IS) Für w=va mit v [mm] \in \summe [/mm] * und a [mm] \in \summe [/mm] ist [mm] w^{R}=_{def}av^{R}.
[/mm]
Sei w [mm] \in \summe [/mm] * und w = w1w2 mit w1,w2 [mm] \in \summe [/mm] *. Beweisen Sie mit Hilfe obiger Definition, dass [mm] w^{R}=w2^{R}w1^{R}.
[/mm]
Hinweis: Induktion über die Länge von w2.
Hinweis: * hinter [mm] \summe [/mm] enspricht dem "Kleene-Stern-Operator" |
zur 1. Aufgabe)
(IA)
Für [mm] |z|=|\epsilon|=_def [/mm] 0. Hier gilt der (IA) der Definition.
Falls z = 1 Zeichen aus [mm] \summe [/mm] enthält, dann gilt laut (IS) der Definition |xz|=_{def}|x|+1.
(IS) Die Aussage gillt für n, dann auch für n + 1.
Aber wie stellt man das an?
Ist meine Induktionsvoraussetzung (IV) = |xy|=|x|+|z| ?
Dann müßte man ja überlegen, was es heißt, dass die Aussage zunächst mal für n gilt. Heißt dass nun, das die Länge von z genau n Zeichen lang ist? Wie kommt man dannach auf n+1?
zur 2. Aufgabe:
Induktion über |w2|
(IA) n=0
d. h. für [mm] w2=\epsilon [/mm] gilt (IA) der Definition, also [mm] w2=\epsilon [/mm] -> [mm] w^{R}=_{def} \epsilon
[/mm]
Für w2=1 gilt ja schon (IS) der Definition, also
falls w2=va mit |a|=0, |v|=1 gilt:
[mm] w2^{R}=_{def} w2^{R}=a^{R}=w2
[/mm]
Jetzt Betrachtung für |w2|=n.
Aber wie geht man nun weiter vor???
Ich verstehe auch nicht so ganz den Sinn, eine Induktion nur über |w2| durchzuführen. Nach meiner (IV), nämlich [mm] w^{R}=w2^{R}w1^{R} [/mm] müßte ich doch irgendwie auch |w1| betrachten...
Wer kann mir bei diesen Induktionsbeweisen helfen? Bin etwas ratlos.
Mit freundlichen Grüßen,
Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 15.07.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
