Convertir un PDA en DFA

Question

Je cherche à convertir un PDA en DFA. Où la pile du PDA ne contiendra jamais plus de n nombre de symboles.

Toute aide sera appréciée.

Merci

Answer 1

Je n'ai pas une solution complète mais juste une idée: pour chaque transition qui pousse un symbole s sur la pile, vous devez copier le sous-graphe pour les prochaines transitions pop. Le nouveau sous-graphe doit accepter la même sous-chaîne que le sous-graphe correspondant dans le PDA pour s. Lorsque vous recherchez de telles transitions, vous devez aller de l'intérieur, de telle sorte qu'il n'y a pas de poussée interne et de pop dans le sous-graphe. Ainsi, les premiers remplacements consisteront en deux transitions et les autres sous-graphes deviendront de plus en plus grands.