BuK/IIm10/BuK-Übung04 G1

Wiki-Quelltext dieser Seite.

=Aufzählbarkeit und Entscheidbarkeit=
<language>Scheme</language>
==Aufgabenstellung==
Drücken Sie den Beweis des folgenden Satzes mit Racket aus.
Wenn ''M'' eine aufzählbar unendliche Menge ist, dann ist ''M'' semi-entscheidbar.

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==Lösung==
<code id="4da47d51a9ef8" hidden>
;###############   wortmenge.ss   ############

(define wortmenge-stufe
  (lambda (n alphabet)
    (if (= n 0)
        '("")
        (apply
         append
         (map 
          (lambda (zeichen)
            (map
             (lambda (wort)(string-append (string zeichen) wort))
             (wortmenge-stufe (- n 1) alphabet)))
          alphabet)))))

(define wortmenge-bis-stufe
  (lambda (n alphabet)
    (if (= n 0)
        (wortmenge-stufe 0 alphabet)
         (append 
          (wortmenge-bis-stufe (- n 1) alphabet)
          (wortmenge-stufe n alphabet)))))

;################ buk-impl.rkt #######################
(define A '(#\a #\b #\c))  ; Alphabet

(define g      ; verwendet Alphabet A als freie Variable!!
  (lambda (i)
    (let* ((s (if (< i 2) 1 (ceiling (/ (log i)(log (length A))))))
           (A*-bis-stufe (wortmenge-bis-stufe s A)))
      (list-ref A*-bis-stufe i))))
</code>
<code id="4da47a7597a9d">
(define chi-strich?
  (lambda (w)
    (letrec
        ((helfer
          (lambda (i)
            (if (string=? w (g i))
                #t
                (helfer (+ i 1))))))
      (helfer 0))))
</code>
<run id="4da47a7597b2e">
(chi-strich? "aaa")
</run>
Das nachfolgende Beispiel muss manuel unterbrochen werden, da es sonst ewig laufen würde.
<run id="4da47fac2798b">
(chi-strich? "aaa1")
</run>

=Entscheidbarkeit und Aufzählbarkeit=
==Aufgabenstellung==
Beweisen Sie: Wenn ''M'' entscheidbar ist, dann sind ''M'' und ''A''* \ ''M'' aufzählbar. Illustrieren Sie anschließend mit Racket.
==Lösung==

=Semi-Entscheidbarkeit=
==Aufgabenstellung==
Zeigen Sie auf der Basis der Semi-Entscheidbarkeit, dass wenn ''M'' und ''A''* \ ''M'' aufzählbar sind, ''M'' entscheidbar ist. Repräsentieren Sie den Beweis anschließend mit Racket. Verwenden Sie die entwickelten Racket-Prozeduren für folgendes Beispiel: ''A''* ist die Menge der natürlichen Zahlwörter, ''M'' die Menge der Zahlwörter für die geraden Zahlen und ''A''* \ ''M'' die Zahlwörter für die ungeraden Zahlen.
==Lösung==