¨Ubungen zur Vorlesung Einführung in die Theoretische Informatik

Universit¨
at Heidelberg / Institut f¨
ur Informatik
Prof. Dr. Klaus Ambos-Spies
Dipl. Math. Martin Monath
23. April 2015
¨
Ubungen
zur Vorlesung
Einfu
¨ hrung in die Theoretische Informatik
Blatt 1
Aufgabe 1 (2 Punkte)
Sei Σ = Σ2 = {0, 1} das bin¨
are Alphabet und sei h : Σ∗ → Σ∗ der durch h(0) = 10, h(1) =
001 induzierte Homomorphismus und Bin(n) die Bin¨ardarstellung der Zahl n. Berechnen
Sie den Wert von
#0 (h((Bin(21) ◦ w12 ) 7)).
Aufgabe 2 (4 Punkte)
Die Bin¨
arsprache L sei induktiv definiert durch
(i) λ ∈ L.
(ii) Geh¨
ort w zu L, dann auch 0w1 und 1w0.
(iii) Geh¨
oren v 6= λ und w 6= λ zu L, dann auch vw.
Zeigen Sie, dass die Sprache L mit der Sprache L0 = {w ∈ Σ∗2 : #0 (w) = #1 (w)}
u
¨bereinstimmt.
Hinweis: F¨
uhren Sie den Nachweis, dass jedes Wort w mit der Eigenschaft #0 (w) = #1 (w)
in L liegt, induktiv nach der L¨ange von w. Beobachten Sie hierbei, dass sich jedes nichtleere
Wort w ∈ L0 , dessen erster und letzter Buchstabe u
¨bereinstimmen, echt in zwei Teilw¨orter
aus L0 zerlegen l¨
asst.
Aufgabe 3 (2+2+2=6 Punkte)
Seien Σ und T Alphabete. Zeigen Sie:
(a) Ist ϕ : Σ∗ → T ∗ partiell berechenbar und injektiv, so ist auch die partielle Umkehrfunktion ϕ−1 : T ∗ → Σ∗ partiell berechenbar. Ist ϕ weiter total und sogar surjektiv, so ist auch
ϕ−1 berechenbar.
(b) Ist h : Σ∗ → T ∗ ein Homomorphimus, so ist h berechenbar. Ist h sogar bijektiv, so ist
auch h−1 ein Homomorphimus.
(c) Betrachten Sie die in der Vorlesung vorgestellte Bin¨arkodierung bink : Σk → Σ2 eines
k-¨
aren Alphabets Σk = {a0 , . . . , ak−1 } f¨
ur k ≥ 3. Warum ist die partielle Umkehrfunktion
bin−1
kein
Homomorphismus
und
auch
nicht
zu einem Homomorphismus erweiterbar?
k
Aufgabe 4 (4 Punkte)
Ein Paar (n, n+2) von nat¨
urlichen Zahlen heißt Primzahlzwilling, falls sowohl n als auch n+2
Primzahlen sind (zum Beispiel ist (3, 5) ein Primzahlzwilling). Die Frage, ob es unendlich
viele Primzahlzwillinge gibt, ist ein bislang ungel¨ostes mathematisches Problem.
Sei f : N → N die Funktion, die definiert ist durch
(
1, falls es mindestens n Primzahlzwillinge gibt,
f (n) =
0, sonst.
Ist f berechenbar? Begr¨
unden Sie Ihre Antwort.
Abgabe: Bis Donnerstag, den 30. April 2015, 14 Uhr in den Briefk¨asten im Foyer im
EG der Angewandten Mathematik. Homepage der Vorlesung:
http://www.math.uni-heidelberg.de/logic/ss15/theoinf_ss15.html

Download Report