Uebung3

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Übung 3

Vereinigung mit Streams

Übung 3

Entscheidbarkeit einfacher Mengen

Zu zeigen ist die Entscheidbarkeit der beiden Mengen M1 und M2. Dazu reicht es eine entsprechende Charaktersitische Funktion \chi_{M_x}(w) zu finden.

Bsp1

A^*={a,b}^* und M_1 \subset A^* = \{w | w \in A^* \text{ und } |w| = 3\} M_1 ist die Menge aller Wörter aus A^*, die die Länge 3 beseitzen, d.h. M_1 = \{aaa, aba, aab, baa, bab, abb, bba, bbb\}

Da die Menge endlich ist, können einfach alle Elemente überprüft werden. Somit ergibt sich \chi_{M_1}(w).

\chi_{M_1}(w) = \begin{cases} wahr, & \text{wenn } w==aaa || w==aba || w==aab || w==baa || w==bab || w==abb || w==bba || w==bbb;\\ falsch, & \text{sonst} \end{cases}

function chiM1(wort){
if(wort=="aaa"||wort=="aba"||wort=="aab"||wort=="baa"||wort=="bab"||wort=="abb"||wort=="bbb"){return true;}
else{return false;}
}

chiM1("aaa")

Bsp 2

Abzählbar unendliche Menge. M_2 ist die Menge aller Wörter, die aus beliebig vielen a's und b's bestehen und mit a beginnen. A^* = {a, b}^* und M1 \subset A^* = {w = aw' | w' \in A^*}

Da es reicht das erste Element zu überprüfen, ist die Menge entscheidbar. Dazu sei w \in M_1 = w_1 \circ w_2 \circ ... \circ w_n | w_1,...w_n \in A

\chi_{M_2}(w) = \begin{cases} wahr, & \text{wenn } w_1 == a;\\ falsch, & \text{sonst} \end{cases}

function chiM2(wort){
if(wort.charAt(0)=="a"){return true;}
else{return false;}
}

chiM2("abbbbabababababba")

Anzahl berechenbarer charakteristischer Funktionen

Da die Potenzmenge von A^* überabzählbar unendlich ist, gibt es überabzählbar unendlich viele charakteristische Funktionen (eine für jede Teilmenge). Davon sind nicht alle berechenbar (ein Gegenbeispiel reicht).

Aufzählbarkeit

Eine Menge M \subseteq A^* heißt aufzählbar, wenn es entweder eine total berechenbare surjektive Funktion f : \N \rightarrow M gibt, oder es gilt M=\emptyset Man nennt f eine Aufzählprozedur oder ein Aufzählverfahren von M. Sehr vereinfacht : aufzählbar = abzählbar + berechenbar

Somit muss für den Beweis der Aufzählbarkeit eine entsprechende Funktion f gefunden werden.

Menge der geraden Zahlen G

z.z. Die Menge G = \{g | g=2n , n \in \N\} ist aufzählbar.

Das Aufzählverfahren ergibt sich bereits aus der Definition von G.

f(n) = 2n

Menge der Primzahlen

$ f(n) = \begin{cases} n, & \text{wenn x eine Primzahl ist} ;\\ 2, & \text{sonst} \end{cases} $

A^*

Aufbauschema:

Aufbauprozedur:

function aStern(n,alphabet){
if(n==0){
return "";
}
var array = [];
while(array.length<n){
array=createNextSet(array,alphabet);
}
return array[n-1];
}

function createNextSet(array,alphabet){
var result = [];
if(array.length==0){
result = ["a","b","c"];
return result;
}
for(i=0;i<array.length;i++){
 for(j=0;j<alphabet.length;j++){
 result.push(array[i].concat(alphabet[j]));
 }
}
return array.concat(result);
}

aStern(12,["a","b","c"])

jede endliche Menge

Per Definition ist jede endliche Menge abzählbar. Weiterhin gibt es für jede endliche Menge M eine surjektive total berechenbare Funktion f, mit f : N -> M.

Menge G der Gitterpunkte

???? (0,0),(0,1),...

Geben Sie eine Funktion f an, die N bijektiv auf G abbildet. 2 Definieren Sie eine Ordnungsrelation p < in G . 3 Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y ) des betrachteten Gitterpunktes (x, y ) an. 4 Geben Sie eine Aufz ̈ahlprozedur f ̈ ur G an und begr ̈ unden Sie deren Berechenbarkeit.

Semi Entscheidbarkeit

Halteproblem

Sei A die Menge aller Algorithmen, dann gibt es eine Funktion \chi'_A die wahr zurückgibt, wenn ein Algorithmus terminiert.

\chi'_{A}(a) = \begin{cases} wahr, & \text{wenn a terminiert};\\ \bot, & \text{sonst} \end{cases}

FIBS

Aufzählfunktion $\fib(n) = \begin{cases} 1, & \text{wenn n==1 oder n==0};\\

fib(n-1)*fib(n-2), & \text{sonst}

\end{cases} $

FIBS Entscheidbar?

\chi'_{FIBS}(f) = \begin{cases} wahr, & \text{wenn f in FIBS};\\ falsch, & \text{sonst} \end{cases}

Die Menge ist entscheidbar, da die Charakteristische Funktion berechenbar ist.

function fib(n){
if(n==0||n==1){return 1;}
else{return fib(n-1)+fib(n-2);}
}

function chiFIBS(zahl){
var count = 0;
var running = true;
while(running){
 if(fib(count)==zahl){return true;}
 if(fib(count)>zahl){return false;} //Abbruchbedingung. zahl kann in diesem Fall nicht mehr gefunden werden.
 count = count +1;
}

}

//ACHTUNG rekursive quick&dirty Implementierung von fib. Keine großen Zahlen nehmen!
chiFIBS(10)

Aus der Entscheidbarkeit folgt die semi Entscheidbarkeit.

Quadratzahlen

Aufzählfunktion

f(n)=n^2

$ \chi_{QZ}(n) = \begin{cases} wahr, & \text{wenn } sqrt(n) \in \N;\\ falsch, & \text{sonst} \end{cases} $

Wörter, die mit a beginnen

Aus Entscheidbarkeit folgt die Semi Entscheidbarkeit.

Vereinigung

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.

function even(n){
return 2*n;
}

function unEven(n){
return 3*n;
}

function printSet(numberOfItems,buildFunction){
var result = [];
for (i = 0; i < numberOfItems; i++){ 
  result.push(buildFunction(i));
 }
return result;
}

printSet(15,even);
printSet(15,unEven);