Conversion de PDA en CFG

Question

J'essaie de comprendre cet exemple de convertir le PDA en CFG, mais je ne reçois pas l'idée parfaite. J'ai la compréhension générale du théorème que si $ p, q \ \ epsilon \ q $ et $ x \ varpsilon \ \ Gamma $ pour $ [pxq] $ Nous avons inclus la séquence de dérivations qui sauraient x de la pile.

Je comprends partiellement ce qui se passe mais je ne peux pas sembler comprendre comment puis-je dérouler les productions pour former des cordes afin que je puisse la comprendre clairement. Prendre la production (5) dans l'exemple par exemple. D'après ce que je comprends, nous sommes dans l'état p que nous voulons faire sauter une et à la fin, nous devrions être dans l'état P avec une pile vide. Comme nous lisons 0 nous avons zéro dans la production suivie de $ [paq] [qap] $ , c'est la chose que je suis Pas comprendre parce que si nous regardons le PDA, il n'ya aucun moyen d'aller q sur la lecture 0. J'aimerais savoir ce qui se passe vraiment.

Une question connexe est répondue à une réponse ici Mais je ne peux pas comprendre comment effacer ma confusion.

Answer 1

Vous avez l'intuition de base juste. La variable $ [p, a, q] $ représente l'ensemble de (strings acceptées par) calcul de l'état $ p $ Pour indiquer $ Q $ qui affichera le symbole le plus haut $ A $ DE LA Pile.

technique la relation entre la grammaire $ g $ et pda $ m $ est donné sur le dessus de la diapositive que vous montrez.

Puis la construction suit la récursivité. Si le PDA apparaît $ a $ mais pousse $ b_1b_2b3 $ La grammaire remplacera le calcul sur $ A $ à partir de $ P $ et finissant par $ q $ < / span> en trois calculs distincts $ [q_1, b_1, q_2] [q_2, b_1, q_3] [q_3, b_1, q] $ . Ici, les états intermédiaires $ q_2, q_3 $ sont inconnus et sont devinés par la grammaire. Seulement $ q_1 $ est connu, car il s'agit de l'état où l'instruction PDA passe à.

Votre observation a raison. Cette construction standard pourrait introduire des triplets $ [p, a, q] $ qui sera inutile. Dans votre exemple, il n'y aura pas de calcul de $ q $ to $ p $ donc un triplet $ [q, a, p] $ n'est jamais utilisé dans une dérivation réussie. Ce n'est pas problématique. La construction produit uniquement toutes les possibilités et les variables qui se révèlent inutiles peuvent être supprimées par la suite si on veut vraiment.

note. L'autre question que vous connaissez pour utiliser un modèle d'automaton de style sipser différent! Là, les symboles de pile sont poussés un par un sans apparaître en même temps. Pour ajouter à la confusion The Réponse donnée à cette question correspond parfaitement à la construction de votre diapositive!