0 Daumen
263 Aufrufe

Ist die folgende Aussage wahr?

\(\forall w\in\Sigma^*:\exists X\in\Sigma^*:wX=w\)

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Das leere Wort \(\epsilon\) ist in \(\Sigma^*\) enthalten (\(\epsilon\in\Sigma^*\)). Unabhängig davon, welche Zeichenkette wir aus \(\Sigma^*\) auswählen: Wir werden ein \(X\in\Sigma^*\) finden, sodass \(wX=w\) ist, nämlich das leere Wort. Sei z. B. \(\Sigma=\left\{a\right\}\). Dann ist \(\Sigma^*=\left\{\epsilon, a, aa, aaa, ... \right\}\) und für \(w=a\) wählen wir \(X=\epsilon\in\Sigma^*\) und erhalten $$a\epsilon=a\surd$$ Wichtig: Die Angabe eines einzigen Beispiels ist kein Beweis! Dafür diente die vorangegangene Argumentation.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community