ue3

Aus ProgrammingWiki

Archivierte Version vom 2012-04-01T09:49:41+00:00. Aktuelle Version

Übung 3

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} wahr, & \text{wenn das erste Zeichen von w ein 'a' ist und } w \in A^*\text{, mit } A^* = \{a,b\}^*;\\ falsch, & 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.

(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
        )
      )
    )
  )
)

(b2 "ababbababab")

ue3

Übung 3

Aufgabe 2

Suche