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

Suche