BuK/IIm14/Studenten/s3rozoek/Uebung3

Wiki-Quelltext dieser Seite.

= Ü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="4f78qg7f02fb4">
(define M (list "aaa" "aba" "aab" "baa" "bab" "abb" "bba" "bbb"))
(define chi
  (lambda (w)
    (letrec
      ((suche
        (lambda (menge)
          (cond
            [(null? menge) #f]
            [(string=? (car menge) w) #t]
            [else 
              (suche (cdr menge))
            ]
          )
        )
      ))
      (suche M)
    )
  )
)
</code>

<run id="4f781a7f0309a">
(chi "aab")
</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}
$$