Diagramme machine de Turing pour l'énumérateur

Question

Je suis supposé dessiner un énumérateur pour la langue 0^k1^k (k> = 0). Je ne suis pas sûr que cela soit différent de construire un diagramme d'état de machine de Turing pour ce langage: la façon dont je le comprends est que je dois construire un énumérateur qui reconnaisse le langage mentionné ci-dessus {0,1} en simulant le Turing machine qui reconnaît cette langue sur la chaîne i pour i étapes, que je ne pouvais pas penser à faire en utilisant un diagramme d'état, mais mon professeur a souligné que c'est ainsi que nous prouvons l'équivalence entre un recenseur et une machine de Turing, donc je pensait que ce que nous devons faire est d'utiliser la fonction de transition définie pour les enquêteurs qui rend le diagramme semblable à la machine de Turing qui reconnaît 0^k1^k, seulement au lieu de passer à qaccept nous passons à qprint pour les entrées dans le langage, et alors pour les entrées qui doivent être rejetées, nous imprimons epsilon? Mais comment allons-nous produire un nombre infini de chaînes au-dessus de l'alphabet {0,1}? A l'état initial, la bande de travail et la bande d'impression sont vides. Quelqu'un peut-il clarifier ces points pour moi? Peut-être que je me méprends.

Answer 1

Je pense que je enfin la notion de recenseur claire, un recenseur n'est pas censé lire une entrée, il crée des mots dans la langue pour laquelle il est construit: est ici l'algorithme:

1. impression epsilon sur la bande de sortie
2. écrire 01 sur la bande de travail
3. revenir à l'avant de la bande et copier son contenu sur la bande de sortie
4. revenir à l'extrême gauche 0, le remplacer par 1, aller à l'extrême droite 1 et ajoutez deux 1 à la fin.
5. retourner à l'étape 3

Answer 2

je pensais d'un autre algorithme légèrement différent qui produit un plus petit nombre d'états, et utilise uniquement {0, vide} sur sa bande de travail: