Ist diese Sprache kontextfrei?

Ist die Sprache

L. = {ein, b {}}}^{*} ∖ {({ein}^{n} b^{n})^{n} ∣ n \geq 1}}

$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$

kontextfrei? Ich glaube, dass die Antwort ist, dass es keine CFL ist, aber ich kann es nicht durch Ogdens Lemma oder Pumping Lemma beweisen.

formal-languages context-free pumping-lemma Andrés Felipe Téllez Crespo
quelle

Crossposted auf math.SE ; bitte tu das nicht! Haben Sie die Frage überprüft, auf die ich Sie hingewiesen habe? Bitte geben Sie Ihre Versuche an und warum sie fehlschlagen.

Raphael

Der Satz von Parikh funktioniert für

aber nicht für

; Leider ist

. Auch das Interchange-Lemma scheint erfüllt zu sein. Wow, böser.

{(a^{n} b^{n})^{n} ∣ n \geq 1}

$\{(a^nb^n)^n \mid n \geq 1\}$

L

$L$

Ψ_{{a, b}} [L] = N^{2}

$\Psi_{\{a,b\}}[L] = \mathbb{N}^2$

Raphael

Hinweis:

Ja

Lösung:

und daher ist das Komplement
${(a^{n} b^{n})^{n} ∣ n \geq 1} = {a^{n_{1}} b^{n_{2}} \dots a^{n_{2 k - 1}} b^{n_{2 k}}} : k \geq 1 \land n_{1} = k \land \forall i . n_{i} = n_{i + 1}}$ $\{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}\}: k \geq 1 \land n_1 = k \land \forall i. n_i = n_{i+1} \}$

ist kontextfrei, da Sie leicht einen nicht deterministischen PDA schreiben können. ${a, b}^{*} ∖ {(a^{n} b^{n})^{n} ∣ n \geq 1} = {a^{n_{1}} b^{n_{2}} \dots a^{n_{2 k - 1}} b^{n_{2 k}} : n_{1} \neq k \lor \exists i . n_{i} \neq n_{i + 1}}$ $\{a,b\}^{\ast} \setminus \{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}: n_1 \neq k \lor \exists i. n_i \neq n_{i+1}\}$

sdcvvc
quelle

Ooohhh! * facepalm * Vielleicht möchten Sie den zentralen Designtrick hinzufügen; es könnte für den Anfänger nicht offensichtlich sein.

Raphael

Ich verstehe nicht, ich dachte, dass die Ergänzung einer CFL im Allgemeinen keine CFL ist. Vielen Dank

Andrés Felipe Téllez Crespo

ist nicht kontextfrei, aber seine Ergänzung ist.

{(a^{n} b^{n})^{n}}

$\{(a^n b^n)^n\}$

SDCVVC

@ AndrésFelipeTéllezCrespo: Das Komplement einer CFL ist nicht immer CFL (also keine Closure-Eigenschaft), aber niemand sagt, dass es keine CFL gibt, deren Komplement CFL ist. Insbesondere sind alle Ergänzungen aller regulären Sprachen kontextfrei (weil sie sogar regulär sind).

Raphael

ähnliche Sprachen - eine endliche Disjunktion geeigneter Bedingungen - können mithilfe von Nichtdeterminismus gelöst werden: Erraten Sie die verletzte Bedingung und stellen Sie sicher , dass sie verletzt ist (ignorieren Sie den Rest).

L

$L$

Raphael

Ist diese Sprache kontextfrei?

Antworten: