Universidade Federal de Juiz de Fora

Departamento de Cincia da Computao

Disciplina: TEORIA DA COMPUTAO Turma: A

Professor: LORENZA MORENO Ano/Semestre: 2012/1

LISTA DE EXERCCIOS

1) Construa uma mquina de Turing que, dada uma entrada da forma x$y onde x e y so nmeros binrios,

modifique o contedo da fita para que ao final do processamento esta contenha:

a) x$$$y, ou seja, desloque y duas casas para a esquerda preenchendo os espaos entre x e y com $. b) z$y, onde z=x-1 se x>0.

c) z, onde z = x-y (pode assumir que x > y e x > 0)

d) z, onde z=x, se x e y forem nmeros pares, e z=y, caso contrrio.

e) z, onde z=x, se x maior que y, e z=y, caso contrrio.

2) Construa uma mquina de Turing que, dada uma entrada da forma anbm (n as seguidos por m bs),

modifique o contedo da fita para que ao final do processamento essa contenha:

a) bnam b) ambn

c) anbn+m

d) anbmcnm

3) Para cada linguagem abaixo, construa uma mquina de Turing que a reconhea:

a) LA={anbm, n = m+2}

b) LB = complemento de LA

c) unio de LA e LB d) intercesso de LA e LB

4) Para cada mquina abaixo:

a) descreva informalmente, mas de forma clara, o funcionamento e/ou a linguagem reconhecida. b) d as descries instantneas para cada possvel avaliao da entrada abbba

MA= ({q0,q1,q2,q3}, {a,b}, {a,b,B}, A, q0, B, { q0 }) onde A definido por:

A a b B

q0 {q2aR} {q1bR}

q1 {q3aR} {q0bR} {q0bR}

q2 {q0aR} {q3bR} {q0aR}

q3 {q1aR} {q2bR} {q1aR, q2bR }

MB= ({q0,q1,q2,q3}, {a,b}, {a,b,c,B}, B, q0, B, { q3 }) onde B definido por:

B a b B

q0 {q0aR, q1aR,q2aR } {q0bR} {q3aR}

q1 {q2cR} {q2cR} {q2cR}

q2 {q0cR} {q0cR} {q0cR}

MC= ({q0,q1,q2,q3,q4,q5}, {a,b}, {a,b,c,X,Y,B}, C, q0, B, { q5 }) onde C definido por:

C a b c X Y B

q0 q3XR q1YR

q1 q1aR q2bR q4BL

q2 q2aR q3cR q4BL

q3 q3aR q1bR

q4 q4cL q4bL q4cL q5cL q5bL

MD= ({[q0,B],[q1,B],[q2,k],[q3,B],[q4,B],[q5,B] | k {a,b,B}}, {a,b}, {a,b,B,X}, D, [q0,B], B, {[q4,B]}) onde D definido por:

D [a,B] [b,B] [B,B] [b,X]

[q0,B] {[q1,B],[a,B],R} {[q1,B],[b,B],R} {[q4,B],[B,B],R} {[q5,B],[B,B],R}

[q1,B] {[q1,B],[a,B],R} {[q2,b],[b,X],R} {[q4,B],[B,B],R} {[q5,B],[B,B],R}

[q2,k] {[q2,a],[a,B],R} {[q2,b],[b,B],R} {[q3,B],[k,B],L} {[q2,b],[b,X],R}

[q3,B] {[q2,B],[B,B],L} {[q2,B],[B,B],L} {[q5,B],[B,B],R} {[q0,B],[B,B],R}

ME= ({[q0,B],[q1,k],[q2,k],[q3,k],[q4,k],[q5,B],[q6,B] | k {a,b}}, {a,b}, {a,b,B}, E, [q0,B], B, {[q6,B]}) onde E

definido por:

E a b B

[q0,B] [q1,a],a,R [q1,b],b,R [q5,B],B,R

[q1,k] [q1,k],a,R [q1,k],b,R [q2,k],B,L

[q2,a] [q3,b],a,L [q4,b],a,L

[q2,b] [q4,a],b,L [q3,a],b,L

[q3,a] [q6,B],a,L [q6,B],a,L [q6,B],a,L

[q3,b] [q6,B],b,L [q6,B],b,L [q6,B],b,L

[q4,a] [q6,B],a,L [q5,B],a,L [q5,B],a,L

[q4,b] [q5,B],b,L [q6,B],b,L [q5,B],b,L

5) Como voc faria para criar uma MT para aceitar a unio das linguagens reconhecidas por duas MTs

distintas? Tente apontar o que seria necessrio fazer para criar MTs para cada possvel par de mquinas do

exerccio acima (desconsidere as alteraes feitas na entrada concentrando-se na linguagem reconhecida

por cada MT).

6) Refaa o exerccio acima para a intercesso.