ue3

Aus ProgrammingWiki

Archivierte Version vom 2012-04-01T09:07:40+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: 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
            [(null? liste ) #t]
            [(> index 3) #f]
            [(not (or (string=? "a") (string=? "b"))) #f]
            [else 
              (suche (cdr liste ) (+ index 1))
            ]
          )
        )
      ))
      (suche (string->liste w) 0)
    )
  )
)

(chi "aab")

ue3

Übung 3

Aufgabe 2

Suche