Übung 3

Entscheidbarkeit einfacher Mengen

Zu zeigen ist die Entscheidbarkeit der beiden Mengen M1 und M2. Dazu reicht es eine entsprechende Charaktersitische Funktion \chi_{M_x}(w) zu finden.

Bsp1

A^*={a,b}^* und M_1 \subset A^* = \{w | w \in A^* \text{ und } |w| = 3\} M_1 ist die Menge aller Wörter aus A^*, die die Länge 3 beseitzen, d.h. M_1 = \{aaa, aba, aab, baa, bab, abb, bba, bbb\}

Da die Menge endlich ist, können einfach alle Elemente überprüft werden. Somit ergibt sich \chi_{M_1}(w).

Bsp 2

Abzählbar unendliche Menge. M_2 ist die Menge aller Wörter, die aus beliebig vielen a's und b's bestehen und mit a beginnen. A^* = {a, b}^* und M1 \subset A^* = {w = aw' | w' \in A^*}

Da es reicht das erste Element zu überprüfen, ist die Menge entscheidbar. Dazu sei w \in M_1 = w_1 \circ w_2 \circ ... \circ w_n | w_1,...w_n \in A

Anzahl berechenbarer charakteristischer Funktionen

????

Aufzählbarkeit

Eine Menge M \subseteq A^* heißt aufzählbar, wenn es entweder eine total berechenbare surjektive Funktion f : \N \rightarrow M gibt, oder es gilt M=\emptyset Man nennt f eine Aufzählprozedur oder ein Aufzählverfahren von M. Sehr vereinfacht : aufzählbar = abzählbar + berechenbar

Somit muss für den Beweis der Aufzählbarkeit eine entsprechende Funktion f gefunden werden.

Menge der geraden Zahlen G

z.z. Die Menge G = \{g | g=2n , n \in \N\} ist aufzählbar.

Das Aufzählverfahren ergibt sich bereits aus der Definition von G.

Menge der Primzahlen

$ f(n) = \begin{cases} n, & \text{wenn x eine Primzahl ist} ;\\ 2, & \text{sonst} \end{cases} $

A^*

Aufbauschema:

Aufbauprozedur: