Máquinas de Turing

Prévia do material em texto

1 – A - Máquina de Turing/Máquina de Turing
2 – B - Ler/Escrever
3 – 
A – 	Q = {q0, q1, q2, q3, q4, q5, q6, q7, q8, q aceita}
	∑ = {0, 1, #}
	I = {	
 i1 (q0, Ɵ) = (q1, Ɵ, D)
		i2 (q1, 0) = (q2, X, D)
		i3 (q1, 1) = (q3, X, D)
		i4 (q1, #) = (q8, #, D)
		i5 (q2, 0) = (q2, 0, D)
		i6 (q2, 1) = (q2, 1, D)
		i7 (q2, #) = (q4, #, D)
		i8 (q3, 0) = (q3, 0, D)
		i9 (q3, 1) = (q3, 1, D)
		i10 (q3, #) = (q5, #, D)
		i11 (q4, x) = (q4, X, D)
		i12 (q4, 0) = (q6, X, E)
		i13 (q5, X) = (q5, X, D)
		i14 (q5, 1) = (q6, X, E)
		i15 (q6, 0) = (q6, 0, E)
		i16 (q6, 1) = (q6, 1, E)
		i17 (q6, X) = (q6, X, E)
		i18 (q6, #) = (q7, #, E)
		i19 (q7, 1) = (q7, 1, E)
		i20 (q7, 0) = (q7, 0, E)
		i21 (q7, X) = (q1, X, D)
		i22 (q8, X) = (q8, X, D)
		i23 (q8, β) = (q aceita, β, D)
	}
q0 = {q0}
F = {q aceita} 
V = {X}
β
Ɵ
	I
	Ɵ
	0
	1
	X
	#
	β
	Q0
	(q1, Ɵ, D)
	-
	-
	-
	-
	-
	Q1
	-
	(q2, X, D)
	(q3, X, D)
	-
	(q8, #, D)
	-
	Q2
	-
	(q2, 0, D)
	(q2, 1, D)
	-
	(q4, #, D)
	-
	Q3
	-
	(q3, 0, D)
	(q3, 0, D)
	-
	(q5, #, D)
	-
	Q4
	-
	(q6, X, E)
	-
	(q4, X, D)
	-
	-
	Q5
	-
	-
	(q6, X, E)
	(q5, X, D)
	-
	-
	Q6
	-
	(q6, 0, E)
	(q6, 1, E)
	(q6, X, E)
	(q7, #, E)
	-
	Q7
	-
	(q7, 0, E)
	(q7, 1, E)
	(q1, X, D)
	-
	-
	Q8
	-
	-
	-
	(q8, X, D)
	-
	(q aceita, β, D)
	Q aceita
	-
	-
	-
	-
	-
	-
B – 
C –	
4 –
A – 	Q = {q1, q2, q3, q4, q5, q aceita, q rejeita}
	∑ = {0, U, D}
	I = {	
 		i1 (q1, 0) = (q2, U, D)
		i2 (q1, U) = (q rejeita, U, D)
		i3 (q1, X) = (q rejeita, X, D)
		i4 (q2, 0) = (q3, X, D)
		i5 (q2, U) = (q aceita, U, D)
		i6 (q2, X) = (q2, X, D)
		i7 (q3, 0) = (q4, X, D)
		i8 (q3, U) = (q5, U, E)
		i9 (q3, X) = (q3, X, D)
		i10 (q4, 0) = (q3, 0, D)
		i11 (q4, U) = (q rejeita, U, D)
		i12 (q4, X) = (q4, X, D)
		i13 (q5, 0) = (q5, 0, E)
		i14 (q5, U) = (q2, U, D)
		i15 (q5, X) = (q5, X, E)
	}
q0 = {q1}
F = {q aceita}
	I
	0
	U
	X
	Q1
	(q2, U, D)
	(q rejeita, U, D)
	(q rejeita, X, D)
	Q2
	(q3, X, D)
	(q aceita, U, D)
	(q2, X, D)
	Q3
	(q4, X, D)
	(q5, U, E)
	(q3, X, D)
	Q4
	(q3, 0, D)
	(q rejeita, U, D)
	(q4, X,D)
	Q5
	(q5, 0, E)
	(q2, U, E)
	(q5, X, E)
	Q aceita
	-
	-
	-
	Q rejeita
	-
	-
	-