Vorlesung 3 Thomas

Aus ProgrammingWiki

Seite 9

Beispiel 1: endliche Menge

$A^∗ = \{a, b\}^∗$ und $M \subset A^∗ = \{w | w \in A^∗$ und $|w| = 3\}$.

$M$ ist die Menge aller Wörter aus $A^*$, die die Länge 3 besitzen, d.h.

$M = \{aaa, aba, aab, baa, bab, abb, bba, bbb\}$.

def chi(m): if len(m) == 3: return m in ['aaa', 'aba', 'aab', 'baa', 'bab', 'abb', 'bba', 'bbb'] return False

print(chi("aaa")) print(chi("aa")) print(chi("bab")) print(chi("bcb"))

ausführen

Beispiel 2: abzählbar unendliche Menge

def chi(m): if len(m) > 0: return m[0] == "a" return False

print(chi("abaaba")) print(chi("babbaa"))

ausführen

---

Seite 15

Ü1: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

Ü2: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

def is_prime_number(x): if x >= 2: for y in range(2,x): if not ( x % y ): return False else: return False return True

for i in range(2,60): if is_prime_number(i) == True: print(i)

ausführen

Ü3: Wir wissen, dass $A^∗$ eine abzählbar unendliche Menge ist. Zeigen Sie, dass $A^∗$ auch aufzählbar ist. Hinweis: Hierzu ist es notwendig ein Aufbauschema für $A^∗$ zu entwerfen und anschließend eine Prozedur dafür zu implementieren.

---

Seite 16

Zeigen Sie, dass jede endliche Menge aufzählbar ist.

• $M = \{x_0, ..., x_n\}$ ist Wertebereich von $f$ mit $f(n) = \begin{cases} x_i & falls~i\geq n \\ x_0 & \, \text{sonst} \end{cases}$
• $f$ ist primitiv rekursiv, also berechenbar

Die Menge $G$ der Gitterpunkte $(0, 0),(0, 1), ...$ einer x-y-Ebene ist aufzählbar.

def gitter(x): list = [] startx = 0 while len(list) <= x: list.append("(" + str(startx) + ", " + str(startx) + ")") if len(list) == x: break list.append("(" + str(startx) + ", " + str(startx+1) + ")") if len(list) == x: break list.append("(" + str(startx+1) + ", " + str(startx) + ")") startx+=1 print(list)

gitter(7) gitter(20)

ausführen

def find_gitter(y, x): list = [] startx = 0 while True: list.append("(" + str(startx) + ", " + str(startx) + ")") if startx == y and startx == x: break list.append("(" + str(startx) + ", " + str(startx+1) + ")") if startx == y and (startx+1) == x: break list.append("(" + str(startx+1) + ", " + str(startx) + ")") if (startx+1) == y and startx == x: break startx+=1 print(len(list))

find_gitter(1, 2) find_gitter(2, 1) find_gitter(7, 8) find_gitter(10, 10)

ausführen

---

Seite 20

Ü1: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

Ü2: Geben Sie für die Menge $FIBS$ der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass $FIBS$ eine semi-entscheidbare Menge ist. Zeigen Sie, dass FIBS sogar entscheidbar ist.

def FIBS(n): if n == 0: return 1 if n == 1: return 1 if n == 2: return 2 return FIBS(n-1) + FIBS(n-2)

for i in range(5): print(FIBS(i))

ausführen

Ü3: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2| n \in N\}$.

def q(x): return x*x

print(q(10)) print(q(105)) print(q(1078))

ausführen

Ü4: Weisen Sie nach, dass die Menge $M$ aller Wörter aus ${a, b}^∗$, die mit $a$ beginnen, semi-entscheidbar ist

---

Seite 23

Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.

def even(n): return 2 * n def odd(n): return 2 * n + 1 def unite(i, f, g): if i % 2 == 0: return f(i / 2) else: return g((i-1) / 2)

for i in range(30): print(unite(i, even, odd))

ausführen