Vorlesung 3

Aus ProgrammingWiki

< BuK | IIm19 | Aufzeichnungen Adaszewski

$A^* = \{a,b\}$ und $M \subset A^* =\{w | w \in A^* \text{ und } |w|=3 \}$
Entscheidbar, da folgende Prozedur existiert:

(define endlicheMenge (lambda (wort) (let ((zeichenListe (string->list wort))) (letrec ((alleZeichenImAlphabet? (lambda (alleZeichen) (cond [ (or (char=? #\a (car alleZeichen)) (char=? #\b (car alleZeichen))) (cond [(not (null? (cdr alleZeichen))) (alleZeichenImAlphabet?(cdr alleZeichen))] [else #t] ) ] [else #f] ) ) )) (cond [ (= (string-length wort) 3) (alleZeichenImAlphabet? zeichenListe) ] [else #f] ) ) ) ) )

(endlicheMenge "aba")

$A^* = \{a,b\}$ und $M \subset A^* =\{aw' | w' \in A^* \}$
Entscheidbar, da folgende Prozedur existiert:

(define abzaehlbarUnendlicheMenge (lambda (wort) (let ((zeichenListe (string->list wort))) (letrec ((alleZeichenImAlphabet? (lambda (alleZeichen) (cond [ (or (char=? #\a (car alleZeichen)) (char=? #\b (car alleZeichen))) (cond [(not (null? (cdr alleZeichen))) (alleZeichenImAlphabet?(cdr alleZeichen))] [else #t] ) ] [else #f] ) ) )) (cond [ (and (not (null? zeichenListe)) (char=? #\a (car zeichenListe))) (cond [(null? (cdr zeichenListe)) #t] [else (alleZeichenImAlphabet? (cdr zeichenListe))] ) ] [else #f] ) ) ) ) )

(abzaehlbarUnendlicheMenge "aaaaaba")

Entscheidbarkeit und Aufzählbarkeit

Vorlesung 3

Aus ProgrammingWiki

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge