Idioma aceito e idioma decidido
Uma TM aceita um idioma se entrar em um estado final para qualquer string de entrada w. Uma linguagem é recursivamente enumerável (gerada pela gramática Tipo-0) se for aceita por uma máquina de Turing.
Uma TM decide se um idioma o aceita e entra em um estado de rejeição para qualquer entrada que não esteja no idioma. Uma linguagem é recursiva se for decidida por uma máquina de Turing.
Pode haver alguns casos em que uma MT não para. Essa MT aceita o idioma, mas não o decide.
Projetando uma Máquina de Turing
As diretrizes básicas para projetar uma máquina de Turing foram explicadas abaixo com a ajuda de alguns exemplos.
Exemplo 1
Projete uma TM para reconhecer todas as strings que consistem em um número ímpar de αs.
Solution
A máquina de Turing M pode ser construído pelos seguintes movimentos -
Deixei q1 ser o estado inicial.
E se M é em q1; na varredura α, ele entra no estadoq2 e escreve B (em branco).
E se M é em q2; na varredura α, ele entra no estadoq1 e escreve B (em branco).
A partir dos movimentos acima, podemos ver que M entra no estado q1 se varre um número par de α's, e entra no estado q2se varre um número ímpar de α's. Conseqüentementeq2 é o único estado de aceitação.
Conseqüentemente,
M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}
onde δ é dado por -
| Símbolo do alfabeto de fita | Estado Atual 'q 1 ' | Estado Atual 'q 2 ' |
|---|---|---|
| α | BRq 2 | BRq 1 |
Exemplo 2
Projete uma máquina de Turing que leia uma string representando um número binário e apague todos os zeros iniciais da string. No entanto, se a string for composta por apenas 0s, ela manterá um 0.
Solution
Vamos supor que a string de entrada é encerrada por um símbolo em branco, B, em cada extremidade da string.
A Máquina de Turing, M, pode ser construído pelos seguintes movimentos -
Deixei q0 ser o estado inicial.
E se M é em q0, na leitura 0, move-se para a direita, entra no estado q1 e apaga 0. Na leitura 1, ele entra no estado q2 e se move para a direita.
E se M é em q1, na leitura 0, move-se para a direita e apaga 0, ou seja, substitui 0's por B's. Ao chegar ao 1 mais à esquerda, ele entraq2e se move para a direita. Se atingir B, ou seja, a string é composta por apenas 0's, ela se move para a esquerda e entra no estadoq3.
E se M é em q2, ao ler 0 ou 1, ele se move para a direita. Ao chegar a B, ele se move para a esquerda e entra no estadoq4. Isso valida que a string compreende apenas 0's e 1's.
E se M é em q3, ele substitui B por 0, move-se para a esquerda e atinge o estado final qf.
E se M é em q4, ao ler 0 ou 1, ele se move para a esquerda. Ao chegar ao início da string, ou seja, ao ler B, chega ao estado finalqf.
Conseqüentemente,
M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}
onde δ é dado por -
| Símbolo do alfabeto de fita | Estado Atual 'q 0 ' | Estado Atual 'q 1 ' | Estado Atual 'q 2 ' | Estado Atual 'q 3 ' | Estado Atual 'q 4 ' |
|---|---|---|---|---|---|
| 0 | BRq 1 | BRq 1 | ORq 2 | - | OLq 4 |
| 1 | 1Rq 2 | 1Rq 2 | 1Rq 2 | - | 1Lq 4 |
| B | BRq 1 | BLq 3 | BLq 4 | OLq f | BRq f |