Frage zur Notation einer nicht-kontextfreien Sprache

Wissenschaft Informatik
#1

Hallo,

für eine Übung in Theoretischer Informatik soll ich nachweisen, dass diese Sprache nicht kontextfrei ist:

Bildschirmfoto vom 2020-06-30 23-26-48
Kann mir jemand erklären, was das bedeuten soll?
Bis zu dem Kleene-Stern verstehe ich (Irrtum nicht ausgeschlossen):

L sei eine Sprache mit Wörtern, die Elemente endlicher Sequenzen sind, die aus den Symbolen j und a bestehen.

Danach verstehe ich nicht weiter.

Der Betrag eines Wortes w mit Index j entspricht 2 potenziert mit dem Betrag des Wortes w mit Index a?

Kann mir das jemand in eine natürliche Sprache (vorzugsweise Deutsch) übersetzen?

LG Majoogily

#2

Ich kenne die Notation nicht, aber ich interpretiere mal:

|w|x := Anzahl der Auftreten des Symbols x in w

Hier also: „Anzahl der j in w gleich 2 hoch Anzahl der a in w“

jajjaj oder ajj oder jaj oder aaajjjjjjjj sind z.B. in L

Das sieht mir sehr nach einem Fall für das Pumping-Lemma für KfS aus :nerd_face:

1 Like
#3

Genau so ist es. :sunglasses:

Danke für die Antwort! :slight_smile:

#4

Dieses Thema wurde automatisch 30 Tage nach der letzten Antwort geschlossen. Es sind keine neuen Nachrichten mehr erlaubt.