Exercício resolvido

Enunciado: Propor uma Máquina de Turing determinística capaz de detectar cadeias definidas sobre o alfabeto {a, b}* de tamanho ímpar, tais que o caractere central seja igual ao primeiro caractere.

Observação: Este problema é um problema típico a ser resolvido por um Máquina de Turing. Note que as gramáticas para a linguagem aceita pela máquina é um gramática, pelo menos, sensível ao contexto, sendo necessário o uso da Máquina de Turing como reconhecedor.

Resolução passo a passo:

1. Em primeiro lugar, vamos montar máquina que parará no caractere central da cadeia. Esta é a tarefa mais difícil a ser realizada. Para isso, criemos o estado inicial da máquina:

2. Este estado inicial será responsável por ler o primeiro caractere e marcá-lo com um caractere de "marcado".

3. Um novo estado foi adicionado; estado este que será responsável por caminhar na fita, da esquerda para a direita até encontrar o último caractere marcado e regressar para o último não-marcado. Nesse caso, como não temos caractere marcado à direita, tal estado procurará o caractere branco ('_').

4. Este estado apenas lerá o último caractere não marcado e o marcará. Perceba que este novo estado é similar ao estado q0 introduzido no passo 1, porém com o sentido de leitura invertido.

5. O novo estado caminhará na fita, da direta para esquerda até encontrar o primeiro caractere marcado e avançará ao primeiro não-marcado, similar ao que faz o estado q1, introduzido no passo 2.

6. Com a execução dos passos anteriores, foram marcados os caracteres da borda. Para marcar os demais, basta recomeçar o algoritmo. Dado que a borda já está maracada, o algoritmo não a considerará, desta forma parecendo que a cadeia a ser analisada não contém as bordas. Por isso, volta-se ao estado inicial.

7. O processo se repete até marcar todos os caracteres. Nesse momento, ao tentar-se regressar procurando o primeiro marcado, ele será encontrado imediatamente. Ao encontrá-lo, avança-se na expectativa de encontrar o primeiro não-marcado. Porém, neste caso, ele estará marcado, simbolizando que toda a cadeia foi marcada, de forma que este caractere que não deveria estar marcado mas está, representa o centro da cadeia.

8. As cadeias ímpares encontram o seu meio tentando avançar sobre um caractere que não deveria estar marcado, mas está, ou seja, o meio é encontrado no estado q2. Já para as cadeias pares, tentar-se-á o suposto "meio" na volta procurando um caractere que não deveria estar marcado, mas está. Como o enunciado se preocupa apenas com cadeias de tamanho ímpar, o estado que futuramente poderá levar ao estado final é o estado q2.

9. Está pronta a máquina que detecta o caractere central em q2. Agora, falta comparar com o caractere inicial.

10. Para isso, criaremos um novo estado, que será o verdadeiro estado inicial da máquina, q8, responsável por ler o primeiro caractere.

11. Como a memória da máquina se apresenta na forma de estados, não teremos como decidir a partir de q2 se foi lido inicialmente um 'a' ou um 'b'. Portanto, a solução para este problema é replicar a máquina e adaptar as transições finais. Assim, o estado q8, além de ler o primeiro caractere e marcá-lo também terá que decidir para qual das máquinas a transição ocorrerá.

12. Outra observação importante, é que o estado q8 tem uma tarefa muito parecida com o estado inicial original q0. Logo, ele deve passar para os estados "q1s" das máquinas corretas. Todo este raciocínio, é finalmente demonstrado na imagem:

13. Observe o comportamento análogo dos estados:

• q0 e q4

• q1 e q5

• q2 e q6

• q3 e q7

14. Conforme discutimos anteriormente, o centro da cadeia será descoberto em q2, ou em seu equivalente, q6. Nesses estados, é finalmente necessário conferir se o que está marcado naquela posição da fita corresponde ao caractere inicial lido ('a', no caso de q2; 'b', no caso de q6). Se a comparação for bem sucedida, move-se para o estado final de aceitação.

15. Ao não colocar transições em q0, e seu equivalente, q4, evita-se aceitação de cadeias pares.

16. Qualquer outra cadeia parará antes de atingir o estado de aceitação, sendo assim, rejeitada.

17. Formalizando a máquina, de acordo com a formalização descrita no livro de Hopcroft, 2001: M = ( {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9}, {a, b}, {a, b, A, B, _}, δ, q8, _, {q9} )

δ:

Link para o arquivo para o JFLAP