Antworte auf:  Anzahl Wörter ohne Teilwort 01 bestimmen von pram
Forum:  Formale Sprachen & Automaten, moderiert von: Bilbo

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
pram
Junior
Dabei seit: 21.09.2019
Mitteilungen: 16
Herkunft:
 Beitrag No.8, eingetragen 2019-09-23 11:01    [Diesen Beitrag zitieren]

Hallo zusammen,

vielen lieben Dank Euch für eure Beiträge! Sie alle haben mir enorm weitergeholfen!!


PrinzessinEinhorn
Senior
Dabei seit: 23.01.2017
Mitteilungen: 2453
Herkunft:
 Beitrag No.7, eingetragen 2019-09-23 09:39    [Diesen Beitrag zitieren]


Zu 1: Natürlich musst du jede Lücke füllen! Wenn es für dich selbst nicht "trivial" ist, musst du es beweisen. (Das kann sehr sehr anstrengend sein!)

Zu 2: Das habe ich nicht ganz verstanden

Ja, ich neige dann eben dazu auch die Dinge zu zeigen, die trivial sind.
Etwa so ganz einfache Mengenbeziehungen.
Und da denke ich mir dann, dass wenn ich sowas leichtes nicht immer wieder Haarfein beweisen würde, es sich mir doch eher als 'gegebene Wahrheit' einprägen würde und mir so dann viel eher automatisch in den Sinn kommt. Wenn du verstehst wie ich das meine.

Ist aber auch nicht so wichtig. :D


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 5873
Herkunft: Milchstraße
 Beitrag No.6, eingetragen 2019-09-22 23:02    [Diesen Beitrag zitieren]

2019-09-22 22:45 - PrinzessinEinhorn in Beitrag No. 5 schreibt:
1. Ich glaube ich übertreibe es manchmal auch, wenn ich Beweise durcharbeite und dann der Meinung bin sämtliche Lücken füllen zu müssen.

2. An anderer Stelle habe ich dann oftmals das Gefühl, dass diese Vorgehensweise der mathematischen Intuition nicht dienlich ist.

Zu 1: Natürlich musst du jede Lücke füllen! Wenn es für dich selbst nicht "trivial" ist, musst du es beweisen. (Das kann sehr sehr anstrengend sein!)

Zu 2: Das habe ich nicht ganz verstanden 😮



PrinzessinEinhorn
Senior
Dabei seit: 23.01.2017
Mitteilungen: 2453
Herkunft:
 Beitrag No.5, eingetragen 2019-09-22 22:45    [Diesen Beitrag zitieren]

Da stimme ich dir zu.
Ich glaube ich übertreibe es manchmal auch, wenn ich Beweise durcharbeite und dann der Meinung bin sämtliche Lücken füllen zu müssen.

An anderer Stelle habe ich dann oftmals das Gefühl, dass diese Vorgehensweise der mathematischen Intuition nicht dienlich ist.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 5873
Herkunft: Milchstraße
 Beitrag No.4, eingetragen 2019-09-22 22:35    [Diesen Beitrag zitieren]

Hallo PrinzessinEinhorn,

hier hätte ich allerdings keine Bauchschmerzen. Klar ist: Wenn man behauptet, dass eine Aussage trivial ist, sollte man ohne lange zu überlegen in der Lage sein, die Aussage formal zu beweisen. Allerdings muss man nicht jede triviale Aussage formal beweisen.

Wo die Grenze ist, ist natürlich Auslegungssache. (In meiner Zeit als Korrektor in den Anfängervorlesungen habe ich schon mal Punktabzug gegeben, wenn ein Student 30 Seiten - kein Witz! - abgegeben und jedes My bewiesen hat, obwohl das aufgrund der Vorlesung alles klar war.)


PrinzessinEinhorn
Senior
Dabei seit: 23.01.2017
Mitteilungen: 2453
Herkunft:
 Beitrag No.3, eingetragen 2019-09-22 22:10    [Diesen Beitrag zitieren]

Wie sich die Worte der Menge kombinatorisch konstruieren lassen, ist ja klar. Auf einer 0 kann nur eine 0 folgen etc.

Einfach auflisten würde ich sie jedoch nicht, da hätte ich dann schon ein paar Bauchschmerzen, aber das muss ja nichts heißen.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 5873
Herkunft: Milchstraße
 Beitrag No.2, eingetragen 2019-09-22 22:01    [Diesen Beitrag zitieren]

Hm, macht ihr euch das Leben hier nicht unnötig schwer? Die Wörter ohne 01 haben doch alle die Form
000...000
100...000
110...000
...
111...110
111...111

Also eine Folge von Einsen gefolgt von einer Folge von Nullen. Wenn die Wortlänge n betragen soll, gibt es davon genau n+1 Stück.


PrinzessinEinhorn
Senior
Dabei seit: 23.01.2017
Mitteilungen: 2453
Herkunft:
 Beitrag No.1, eingetragen 2019-09-22 21:45    [Diesen Beitrag zitieren]

Hallo,

ja, dass Resultat ist korrekt.
Allgemein gilt also $|M_n|=n+1$. Das ist vielleicht 'besser' als deine rekursive Formel, wenn du einen geschlossenen Ausdruck angibst.

Ich finde deinen Beweis in Ordnung.
Man könnte ihn vielleicht besser aufschreiben.

Du leitest hier ja eine Art Induktion ein, ohne dann eine formelle Induktion (Induktionsanfang, Induktionsvoraussetzung, Induktionsschritt) durchzuführen.

Der Beweis ist dann ja im Grunde wie deiner, nur ein wenig geordneter und vielleicht auch prägnanter.

Etwa:

Falls b = 1, dann muss a = 1 gelten, und das ganze Wort x muss aus 1ern bestehen.

Hier ist natürlich klar, was du meinst. Die Begründung fällt aber ein wenig vom Himmel, auch wenn wohl jeder deinem Gedankengang folgen kann, warum das entsprechende Wort eben nur aus 1'en bestehen kann.

Auch gibst du zum Beispiel zwei Beispiele $|M_0|=1$ und $|M_1|=2$. Was natürlich alles richtig ist. Für die Induktion bräuchtest du natürlich nur eines. Auch wenn man natürlich auch eine Vermutung für die Anzahl entwickeln muss, also ist es immer gut mehr Beispiele zu betrachten. Aber ist das was du in dem Absatz schreibst wirklich für den Beweis entscheidend?

Dann nimmst du $w\in M_{n+1}$ mit $w=xab$ wobei $x\in M_{n-1}$.
Wieso schreibst du nicht $w=xa$ mit $x\in M_n$ und $a\in \{0,1\}$.
Das ist meiner Meinung nach deutlicher und ja auch genau das, was du im Induktionsschritt tun würdest.

Dort würdest du ja deine Menge $M_{n+1}$ als disjunkte Vereinigung von zwei Mengen schreiben. Nämlich jene die die Worte der Form $x0$ und $x1$ enthalten.

Mit deinen gemachten Überlegungen beendest du dann auch diesen Schritt leicht.

Kurzum:

Dein Beweis geht so wohl in Ordnung, aber das strukturierte Beweisverfahren der vollständigen Induktion könnte dir helfen deine Ideen prägnanter zu formulieren und auf das wesentliche zu reduzieren, was letztendlich einen Beweis ergibt, der sich schöner lesen würde.

:)


pram
Junior
Dabei seit: 21.09.2019
Mitteilungen: 16
Herkunft:
 Themenstart: 2019-09-22 21:16    [Diesen Beitrag zitieren]

Hallo zusammen,

ich bitte euch um Hilfe in folgender Frage. Ich muss Anzahl der Wörter der Länge \(n \in \mathbb N \) über \(\sum = \{0, 1 \}\) bestimmen, die nicht das Teilwort 01 enthalten.

Ich gehe folgendermaßen vor. Sei \(M_n\) die Menge der Wörter aus \(\sum^n\), die nicht das Teilwort 01 enthalten.

Es gilt \(|M_0|\) = 1 => nur das leere Wort enthalten; \(|M_1|\) = 2 => 0 und 1 enthalten.

Nun betrachten wir ein Wort \(w \in M_{n+1} \)\(\), dann können wir \(w\) schreiben als \(w = xab\) mit \(a, b \in \{0,1\} \) und \(x \in M_{n-1} \).

Falls \(b\) = 0, dann ist für \(xa\) ein beliebiges Wort aus \(M_n\) möglich.
Falls \(b\) = 1, dann muss \(a\) = 1 gelten, und das ganze Wort \(x\) muss aus 1ern bestehen.

Somit |\(M_{n+1}\)| = |\(M_{n}\)| + 1.

Ist das korrekt? Danke euch für jede Hilfe!


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]