Aufgabe:
Die Menge M ⊆ {a, b, c} von Zeichenreihen über dem Alphabet {a, b, c} ist induktiv definiertals die kleinste Menge, für die gilt:
• ab ∈ M und ba ∈ M.
• Falls w1, w2 ∈ M, dann ist auch w1w2 ∈ 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 überden Wortanfang bzw. das Wortende (Verschärfung der Induktionsbehauptung).
Problem/Ansatz:
Ich habe das Thema aus der Vorlesung noch nicht ganz verstanden und bin unsicher wie die Aufgabe zu bearbeiten ist.
