Mudanças entre as edições de "Material de scc605(sandra)"

De CoteiaWiki
Linha 40: Linha 40:
 
   L = {ww | w in {a,b}+} e L = {0^(2n) | n >= 0}
 
   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
  
−
Só relembrando: a ideia da máquina que resolve ww é
+
  A ideia da máquina que resolve 0^2n é
−
1) Marcar inicio (a -> X, b -> Y)
+
  1) Marcar inicio (0 -> I)
−
2) Alternadamente, encontrar o fim e o inicio da cadeia de a's e b's e substitui-los (a->A, b->B)
+
  2) Copiar a cadeia de I e Z's presente, duplicando a cadeia a cada iteração. Para isso,  
−
3) Uma vez encontrado o meio da cadeia, comparar a 2a. com a 1a. palavra, assegurando que são iguais (A->a, B->b)
+
  2a) A primeira cadeia é escrita por I e A's (Z -> A);
−
4) Se alcançar um branco, escreve 1 e termina
+
  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
−
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
 
  
 
* '''Exercícios Resolvidos MT: '''[[Media:ex_resol_MT_2011.pdf]]
 
* '''Exercícios Resolvidos MT: '''[[Media:ex_resol_MT_2011.pdf]]

Edição das 19h03min de 24 de maio de 2011

  • 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=16783"