Entscheidbarkeit und Aufzählbarkeit

Aus ProgrammingWiki

Archivierte Version vom 2012-03-23T17:17:04+00:00. Aktuelle Version

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.

(define chi-laenge3
  (lambda (w)
    (if (member w '("aaa" "aab" "aba" "baa" "abb" "bab" "bba" "bbb"))
      #t
      #f)))

(chi-laenge3 "abb")

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

(define chi-a
  (lambda (w)
    (char=? (string-ref w 0) #\a)))

(chi-a "ababaab")