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

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