Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 2

Aufgabe 7. Sei Σ = {a, b}. Geben Sie ein R-Programm an, das die Menge

{x ∈ Σ^{∗} | x enthält keine 2 benachbarten a

oder x enthält keine 2 benachbarten b}

entscheidet.

Aufgabe 8. Sei Σ ein Alphabet und W ⊆ Σ^{∗} eine nichtleere Wortmenge über Σ. Zeigen Sie, daß folgende Aussagen äquivalent sind:

(i) W ist R-aufzählbar.

(ii) Es gibt eine berechenbare Funktion f mit df(f) = W und bd(f) ⊆ Σ^{∗}.

(iii) Es gibt eine berechenbare Funktion f mit df(f) = Σ^{∗} und bd(f) = W.

Aufgabe 9. Sei Σ ein Alphabet und W ⊆ Σ^{∗}. Zeigen Sie, daß W genau dann Rentscheidbar ist, wenn es ein Aufzählungsverfahren P für W gibt, welches die Elemente von W ohne Wiederholungen in lexikographischer Reihenfolge ausgibt.

Aufgabe 10. Seien Σ_{1} und Σ_{2} Alphabete und W_{1} ⊆ Σ_{1}^{∗}, W_{2} ⊆ Σ_{2}^{∗}. W_{1} heißt auf W_{2} (many-one-) reduzierbar (in Notation W_{1} ≤_{m} W_{2}), wenn es eine R-berechenbare Abbildung f : Σ_{1}^{∗} → Σ_{2}^{∗} gibt, sodaß für alle x ∈ Σ_{1}^{∗}:

x ∈ W_{1} ⟺ f(x) ∈ W_{2}.

Ein solches f ist eine Reduktion von W_{1} auf W_{2}. Zeigen Sie:

1. Ist W_{1} ≤_{m} W_{2} und W_{2} R-entscheidbar, so ist auch W_{1} R-entscheidbar.

2. Ist W_{1} ≤_{m} W_{2} und W_{2} R-aufzählbar, so ist auch W_{1} R-aufzählbar.

Wurde in der Vorlesung bereits eine Reduktion (implizit) angegeben?

Aufgabe 11. a) Sei Σ = {a_{0}, …, a_{m}}. Zu W ⊆ Σ^{∗} sei

χ_{W} : Σ^{∗} → Σ^{∗} mit χ_{W} (x) = \begin{cases}λ & , x ∈ W \\ a_{0} & , x ∉ W \end{cases}

die charakteristische Funktion von W. Zeigen Sie, daß W genau dann R-entscheidbar ist, wenn χ_{W} berechenbar ist.

b) Für eine Funktion f mit df(f), bd(f) ⊆ Σ^{∗} sei

G_{f} := {(x, f(x)) | x ∈ df(f)}

der Graph von f. Zeigen Sie, daß G_{f} genau dann R-aufzählbar ist, wenn f berechenbar ist.

Abgabe: Mittwoch, 7. Mai 2008, vor der Vorlesung.