une poussée vers le bas Automates qui produit la bascule et inverse d'une chaîne

Question

L'alphabet: 0, 1

Considérons une bascule, pour faire basculer chaque caractère: 0 -> 1; 1 -> 0 Donc, si w = 0011 alors w-flip = 1100

Tenir compte un revers pour être les personnages dans l'ordre inverse Donc, si w = 01101 alors w-reverse = 10110

Maintenant, je suis en train pour produire un PDA qui prend la chaîne w, puis imprime w, estampes (inversée-w-flip)

w = 011 
w-flip = 100 
w-flip-reverse = 001 

donc, ce imprimerait: "011001"

Tenir compte # pour être un blanc. Donc, une chaîne commencerait # 011 #

table de transition ressemble à ceci:

State: Symbol Read: Next State: Head Instruction: 
start  #    r1    L 

Et ainsi de suite

Toutes les idées?

Answer 1

L'impression de la chaîne est simple (j'espère). Impression de la bascule est aussi facile que l'impression 0 lorsque vous lisez un 1 et vice-versa.

Une esquisse pour vous permettre de continuer sur le renversement:

• Vous avez besoin d'un endroit pour mettre la pièce de chaîne par pièce qui se prête à l'inversion, le stockage donc d'abord en dernier sorti est idéal (Qu'est-ce que cela pourrait être dans un PDA?).
• Ensuite, vous devez regarder la fin de la chaîne pour savoir quand passer du stockage de la chaîne à l'inversion de sortie.
• puis vous devez récupérer chaque partie de la chaîne dans le bon ordre inverse (qui, si elle est stockée FILO est trivial) et la sortie, en s'arrêtant lorsque vous atteignez la fin de la chaîne.

Dans votre cas, vous devrez mettre la chaîne retournée en mémoire pour l'annuler.