MaquinasTuring
88 pág.

MaquinasTuring


DisciplinaTeoria da Computação547 materiais16.691 seguidores
Pré-visualização4 páginas
M continua executando para sempre 
22 
q 
qa \u2fd \u2192 \u2fd, R 
qr 0 \u2192 0, R 
loop 
aceita 
rejeita 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configuração de MTs 
\uf0a7 Existem três componentes que são 
modificáveis em uma MT 
\u2022 Estados 
\u2022 Conteúdo da fita 
\u2022 Localização da cabeça de le 
\uf0a7 O conjunto destes três componentes é 
chamado de configuração da MT 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Notação Para Configurações 
\uf0a7 u q v representa uma configuração de MT onde 
\u2022 q é um estado 
\u2022 o conteúdo da fita é uv, onde u e v são palavras sobre 
o alfabeto \u393 
\u2022 A cabeça de le encontra-se sobre o primeiro 
símbolo de v. A fita contém apenas símbolos 
brancos após o último símbolo de v 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
25 
1 2 3 4 5 6 7 8 9 \u2fd \u2026 
qi 
\u2022 u = 1234 
\u2022 v = 56789 
\u2022 Configuração: 1234qi56789 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 1 
\uf0a7 Apresente o diagrama para a máquina M1 que 
reconhece a linguagem B = {p#p | \ud835\udc5d \u2208 0,1
\u2217
 } 
\uf0a7 Simplificação: não é necessário representar o 
estado de rejeição e as transições que 
conduzem a este estado 
 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2: 
Solução 
27 
q1 
q8 
qa 
q6 
q7 
q2 
q4 
q3 
q5 
#\u2192R 
x\u2192R 
\u2fd\u2192R 
#\u2192R 
0,1\u2192R 
x\u2192R 
0,1,x\u2192L 
#\u2192L 
x\u2192R 
0,1\u2192L 
#\u2192R 
0,1\u2192R 
x\u2192R 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações de MTs 
\uf0a7 Uma configuração C1 produz outra 
configuração C2 se a MT pode transitar de C1 
para C2 em um único passo, isto é, se existe 
uma transição de estados que conduz a MT da 
configuração C1 para C2 
28 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações de MTs (2) 
\uf0a7 Considere a, b, e c em \u393 e u e v em \u393* e os 
estados qi e qj 
\uf0a7 Caso em que MT move-se para a esquerda 
\u2022 Considere as configurações uaqibv e uqjacv 
\u2022 Dizemos que uaqibv produz uqjacv se na função de 
transição: 
(q1,b) (qj, c, L) 
\uf0a7 Caso em que MT move-se para a direita 
\u2022 Considere as configurações uaqibv e uacqjv 
\u2022 Dizemos que uaqibv produz uacqjv se na função de 
transição: 
(q1,b) (qj, c, R) 
 
 
 
 
 
 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações de MTs (3) 
\uf0a7 Ínicio da fita -> qibv 
\u2022 qibv produz qicv quando o movimento é para 
esquerda (cabeça le não se movimenta ) 
\u2022 qibv produz cqiv quando o movimento é para 
direita 
\uf0a7 Final da fita 
\u2022 uaqi é equivalente a uaqi \u2fd 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações Especiais 
\uf0a7 Configuração de início: q0p para uma entrada p 
\uf0a7 Configuração de aceitação: o estado da 
configuração é qa 
\uf0a7 Configuração de rejeição: o estado da 
configuração é qr 
\uf0a7 Configurações de aceitação e rejeição são 
também configurações de parada porque não 
produzem outras configurações 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Aceitação da Entrada 
\uf0a7 Uma MT aceita uma entrada p se existe uma 
sequência de configurações C1C2,...,Ck onde 
\u2022 C1 é uma configuração de ínicio de M para entrada p 
\u2022 Cada Ci produz Ci+1 
\u2022 Ck é uma configuração de aceitação 
\uf0a7 A coleção de palavras que M aceita ou a 
linguagem que M reconhece, denotado por 
L(M), é a linguagem de M 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 
\uf0a7 Projete uma TM M2 que reconheça a 
linguagem A = {02
\ud835\udc5b
\ud835\udc5b \u2265 0 
\uf0a7 Ou seja a TM deve reconhecer palavras de 
comprimento igual a alguma potência de 2 (0, 
00, 0000, 00000000, etc, mas não 000 ou 
000000) 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 1 (2) 
\uf0a7 Intuição: |p| = 2n = 2 X 2 X ... X 2 
34 
n 
\uf0a7 Caso trivial: comprimento de p é ímpar->Rejeita 
\uf0a7 Se o comprimento de p é par e realizarmos divisões 
sucessivas por 2 iremos obter em algum momento o 
resultado 1 (após n divisões). Qualquer outro número 
ímpar obtido como resultado de uma divisão implica 
que o tamanho de p não é uma potência de dois 
\uf0a7 Como podemos expressar esta computação usando 
uma MT? 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 (3) 
1. Percorra a palavra p realizando o seguinte 
procedimento: após ler um 0, marque o zero 
seguinte com x. Se apenas um 0 foi lido no 
Passo 1, Aceita 
2. Se a fita continha mais de um zero e o 
número é impar, Rejeita 
3. Volte a cabeça le para o começo da fita 
4. Vá para o passo 1 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 (4) 
\uf0a7 M2 = (Q, \u2211, \u393, , q1, qa, qr) 
\uf0a7 Q = {q1, q2, q3, q4, q5, qa, qr}, 
\uf0a7 \u2211={0}, 
\uf0a7 \u393 = {0, x, \u2fd} 
\uf0a7 (diagrama de estados nos próximos slides) 
\uf0a7 Estado inicial, de aceitação e rejeição são q1, qa, e 
qr, respectivamente 
\uf0a7 Notação: 
\u2022 0 \u2192 x,R: associado a transição saindo do estado q1 
para q2 corresponde a (q1,0) = (q2, x, R) 
\u2022 0 \u2192 R: significa que o símbolo lido não é sobescrito ou 
permance o mesmo: (q1,0) = (q2, 0, R) 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 (5) 
37 
q1 q2 q3 
qr qa q4 
q5 
\u2fd\u2192R 
x\u2192R 
0\u2192\u2fd, R 
\u2fd\u2192R 
\u2fd\u2192R 
0\u2192x, R 
x\u2192R 
0\u2192R 
x\u2192R 
0\u2192x, R 
0\u2192L 
x\u2192L 
x\u2192R 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Sequência de Configurações 
\uf0a7 Considerando a MT anterior, apresente a sequência de 
configurações para entrada 0 
1. q10 
2. \u2fdq2 
3. \u2fd \u2fdqa 
 
\uf0a7 Apresente a sequência de configurações para entrada 000 
1. q1000 
2. \u2fd q200 
3. \u2fd xq30 
4. \u2fd x0q4 
5. \u2fd x0 \u2fd qr 
 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
\uf0a7 Apresente a sequência de configurações para as 
entrada 000000 e 000000000000 
 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
\uf0a7 Projete uma MT para resolver o problema dos 
elementos distintos. Dado um lista de palavras 
sobre {0,1} separadas pelo símbolo #, a MT 
deve aceitar a entrada se todas as palavras 
contidas na lista forem diferentes 
\u2022 L = {#a1#a2\u2026#an} cada ai \u404 {0,1}* and ai \u2260 aj 
para i \u2260 j 
40 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
\uf0a7 Projete uma MT para resolver o problema dos 
elementos distintos. Dado um lista de palavras 
sobre {0,1} separadas pelo símbolo #, a MT 
deve aceitar a entrada se todas as palavras 
contidas na lista forem diferentes 
\u2022 L = {#a1#a2\u2026#an} cada ai \u404 {0,1}* and ai \u2260 aj 
para i \u2260 j 
\uf0a7 Dica: Represente loops aninhados na MT (for-
for) 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
\uf0a7 Projete uma MT para resolver o problema dos 
elementos distintos. Dado um lista de palavras 
sobre {0,1} separadas pelo símbolo #, a MT 
deve aceitar a entrada se todas as palavras 
contidas na lista forem diferentes 
\u2022 L = {#a1#a2\u2026#an} cada ai \u404 {0,1}* and ai \u2260 aj 
para i \u2260 j 
\uf0a7 Dica: Represente loops aninhados na MT (for-
for) 
42 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 3: Solução 
1. Escreva um marcador (m1) no lugar do primeiro 
símbolo da entrada. Se o símbolo original for #, 
prossiga para o próximo passo; caso contrário 
rejeite 
2. Percorra a fita até o próximo símbolo # e escreva 
um segundo marcador sobre ele (m2). Se 
nenhum for encontrado, aceite (a lista de 
entrada contém apenas 1 palavra) 
3. Fazendo movimentos em zig-zag, compare as 
palavras à direita de cada marcador. Se forem 
iguais rejeite 
43 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 3: Solução (2) 
4. \u201cMova\u201d m2 para o próximo símbolo #, isto é, 
substitua m2 por # na sua posição original e 
escreva-o na posição do próximo símbolo # 
encontrado. Se nenhum outro # for encontrado, 
então mova m1 (marcador mais a esquerda) 
para o próximo símbolo # à sua direita e depois 
mova m2 para próximo símbolo # à direita de 
m1. Neste ponto, se não existir mais símbolos # 
para m2, então todas palavras foram 
comparadas. Aceite 
5. Volte ao passo 3 
 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Turing Reconhecível 
\uf0a7 Uma linguagem é chamada Turing 
reconhecível se alguma MT a reconhece 
\uf0a7 Estas linguagens são também chamadas 
linguagens recursivamente enumeráveis 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Decididores 
\uf0a7 Existem três possibilidades para o resultado de uma 
MT 
\u2022 Aceita 
\u2022 Rejeita 
\u2022 Executa para sempre (entra