Entscheidbarkeit und Aufzählbarkeit

Aus ProgrammingWiki

Archivierte Version vom 2012-03-27T10:07:27+00:00. Aktuelle Version

Aufzählbarkeit

(define tree-1 '(1 (2 (4) (5)) (3 (6) (7))))

(define node? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 3))))

(define leaf? (lambda (tree)
                (and 
                 (list? tree)
                 (= (length tree) 1))))


(define tiefe (lambda (tree)
                (cond
                  [(leaf? tree) (list (car tree))]
                  [else 
                   (let( [element (car tree)]
                         [left (cadr tree)]
                         [right (caddr tree)])
                     (cons element
                           (append (tiefe left)
                                   (tiefe right))))])))

(display tree-1)

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

Die Menge der Primzahlen ist aufzählbar unendlich:

(prim? 31)

(define f 
  (lambda (n)
    (if (prim? n)
      n
      2)))

(f 31)

Entscheidbarkeit und Aufzählbarkeit

Aufzählbarkeit

Suche