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

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

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)

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

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)

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

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

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

Vorlesung 3 Thomas

Suche