Metodologia para construção de uma máquina de Turing a partir de uma definição de linguagem

---

A melhor forma de construir o diagrama não é começando pelos estados, mas dividindo o problema em camadas de abstração adotando o design top-down.

1. Escreva o algoritmo em alto nível (português):

   • Esqueça a fita por um momento.
   • Como você, ser humano, resolveria o problema se tivesse que olhar para a palavra e validá-la usando apenas um lápis e uma borracha?
   • Descreva o passo a passo lógico.

2. Defina a estrutura de dados (“a estratégia de fita”):

   • Como você vai manipular a informação?
   • Defina:
     • Que símbolos usarei para “marcar” o que já foi lido? (ex.: trocar a por X)
     • Preciso de delimitadores para separar informações? (ex.: usar um # no meio da fita)

3. Pense em sub-rotinas:

   • Agrupe ações em blocos lógicos menores, como se fossem funções em programação.
   • Exemplos clássicos de sub-rotinas de uma MT:
     • “Varrer para a direita até encontrar um espaço em branco”
     • “Rebobinar a fita toda para a esquerda até achar o marcador de início”
     • “Deslocar toda a palavra um caractere para a direita”

4. Tradução para baixo nível (estados e transições):

   • Cada estado ($q_n$) deve representar um objetivo único e simples dentro de uma sub-rotina.

Referências

---