Existe-t-il un DCFL le plus difficile?

Greibach célèbre défini un langage , que l'on appelle la version non - déterministe de , de telle sorte que toute la LCF est une image inverse de morphique . Existe-t-il une déclaration similaire avec DCFL, éventuellement avec une certaine restriction sur les morphismes autorisés? $H$ $D_2$ $H$

(Voir, par exemple, M. Autebert, J. Berstel et L. Boasson. Langages sans contexte et automates de refoulement. Dans R. Rozenberg et A. Salomaa, éditeurs, Handbook of Formal Languages, volume I, chapitre 3. Springer Verlag , 1997.)

fl.formal-languages open-problem context-free nondeterminism hard-instances Michaël Cadilhac
la source

Réponses:

Une caractérisation homomorphique identique du DCFL ne semble pas possible. Ce qui suit est extrait de l' article original de Greibach .

Nous montrons que tout langage sans contexte peut être exprimé comme ou pour un homomorphisme . L'énoncé algébrique est le suivant: la famille des langages sans contexte est un AFDL principal; ... En revanche, la famille des langages déterministes sans contexte n'est pas un AFDL principal [7]. $h^{-1}(L_0)$ $h^{-1}(L_0-\{e\})$ $h$

Le document 7 est la version conférence du document. Dans la version conférence, le théorème 4.2 déclare que "la famille des langages déterministes sans contexte n'est pas un AFDL principal".

Cependant, une caractérisation analogique peut encore être possible. Okhotin a fourni des caractérisations homomorphes des grammaires conjonctives et booléennes. Pour DCFL, le problème semble être ouvert. Ce qui suit est la conclusion de l'article d'Okhotin (de 2013).

Chaque famille de langues fermées sous des homomorphismes inverses peut potentiellement avoir un analogue de la caractérisation homomorphique inverse de Greibach. La question est, quelles familles l'ont? Pourrait-il exister pour des variantes linéaires, déterministes ou non ambiguës de grammaires ordinaires (hors contexte)? Pourrait-il y avoir une telle caractérisation pour les grammaires conjonctives linéaires, les grammaires conjonctives non ambiguës, etc.?

Mateus de Oliveira Oliveira
la source

Merci! Cependant, je sais que le DCFL n'est pas principal; c'est pourquoi je permets de restreindre les morphismes si nécessaire - je peux exprimer plus précisément ma question comme: quelle est la plus petite classe de fonctions F pour laquelle il existe un langage H où F (H) est l'ensemble de tous les DCFL - donner ou prendre des fermetures supplémentaires.

Michaël Cadilhac

D'accord. J'ai édité ma réponse. Il semble que pour DCFL c'est un problème ouvert.

Mateus de Oliveira Oliveira

Curieusement, je connais très bien l'article d'Okhotin, mais je n'ai pas remarqué qu'il faisait explicitement référence au problème! Eh bien, je ne sais pas quoi faire ici; Bien sûr, c'est une réponse valable pour le moment , mais devrait-elle rester ouverte jusqu'à ce qu'elle soit résolue?

Michaël Cadilhac

Je ne sais pas quelle est la police du site pour demander des solutions aux problèmes ouverts et difficiles. Personnellement, si quelqu'un me montrait qu'un problème qui m'intéresse est ouvert depuis de nombreuses années, j'accepterais la réponse. À mon avis, dans ce cas, il est plus approprié de considérer la question comme une demande de référence. Mais il peut y avoir des points de vue divergents à ce sujet. Je pense que cette discussion dans meta.cstheory pourrait être utile meta.cstheory.stackexchange.com/questions/1058/…

Mateus de Oliveira Oliveira

Bien sûr, cela ne me dérange pas que vous acceptiez votre réponse. En effet, c'est une réponse très intéressante. Cependant, bien que la réponse corresponde en quelque sorte au titre, elle est très différente de la question elle-même, car les réductions d'espace de journalisation sont beaucoup plus puissantes que les homomorphismes.

Mateus de Oliveira Oliveira

Il y a en fait un DCFL le plus dur, qui est une version déterministe de Greibach; il a été introduit par Sudborough en 78 dans On langages sans contexte déterministes, les automates multi-têtes et la puissance d'un magasin auxiliaire déroulant - il s'agit cependant de la réduction la plus difficile de l'espace de journalisation. La langue qui y est référencée est l'ensemble des mots sur où: $L_0^{(2)}$ $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$

γ_{0} [\bar{a} γ_{a}^{(1)} # \bar{b} γ_{b}^{(1)}] \dots [\bar{a} γ_{a}^{(k)} # \bar{b} γ_{b}^{(k)}],

$\gamma_0\;[\bar{a}\gamma_a^{(1)}\#\bar{b}\gamma_b^{(1)}]\;\cdots\; [\bar{a}\gamma_a^{(k)}\#\bar{b}\gamma_b^{(k)}]\enspace,$

avec mots sur , de sorte qu'il existe un mot with un mot Dyck. $\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ $\{a, \bar{a}, b, \bar{b}\}$ $w_1w_2\cdots w_k \in \{a, b\}^k$ $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots \bar{w_k}\gamma_{w_k}^{(k)}$

Il considère alors que est un DCFL et que tout espace de journalisation DCFL se réduit à . En ce sens, est la bande DCFL la plus dure. $L_0^{(2)}$ $L_0^{(2)}$ $L_0^{(2)}$

Comme l'a mentionné le contributeur Mateus de Oliveira Oliveira, le DCFL n'est pas un AFL principal, et on ne sait pas s'il existe une caractérisation exacte impliquant la fermeture d'une seule langue dans certaines opérations.

Michaël Cadilhac
la source

Le papier

J.-M. Autebert, Une note sur le cylindre des langages déterministes, Théorie informatique 8 (1979), 395-399

donne une brève preuve du résultat suivant (crédité à Greibach) qui semble répondre à votre question:

il n'y a pas de langue déterministe sans contexte tel que, pour toutes les langues déterministe sans contexte , il y a un homomorphisme et un langage régulier tel que . $L$ $C$ $h$ $R$ $C = h^{-1}(L)\cap R$

J.-E. Épingle
la source