Si

9

Je suis coincé à résoudre le prochain exercice:

Faire valoir que si est sans contexte et R est régulier, alors L / R = { w x RLR (c'est-à-dire lebon quotient) est sans contexte.L/R={wxRs.twxL}

Je sais qu'il devrait exister un PDA qui accepte et un DFA qui accepte R . J'essaie maintenant de combiner ces automates à un PDA qui accepte le bon quotient. Si je peux construire ça, j'ai prouvé que LLR est sans contexte. Mais je suis coincé à construire ce PDA.L/R

Voilà jusqu'où je suis arrivé:

Dans le PDA combiné, les états sont un produit cartésien des états des automates séparés. Et les bords sont les bords du DFA mais seulement ceux pour lesquels à l'avenir un état final du PDA d'origine de L peut être atteint. Mais je ne sais pas comment l'écrire officiellement.

Dommicentl
la source
Bienvenue! Où êtes-vous coincé exactement, quelle est votre approche?
Raphaël
1
Astuce: réfléchissez à la meilleure façon d'utiliser le non-déterminisme.
Artem Kaznatcheev
Dans le PDA combiné, les états sont un produit cartésien des états des automates séparés. Et les bords sont les bords du DFA mais seulement ceux pour lesquels à l'avenir un état final du PDA d'origine de L peut être atteint. Mais je ne sais pas comment le corriger formellement.
Dommicentl
3
J'ai copié votre commentaire dans la question. C'est un meilleur endroit pour ça.
Dave Clarke

Réponses:

8

Voici un indice.

Vous devez que votre machine accepte initialement une partie d'un mot de , consommant la bande au fur et à mesure. Ensuite, sans rien consommer, vous devez trouver un mot de R qui poussera la machine dans un état final. Le mot choisi de R joue le rôle du mot d'entrée pour la seconde moitié du calcul.LRR

De toute évidence, le non-déterminisme aura un rôle, tout comme le produit entre les deux machines. L'astuce pour formaliser cela consiste à ajuster le produit pour faire face au fait que l'entrée provient de non de l'entrée.R

Dave Clarke
la source
6

Je ne suis pas sûr de ce que vous voulez dire avec le produit cartésien; cela simule les deux automates en parallèle, ce qui vous donnera l'intersection. Mais vous voulez qu'il identifie tous les mots de qui ont un suffixe de R ! À un niveau intuitif, c'est.LR

Supposons que notre entrée soit . Evidemment, on ne peut pas vérifier toutes les suites possibles (pour l'appartenance à R ) mais seulement un nombre fini d'entre elles. Le commentaire d'Artem est très utile ici; nous devinons ce que sera le suffixe x et y exécuterons les deux automates.wΣRx

Soit et A R PDA pour L et NFA pour R , respectivement. Construisez un automate A comme suit. En entrée w Σ * , simuler A L . Après que w est consommé, passez à une intersection modifiée A L , si et seulement si les deux composantes de A L , R atteignent un état final simultanément, c'est-à-dire siALARLRAwΣALw de A L et A R ,maintenant l'état de A L . Maintenant, décidez pour chaque transition de façon non déterministe quel symbole est le suivant dans l'entrée virtuelle. AccepterwAL,RALARALwAL,R a une continuation x de telle sorte que w x de la L et x R .wxwxLxR

Vous pouvez également utiliser des grammaires formelles. Voyez-vous comment vous pouvez dériver en deux grammaires en parallèle? En général, il n'est pas clair comment adapter donc vous obtenez une poignée sur les suffixes; l'utilisation de la forme normale de Chomsky aide.GL

Supposons que et G R sont donnés sous forme normale de Chomsky. Modifiez G L de sorte que le non-terminal le plus à droite soit reconnaissable et faites de son symbole de départ le nouveau symbole de départ. Introduire pour les versions distinguées des non terminaux de nouvelles règles qui conduisent à une grammaire dérivée en G L et G RGLGRGLGLGR en parallèle (les non-terminaux sont des paires de non-terminaux); si les deux grammaires s'accordent sur un symbole terminal, supprimez le non-terminal composite. De cette façon, un suffixe dans est supprimé si et seulement s'il peut être dérivé dans G L et dans G RGLGLGR , il reste .wL/R

Raphael
la source
Notez que même ce qui se trouve dans les zones de spoiler n'est ni rigoureux ni formel. Veuillez me faire savoir si vous avez besoin de plus de détails (après l'avoir essayé vous-même).
Raphael
6

Je recommande d'utiliser la réponse de Raphaël, qui est beaucoup plus facile à comprendre, mais voici une alternative, en utilisant des propriétés de fermeture au lieu d'automates:

Soit une langue. Nous voulons lire un mot w , mais demandons à L si w x est dans la langue. Nous voulons donc créer un nouveau langage à partir de L qui a x "effacé". Nous pouvons le faire en utilisant un homomorphisme, mais cela pourrait supprimer des lettres de w . Solution: divisez l'alphabet en deux et utilisez des lettres différentes pour w et x .LAwLwxLxwwx

Plus formellement:

1) Créez de mots à partir de L , chaque lettre étant étiquetée 0 ou 1. 2) Intersectez-la avec un langage régulier ( A × 0 ) ( R × 1 ) . Cela force que tous les 0 viennent avant tout de 1, et la deuxième partie provient de R . La signification précise de × est laissée au lecteur. 3) Remplacer ( aL(A×{0,1})L
(A×0)(R×1)R×
(a,0)a et . Propriétés de fermeture utilisées: image homomorphe, pré-image, intersection avec des langages réguliers. Avantage: cette preuve fonctionne pour d'autres familles (par exemple, remplacez context-free par regular).(a,1)ε


sdcvvc
la source
1
Pour ce que ça vaut, la construction des automates évolue également vers d'autres classes: à aucun moment, nous n'utilisons réellement que est un PDA. AL
Raphael
Bon point.
sdcvvc
1
Techniquement, une telle classe (où cette preuve fonctionne) est appelée cône ou trio complet .
Hendrik Jan