BuK/IIm19/Aufzeichnungen Adaszewski/Vorlesung 3

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
<math> A^* = \{a,b\}</math> und <math>M \subset A^* =\{w | w \in A^* \text{ und } |w|=3 \}</math> <br>
Entscheidbar, da folgende Prozedur existiert:

<code id="5e8f143dab426">
(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]
        )
      )
    )
  )
)
</code>

<run id="5e8f143dab4a4">
(endlicheMenge "aba")
</run>



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

<code id="5e8f16615fbc8">
(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]
        )
      )
    )
  )
)
</code>

<run id="5e8f16615fc44">
(abzaehlbarUnendlicheMenge "aaaaaba")
</run>

* <b>Entscheidbarkeit und Aufzählbarkeit</b>

[[Bild:Bockwurstpaule_NachweisAufzahlbarkeit.jpg|800px]]

[[Bild:Bockwurstpaule_NachweisAufzahlbarkeit2.jpg|800px]]

[[Bild:Bockwurstpaule_NachweisAufzahlbarkeit3.jpg|800px]]

[[Bild:Bockwurstpaule_Gitterpunkte1.jpg|800px]]

[[Bild:Bockwurstpaule_Gitterpunkte2.jpg|800px]]

[[Bild:Bockwurstpaule_Gitterpunkte3.jpg|800px]]

[[Bild:Bockwurstpaule_Halpeproblemsemientscheidbar.jpg|800px]]

[[Bild:Bockwurstpaule_Fibonaccihlaufzahlbarkeit.jpg|800px]]

[[Bild:Bockwurstpaule_Quadratzahlenundmengeuberab.jpg|800px]]