BuK/IIm12/Studenten/siclsche/Thema3

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Wie viele berechenbare charakteristische Funktionen gibt es?

''Hinweis: Potenzmenge unendlicher Mengen''

<language>Java</language>
<language>Java</language>
<language>Java</language>
== 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\}$

'''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="516bb99f33eed" hidden>
public class MyStack <T> implements Iterable<T>{
	
	private ArrayList<T> stack = new ArrayList<T> ();

 	public MyStack(){
 		stack = new ArrayList<T> ();
 	}
 	
 	public MyStack(ArrayList<T> stack){
 		this.stack = stack;
 	}
 	
 	public void add(T element){
 		stack.add(element);
 	}
 	
 	public void push(T element){
 		stack.add(0, element);
 	}
 	
 	public T pop( ){
 		if(!stack.isEmpty()){
 			T element = stack.get(0);
 			stack.remove(0);
 			return element;
 		}
 		return null;
 	}
 	
 	public T getFirstElement(){
 		return stack.get(0);
 	}
 	
 	public int getSize(){
 		return stack.size();
 	}
 	
 	public boolean removeAt(int index) {
 		if(index < stack.size()){
 			stack.remove(index);
 			return true;
 		}
 		return false;
 	}
 	
 	public void overrideStack(ArrayList<T> element){
 		stack = new ArrayList<T>();
 	}
 	
 	public boolean isEmpty(){
 		return stack.isEmpty();
 	}
 	
 	public T getElementAt(int index){
 		return stack.get(index);
 	}
 	
    public Iterator<T> iterator()  { 
    	return new StackIterator();  
    }
    
    public String toString(){
    	String value = "";
    	for(T stackElement : stack){
    		value+=stackElement.toString()+";";
    	}
		return value;
    	
    }

    private class StackIterator implements Iterator<T> {
    	
    	private int count=0;  
        public boolean hasNext(){ 
        	if(count < stack.size()){
        		return true;
        	}
        	return false;
        	                  
        }
        
        public void remove() { 
        	throw new UnsupportedOperationException();  
        }

        public T next() {
            if (!hasNext()) {
            	throw new NoSuchElementException();
            }
            T element = stack.get(count);
            count++;
            return element;
        }
    }
 	
}</code>


<code id="516bb99f33ff3" hidden>
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>

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