0 Daumen
257 Aufrufe

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community