BuK/IIm12/Studenten/siclsche/Thema9

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Weisen Sie nach, dass die AP-Funktion WHILE-berechenbar ist.
$$AP(0,\ y) = y+1$$
$$AP(x,\ 0) = AP(x-1,\ 1), x > 0$$
$$AP(x,\ y) = AP(x-1,\ AP(x,\ y-1)), x, y>0$$

== Aufgabe 2 ==
Folgende Klassen sollen dargestellt werden:
* Turing-berechenbare Funktionen
* WHILE-berechenbare Funktionen
* GOTO-berechenbare Funktionen
* partiell berechenbare Funktionen
* total berechenbare Funktionen
* LOOP-berechenbare Funktionen
* AP-Funktion



[[Bild:Siclsche_Mengendiagramm.png|500 px]]

== Kreativaufgabe: LOOP-, WHILE, GOTO-Grammatik ==
Entwickeln Sie jeweils zu LOOP-, WHILE- und GOTO-Programmen eine entsprechende Grammatik. Überprüfen Sie anhand eines Beispiels ob die von Ihnen entwickelten Grammatiken korrekt sind.

Verwenden Sie AtoCC.


'''LOOP-Grammatik'''

$G = (N, T, P, s)$ 

\begin{eqnarray*}
N & = & \{LProgramm,\ LProg,\ Zuweisung,\ Zyklus,\ Sequenz,\ Variable,\ Konstante,\ Operation,\ Zahl,\ Ziffer\}\\
T & = & \{\tt{:=},\ \tt{LOOP},\ \tt{DO},\ \tt{END},\ \tt{;},\ \tt{x},\ \tt{+},\ \tt{-},\ \tt{0},\ \tt{1},\ \tt{2},\ \tt{3},\ \tt{4},\ \tt{5},\ \tt{6},\ \tt{7},\ \tt{8},\ \tt{9}\}\\
P & = & \{
   LProgramm \rightarrow LProg\ \\
    & & \ \ LProg \rightarrow Zyklus\ \mid\ Sequenz\ \mid\ Zuweisung\ \\
    & & \ \ Zuweisung \rightarrow Variable\ \tt{:=}\ Variable\ Operation\ Konstante\ \\
    & & \ \ Zyklus \rightarrow \tt{LOOP}\ Variable\ \tt{DO}\ LProg\ \tt{END}\ \\
    & & \ \ Sequenz \rightarrow LProg\ \tt{;}\ LProg\ \\
    & & \ \ Variable \rightarrow \tt{x}\ Zahl\ \\
    & & \ \ Konstante \rightarrow Zahl\ \\
    & & \ \ Operation \rightarrow \tt{+}\ \mid\ \tt{-}\ \\
    & & \ \ Zahl \rightarrow Ziffer\ \mid\ Ziffer\ Zahl\ \\
    & & \ \ Ziffer \rightarrow \tt{0}\ \mid\ \tt{1}\ \mid\ \tt{2}\ \mid\ \tt{3}\ \mid\ \tt{4}\ \mid\ \tt{5}\ \mid\ \tt{6}\ \mid\ \tt{7}\ \mid\ \tt{8}\ \mid\ \tt{9}\ \\
  &   & \}\\
s & = & LProgramm
\end{eqnarray*}