BuK/IIm12/Studenten/siclsche/Thema3

Wiki-Quelltext dieser Seite.

<language>Java</language>
== Aufgabe 1 ==
Wie viele berechenbare charakteristische Funktionen gibt es?

''Hinweis: Potenzmenge unendlicher Mengen''

Zu jeder Teilmenge der Menge $A*$ existiert eine charakteristische Funktion. Daher gibt es so viele charakterisitsche Funktionen, wie es Teilmengen gibt. Sämtliche Teilmengen einer Menge $M$ sind in der Potenzmenge von $M$ enthalten. Da die Potenzmenge einer unendlichen Menge überabzählbar unendlich viele Elemente besitzt, gibt es demzufolge ebenfalls überabzählbar unendlich viele charakteristische Funktionen.

== Aufgabe 2 == 
'''Beispiel 1:'''

M ist die Menge aller Wörter aus $A^*$, die die Länge 3 besitzen, d.h.:

$A^* = \{a, b\}^* \text{ und } M \subset A^* = \{w \mid w \in A^*\text{ und } |w| = 3\}$

* bei diesem Beispiel handelt es sich um eine endliche Menge
** somit kann jedes Element der Menge mit dem gesuchten Element verglichen und eine Entscheidung getroffen werden
* die entsprechende charakteristische Funktion dazu ist: $
\chi_M(w) = \begin{cases}
wahr, & \text{wenn } w \in M;\\
falsch, & \text{sonst}
\end{cases}
$


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

$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen: $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion
<code id="516bb99f33ff3">
public enum SubsetEnum {
	ODD,EVEN,WORDLENGTH,EXPRESSION
}
</code>

<code id="516bb99f3405f">
public class Subset {
	private WordAmountStream stream;//alle n (< maxWordDisplay) Wörter aus A* 
	private int maxWordToDisplay; 
	private int wordlength = 3; // Wörter mit der Länge 3
	private String containExpression ="[a].*?";  // Wörte die mit a beginnen
	
	public Subset (int maxWordtoDisplay, ArrayList<String> alphabet){
		stream = new WordAmountStream(alphabet);
		this.maxWordToDisplay = maxWordtoDisplay;
	}
	
	public ArrayList<String> getSubset(SubsetEnum subset){
		if(subset.equals(SubsetEnum.WORDLENGTH)){
			return subsetWordlength();
		}
		if(subset.equals(SubsetEnum.EXPRESSION)){
			return subsetExpression();
		}
		
		if(subset.equals(SubsetEnum.EVEN)){
			return null;
		}
		if(subset.equals(SubsetEnum.ODD)){
			return null;
		}
		return null;
	}
	
	private ArrayList<String> subsetExpression(){
		ArrayList<String> result = new ArrayList<String>();
		ArrayList<String> words=stream.getWordAmount(maxWordToDisplay);
		for(String word :words){
			if(word.matches(containExpression)){
				result.add(word);
			}
		}
		return result;
	}

	private ArrayList<String> subsetWordlength(){
		ArrayList<String> result = new ArrayList<String>();
		ArrayList<String> words=stream.getWordAmount(maxWordToDisplay);
		for(String word :words){
			if(word.length() == wordlength){
				result.add(word);
			}
		}
		return result;
	}
	
}
</code>
[[BuK/IIm12/Studenten/siclsche/Thema3/wordAmount|WordAmount.java]], [[BuK/IIm12/Studenten/siclsche/Thema3/MyStack|MyStack.java]]

== Aufgabe 3 ==
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

== Aufgabe 4 ==
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

== Aufgabe 5 ==
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.

== Aufgabe 6 ==
Zeigen Sie, dass jede endliche Menge M aufzählbar ist.

== Aufgabe 7 ==
Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.

1. Geben Sie eine Funktion f an, die $\N_0$ 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ählprozedur für G an und begründen Sie deren Berechenbarkeit.

== Aufgabe 8 ==
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

== Aufgabe 9 ==
Geben Sie fur 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.

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

== Aufgabe 11 ==
Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.

== Aufgabe 12 ==
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.