Peut-il y avoir un lemme de pompage contextuel?

Une propriété de «pompage» (des mots d'une certaine longueur impliquent l'existence de boucles dans le mécanisme de définition de la langue) est connue pour exister pour les langues régulières et sans contexte et quelques autres (généralement utilisées pour réfuter l'appartenance d'une langue à une certaine classe). ).

Dans la discussion autour de cette question , la réponse de Daisy suggère qu'il ne peut pas y avoir de lemme de pompage pour les langages contextuels - car ils sont si complexes.

Est-ce vrai - peut-on montrer qu'il ne peut pas y avoir de propriété de pompage - et y a-t-il une bonne référence pour cela (ou contre cela)?

Voici quelques preuves qu'il n'y a pas de lemme de pompage pour les langages contextuels.

Bien sûr, une réponse dépend de la question de savoir ce qui constitue un lemme de pompage. La définition raisonnable la plus faible à laquelle je pourrais penser est la suivante: une classe de langage a un lemme de pompage s'il existe un prédicat ternaire décidable où veux dire:$\mathcal{C}$$P(\cdot,\cdot,\cdot)$$P(g,w,d)$

• $g$ est un mot codant une langue de (pensez: grammaire),$L(g)$$\mathcal{C}$
• $w$ est un mot dans la langue codée par$g$
• $d$ est un mot codant un calcul / dérivation pompable pour (pensez: calcul NFA avec état répété ou arbre de dérivation CFG avec non-terminal répété). Ici, pompable signifie: il existe une infinité de mots dans .$w$$L(g)$

De plus, nous voulons que, étant donné un langage dans codé par , pour chaque mot suffisamment long , il existe un mot tel que .$L$$\mathcal{C}$$g$$w\in L$$d$$P(g,w,d)$

Par exemple, le lemme de pompage pour les langages normaux donnerait lieu au prédicat " encode un NFA sans et encode un cycle qui répète un état et lit ". Pour des codages appropriés, cela satisfait clairement aux conditions ci-dessus.$g$$\varepsilon$$d$$w$

Montrons maintenant qu'un tel prédicat n'existe pas pour les langages contextuels.

Observez que si une classe de langue a un lemme de pompage, alors le problème de l'infini (étant donné une grammaire, génère-t-il un langage infini?) Est récursivement énumérable: étant donné un codage , nous pouvons énumérer les mots et et vérifier si . Si nous trouvons un tel , nous répondons «oui», sinon, nous continuons l'énumération.$g$$w$$d$$P(g,w,d)$$w,d$

Cependant, nous montrons que le problème de l'infini pour les langages contextuels n'est pas récursivement énumérable. Rappelons que est un niveau de la hiérarchie arithmétique qui inclut strictement les langages récursivement énumérables. Il suffit donc de prouver:$\Pi_2^0$

Affirmation : Le problème de l'infini pour les langages contextuels est -complete.$\Pi_2^0$

Il est bien connu que le problème de l'infini pour les langages récursivement énumérables est -complet (le plus souvent, on trouve la formulation que le problème de finitude est -complete). Il suffit donc de réduire ce dernier problème au problème de l'infini pour les langages contextuels.$\Pi_2^0$$\Sigma_2^0$

Étant donné un TM , nous construisons un LBA pour la langue Alors, est infini si est infini, ce qui complète notre preuve.$M$$A$

Mise à jour: J'ai essayé d'être plus clair. Mise à jour: exemple ajouté.