ue3

Aus ProgrammingWiki

Ü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")

ausführen

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")

ausführen

Beispiel 2 abzählbar unendliche Menge

$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen: $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .

Lösung

Die Menge M ist entscheidbar, da folgende charakteristische Funktion existiert:

$$ \chi_M(w) = \begin{cases} wahr, & \text{wenn das erste Zeichen von } w \text{ ein '}a\text{' ist und } w \in A^*\text{, mit } A^* = \{a,b\}^*;\\ falsch, & \text{sonst}; \end{cases} $$

Die Funktion liefert wahr, wenn das erste Zeichen des Wortes $w$ ein '$a$' ist und der Rest des Wortes aus dem Alphabet $ A^* $ ist. Falsch, wenn nicht.

(define b2 (lambda (w) (let ((l (string->list w))) (letrec ((helper (lambda (a) (if (or (char=? #\a (car a)) (char=? #\b (car a))) (if (not (null? (cdr a))) (helper (cdr a)) #t ) #f ) ) )) (if (and (not (null? l)) (char=? #\a (car l))) (helper (cdr l)) #f ) ) ) ) )

(b2 "ababbababab")

ausführen