Strukturelle Induktion

Question

Aufgabe:

 Die Menge M ⊆ {a, b, c} von Zeichenreihen über dem Alphabet {a, b, c} ist induktiv definiert

als die kleinste Menge, für die gilt:
• ab ∈ M und ba ∈ M.
• Falls w1, w2 ∈ M, dann ist auch w1 w2 ∈ M.
• Falls w ∈ M, dann ist auch ac w ∈ M.

Zeigen Sie mit struktureller Induktion, dass kein Wort aus M drei aufeinanderfolgende a’s
enthält.

Hinweis: Erweitern Sie die Behauptung zunächst um geeignete zusätzliche Aussagen über
den Wortanfang bzw. das Wortende (Verschärfung der Induktionsbehauptung).

Kann mir jemand bei dieser Aufgabe helfen?

Comments

Die Menge M ⊆ {a, b, c} von Zeichenreihen über dem Alphabet {a, b, c} ist induktiv definiert.

Hier stimmt etwas nicht. M kann keine Elemente enthalten ausser den 3 angegebenen Elemente. D.h. insbesondere keine Wörter der Länge 3.

Answer 1

Die Menge M ⊆ {a, b, c} von Zeichenreihen über dem Alphabet {a, b, c}

Das muss wohl lauten

        "Die Menge M ⊆ {a, b, c}* von Zeichenreihen über dem Alphabet {a, b, c}".

Induktionsanfang. Die Wörter ab und ba enthalten keine drei aufeinanderfolgende a’s.

Induktionsvoraussetzung. Sei w ∈ M mit w≠ab und w≠ba und kein Wort w' ∈ M mit |w'| < |w| enthält drei aufeinanderfolgende a’s.

Induktionsschluss:

Fall 1: Es gibt w₁, w₂ ∈ M mit w = w₁w₂. Dann enthalten w₁ und w₂ keine drei aufeinanderfolgende a’s. Also enthält auch w₁w₂ keine drei aufeinanderfolgende a’s.

Fall 2: Es gibt w' ∈ M mit w = acw'. Dann enthält w' keine drei aufeinanderfolgende a’s. Also enthält auch acw' offensichtlich keine drei aufeinanderfolgende a’s.

Erweitern Sie die Behauptung zunächst um geeignete zusätzliche Aussagen über
den Wortanfang bzw. das Wortende

Die Schlussfolgerung "Also enthält auch w₁w₂ keine drei aufeinanderfolgende a’s." aus Fall 1 wäre nicht korrekt, wenn w₁ auf aa endet und w₂ mit a beginnt oder umgekehrt. Begründe, dass kein Wort aus M mit auf aa endet oder mit aa beginnt.