Lista Exercícios sobre Máquina de Turing Resolvida

Prévia do material em texto

Universidade*Federal*Rural**de**Pernambuco*
Departamento*de*Estatística*e*Informática*
Licenciatura*em*Computação*
Teoria*da*Computação*
Prof.**George**Gomes**Cabral*
*
*
4a*lista*de*exercícios*!
!
Figura*1*6*Máquina*de*Turing*M2*1. Dada!a!Máquina!de!Turing!M2,!dê!a!seqüência!de!configurações!nas!quais!M2!entra!quando!iniciada!sobre!a!cadeia!de!entrada!indicada.!a!) 0!!Uq00U!UU!q1U!UU!q5U!(aceita)!! b!) 00!!Uq000U!UU!q10U!UUxq2U!UUq4xU!Uq4UxU!UUq1xU!UUxq1U!UUxq5U!!(aceita)!! c!) 000!!Uq0000U!UU!q100U!UUxq20U!UUx0q3U!UUx0q6U!!(rejeita)!!
d!) 000000!!Uq0000000U!UUq100000U!UUxq20000U!UUx0q3000U!UUx0xq200U!UUx0x0q30U!UUx0x0xq2U!UUx0x0q4xU!UUx0xq40xU!UUx0q4x0xU!UUxq40x0xU!UUq4x0x0xU!Uq4Ux0x0xU!UUq1x0x0xU!UUxq10x0xU!UUxxq2x0xU!UUxxxq20xU!UUxxx0q3xU!UUxxx0xq3U!UUxxx0xq6U!!(rejeita)!!!!!!2. Examine!a!definição!formal!de!uma!Máquina!de!Turing!e!responda!as!seguintes!questões.!a!) Uma!MT!pode!alguma!vez!escrever!o!símbolo!branco!em!sua!fita!?!Sim.!O!símbolo!em!branco!pode!estar!no!alfabeto!de!fita,!porém!não!no!de!entrada.!b!) O!alfabeto!de!fita!pode!ser!o!mesmo!que!o!alfabeto!de!entrada!?!Não.!Dessa!forma,!símbolos!escritos!pela!cabeça!poderiam!se!confundir!com!símbolos!da!cadeia.!c!) A!cabeça!de!uma!MT!pode!alguma!vez!estar!na!mesma!localização!em!dois!passos!sucessivos!?!Sim.!Estando!em!uma!das!extremidades!da!cadeia!(lendo!o!símbolo!em!branco)!ela!pode!ficar!emperrada!até!receber!um!comando!para!seguir!outra!direção.!d!) Uma!máquina!de!Turing!pode!conter!apenas!um!estado!?!Não.!Por!definição!a!máquina!deve!ter!pelo!menos!os!estados!qaceita!e!qrejeita!que!são!distintos.!!!3. Dê!descrições!de!MTs!que!decidam!as!seguintes!linguagens!sobre!o!alfabeto!{0,!1}.!!a!) {w!|!w!possui!o!mesmo!numero!de!0s!e!1s}!i. caso!leia!símbolo!em!branco!rejeite.!Senão!vá!para!o!passo!ii.!ii. ! 1. Procure!por!símbolos!do!alfabeto!de!entrada.!Caso!leia!0(zero),!marque!um!x,!siga!para!a!direita!procurando!por!um!1!(um).!Ao!encontrar!marque!um!x!e!volte!para!o!início!da!fita.!Caso!não!encontre!o!1,!rejeite.!
2. Procure!por!símbolos!do!alfabeto!de!entrada.!Caso!leia!um!1!(um),!marque!um!x,!siga!para!a!direita!procurando!por!um!0!(zero).!Ao!encontrar!marque!um!x!e!volte!para!o!início!da!fita.!Caso!não!encontre!o!0,!rejeite.!3. Caso!não!encontre!nenhum!símbolo!do!alfabeto!de!entrada!(encontre!apenas!xs),!aceite.!iii. Pule!todos!os!xs!até!encontrar!ou!um!0!ou!um!1!e!volte!para!o!passo!ii.!b!) {w!|!w!contem!duas!vezes!mais!0s!que!1s}!i. !caso!leia!símbolo!em!branco!rejeite.!Senão!vá!para!o!passo!ii.!ii. ! 1. Procure!por!símbolos!do!alfabeto!de!entrada.!Caso!leia!1(zero),!marque!um!x!e!retorne!ao!início.!Procure!por!dois!0s!e!marque!x!também.!!2. Caso!não!encontre!nenhum!símbolo!do!alfabeto!de!entrada!(encontre!apenas!xs),!aceite.!iii. Volte!para!o!início!da!fita.!Volte!para!o!passo!ii.!!4. Defina!os!estados!!de!transições!!para!as!MTs!do!exercício!anterior.!!
!(!A!)!!
(B)!!!
1. Desenvolva!Máquinas!de!Turing!que!computem!as!seguintes!linguagens:!! a!) L!=!(aba*b)!b!) L!=!{0n1n!|!n!≥!0}!c!) L!=!{anbnan|!n!≥!1}!d!) L!=!{anbncn|!n!≥!0}!e!) L!=!{w!|!w!=!b1+b2!e!b1!e!b2!são!números!binários!tais!que!o!dígito!de!ordem!superior!de!ambos!é!0}!(descrição!informal!abaixo)!f!) L!=!{w!|!w!=!b1db2!e!b1!e!b2!são!números!binários!e!b1!>!b2}!g!) L!=!{aibjak!|!k!=!max(i,!j)}!h!) L!=!{aibjak!|!i!<!j!<!k}!i!) L!=!{wcwR!!|!wR!=!w!=!na!ordem!inversa}!j!) L!=!{wwR!!|!wR!=!w!=!na!ordem!inversa}!k!) L!=!{aibjck!|!k!=!(i!*!j)!e!i,!j!e!k!>=!1}!!!
 !
 
 
 
 
 
 
 
 
 
 
a) 
 
b) 
 
 
c) 
Descrição informal letra e) 
1. Adicionar 1 a b2 
a. vá para o segundo # 
b. da direita para a esquerda troque todos os 1's por 0's 
c. no primeiro 0, troque por 1 
2. Subtrair 1 do b1 
a. tire o complemento de 1 de b1 (troque 0's por 1's e vice-versa) 
b. adicione 1 ao b1 
c. tire o complemento de 1 de b1 novamente 
3. Cheque se b1 é igual a zero 
a. caso sim, w está no local original de b2 
b. caso contrário, volta para 1. 
 
 
e) 
 
 
f) 
 
 
g) 
 
 
 
 
k) 
!