Berechenbarkeitstheorie/Entscheidbarkeit und Aufzählbarkeit

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==Charakteristische Funktion==

Beispiel: Wörter der Länge 3 über $\{a,b\}^*$

Die zu charakterisierende Menge ist eine endliche, denn es gibt nur $2^3=8$ solche Wörter.

<code id="4f6cafece05e6">
(define chi-laenge3
  (lambda (w)
    (if (member? w '("aaa" "aab" "aba" "baa" "abb" "bab" "bba" "bbb"))
      #t
      #f))) 
</code>
<run id="4f6cafece065c">(chi-laenge3 "abb")</run>


Beispiel: Wörter über $\{a,b\}^*$, die mit $a$ beginnen. 

<code id="4f6ca9bc8928d">
(define chi-a
  (lambda (w)
    (char=? (string-ref w 0) #\a)))
</code> 
<run id="4f6ca9bc89383">
(chi-a "ababaab")
</run>