Converter uma AFD em Máquina de Turing

---

$L_2=\{\omega \in \{0,1{\}}^{\ast }|\omega \text{comec¸a com b e tem uma quantidade par de a}\}$

Autômato:

1. Adapte a função de transição para o formato de tripla
   • (<ler símbolo>, <escrever símbolo>, <direção>)
   • direção indica para qual direção do cabeçote será posicionado após a leitura do símbolo. Pode ser L (left) ou R (right)

Note

Não colocar a indicação de “estado final” igual no autômato (no caso q1), pois nas Máquinas de Turing toda vez que um estado final é atingido a palavra é aceita e a leitura da palavra é interrompida, independente dela ter finalizada ou não.

Isso implica em, nenhuma transição deve sair de um estado final

2. (IMPORTANTE) No estado do autômato onde há a marcação de “estado final”, adicionar uma transição lendo a palavra vazia para um novo estado (“estado final”).

Referências

---