BuK/IIm11/Studenten/sidatasc/ue3

Wiki-Quelltext dieser Seite.

== Übung 3 ==

=== Aufgabe 2 ===

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki). 

'''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^* \} $ .