Uebung3
Inhaltsverzeichnis |
Ü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).
\chi_{M_1}(w) = \begin{cases} wahr, & \text{wenn } w==aaa || w==aba || w==aab || w==baa || w==bab || w==abb || w==bba || w==bbb;\\ falsch, & \text{sonst} \end{cases}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
\chi_{M_2}(w) = \begin{cases} wahr, & \text{wenn } w_1 == a;\\ falsch, & \text{sonst} \end{cases}