Könnte jemand mir bei der Aufgaben helfen? Vielen lieben Dank im Voraus

Aufrufe: 886     Aktiv: 02.11.2019 um 20:46
-4

 Induktionsbeweise 1

a) Im folgenden sehen Sie den Induktionsbeweis fu ̈r die Assoziativit ̈at von ◦. Begru ̈nden Sie die einzelnen Schritte des Beweises und schreiben Sie diese jeweils hinter die entsprechenden Zeilen (z.B. ,,Induktionsvoraussetzung“, ,,Definition ◦, Fall 1“ etc.).

Behauptung/Annahme: ∀u,v,w∈Σ⋆ :(u◦v)◦w=u◦(v◦w).

BeweismittelsInduktionu über u,wähle P(u)=∀v,w∈Σ⋆ :(u◦v)◦w=u◦(v◦w)

Induktionsanfang: P(ε)=∀v,w∈Σ⋆ :(ε◦v)◦w=ε◦(v◦w)

P(ε) ⇔ ∀v,w∈Σ⋆ :(ε◦v)◦w=ε◦(v◦w)

⇔ ∀v,w∈Σ⋆ :v◦w=v◦w

1 ⇔ true.

Induktionsschritt: ∀a ∈ Σ.∀u′ ∈ Σ⋆ : P (u′ ) =⇒ P (a.u′ )

P(a.u′) ⇔ ∀v,w∈Σ⋆ :􏰀a.u′◦v􏰁◦w=a.u′◦(v◦w)
⇔ ∀v,w∈Σ⋆ :a.􏰀u′◦v􏰁◦w=a.(u′◦(v◦w))

⇔ ∀v,w∈Σ⋆ :a.(􏰀u′◦v􏰁◦w)=a.(u′◦(v◦w))

⇔ ∀v,w∈Σ⋆.a.(u′◦(v◦w))=a.(u′◦(v◦w))

⇔ true.

Induktionsschluss: ∀w ∈ Σ⋆.P (w).


b) Beweisen Sie nun |u ◦ v| = |u| + |v|  und begründen Sie jeden Schritt wie in Teilaufgabe a).

 

Induktionsbeweise 2

a) Zeigen Sie |Σn| = |Σ|n. Hinweis: Mit Σn wird die Menge der Worte u ̈ber den AlphabetΣ gebildet, in welcher alle Worte die L ̈ange n haben. Mit |Σn| wird die Gro ̈ße der Menge bestimmt, also die Anzahl der Worte.

b) Bestimmen Sie die Formel (Definition) fu ̈r |Σ≤n| und beweise Sie diese (Zeigen Sie die Richtigkeit fu ̈r alle n ∈ N. Dabei ist 0 ∈ N.).

Diese Frage melden
gefragt

Student, Punkte: -1

 
Hallo,

Ich brauche auf jeden Fall mehr Informationen um dir zu helfen.
1)
Wie ist denn die Definition von \( \circ \)? Was für eine Verknüpfung ist das? Was ist \(\sum^*\)?

2)
a) Hier bin ich mir sicher, das dies ein kombinatorisches Problem ist. Wenn \( \sum \) die Menge aller Buchstaben ist und \( \sum^n \) die Menge aller Wörter aus diesen Buchstaben, dann musst du nur zeigen dass man die Elemente aus \( \sum \) genau \( \vert \sum^n \vert \)-mal miteinander kombinieren kann.

b) Welche Formel?

Grüße Christian   ─   christian_strack 30.10.2019 um 15:05
Das sieht nach theoretischer Informatik aus. Da ist der Kingel die Konkatenierung. "christian" \( \circ \) " " \( \circ \) "strack" = "christian strack"   ─   stehgold 30.10.2019 um 16:10
\( \Sigma^* \) heißt Worte der Länge 0 bis n. \( \Sigma \) ist das Alphabet, die zulässigen Zeichen. Der "Kleene-Stern" sagt, dass auch ein leeres Zeichen erlaubt ist.   ─   stehgold 30.10.2019 um 16:16
∘ bedeutet konkatenation also A∘B= A*B
∑* ist für alle Buchstaben
   ─   sab 31.10.2019 um 13:15
Kommentar schreiben
1 Antwort
0

Hallo,

vielen Dank an stehgold, für die fehlenden Informationen. Wenn ich das richtig verstanden habe, gilt sogar

$$ christian \circ strack = christianstrack $$

Also diese Konkatenierung erzeugt ein neues Wort oder?

Bei der a) bin ich mir immer noch etwas unsicher. Geht es darum die Rechtecke auszufüllen? Ich habe das Gefühl, da fehlen überall nur die Klammern. 
Vielleicht habt ihr noch in einem Satz oder einer Definiton besprochen, das man \( a.u \) auseinander ziehen darf. 

Das solltest du selbst nochmal mit deinem Skript vergleichen.

zur b) Hier geht es darum zu zeigen, das wenn wir zwei Wörter zusammfügen, es genauso lang ist, wie die Summe der einzelnen Längen.

Dies würde ich wieder mit Induktion beweisen.

Dann wäre dein Induktionsanfang

$$ \vert \varepsilon \circ v \vert = \vert \varepsilon \vert + \vert v \vert \\ \vert v \vert = 0 + \vert v \vert $$

Schaffst du weiter vorzugehen?

2a) Hier musst du wie ich es im Komentar beschrieben habe vorgehen. Wir berechnet man kombinatorisch wie oft man \(n \) Buchstaben zu einem Wort der Länge \( n \) zusammenlegen kann (doppelte Buchstaben sind erlaubt).

b) Hier hast du auch ein kombinatrisches Problem. Es ist ziemlich analog zu b), mit dem Unterschied, das hier die Wörter maximal die Länge \( n \) haben dürfen. Allerdings dürfen sie auch kürzer sein. Das liefert uns noch mehr Wörter als in a).

Versuch dich mal. Wenn du nicht weiter kommst, melde dich gerne wieder.

Grüße Christian

Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 29.81K

 
sie haben richtig verstanden, aber ich habe leider dafür wenig zeit zu schaffen.
danke sehr
  ─   sab 31.10.2019 um 13:18
Gerne. Das tut mir Leid. Vielleicht hilft es trotzdem etwas beim Verständnis :)

Grüße Christian   ─   christian_strack 31.10.2019 um 13:30
Vielen Dank, Ich habe es geschafft. :)   ─   sab 02.11.2019 um 20:46

Kommentar schreiben