0 Daumen
914 Aufrufe

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?

Avatar von

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.

1 Antwort

+1 Daumen
 
Beste Antwort
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 w1, w2 ∈ M mit w = w1w2. Dann enthalten w1 und w2 keine drei aufeinanderfolgende a’s. Also enthält auch w1w2 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 w1w2 keine drei aufeinanderfolgende a’s." aus Fall 1 wäre nicht korrekt, wenn w1 auf aa endet und w2 mit a beginnt oder umgekehrt. Begründe, dass kein Wort aus M mit auf aa endet oder mit aa beginnt.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community