BuK/IIm10/BuK-Übung03 G1

Wiki-Quelltext dieser Seite.

=Beweis=
==Aufgabenstellung==
Zeigen Sie, dass <math>\wp(A^*)</math> für ein beliebiges Alphabet <math>A</math> eine überabzählbar unendliche Menge ist.

==Lösung==
Um nachzuweisen, dass eine Menge abzählbar unendlich ist, muss eine bijektive Abbildung auf die natürlichen Zahlen möglich sein.

Für die Wortmenge <math>A^*</math> wurde in der [[BuK-Übung02_G1|letzen Übung nachgewiesen]], dass eine Abbildung möglich ist, die Wortmenge <math>A^*</math> über einem Alphabet <math>A</math> also abzählbar unendlich ist.

=Entscheidbarkeit endlicher Mengen=

==Aufgabenstellung==
Implementieren Sie eine Scheme-Prozedur <math>chi-endlich</math>, die eine natürliche Zahl n und eine Liste L nimmt und entweder <math>\#t</math> oder <math>\#f</math> zurück gibt, je nachdem ob <math>n \in L</math> oder <math>n \notin L</math> gilt. Stellen Sie für den Entwurf von <math>chi-endlich</math> die erforderlichen Hilfsprozeduren bereit.

==Lösung==

=Aufzählbarkeit=

==Aufgabenstellung==
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.

==Lösung==

=Semientscheidberkeit=
==Aufgabenstellung==
Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen relativ zur Menge der natürlichen Zahlen semi-entscheidet.

Hinweis: Implementieren Sie eine Prozedur für die (allgemeingültige) <math>\chi'_{M}</math> und wenden Sie sie auf die Menge (stream) der natürlichen Zahlen an. Überlegen Sie sich vor dem Aufruf genau, welche Ausgabe Sie erwarten.

==Lösung==