Beweisen Sie mit struktureller Induktion, dass die Länge von allen w in L gerade ist

Question

Aufgabe:

L = (a^n) ( b^n)

Induktive Definition angeben und dann dazu mit Strukturelle Induktion beweisen das die Länge von allen w in L gerade ist.

Problem/Ansatz:

L würde ja aus ab,aabb,aaabbb ... usw bestehen.

Was ist denn hier genau das Basiselement für den Induktionsanfang weil wenn ich ab als BasisElement wähle

kann ich im Induktionsschritt nicht aabb bilden. Brauche gerade nur Hilfe beim Induktionsanfang danach würde ich damit weiterarbeiten und die Lösung reinstellen um zu schauen ob ich das so richtig gemacht habe.

Comments

Induktive Definition :

(IA) : ab ist Basiselement von der Menge L

(IS) : Sind a ∈ L, dann auch a*a

DIe Länge aller w in L ist gerade

Strukturulle Induktion:

(IA): Ist G ein Basiselement ab so ist die Länge definiert als 2

(IS): Ist G aus anderen Ausdrücken zusammengesetzt dann ist G=(a*a) aus L.

Laut IV hat a die Länge 2.

Mit G = a * a hat G die Länge a+a.

Nach dem Prinzip gilt E(G) für alle G ∈ L ist gerade.

Soweit richtig?

---

Induktive Definition :

(IA) : ab ist Basiselement von der Menge L

(IS) : Sind a ∈ L, dann auch a*a



DIe Länge aller w in L ist gerade

Strukturelle Induktion:

(IA): Ist G ein Basiselement ab so ist die Länge definiert als 2

(IS): Ist G aus anderen Ausdrücken zusammengesetzt dann ist G=(a*a) aus L.


Laut IV ist die Länge von alle w in L gerade.

Mit G = a * a folgt daraus das auch G gerade ist.





Nach dem Prinzip gilt E(G) für alle G ∈ L ist gerade.



Soweit richtig?

Answer 1

L = (aⁿ) ( bⁿ)

Genauer gesagt

        L = {aⁿbⁿ ∈ {a,b}^* | n ∈ M}.

Dabei ist M die Menge der Zahlen, die du für n einsetzen darfst.

Induktive Definition angeben

Das ist keine unabhängige Teilaufgabe, die man zunächst ignorieren kann. Das ist wesentlich für strukturelle Induktion.

Falls M = ℕ₀ ist, dann ist L die Menge aller Wörter, die mit folgenden Regeln gebildet werden können.

1. Es ist ε ∈ L
2. Ist w ∈ L, dann ist awb ∈ L.

mit Strukturelle Induktion beweisen

IA: Es ist |ε| = 0. Wegen 2 | 0 ist |ε| gerade

IS: Sei w ∈ L mit 2 | |w|. Dann ist

        |awb| = |w|+2.

Wegen

        m|2 ⇒ (m+2)|2    ∀ m∈ℕ₀

gilt deshalb

        |awb| | 2.

Man hätte sich die induktive Definition sparen können und einfach eine vollständige Induktion über n durchführen können. Dann hätte man zwar auch bewiesen, dass die Länge von allen w in L gerade ist, hätte dabei aber nicht die Aufgabe gelöst, da diese ja explizit eine strukturelle Induktion verlangt.

Comments

Vielen Dank!

Was genau meinen Sie mit  Wegen 2 | 0 ist |ε| gerade

"|"was genau soll dadurch ausgedrückt werden?

Wegen 2 | 0 ist die Länge von Epsilon gerade.