Comment convertir un CFG en une machine de Turing

Question

Comment convertir un CFG en TM? J'ai une idée de base sur la façon de convertir un DFA en un TM, mais je ne peux pas penser à un moyen de le faire correctement. Puis-je avoir des étapes générales de mise en œuvre à ce sujet?

Answer 1

1. Construire un automate à pile (PDA) à l'aide d'un algorithme standard. Je ne vais pas entrer dans les détails d'une construction particulière (une question distincte serait un meilleur endroit pour couvrir cela), mais vous pouvez rechercher "convertir cfg en PDA" et obtenir des résultats. Un exemple est here.

2. construire une Turing à deux bande machine du PDA comme suit:

   • La machine de Turing lit la bande d'entrée (cassette N ° 1) de gauche à droite
   • La machine de Turing utilise la deuxième bande en tant que la pile, se déplaçant à droite en poussant et à gauche en éclatant.

3. Construire une machine de Turing à une bande de vanille à partir de la machine à deux rubans en utilisant une construction standard. La preuve que les mémoires à bande unique et à bande double sont équivalentes est une preuve constructive et vous pouvez suivre l'algorithme implicite pour montrer la construction d'une seule bande TM pour la langue de votre CFG.

Answer 2

Chaque mot produit du CFG peut être écrit comme un arbre d'analyse. Si vous obtenez une chaîne produite par le CFG, ce sont les feuilles de votre arbre d'analyse. Pour déterminer si la chaîne est produite par le CFG, il suffit de passer des feuilles aux nœuds internes jusqu'à la racine. L'idée générale est donc de contourner les règles de production. Si vous pouvez atteindre la racine, alors la chaîne fait partie de la grammaire. Si vous êtes à un point où aucune règle de production retournée ne correspond, le mot n'est pas produit par le CFG. Notez que s'il y a plus d'une possibilité, vous devez essayer toutes les possibilités et si une personne travaille, la chaîne est produite par le CFG. Si aucun ne fonctionne, ce n'est pas le cas.