Decidibilidade da igualdade de CFLs

O seguinte problema é decidível:

Dada uma gramática livre de contexto , L ( G ) = ∅ ?$G$$L(G) = \varnothing$

O seguinte problema é indecidível:

Dada uma gramática livre de contexto , L ( G ) = A ∗ ?$G$$L(G) = A^{\ast}$

Existe uma caracterização de linguagens livres de contexto com igualdade decidível L ( G ) = M ?$M$$L(G) = M$

Não tenho certeza de que exista alguma caracterização geral para equivalência, mas os seguintes artigos de Hopcroft e Hunt e Rosenkrantz, respectivamente. pode ser um bom começo:

• John E. Hopcroft, Sobre os problemas de equivalência e contenção para linguagens sem contexto, Theory of Computing Systems 3 (2): 119-124, doi: 10.1007 / BF01746517 ;
• Harry B. Hunt, III e Daniel J. Rosenkrantz, Sobre problemas de equivalência e contenção para línguas formais, Journal of the ACM 24 (3): 387--396, 1977, doi: 10.1145 / 322017.322020 .

Hopcroft mostra em particular que, se é regular, então L ( G ) = M é decidível se M estiver delimitado, ou seja, existem n palavras w 1 , w 2 , … , w n st M ⊆ w ∗ 1 w ∗ 2 ⋯ w * n .$M$$L(G)=M$$M$$n$$w_1,w_2,\ldots,w_n$$M\subseteq w_1^\ast w_2^\ast\cdots w_n^\ast$

Desculpe abrir um tópico antigo. Mas aqui está algo que pode ser relevante.

Seja pCFL a classe de CFLs fechadas por permutação. O problema da igualdade para o pCFL é decidível.

$L$$\Sigma = \{ \sigma_1 , \dots , \sigma_n \}$$W_L = \{ \langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \mid w \in L\}$$W_L$$L$

$L$$w \in L$$\langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \in W_L$$L_1 , L_2$$L_1 = L_2$$W_{L_1} = W_{L_2}$

• Huynh 1980 "A complexidade dos conjuntos semilineares": http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#

Isso levanta uma questão para a qual eu gostaria de saber a resposta: é decidível se uma determinada linguagem livre de contexto é fechada por permutação?