Entscheidbarkeit der Gleichheit der CFLs

Das folgende Problem ist entscheidbar:

Bei einer kontextfreien Grammatik ist L ( G ) = ∅ ?$G$$L(G) = \varnothing$

Das folgende Problem ist unentscheidbar:

Bei einer kontextfreien Grammatik ist L ( G ) = A * ?$G$$L(G) = A^{\ast}$

Gibt es eine Charakterisierung kontextfreier Sprachen mit entscheidbarer Gleichheit L ( G ) = M ?$M$$L(G) = M$

Ich bin nicht sicher, ob es eine allgemeine Charakterisierung für die Äquivalenz gibt, aber die folgenden Arbeiten von Hopcroft, Hunt und Rosenkrantz resp. könnte ein guter Anfang sein:

• John E. Hopcroft, Zu den Äquivalenz- und Eindämmungsproblemen für kontextfreie Sprachen, Theory of Computing Systems 3 (2): 119-124, doi: 10.1007 / BF01746517 ;
• Harry B. Hunt, III und Daniel J. Rosenkrantz, Über Äquivalenz- und Eindämmungsprobleme für formale Sprachen, Journal of the ACM 24 (3): 387-396, 1977, doi: 10.1145 / 322017.322020 .

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

Tut mir leid, einen alten Thread aufzurufen. Aber hier ist etwas, das relevant sein könnte.

Sei pCFL die Klasse der permutationsgeschlossenen CFLs. Das Gleichstellungsproblem für pCFL ist entscheidbar.

$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 "Die Komplexität semilinearer Mengen": http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#

Dies wirft eine Frage auf, auf die ich die Antwort wissen möchte: Ist es entscheidbar, ob eine bestimmte kontextfreie Sprache permutationsgeschlossen ist?