formale Sprache, Beweis < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:37 Do 23.04.2009 | | Autor: | diecky |
| Aufgabe | Es sei ein v, w [mm] \in [/mm] Sigma* gegeben mit:
1) vw = [mm] w^{R}v [/mm] (R bezeichnet das Wort ruckwärts geschrieben)
2) |w| [mm] \ge [/mm] |v|
Beweisen oder zeigen sie einen Widerspruch, dass daraus [mm] (vw)^{R} [/mm] = vw folgt. |
Noch eine kurze Anmerkung: v und w seien Wörter, Sigma soll irgendein Alphabet mit beliebiger Länge (kann auch [mm] \varepsilon [/mm] := Länge ist 0 sein).
Leider habe ich absolut keine Ahnung wie ich am besten an die Aufgabe rangehe. Geht das vielleicht bei der a) über strukturelle Induktion? Und wenn ja, kann mir jemand einen Tipp oder Ansatz geben?
Wär wirklich super klasse!
Und wenn ich sag ich mal zu b) einfach ein Widerspruch zeige, indem ich zwei Wörter finde (reines Zahlenbsp.), die die gegebene Bedingung zwar erfüllen, aber nicht das was bewiesen werden soll: hab ich dann automatisch die Aufgabe schon gelöst? Zum Beispiel wäre für die Aufgabe b) ja für v= 1111 und w = 1011 die Bedingung ja erfüllt (Wortlänge beide Male 4), aber es stimmt die zu zeigende Bedingung nicht, da [mm] (vw)^{R} [/mm] = vw => 11011111 [mm] \not= [/mm] 11111011 ?!
Vielen Dank schonmal
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:11 Do 23.04.2009 | | Autor: | felixf |
Hallo!
> Es sei ein v, w [mm]\in[/mm] Sigma* gegeben mit:
> 1) vw = [mm]w^{R}v[/mm] (R bezeichnet das Wort ruckwärts
> geschrieben)
> 2) |w| [mm]\ge[/mm] |v|
Betrag ist die Laenge des Wortes, oder?
> Beweisen oder zeigen sie einen Widerspruch, dass daraus
> [mm](vw)^{R}[/mm] = vw folgt.
>
> Noch eine kurze Anmerkung: v und w seien Wörter, Sigma
> soll irgendein Alphabet mit beliebiger Länge (kann auch
> [mm]\varepsilon[/mm] := Länge ist 0 sein).
Aus $v w = [mm] w^R [/mm] v$ und $|w| [mm] \ge [/mm] |v|$ folgt ja schonmal, dass $w$ von der Form $t v$ sein muss mit $t$ einem anderen Wort.
Dann folgt aus $v w = [mm] w^R [/mm] v$, dass $v t v = [mm] v^R t^R [/mm] v$ ist, also dass [mm] $v^R [/mm] = v$ und [mm] $t^R [/mm] = t$ ist.
Damit solltest du weiterkommen...
LG Felix
|
|
|
|
