BuK/IIm20/Vorlesung 3 Thomas

Wiki-Quelltext dieser Seite.

<language>Python</language>
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\}$.

<code id="606703bee3717">def chi(m):
    return len(m) == 3</code>
<run id="606703bee3801">
print(chi("aaa"))
print(chi("aa"))
print(chi("bab"))
print(chi("bb"))</run>

'''Beispiel 2: abzählbar unendliche Menge'''

<code id="606703bee3789">
def chi(m):
    if len(m) > 0:
        return m[0] == "a"
    return False</code>
<run id="606703bee3871">
print(chi("abaaba"))
print(chi("babbaa"))</run>


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

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

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

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

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