Theoretische Informatik (WS 2005/2006) - Übungsblatt 2

Jan Hendrik Dithmar - Matrikelnummer 2031259 Do, 11-13 Uhr, Vasileios Anastasatos

Aufgabe 1

{0, 1}^{ℕ} ⊂ ℕ^{ℕ} ⇒ ∃ Surjektion von ℕ^{ℕ} → {0, 1}^{ℕ}. Fasse jede Funktion f : ℕ → {0, 1} als unbeschränkten Bitstring b auf. Betrachte Funktion g(x) mit

g : x ↦ \begin{cases}# Nullen zwischen x-ten und (x+1)-ten Eins & falls # Nullen endlich \\ # Einsen zwischen x-ten und (x+1)-ten Null & sonst \end{cases}

Für x = 0 sei g(x) = g(0) zu verestehen als

g : 0 ↦ \begin{cases}# Nullen vor 1. Eins & falls # Nullen endlich \\ # Einsen vor 1. Null & sonst \end{cases}

⇒ ∃ Surjektion von ℕ^{ℕ} → {0, 1}^{ℕ} und ∃ Surjektion von {0, 1}^{ℕ} → ℕ^{ℕ}. ⇒ |{0, 1}^{ℕ}| = |ℕ^{ℕ}|. □

Aufgabe 2

(a)

b  b  aaa b  b b  b b  b aaa  aaa a  a a  b b b b

(b)

S 0  1 36  52  4 01 0  1 01  10 1 0  0 1  1 01  0

(c)

Sei S die Menge der Quadratzahlen. Sei S′ ⊂ S mit der Form 1^{n}0^{n}01, n ∈ ℕ, also

S′ = {w|w = 2^{2a} − 2^{2a+1} + 1} ∀a ∈ ℕ

(Es gilt 2^{2a} − 2^{a+1} + 1 = (2^{a} − 1)^{2} ∈ S ∀a ∈ ℕ).

Ist a = 1, b = 0 so hat man also mit v ∈ S′ Worte der Form v = a^{n}b^{n}01. Für Worte dieser Form gibt es jedoch keine DEA-Sprache, da in der Vorlesung gezeigt wurde, dass L = {a^{n}b^{n}|n ∈ ℕ} keine DEA-Sprache ist. Die einzige Möglichkeit, Worte der Form 1^{n}0^{n}01 zu akzeptieren wäre, die ”0”-en in einer Schleife zu überlesen, sie also zu ignorieren. Solche Worte wären dann aber auch z.B. 1^{m}1^{n}01 mit m, n ∈ ℕ und m ≠ n. Sie sind aber in der Regel keine Quadratzahlen: ∃v ∈ {1^{m}1^{n}01} mit v ∉ S, z.B. m = 4, n = 3:

⟨111100001⟩ = 2^{9} − 2^{5} + 1 = 512 − 32 + 1 = 481 ∉ S

Somit hat 1^{n} für jedes n eine Fortsetzungssprache, die sich von denen der Worte 1^{n′} mit n′ ≠ n unterscheidet. Da aber n ∈ ℕ, somit {w|w = 1^{n}0^{n}01, n ∈ ℕ} unendlich (mindestens eine pro Wort der Teilmenge S′), somit ist F endlich. ⇒ ∄ DEA. □

(d)

Man kann hier keinen DEA konstruieren. Denn: Seien a, b ∈ ℕ, a prim, b < a. Dann lässt sich sicher sagen, dass ggT (a, b) = 1. Außerdem ist 2^{n} teilerfremd a, ∀a > 2, n ∈ ℕ. Aus diesen Eigenschaften folgt ggT (a, b · 2^{|a|}) = 1, was eine Primfaktorzerlegung einfach zeigt. |a| sei hierbei die Länge des Binärwortes a. Nach dem Satz von Dirichlet ist jetzt aber

∃x c := a + x · (b · 2^{|a|})

prim, wobei das x ∈ ℕ eine bestimmte Zahl ist, für die das gilt. Wenn man das rückwärts gelesene Wort betrachtet, hat jedes a ∈ {p|p ist prim} mindestens eine Fortsetzungssprache, die von seiner jeweiligen Länge als Binärwert abhängt. Da es aber unendlich viele Primzahlen und damit auch beliebig lange Bitstring-Darstellungen solcher Zahlen gibt, muss die Menge aller Fortsetzungssprachen F unendlich sein. ⇒ ∄ DEA, der das akzeptiert.

Aufgabe 3

• \overline{L}:

Sei M der Automat, der L akzeptiert. Es existiert ein Automat M′ = (Σ, Q′, s′, F′, Δ′), der \overline{L} akzeptiert. M′ sieht wie M aus mit folgenden Unterschieden:

– alle Endzustände von M sind in M′ keine Endzustände und alle nicht-Endzustände von M sind in M′ Endzustände.

– M′ besitzt noch einen weiteren Endzustand, in den der Automat M′ für ein eingelesenes Zeichen übergeht, d.h.

Δ′ = {(q, a, β)|(q, a, q′) ∉ Δ für q, q′ ∈ Q, a ∈ Σ}

• L ∩ L′: L ∩ L′ ⇒ Es existieren Automaten M, der L akzeptiert, und M′, der L′ akzeptiert. Nach dem Satz von Myhill-Nerode gilt: L ⊂ Σ^{∗} DEA-Sprache ⇔ F endlich. ⇒ F_{L} ∩ F_{L′} endlich ⇒ L ∩ L′ DEA-Sprache.

• L ∪ L′: analog zu L ∩ L′: F_{L} ∩ F_{L′} endlich ⇒ L ∪ L′ DEA-Sprache.