Übung 7 G4

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Übung 7 G4

Beitrag von JanM »

Hi ich hab mal ne Frage:
in Übung 7 G4 b) heißt es: Folgern Sie hieraus, dass jede kontextfreie Sprache uber einem einelementigen Alphabet regulär ist.

In Übung 4 G3 b) wird gezeigt, dass die Sprache \(a^{n^2}\) nicht regulär ist.

Kann ich aus diesen Sätzen schließen, dass die Sprache \(L = \{a^{n^2} : n \ge 0\}\) nicht kontextfrei ist?

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: Übung 7 G4

Beitrag von JanM »

Ja ok hab mir die Frage selbst beantwortet. Es ist ja eigentlich klar, dass die Sprache dann auch nicht kontextfrei ist, da das PL für reguläre Sprachen und das PL für kontextfreie Sprachen eigentlich genau das selbe machen.( sehr leicht informell ausgedrückt)
Das Wort wird nur anders zerlegt und es wird etwas anderes "gepumpt". Aber da wir nur ein 1-elementiges Alphabet haben, ist die Zerlegung und das abgeänderte Pumpen gleich.
oder?
Mir ist klar, dass das ganze sehr informell ist.

Antworten

Zurück zu „Archiv“