BuK/IIm11/Studenten/sijeheid/ue3

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Ü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}
$$

<code id="4f781a7f02fb4">
(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)
    )
  )
)
</code>

<run id="4f781a7f0309a">
(chi "aab")
</run>

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'):

<code id="4f781a7f03029">
(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)
    )
  )
)
</code>

<run id="4f781a7f030f5">
(chi "aab")
</run>