Alan Turing

Teoria da Computação
Aula 9
Prof. Me. João Paulo R. de Siqueira

Prof. Me. João Paulo R. Siqueira – www.jpsiqueira.com.br

1

Exemplo 3
• Máquina de Turing de duplo balanceamento;

Duplo_Bal = { anbn | n ≥ 0 }

Prof. Me. João Paulo R. Siqueira – www.jpsiqueira.com.br

2

Exemplo 3
(A/A, D)

ab aab abb aabb aba

q3

(b/B, E) q1 q2

(a/a, D)
(B/B, D)

(a/a, E)
(B/B, E)

(B/B, D)

(�/ �, E)

Analise as palavras: (�/ �, D)

(B/B, D)

q0

(a/A, D)

q4

• Duplo_Bal = { anbn | n ≥ 0 }
3

Exemplo 3
M = ( {a,b} , {q0,q1,q2,q3,q4}, Π, q0, {q4}, {A,B} , β, ⍟)
∏

⍟

a

→q0 (q0, ⍟, D) (q1, A, D)

q1 q2 q3

←q4

b

A

(q1, a, D) (q2, B, E)
(q2, a, E)

B

(q3, B, D) (q4, �, D)

(q1, B, D)
(q0, A, D)

�

(q2, B, E)

(q3, B, D)

(q4, �, E)

4

Exercícios
1. Seja o alfabeto ∑ = {0, 1} e nele a linguagem L= (00*), composta por todas as cadeias com um ou mais zeros (sem 1’s). Construa uma MT que aceite esta linguagem.

2. Seja o alfabeto ∑ ={a,b} e a linguagem composta pelas cadeias com um número de a’s igual ao número de b’s, em qualquer ordem. Por exemplo: ab, ba, abaaabbabb, etc.

M = (Σ, Q, Π, q0, F, V, β, ⍟)
Prof. Me. João Paulo R. Siqueira – www.jpsiqueira.com.br

5

Para exercitar

a) { w | w possui aaa como subpalavra }

b) { w | o sufixo de w é aa }
c) { w | w possui um número ímpar de a e b }
d) { w | w possui número par de a e ímpar de b }
e) { w | w possui número par de a e par de b }

Prof. Me. João Paulo R. Siqueira – www.jpsiqueira.com.br

9

Modelos equivalentes

Prof. Me. João Paulo R. Siqueira – www.jpsiqueira.com.br

10

Modelos equivalentes
• MT determinística
– A facilidade de não determinismo não aumenta o poder computacional da MT;
• MT com fita infinita à esquerda e à direita
– A modificação na definição básica da MT permitindo que a fita seja infinita dos dois lados não aumenta o seu poder computacional; • MT com