endliche Automaten & Sprachen

26.11.2004, 20:17

Werna

endliche Automaten & Sprachen

Nabend zusammen.

Hänge seit ein paar stunden an ein paar aufgaben fest und komm einfach nicht weiter. Die Aufgaben stammen zwar aus dem wunderbaren Fach Theoretische Informatik, allerdings besteht das eh zu 95% aus Mathe.
Und da hab ich mir gedacht, das man mir hier vielleicht weiterhelfen könnte =)

Also, los gehts:
1.Problem

http://www.sau-dumm.de/files/attachments/theo_inf2.jpg
die a) ist kein problem... allerdings bin ich bei der b) etwas stutzig geworden.
Übersetz heisst es: Ist die Potenzmenge aller Wörter über Sigma abzählbar? Gute Frage... smile

Hab mit nem Gegenbeweis angefangen und bin da auch zu ner Matrix gekommen, allerdings enden dort auch jegliche Grenzen meiner Verständnis. Irgendwie müsste man von dort aus mit ner Diagonalen weiter machen und ne Menge bilden, etc.
Ich bekomms jedenfalls nich auf die Reihe...
Für Tipps wär ich dankbar!! =)))

2. Problem

http://www.sau-dumm.de/files/attachments/theo_inf1.jpg
Hier häng ich total fest... hab keine Ahnung wie ich anfangen soll bzw was man dort von mir verlangt =) böse

So, help me Hilfe

Danke im vorraus

26.11.2004, 23:18

Tobias

Auf diesen Beitrag antworten »

Hmm also a) ist ja klar.

$\begin{eqnarray*} \text{Sei } \varphi : \Sigma \to \{0, 1, \ldots, | \Sigma | -1 \} \text{ eine bijektive Bewertungsfunktion} \end{eqnarray*}$

Dann haben wir eine Abzählung gegeben durch:

$\begin{eqnarray*} f : \Sigma^* \to \mathbb{N}, \; \omega_{n-1} \ldots \omega_0 \mapsto \sum_{k=0}^{n-1} \varphi(\omega_k) \cdot |\Sigma|^k \end{eqnarray*}$

Das heißt automatisch, dass $\begin{eqnarray*} \Sigma^* \end{eqnarray*}$ gleichmächtig zu $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ ist. Die Potenzmenge der natürlichen zahlen ist aber überabzählbar, also auch die Potenzmenge aller Wörter. Du kannst also einfach den Beweis der Überabzählbarkeit von N irgendwo abschreiben. Augenzwinkern

Zu A4 fehlen mir leider (noch) die Grundlagen.

27.11.2004, 13:26

Werna

Auf diesen Beitrag antworten »

danke erstmal für deine antwort, so in etwa hab ichs auch gemacht.

Zitat:

Original von Tobias
Du kannst also einfach den Beweis der Überabzählbarkeit von N irgendwo abschreiben. Augenzwinkern

das wär allerdings mehr als schön... wird dem prof aber leider nich reichen *g*
mal sehen was draus wird.. Augenzwinkern

27.11.2004, 15:08

Tobias

Auf diesen Beitrag antworten »

Naja indirekt wird wohl auch dein Prof nichts dagegen sagen können.

Du musst beweisen, dass es keine surjektive Abbildung von $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ nach $\begin{eqnarray*} P(\Sigma^*) \end{eqnarray*}$ gibt. (Dann existiert auch keine Abzählung).

Jetzt bedienen wir uns der oben angegebenen bijektiven Abzählungsfunktion $\begin{eqnarray*} f : \Sigma^* \to \mathbb{N} \end{eqnarray*}$ und führen den schon 1000mal gesehenen Beweis, dass Menge und Potenzmenge nicht gleichmächtig sind in leicht abgewandelter Form.

Sei $\begin{eqnarray*} \sigma : \mathbb{N} \to P(\Sigma^*) \end{eqnarray*}$ bijektiv.

Wir definieren die Menge

$\begin{eqnarray*} M := \left\{ f^{-1}(n) \in \Sigma^* \; | \; n \in \mathbb{N}, \; f^{-1}(n) \notin \sigma(n) \right\} \in P(\Sigma^*) \end{eqnarray*}$

Da $\begin{eqnarray*} \sigma \end{eqnarray*}$ bijektiv ist, existiert ein eindeutiges Urbild zu $\begin{eqnarray*} M \end{eqnarray*}$ . Sei deshalb $\begin{eqnarray*} M = \sigma(x), x \in \mathbb{N} \end{eqnarray*}$

Jetzt erhalten wir den paradoxen Widerspruch:

$\begin{eqnarray*} f^{-1}(x) \in M \quad\Rightarrow\quad f^{-1}(x) \in \sigma(x) \quad\Rightarrow\quad f^{-1}(x) \notin M \end{eqnarray*}$
$\begin{eqnarray*} f^{-1}(x) \notin M \quad\Rightarrow\quad f^{-1}(x) \notin \sigma(x) \quad\Rightarrow\quad f^{-1}(x) \in M \end{eqnarray*}$

Es existiert also keine solche bijektive Abbildung $\begin{eqnarray*} \sigma \end{eqnarray*}$ .

$\begin{eqnarray*} P(\Sigma^*) \end{eqnarray*}$ ist nicht abzählbar.

28.11.2004, 18:55

Werna

Auf diesen Beitrag antworten »

alles klar, vielen dank. habs jetzt auch nach dem prinzip gemacht.
mal gespannt was bei rum kommt =)

danke nochmal und schönen abend noch.

mfg werna

Neue Frage »

Antworten »

endliche Automaten & Sprachen

Verwandte Themen