Pousser/popping pile dans l'ordre inverse dans un Pushdown Automaton

Question

Donc j'étudie pour un test que j'ai à venir sur les automates pushdown et les langages sans contexte et je suis coincé sur cette construction.

J'ai chaque partie de cet automate fonctionnant parfaitement à l'exception d'une partie que j'expliquerai ci-dessous. Le langage à reconnaître est: {x # y # z # w | x, y, z, w dans {0, 1} + avec x ≠ w et y ≠ z}. Donc le problème que j'ai est de comparer Xi à Wi, puisque les éléments de Wi ne sont pas connus au moment où l'automate arrive à traiter W, la façon dont je l'ai conçu. Si je stocke le contenu de X, quand le temps viendra de sauter et de comparer chaque élément à ceux de W, ils apparaîtront dans l'ordre inverse et considéreront donc 000111 et 111000 comme étant la même chaîne et le PDA rejettera , quand il devrait clairement accepter (ce sont des chaînes différentes). Ceci n'est qu'un exemple, cela entraînera également l'analyse incorrecte d'autres entrées.

S'il y a un moyen de pousser le contenu de X sur la pile dans l'ordre inverse, ils apparaîtront dans leur forme originale, me permettant de comparer correctement le contenu des chaînes.

S'il y a un moyen d'inverser le contenu de la pile après avoir poussé normalement, cela me permettra également d'arriver à la solution.

Toute aide serait grandement appréciée. Merci.

Answer 1

La solution est un peu compliquée.

Il n'y a en fait aucun moyen d'inverser le contenu de la pile dans le PDA. Tout dépend de la nature non-déterministe de npda qui permet de résoudre ce problème.

Démarrer avec cette version plus simple

L = {x#w: x,w in {0,1}+ and x≠w}. 

Solution:

Démarrer avec l'état q. poussez un $ pour chaque lettre de x jusqu'à la lettre k (k n'est pas important, choisissez k de manière non déterministe), puis examinez la lettre k et allez à q0 si c'était ou allez à q1 si c'était . Ignorer le reste de x jusqu'à atteindre #. Tapez $ pour chaque lettre de w jusqu'à ce que vous atteigniez le bas de la pile (disons z). Examinez la lettre k'th de w. Si [vous étiez à q0 et la lettre n'a pas été ] ou [vous étiez à q1 et la lettre n'a pas été ] accepter.

C'est tout, la magie!