J'allais poster ceci comme une réponse, mais cela ne répond pas à toute votre question: le complément de n'importe quelle CFL est R (récursif), car les langues récursives sont fermées sous complément et toutes les CFL sont R.
Eric
CFL n'étant pas fermé sous complémentation ne signifie pas qu'un «L» étant dans CFL signifie que son complément n'est pas dans CFL. Cela signifie simplement qu'il existe un «L» dans la LCF tel que son complément ne se trouve pas dans la LCF
SHREYANSHU THAKUR
@Eric Le demandeur sait déjà que le complément de n'importe quelle LFC est récursif. Ils ont fait la plus forte déclaration que le complément de toute CFL est en P .
David Richerby
Réponses:
17
On peut comprendre votre question de deux manières, selon la définition de "le complément de CFL".
cas A: le complément de CFL est la classe de toutes les langues qui ne sont pas en CFL. Formellement,
Dans ce cas, est bien plus grand que , il a même des langages qui ne sont pas en , etc. Mais peut-être que ce n'est pas ce que vous vouliez dire.
CFL¯¯¯¯¯¯¯¯¯¯¯={L∣L∉CFL}.
CFL¯¯¯¯¯¯¯¯¯¯¯PR
cas B: définir la classe complément-CFL comme
en mots, l'ensemble de toutes les langues , de telle sorte que le complément de soit hors contexte .
coCFL={L¯∣L∈CFL},
LL
Dans ce cas, ce que vous avez écrit est logique:
(par l'algorithme CYK ), et également (exécutez le même algorithme, affichez la réponse opposée), et puisque , alors il devrait être immédiat que , non?CFL⊊PcoCFL⊆PCFL≠coCFLcoCFL⊊P
définition de CFK pour autant que je le comprenne: le langage L est en coCFK si et seulement si le complément de L est en CFK. Par complément de LI, on entend toutes les chaînes possibles sauf les chaînes en L. Le problème, je pense, est que le complément ne peut pas être défini comme "exécuter le même algorithme et inverser la réponse" Par exemple: L = (x ^ iy ^ iz ^ i) n'est pas CFL, mais je ne sais pas quel algorithme je peux exécuter pour obtenir la réponse (négative).
user432
1
vous faites donc référence au cas B. Notez que le complément d'un CFL peut ne pas être CFL, mais cela ne signifie pas que l'algorithme CYK ne fonctionne pas de la même façon. Je veux dire, nous exécutons le CYK sur , ce qui est de la LCF, et d' obtenir une réponse pour chaque si oui ou non il est dans . l'opposé de cela est la réponse à la question de savoir si est ou non dans , même si peut être non-CFL. LL¯¯¯¯xL¯¯¯¯L LxLL
Ran G.
1
@ user432 ! coCFL≠CFL¯¯¯¯¯¯¯¯¯¯
Raphael
1
@RanG est votre standard de notation ici? Je m'attendrais à et ¯ C F L = la classe des langages L tels que L ∉ C F L . coCFL={L:L¯∈CFL}CFL¯¯¯¯¯¯¯¯¯¯¯=LL∉CFL
usul
1
En fait, permettez-moi de changer la notation selon votre suggestion, cela aura plus de sens.
Ran G.
3
Une classe robuste qui contient à la fois CFL et coCFL est LOGCFL , qui contient toutes les langues réductibles dans l'espace de journalisation en une langue sans contexte. Cette classe est intermédiaire entre NL et AC1 et présente des problèmes complets naturels. Il peut également être défini en termes de circuits AC1 restreints. LOGCFL est fermé sous complément (c'est une extension de l'argument utilisé pour montrer que NL = coNL).
Le complément de CFL pourrait éventuellement être CFL mais pas nécessairement. Le complément de CFL est à la fois récursif (R) et récursivement énumérable (RE). Pourquoi? Toutes les LFC sont à la fois R et RE. Les langues R sont fermées sous complément (mais RE ne le sont pas). Dans ce contexte, le complément de CFL est R qui est intrinsèquement RE.
Le demandeur a déjà dit qu'ils savent que le complément de toute PCP est en P . C'est une affirmation beaucoup plus forte que c'est récursif ou RE. C'est comme si le demandeur a mentionné une personne qui ne peut pas marcher et vous avez répondu avec une preuve qu'il ne peut pas courir à la vitesse du son.
Réponses:
On peut comprendre votre question de deux manières, selon la définition de "le complément de CFL".
cas A: le complément de CFL est la classe de toutes les langues qui ne sont pas en CFL. Formellement, Dans ce cas, est bien plus grand que , il a même des langages qui ne sont pas en , etc. Mais peut-être que ce n'est pas ce que vous vouliez dire.
cas B: définir la classe complément-CFL comme en mots, l'ensemble de toutes les langues , de telle sorte que le complément de soit hors contexte .
Dans ce cas, ce que vous avez écrit est logique: (par l'algorithme CYK ), et également (exécutez le même algorithme, affichez la réponse opposée), et puisque , alors il devrait être immédiat que , non?CFL⊊P coCFL⊆P CFL≠coCFL coCFL⊊P
la source
Une classe robuste qui contient à la fois CFL et coCFL est LOGCFL , qui contient toutes les langues réductibles dans l'espace de journalisation en une langue sans contexte. Cette classe est intermédiaire entre NL et AC1 et présente des problèmes complets naturels. Il peut également être défini en termes de circuits AC1 restreints. LOGCFL est fermé sous complément (c'est une extension de l'argument utilisé pour montrer que NL = coNL).
la source
Le complément de CFL pourrait éventuellement être CFL mais pas nécessairement. Le complément de CFL est à la fois récursif (R) et récursivement énumérable (RE). Pourquoi? Toutes les LFC sont à la fois R et RE. Les langues R sont fermées sous complément (mais RE ne le sont pas). Dans ce contexte, le complément de CFL est R qui est intrinsèquement RE.
la source