BuK/IIm20/Vorlesung 4 Seidl

Wiki-Quelltext dieser Seite.

<language>Python</language>
=== KA ===
<code id="607b30f0aee5d">
from itertools import product
from browser import timer
import math


a = ["a", "b", "c"]

def paarungsfunktion(i):
    z = i
    w = math.trunc((math.sqrt(8 * z + 1) - 1) / 2)
    t = (w * (w + 1)) / 2
    y = z - t
    x = w - y
    return (x, y)

def g(generator, index):
    count = -1
    for w in generator():
        count += 1
        if count == index:
            return w

def a_stern():
    count = 0
    while True:
        for w in product(a, repeat=count):
            yield "".join(w)
        count += 1

def chi_strich(wort, ticks):
    if wort.startswith("ab") is True:
        return True
    else:
        for i in range(0, ticks):
            timer.set_timeout(None, 1)
        return

def f(z):
    count = 0
    while True:
        wort_index, ticks = paarungsfunktion(count)
        wort = g(a_stern, wort_index)
        
        wert = chi_strich(wort, int(ticks))
        if wert is True:
            print(wort)
        else:
            print("abc")
        
        count += 1
        if count >= z:
            return
</code>
<run id="607b30f0aeec2">f(5000)</run>

=== S. 33 ===
p(A):
        - A ist ein endliches Alphabet: [a, b]
        - Potenzmenge von A sind alle möglichen Kombinationen (Wörter) aus A + leere Menge: [ , a, b, aa, ab, ..., bb]

p(A*):
        - A* ist eine unendliche Wortmenge
        - Potenzmenge von A* sind alle möglichen Kombinationen (Wörter) aus A* + leere Menge (überabzählbar unendlich?)

A*:
        - A* sind unendlich viele Kombinationen (Wörter) aus A ohne Längenbegrenzung
        - z.B. [ , a, aa, aaa, aaaa, aaaaa, ...]

endliche Menge (abzählbar unendlich viele):
        - [[ , a, b, aa, ab, ..., bb], [ , c, d, cc, cd, ..., dd], ...]


entscheidbare Menge (abzählbar unendlich viele):
        - muss größer als semi-entscheidbare Menge (abzählbar unendlich viele) sein, weil Entscheidbarkeit impliziert semi-Entscheidbarkeit

aufzählbare Menge (abzählbar unendlich viele):
        - [[a, b, ab, ...], [b, c, bc, ...], ...]

abzählbare Menge (überabzählbar unendlich viele):
        - [[a, b, ab, ...], ..., [b, c, bc, ...], ...]


Von größer zu kleiner:
p(A*)<br/>
abzählbare Menge (überabzählbar unendlich viele)<br/>
aufzählbare Menge (abzählbar unendlich viele) - entscheidbare Menge (abzählbar unendlich viele)<br/>
semi-entscheidbare Menge (abzählbar unendlich viele)<br/>
endliche Menge (abzählbar unendlich viele)<br/>
A*<br/>
p(A)<br/>