BuK/IIm14/Studenten/s3rozoek/Uebung3

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
= Ü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}
$$

<code id="552e54cde090f">
function chiM1(wort){
if(wort=="aaa"||wort=="aba"||wort=="aab"||wort=="baa"||wort=="bab"||wort=="abb"||wort=="bbb"){return true;}
else{return false;}
}
</code>

<run id="552e54cde0985">
chiM1("aaa")
</run>


=== 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}
$$

<code id="552e554c46082">
function chiM1(wort){
if(wort=="aaa"||wort=="aba"||wort=="aab"||wort=="baa"||wort=="bab"||wort=="abb"||wort=="bbb"){return true;}
else{return false;}
}
</code>

<run id="552e554c460f9">
chiM1("aaa")
</run>