Cette langue est-elle sans contexte?

Est la langue

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

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

sans contexte? Je crois que la réponse est que ce n'est pas une LFC, mais je ne peux pas le prouver par le lemme d'Ogden ou le lemme de pompage.

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

Crossposted sur math.SE ; s'il vous plaît ne faites pas ça! Avez-vous vérifié la question que je vous ai indiquée? Veuillez inclure vos tentatives et pourquoi elles ont échoué.

Raphael

Le théorème de Parikh fonctionne pour mais pas pour ; malheureusement, . Même le lemme d'échange semble être rempli. Wow, méchant.

{(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

Allusion:

Oui

Solution:

${(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} \}$

et donc le complément est qui est sans contexte car vous pouvez facilement écrire un PDA non déterministe.

${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
la source

Ooohhh! * facepalm * Peut-être que vous voulez ajouter l'astuce de conception centrale; cela pourrait ne pas être évident pour le novice.

Raphael

Je ne comprends pas, je pensais que le complément d'une CFL n'était pas CFL en général. Merci

Andrés Felipe Téllez Crespo

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

$\{(a^n b^n)^n\}$ n'est pas sans contexte, mais son complément l'est.

sdcvvc

@ AndrésFelipeTéllezCrespo: Le complément d'une CFL n'est pas toujours CFL (donc pas de propriété de fermeture) mais personne ne dit qu'il n'y a pas de CFL dont le complément est CFL. En particulier, tous les compléments de toutes les langues régulières sont sans contexte (car ils sont même réguliers).

Raphael

Des langages similaires à - une disjonction finie de conditions appropriées - peuvent être résolus en utilisant le non-déterminisme: devinez la condition violée et vérifiez qu'elle est violée (ignorez le reste).

L

$L$

Raphael

Cette langue est-elle sans contexte?

Réponses: