ue3

Aus ProgrammingWiki

Archivierte Version vom 2012-04-01T09:34:39+00:00. Aktuelle Version

Übung 3

Aufgabe 2

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).

Beispiel 1:

M ist die Menge aller Wörter aus A^*, die die Länge 3 besitzen, d.h.:

A^* = \{a, b\}^* \text{ und } M \subset A^* = \{w \mid w \in A^*\text{ und } |w| = 3\}

Lösung:

Die Mengen sind (absolut) entscheidbar, wenn es eine charakteristische Funktion gibt, die "wahr" zurückgibt, wenn das Element in der Menge enthalten ist und "falsch", wenn es definitiv nicht enthalten ist.

Da es sich um eine endliche Menge handelt, kann eine Iteration über die Elemente der Menge erfolgen, wobei das jeweilige Element mit dem gesuchten verglichen wird. Bei Übereinstimmung wird "wahr" zurückgegeben. Wird die Iteration erfolglos beendet, wird "falsch" zurückgegeben.

\chi_M(w) = \begin{cases} wahr, & \text{wenn } w \in M;\\ falsch, & \text{sonst} \end{cases}

(define M (list "aaa" "aba" "aab" "baa" "bab" "abb" "bba" "bbb"))
(define chi
  (lambda (w)
    (letrec
      ((suche
        (lambda (menge)
          (cond
            [(null? menge) #f]
            [(string=? (car menge) w) #t]
            [else 
              (suche (cdr menge))
            ]
          )
        )
      ))
      (suche M)
    )
  )
)

(chi "aab")

Eine alternatie Möglichkeit besteht in der Überprüfung, ob das Wort den Regeln entspricht (Wortlänge von 3, Alphabet enthält nur 'a' und 'b'):

(define chi2
  (lambda (w)
    (letrec
      ((suche
        (lambda (liste index)
          (cond
            [(and (null? liste) (<= index 3)) #f]
            [(null? liste) #t]
            [(> index 3) #f]
            [(not (or (char=? #\a (car liste)) (char=? #\b (car liste)))) #f]
            [else 
              (suche (cdr liste) (+ index 1))
            ]
          )
        )
      ))
      (suche (string->list w) 1)
    )
  )
)

(chi2 "aaaa")

ue3

Übung 3

Aufgabe 2

Suche