BuK/IIm11/Studenten/sidatasc/ue3

Wiki-Quelltext dieser Seite.

== Übung 3 ==

<language>Scheme</language>
=== Aufgabe 2 ===

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki). 

'''Beispiel 2''' abzählbar unendliche Menge

$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen. $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .

'''Lösung'''

Die Menge M ist entscheidbar, da folgende charakteristische Funktion existiert:

$$ \chi_M(w) = \begin{cases} 
\#t, & \text{wenn das erste Zeichen von w ein 'a' ist und } w \in A^*\text{, mit } A^* = \{a,b\}^*;\\ 
\#f, & sonst; 
\end{cases} $$

Die Funktion liefert wahr, wenn das erste Zeichen des Wortes $w$ ein 'a' ist und der Rest des Wortes aus dem Alphabet $ A^* $ ist. Falsch, wenn nicht. 

<code id="4f7823a97ad2e">
(define b2
  (lambda (w)
    (let ((l (string->list w)))
      (letrec 
           ((helper
             (lambda (a)
               (if (or (char=? #\a (car a)) (char=? #\b (car a)))
                 (if (not (null? (cdr a)))
                     (helper (cdr a))
                     #t
                  )
                 #f
               )
             )
           ))
        (if (and (not (null? l)) (char=? #\a (car l)))
         (helper (cdr l))
         #f
        )
      )
    )
  )
)
</code>
<run id="4f7823a97adb8">(b2 "ababbababab")</run>