0 Daumen
107 Aufrufe

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community