Décidabilité de l'égalité des CFL

Le problème suivant est décidable:

Étant donné une grammaire sans contexte , ? $G$ $L(G) = \varnothing$

Le problème suivant est indécidable:

Étant donné une grammaire sans contexte , ? $G$ $L(G) = A^{\ast}$

Existe-t-il une caractérisation des langages sans contexte avec une égalité décidable ? $M$ $L(G) = M$

computability fl.formal-languages sdcvvc
la source

Crosspost de math.SE .

sdcvvc

Par exemple, il est décidable lorsque

est fini (facile), lorsque

(par le théorème de Parikh) ou lorsque

(par Parikh et en vérifiant l'intersection avec le complément de

)

M

$M$

M = {a}^{*}

$M = \{a\}^{\ast}$

M = {a^{n} b^{n}}

$M = \{a^n b^n\}$

a^{*} b^{*}

$a^{\ast} b^{\ast}$

sdcvvc

Savez-vous si l'ensemble des CFG

st étant égal à

est décidable, est décidable lui-même? Quel type de caractérisation recherchez-vous? Voulez-vous une liste "simple" de propriétés qui couvrira tous les cas?

G

$G$

L (G)

$L(G)$

Kaveh

Je pense que c'est exactement la question.

domotorp

@Kaveh: Je ne sais pas si cet ensemble est décidable, bien qu'il semble que ce ne soit pas le cas. La meilleure réponse serait soit des conditions «simples» couvrant tous les cas, soit des exemples montrant que le phénomène est trop complexe. C'est un peu vague, mais je pense que c'est responsable.

sdcvvc du

Réponses:

Je ne suis pas sûr qu'il existe une caractérisation générale de l'équivalence, mais les articles suivants de Hopcroft et Hunt et Rosenkrantz resp. pourrait être un bon début:

John E. Hopcroft, Sur les problèmes d'équivalence et de confinement pour les langages sans contexte, Theory of Computing Systems 3 (2): 119-124, doi: 10.1007 / BF01746517 ;
Harry B. Hunt, III et Daniel J. Rosenkrantz, On Equivalence and Containment Problems for Formal Languages, Journal of the ACM 24 (3): 387--396, 1977, doi: 10.1145 / 322017.322020 .

Hopcroft montre notamment que, si est régulier, alors est décidable si est borné, c'est-à-dire qu'il existe mots st . $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$

Sylvain
la source

-2

Désolé de faire apparaître un ancien fil. Mais voici quelque chose qui pourrait être pertinent.

Soit pCFL la classe des LFC fermées par permutation. Le problème d'égalité pour pCFL est décidable.

$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 "La complexité des ensembles semi-linéaires": http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#

Cela soulève une question à laquelle j'aimerais connaître la réponse: est-il possible de décider si un langage sans contexte donné est fermé par permutation?

Shane Steinert-Threlkeld
la source

Ce n'est pas une réponse à la question d'origine, mais une question distincte (bien que liée). Vous devriez demander comme il est propre question (avec un dos de lien vers cette question) soit ici ou sur CS.SE .

Artem Kaznatcheev

Oui, veuillez supprimer cette réponse et la republier en tant que nouvelle question (avec un lien vers celle-ci)

Suresh Venkat

@SureshVenkat, il semble que l'utilisateur pose cette question à la fin de cette question . Alors peut-être qu'une nouvelle question n'est pas nécessaire.

Artem Kaznatcheev

pCFL

$\textbf{pCFL}$