0 Daumen
27 Aufrufe

Ist die folgende Aussage wahr?

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

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.

von 8,3 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...