0 Daumen
685 Aufrufe

Hallo :) Die Aufgabe lautet :

Sei L die Sprache L={a^n | n ist keine Primzahl} über dem Alphabet ={a}.

Ist L kontextfrei ? Beweisen sie ihre Antwort.

Ich bin wirklich ratlos, wäre euch wirklich dankbar, wenn jemand antworten würde.

Danke im Voraus !

von

Hast Du schon einen Ansatz? Weißt Du, dass hier das Pumping-Lemma für kontextfreie Sprachen brauchst?

Nun ja, das Pumping-Lemma hilft nur dann, wenn es sich nicht um eine kontextfreie Sprache handelt.

das Pumping-Lemma hilft nur dann

Das Pumping-Lemma für kontextfreie Sprachen.

wenn es sich nicht um eine kontextfreie Sprache handelt.

Richtig. Zu evaluieren, ob es hier tatsächlich nötig ist oder nicht, ist Teil der Aufgabe. Besagtes Lemma sollte jedoch ein Begriff sein. Vor allem, wenn man (wie ich annehme) zuvor gezeigt hat, dass L={a^n | n ist eine Primzahl} nicht kontextfrei ist.

@Gast: Schau mal bei den "ähnlichen Fragen." Bei https://www.stacklounge.de/2238/zeige-mit-dem-pumping-lemma-dass-die-sprache-nicht-regular-ist z.B. ist im Kommentar ein Video verlinkt, das offenbar das Problem behandelt.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community