Induktion verbunden mit Informatik

Neue Frage »

HELP Auf diesen Beitrag antworten »
Induktion verbunden mit Informatik
Hi leute ist zwar jetzt nicht direkt Mathe aber ich weis nicht wo ich mich da hinwenden soll. Es ge´ht um folgendes
Es geht um die Sprache WAS mit:
1: WA ist ein gültiges Wort der Sprache
2: Wenn xA ein gültiges Wort dann auch xAS
3: Wenn Wx ein gültiges Wort dann auch Wxx

Beweisen sie durch vollständige Induktion dass das Wort WS nicht Teil der Sprache WAS ist.
BITTE KANN MIR JMD HELFEN traurig
carsten Auf diesen Beitrag antworten »

Ueberleg dir doch erst einmal alle gueltigen Worte der Sprache und schreib sie auf. Es ist genau vorgegeben, wie man ein gueltiges Wort "erweitern" kann, durch die Regeln (2) und (3). Und es gibt ein "kleinstes" gueltiges Wort.

Wenn man sich die gueltigen Worte aufschreibt und sieht, was die beiden Regeln (2) und (3) bedeuten, sollte man eine Idee fuer die vollstaendige Induktion bekommen.

Gruesse
Carsten
HELP Auf diesen Beitrag antworten »

Hi carsten

Ich schieb grad voll die panik. Ich muss diese Aufgabe bis morgen gemacht haben und versteh grad absolut nix. Mein Problem ist das ich nicht weis wie man so etwas überhaupt induziert.
Bitte helf mir dabei unglücklich
carsten Auf diesen Beitrag antworten »

Dein einziges gegebenes Wort ist WA, das ist dein Ausgangspunkt.

Jetzt kann man mit Regel (2) oder Regel (3) etwas zum Wort hinzufuegen.

Mit Regel (2) koennte man aus WA (ist ja ein gueltiges Wort) WAS machen.
Mit Regel (3) koennte man aus WA -> WAA erzeugen.

jetzt koennte man da immer wieder mit Regel (2) und Regel (3) drauflosgehen ...

man koennte z.B. WASAS, WAAAA, WAAAAS, usw. erzeugen.
Hinweis: man kann nicht mehr bei jedem gueltigen Wort beliebig Regel (2) anwenden, Regel (3) dagegen geht immer, da das "W" am Anfang stehenbleibt.
Genau sieht es so aus, dass man Regel(2) einmal (oder keinmal) anwenden kann. Nachdem man (2) einmal angewendet hat, ist immer ein S am Ende des Wortes, und damit kann man nicht mehr (2) anwenden, sondern nur noch (3).

was eigentlich klar zusehen ist, ist das die Woerter immer laenger werden. Man hat ja schliesslich keine regel zum kuerzen.

Ich hoffe mal ich habe die Regeln richtig aufgefasst, denn vollstaendige Induktion ist an dieser Stelle ziemlich sinnlos. Das einzige Wort aus 2 Buchstaben ist WA und dieses ist nunmal nicht WS.

Wozu man eventuell die Induktion nehmen koennte, waere um nachzuweisen, dass die Worte immer laenger werden, um damit WA als einziges Wort aus 2 Buchstaben zu bestaetigen. Waere fuer mich aber offensichtlich ....

hm Induktionsbehauptung waere sowas:
Durch jedes Anwenden einer Regel werden die gueltigen Worte laenger.

n sei die Anzahl der Regelanwendungen auf WA (man hat ja nur den einen Ausgangspunkt)

Induktionsanfang

n=1
bei Regel 2 folgt , neues Wort WAS hat 3 Buchstaben
Regel 3 folgt, neues Wort hat 3 Buchstaben

Annahme Behauptung gilt fuer n
wenden n+1 tes mal eine regel auf ein Wort mit n maliger Regelanwendung an. Sei k die Anzahl der Buchstaben dieses Wortes
Wenn Regel (2) angewandt werden darf, dann hat das neue Wort k+1 Buchstaben
Wenn regel (3) angewandt wird, dann hat das neue Wort (k-1)*2+1 Buchstaben. da k immer groesser gleich 2 ist, ist (k-1)*2+1=2*k-1 immer groesser als k.


sieht irgendwie bloed aus, aber es wurde vollstaendige Induktion benutzt Augenzwinkern

Gruesse Carsten

EDIT:
habe noch ein +1 bei (k-1)*2 eingefuegt, das 2*k-1 stimmt natuerlich ... ich hab wohl vorhin getraeumt ich habs getippt Schläfer
HELP Auf diesen Beitrag antworten »

Ich dank dir vielmals Carsten für deine Hilfe

Gruss Jessi
HELP Auf diesen Beitrag antworten »

Carsten das ist jetzt zwar lästig aber ich kipp gleich vom hocker. kannst du mir vielleicht noch sagen wie man sowas induziert? Man sieht natürlich eindeutig das es nur dieses wort geben kann, dass ist mir jetzt auch klar geworden aber in der Aufgabe steht halt das mit induktion.

LG Jessi
 
 
HELP Auf diesen Beitrag antworten »

Vielen Vielen Vielen Dank Carsten. Hab echt grössten Respekt vor dir.
Vielen dank und ganz LG Jessi
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »