BuK/IIm11/Studenten/sitosalz

Wiki-Quelltext dieser Seite.

= Übung 2 =

== Aufgabe 2 ==

$$ \sum\limits_{k=1}^{n} F_{2k} =  F_{2n+1} - 1$$

IA: 

Für $n = 1$ ergibt sich:

$ F_2 =  F_{2*1+1} - 1$

$ F_2 =  F_{3} - 1$

$ 1 =  2 - 1 $

$ 1 = 1 \Rightarrow OK $

IS:

Wenn $ \sum\limits_{k=1}^{i} F_{2k} =  F_{2i+1} - 1$ (IV), dann gilt auch:

$ \sum\limits_{k=1}^{i+1} F_{2k} =  F_{2(i+1)+1} - 1 =  F_{2i+3} -1$ (IB)



$ \sum\limits_{k=1}^{i+1} F_{2k} = \sum\limits_{k=1}^{i} F_{2k} + F_{2(i+1)} \quad \stackrel{IV}{=}  \quad F_{2i+1} - 1 + F_{2i+2}  \quad = \quad F_{2n+3} - 1 $

<div align="right">$\square $</div>

= Übung 3 =

== Aufgabe 5 ==

=== ÜA: Weisen Sie nach, dass die Menge M aller "Wörter aus {a, b}*, die mit a beginnen, semi-entscheidbar ist. ===

Wie in der Übersicht zu den Mengenklassen ersichtlich, ist eine Menge auch semi-entscheidbar, wenn Sie entscheidbar ist. In Aufgabe 2 wurde die Entscheidbarkeit  dieser Menge gezeigt, daraus folgt das Sie auch semi-entscheidbar sein muss.