Material de scc605(sandra)

De CoteiaWiki
  • Soluções do Bruno Kim para a Lista de Exercícios sobre MT:
 Seguem anexas as máquinas de Turing que resolvem os problemas das linguagens 
 L = {ww | w in {a,b}+} e L = {0^(2n) | n >= 0}

 Só relembrando: a ideia da máquina que resolve ww é
 1) Marcar inicio (a -> X, b -> Y)
 2) Alternadamente, encontrar o fim e o inicio da cadeia de a's e b's e substitui-los (a->A, b->B)
 3) Uma vez encontrado o meio da cadeia, comparar a 2a. com a 1a. palavra, assegurando que são iguais (A->a, B->b)
 4) Se alcançar um branco, escreve 1 e termina

 A ideia da máquina que resolve 0^2n é
 1) Marcar inicio (0 -> I)
 2) Copiar a cadeia de I e Z's presente, duplicando a cadeia a cada iteração. Para isso, 
 2a) A primeira cadeia é escrita por I e A's (Z -> A);
 2b) A segunda cadeia é escrita por B's (0 -> B);
 2c) Ao fim da etapa, transforma A -> Z e B -> Z
 3) Se alcançar um branco, escreve 1 ao final, substitui Z -> 0 e I -> 0, e termina


Voltar para Scc-605(sandra)

Disponível em "http://wiki.icmc.usp.br/index.php?title=Material_de_scc605(sandra)&oldid=17356"