ue3

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