Les DCFL sont-ils fermés en cas d'annulation?

Selon ce graphique , les DCFL sont fermés sous inversion.

Cependant, je ne suis pas convaincu que la preuve intuitive (inversant les flèches de la machine à états finis contrôlant et commutant les poussées et les pops) pour cela semble dépendre du non-déterminisme dans le choix de la transition nulle à prendre de l'état initial (depuis le le nouvel état initial contiendrait une transition nulle vers tous les anciens états finaux).

Cela rendrait le "PDA inversé" d'un DPDA non déterministe chaque fois qu'il y a plus d'un seul état final dans le DPDA d'origine.

Quelle est l'erreur dans mon argument? Ou existe-t-il une autre façon de prouver cela?

formal-languages context-free closure-properties pushdown-automata nondeterminism peteykun
la source

Veuillez me faire savoir si ma réponse StackOverflow nécessite une explication supplémentaire. Le problème avec votre tentative de preuve est le suivant: le PDA que vous construisez n'est pas le seul PDA pour la langue qu'il accepte. Il pourrait y en avoir d'autres, éventuellement arrivés différemment, qui sont déterministes. En particulier, les DCFL peuvent être acceptés par les PDA qui ne sont pas déterministes.

Patrick87

C'est vrai, c'est pourquoi je me rends compte que ce n'est pas du tout une "preuve", cela n'aurait de sens que si le résultat était toujours un DCFL, ce qui n'est pas le cas. Je suppose que j'essayais juste de le prouver en utilisant la même méthode que celle utilisée pour les langues régulières et j'ai échoué. Merci pour le contre-exemple!

peteykun

Considérer

L = b^{n} c^{n} \cap a b^{2} n c^{n}

$L={b^n c^n} \cap {a b^2n c^n}$

Pranav

Ce tableau indique également que les langues récursives sont fermées

λ

$\lambda$ -remplacement gratuit ... est-ce correct?

anir

Réponses:

J'ai recherché Hopcroft et Ullman 1979 et il est dit à la page 281 qu'il n'est pas fermé en cas d'inversion. Mais je n'ai trouvé aucune preuve dans mon regard très rapide sur le chapitre pertinent.

La recherche sur le web donne également une réponse négative, avec contre-exemple, sur stackoverflow par un membre de CS (notation adaptée):

$(a+b+c)^*WcW^R$ , où $W \in (a+b)^+$ ; ce n'est pas déterministe parce que vous ne savez pas où le $WcW$ peu commence.

$W^RcW(a+b+c)^*$ , où $W \in (a+b)^+$ ; c'est déterministe car vous pouvez écrire un PDA déterministe pour accepter des palindromes simples de la forme $W^RcW$ et modifier l'état d'acceptation pour boucler sur lui-même sur l'un des $a$ , $b$ et $c$ .

L'astuce ici est que les PDA doivent lire les entrées de gauche à droite.

babou
la source

Ceci est absurde. Patrick87 a fourni les exemples, @Raphael a fait la moitié du travail d'édition et je reçois le représentant. Ensuite, nous obtenons si peu pour le vrai travail ... :)

babou

Considérez-le comme une "commission de recherche" :) Je suis juste perplexe que le système fonctionne suffisamment bien pour que vous trouviez ce vieux poste. Le système fonctionne! Je vous salue SE!

Patrick87

H&U a-t-il négligé l'inversion pour DCFL? Ils mentionnent la non-fermeture sous union, la concaténation, Kleene, le morphisme dans Thm 10.5 voir l'exercice 10.4 (étoilé mais avec une solution). Cependant, ils notent

{0^{i} 1^{i} 2^{j} ∣ i, j} \cup {0^{i} 1^{j} 2^{j} ∣ i, j}

$\{ 0^i1^i2^j\mid i,j\} \cup \{ 0^i1^j2^j\mid i,j\}$ n'est pas DCFL, donc

K = {0^{i} 1^{i} 2^{j} a ∣ i, j} \cup {0^{i} 1^{j} 2^{j} b ∣ i, j}

$K = \{ 0^i1^i2^ja \mid i,j\} \cup \{ 0^i1^j2^jb\mid i,j\}$ par fermeture de DCFL sous quotient avec set régulier, Thm 10.2. Mais le renversement de

K

$K$ est un DCFL, les «marqueurs»

a

$a$ et

b

$b$ donner les informations sur l'utilisation du pushdown. [Peut-être @babou peut ajouter ceci s'il le souhaite; c'est lui qui collectionne les représentants ici :)]

Hendrik Jan