Este idioma é livre de contexto?

Dica:

sim

Solução:

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

e, portanto, o complemento é que é livre de contexto, pois você pode escrever facilmente um PDA não determinístico.

${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
fonte

Ooohhh! * facepalm * Talvez você queira adicionar o truque central de design; pode não ser óbvio para o novato.

Raphael

Não entendo, pensei que o complemento de uma CFL não fosse a CFL em geral. Obrigado

Andrés Felipe Téllez Crespo

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

$\{(a^n b^n)^n\}$ não é livre de contexto, mas seu complemento é.

Sdcvvc

@ AndrésFelipeTéllezCrespo: O complemento de uma CFL nem sempre é CFL (portanto, nenhuma propriedade de fechamento), mas ninguém diz que não há CFL cujo complemento é CFL. Em particular, todos os complementos de todas as linguagens regulares são livres de contexto (porque são regulares).

Raphael

Idiomas semelhantes a - uma disjunção finita de condições adequadas - podem ser resolvidos usando o não-determinismo: adivinhe a condição violada e verifique se ela é violada (ignore o resto).

L

$L$

Raphael

Este idioma é livre de contexto?

Respostas: