Theoretische Informatik: Logik WS 96/97

Übung 4, Abgabetermin: 20.-25.11.96 in der jeweiligen Übung

1. Die Relation ⊑ ist in der MengeW (X) der Wörter über einem gegebenen Alphabet X wie folgt definiert: w_{1} ⊑ w_{2} genau dann, wenn ein Wort w existiert, so daß w_{1}^{⌢}w = w_{2} ist. Zeigen Sie, daß diese Relation eine reflexive Halbordnung in W (X) ist!

2. Über der Menge M = {a, b, c, d} sei die Operation ”•“ durch folgende Tabelle definiert:

\begin{matrix}• & a & b & c & d \\ a & a & b & c & d \\ b & b & c & d & a \\ c & c & d & a & b \\ d & d & a & b & c \end{matrix}

(a) Überprüfen Sie, ob [M, •] eine Halbgruppe mit Nullelement ist!

(b) Geben Sie ein Erzeugendensystem an!

(c) Ist das von Ihnen gewählte Erzeugendensystem frei?

3. Sei X = {0, 1, 2, ..., 9} ein Alphabet. Die Abbildung ψ : N^{+}×W (X) → N (N ist die Menge der nat. Zahlen) ordnet einem Wort p ∈ W (X) (Zahl) und einem Buchstaben n ∈ N^{+} (Zahl) den Rest bei der Division der Quersumme von p durch n zu. Beispiele:

ψ(\underbrace{3}_{n}, \underbrace{2789}_{p}) = Rest(\frac{26}{3}) = 2

ψ(\underbrace{27}_{n}, \underbrace{28979}_{p}) = Rest(\frac{35}{27}) = 8

Geben Sie eine induktive Definition dieser Abbildung an!

4. Gegeben seien zwei Mengen X und Z sowie eine Abbildung δ : Z × X → Z. Die Abbildung δ^{∗} : Z × W (X) → Z sei induktiv definiert durch:

δ^{∗}(z, e) := z (für alle z ∈ Z)
δ^{∗}(z, p^{⌢}x) := δ(δ^{∗}(z, p), x) (für alle x ∈ X, z ∈ Z und p ∈ W (X))

Zeigen Sie durch Induktion, daß für alle z ∈ Z, p, q ∈ W (X) die folgende Gleichung gilt (bekannt als Zustandsgleichung für Automaten):

δ^{∗}(z, p^{⌢}q) = δ^{∗}(δ^{∗}(z, p), q)!