Démontrer que DPDA est fermé sous complément par construction

J'essaie depuis un certain temps de trouver une construction afin de pouvoir démontrer formellement qu'un PDA déterministe est fermé sous complémentation. Cependant, il arrive que chaque idée que j'ai a quelque chose qui ne correspond pas à la fin. Pourriez-vous me donner un coup de main?

Le principal problème se produit avec les mouvements ε . Un PDA pourrait terminer la lecture de son entrée dans un état non final (état de rejet) mais peut toujours passer à un état final (acceptation) par un mouvement ε et finir par accepter la chaîne. Cela signifie que simplement ajouter un état mort et compléter les états ne fonctionne pas. J'ai déjà résolu le problème d'éventuelles séquences infinies de mouvements ε , ce qui n'est pas une partie principale de ma question.

EDIT: Pour autant que je comprends, si le DPDA atteint la fin de l'entrée et est dans un état d'acceptation et passe à un état de rejet par un mouvement ε, il l'accepterait toujours (car il a atteint un état final sans symbole d'entrée laissé à lis).

Veuillez me faire savoir si je peux être plus clair.

Je n'ai pas eu le temps d'écrire cela auparavant mais j'ai trouvé une réponse. Voici ce que j'ai fait:

Soit le origine . Nous allons construire un nouveau , appelons-le ( signifie modifié).$O$$PDA$$PDA$$M$$M$

Pour trouver le complément de , nous pouvons inverser les états finaux en états non finaux et vice-versa. C'est la même procédure que pour les automates finis. Cependant, il y a une subtilité. Le problème principal est que dans le PDA l'entrée peut conduire à un état qui n'est pas un état final mais pourrait effectuer un et atteindre un état acceptant . Le basculement des états, comme mentionné ci-dessus, ferait que termine par avec l'entrée qui serait un état final (obligeant à accepter d'accepter l'entrée) même s'il fera plus tard un vers$O$$O$$w$$S$$\epsilon-move$$S'$$M$$S$$w$$M$$\epsilon-move$$S'$, un état non acceptant. Par conséquent, et accepteront tous les deux . Quelque chose de similaire se produit si était un état final et un état non final accessible depuis via un .$O$$M$$w$$S$$S'$$S$$\epsilon-move$

Afin de surmonter ce problème, nous devons nous assurer que tous les mouvements se produisent avant de lire le symbole suivant. Autrement dit, nous n'entrerons dans un état de lecture que lorsqu'un chemin de -moves est suivi et nous atteindrons un état qui n'a pas de -move disponible. Nous appelons ces derniers états des états de lecture , car ils ont besoin d'un symbole réel pour effectuer une nouvelle transition.$\epsilon$$\epsilon$$\epsilon$

Définissez les états de comme des tuples de la forme où ( est l'ensemble des états du origine ) et .$M$$<q, n>$$q \in Q$$Q$$PDA$$n \in \{1, 2, 3, 4\}$

• Si dans , soit dans si .$\delta(q, \epsilon, X) = <q', \alpha>$$O$$\delta(<q, 3>, \epsilon, X) = <<q', 2>, \alpha>$$M$$q \in F_O$

• Si dans , soit dans si .$\delta(q, \epsilon, X) = <q', \alpha>$$O$$\delta(<q, 3>, \epsilon, X) = <<q', 3>, \alpha>$$M$$q \notin F_O$

• Si dans , soit dans .$\delta(q, \epsilon, X) = <q', \alpha>$$O$$\delta(<q, 2>, \epsilon, X) = <<q', 2>, \alpha>$$M$

• Si n'est dans , dans$\delta(q, \epsilon, X)$$undefined$$O$$\delta(<q, 2>, \epsilon, X) = <<q, 1>, X>$$M$

• Si n'est dans , dans$\delta(q, \epsilon, X)$$undefined$$O$$\delta(<q, 3>, \epsilon, X) = <<q, 4>, X>$$M$

Dans ces définitions, nous laissons les états de la forme et consommer -moves imitant -moves de jusqu'à ce qu'il n'y en ait plus. Ensuite, effectuez un -move à un état de lecture. Maintenant pour les états de lecture,$<q, 2>$$<q, 3>$$\epsilon$$\epsilon$$O$$\epsilon$

• Si dans , soit en .$\delta(q, a, X) = <q', \alpha>$$O$$\delta(<q, 1>, a, X) = \delta(<q, 4>, a, X) = <<q', 3>, \alpha>$$M$

En faisant cette définition, nous consommons un symbole de l'entrée et passons à un état de la forme pour commencer une nouvelle série de -moves.$<q, 3>$$\epsilon$

Enfin, faire des états de la forme accepter des états de si . En outre, make l'état initial de si est l'état initial d' .$<q, 4>$$M$$q \notin F_O$$<q_0, 3>$$M$$q_0$$O$

Ce que nous avons fait est le suivant:

Créez 4 "étages" d'états (le deuxième élément du tuple dans les états de détermine dans quel étage nous sommes). Etage 3 imite -moves de pouvant atteindre un état acceptant d' . Si tel est le cas, nous passons à l'étage 2; sinon, nous restons à l'étage 3. Lorsqu'il n'y a plus de -moves à suivre de , nous définissons -moves de pour atteindre un état de lecture. Les étages 1 et 4 correspondent aux états de lecture. Si nous étions à l'étage 3, nous allons à l'étage 4. Si nous étions à l'étage 2, nous atteignons l'étage 1. Seuls les états (les états qui sont à l'étage 4) acceptent les états de$M$$\epsilon$$O$$q$$O$$\epsilon$$O$$\epsilon$$M$$<q, 4>$$M$ , à condition que ne sont pas accepter un état de .$q$$O$

Veuillez me faire savoir si j'ai fait une faute de frappe lors de l'écriture de ceci. J'aurais pu facilement me tromper. De plus, mon anglais n'est pas très bon, alors n'hésitez pas à modifier et à reformuler les choses mieux.

Il y a une preuve par construction dans l' introduction de Sipser à la théorie du calcul (l' édition 3 a une section sur les DCFL) qui identifie les états de lecture de l'automate en divisant tout état qui lit et apparaît à la fois. Seuls ces états de lecture peuvent être des états finaux, et pour obtenir le complément DPDA, vous inversez uniquement le comportement d'acceptation dans l'ensemble des états de lecture.$^{rd}$

Vous pouvez supposer que l'automate est exempt de -transitions sans perte de généralité.$\varepsilon$

Cela peut être démontré en utilisant la construction standard de CFG à PDA appliquée à une forme normale de Greibach . Dans Silent Transitions in Automata with Storage , G. Zetzsche a récemment présenté une construction directement sur les automates.

Mise en garde potentielle: Je suppose en quelque sorte que ladite construction standard donne un DPDA si nous l'appliquons à une grammaire appropriée, c'est-à-dire "déterministe" et que cette aptitude survit à la transformation sous la forme normale de Greibach.