Strukturelle Induktion < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:51 Do 29.01.2009 | | Autor: | farnold |
| Aufgabe | Vollständige Induktion
Gegeben sei folgende Sprache:
IMI ist ein Wort der Sprache
Wenn xMx ein Wort der Sprache ist für eine beliebige nichtleere Zeichenkette x, dann ist auch
xxMxx ein Wort der Sprache.
Beweisen Sie durch vollständige Induktion, dass MM kein Wort der Sprache ist |
Hallo,
wie soll ich sowas per struktureller Induktion zeigen, ich mein ich seh auf den ersten Blick dass das Wort nicht in der Sprache enthalten sein kann.
Da IMI Sprache => IIMII Sprache (nach Erzeugungsregel)
IIMII Sprache => IIIIMIIII Sprache (nach Erzeugungsregel)
=> MM kann mit den gegebenen Erzeungsregeln nicht erzeugt werden
Aber wie zeig ich das per Induktion?
Wo soll ich da für die Induktion ansetzen?
Ich könnte nichtmal sagen was hier die Induktionsannahme ist :(
Was wäre wenn gefragt sei, ob zb. IIIIIIIIMIIIII Sprache ist, wie gehe ich dann vor?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo farnold,
Du könntest z.B. zeigen, dass jedes Wort der Sprache aus einer Zeichenkette der Länge [mm] 2^{k}+1, k\in\IN, [/mm] besteht.
Oder Du könntest zeigen, dass jedes Wort der Sprache aus einer Zeichenkette der Länge 2k+1, [mm] k\in\IN, [/mm] besteht - und dass an (k+1)-ter Stelle ein M steht, an allen anderen ein I.
Du könntest auch ohne Induktion zeigen, dass alle Wörter jedes Zeichen in gerader Anzahl erhalten, mit Ausnahme des M, das in ungerader Anzahl vorkommt.
"Sehen" reicht jedenfalls nicht, auch wenn in diesem Fall wohl jeder "sieht", warum MM nicht aus dem einzigen vorgegebenen "Grundwort" hervorgegangen sein kann.
lg,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:35 Do 29.01.2009 | | Autor: | farnold |
> Du könntest auch ohne Induktion zeigen, dass alle Wörter > jedes Zeichen in gerader Anzahl erhalten, mit Ausnahme
> des M, das in ungerader Anzahl vorkommt.
Das wäre dann die strukturelle Induktion?
I.Annahme: Alle Wörter außer M kommen in gerader Anzahl vor
I.Anfang: IMI Sprache xMx Sprache => I.Annahme stimmt
I.Schritt: n->n+1
hmm ehrlich gesagt hab ich keine Ahnung wie ich das beweise soll. Induktion und Buchstaben(Sprache) passt für mich irgendwie nicht zusammen :(
|
|
|
| |
|
Hallo farnold,
nein, das wäre gerade nicht die strukturelle Induktion. Die beiden anderen Vorschläge wären per Induktion zu zeigen.
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:46 Fr 30.01.2009 | | Autor: | bazzzty |
> Du könntest z.B. zeigen, dass jedes Wort der Sprache aus
> einer Zeichenkette der Länge [mm]2^{k}+1, k\in\IN,[/mm] besteht.
> Oder Du könntest zeigen, dass jedes Wort der Sprache aus
> einer Zeichenkette der Länge 2k+1, [mm]k\in\IN,[/mm] besteht - und
> dass an (k+1)-ter Stelle ein M steht, an allen anderen ein
> I.
Man kann in diesem Fall die Aussage direkt per struktureller Induktion zeigen: "Jedes Wort der Sprache ist nicht MM".
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:31 Fr 30.01.2009 | | Autor: | reverend |
Hallo bazzzty,
das freut mich. Wie macht man das formal richtig?
Ernstgemeinte Frage!
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:32 Sa 31.01.2009 | | Autor: | bazzzty |
> Hallo bazzzty,
>
> das freut mich. Wie macht man das formal richtig?
>
> Ernstgemeinte Frage!
Gegeben sei folgende Sprache:
IMI ist ein Wort der Sprache
Wenn xMx ein Wort der Sprache ist für eine beliebige nichtleere Zeichenkette x, dann ist auch
xxMxx ein Wort der Sprache.
Beweisen Sie durch vollständige Induktion, dass MM kein Wort der Sprache ist.
Der Unsinn bei dieser Aufgabe ist, dass zwar eine Induktion verlangt wird, dass man aber dazu verdammt ist, eine Induktionshypothese aufzustellen, die man nicht braucht. Egal, ob man über die Wortlänge, die Anzahl der Ableitungen, oder was auch immer beweist. Insofern kann man die Hypothese auch guten Gewissens überspringen.
IA: IMI ist nicht MM.
IS: Jedes Wort xxMxx ist für jedes [mm]x\in\Sigma*[/mm] nicht MM.
(Eine sinnvolle Aufgabe wäre das ganze erst dann, wenn man hier hätte einfließen lassen müssen, dass xMx nicht MM war).
Beweise über die Wortlänge geben keinen Sinn, hier geht nur strukturelle Induktion.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:49 Sa 31.01.2009 | | Autor: | reverend |
Hallo bazzzty,
danke für die Erläuterung!
Eine Bemerkung noch zum Ende:
> Beweise über die Wortlänge geben keinen Sinn, hier geht nur
> strukturelle Induktion.
Das allerdings stimmt nicht. Die Wortlänge kann nie 2 sein, das lässt sich umständlich oder auch leicht zeigen. Auch der andere Weg (die Anzahl der M's in einem Wort ist ungerade) funktioniert.
Liebe Grüße,
reverend
|
|
|
|
