Betrachten Sie ein einelementiges Alphabet \( \Sigma \) und eine unendliche kontextfreie Sprache \( L \) über \( \Sigma \).
(a) Denken Sie an das Pumping Lemma für kontextfreie Sprachen und spalten Sie \( L \) auf in eine endliche und eine unendliche Menge \( L_{\infty} \).
(b) Zeigen Sie, dass die unendliche Menge als endliche Vereinigung von regulären Mengen dargestellt werden kann.
(c) Nutzen Sie das letzte Resultat und zeigen Sie, dass eine Sprache über einem einelementigen Alphabet genau dann kontextfrei ist, wenn sie regulär ist.
