Complexidade de Linguagens
Influência do Modelo de
Computação
Profa. Sandra de Amo
Teoria da Computação
Mestrado em Ciência da Computação
Fato importante
• Decidibilidade não é afetada pelo modelo de
computação usado: Tese de Church
– Se uma linguagem é decidível por uma máquina de
Turing a duas fitas, ou não-determinista, etc então é
decidível por uma máquina a uma fita.
• Complexidade é afetada pelo modelo de
computação usado.
– Modelo padrão utilizado : Máquina de Turing
Determinista a uma fita.
Exemplo
L = {0n 1n | n ≥ 0}
• L é decidida por uma máquina a uma fita O(n2)
• L é decidida por uma máquina a uma fita
O(nlogn)
• L não pode ser decidida por uma máquina de
Turing a uma fita O(n)
– Teorema: Toda linguagem que pode ser decidida por
uma MT a uma fita o(nlogn) é regular !
– L = {0n 1n | n ≥ 0} não é regular.
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
qo
B
qo
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
B
B
B
B
B
qo
0
B
qo
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
B
B
B
B
qo
0
0
B
qo
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
B
B
B
qo
0
0
0
B
qo
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
B
B
B
qo
0
qo
0
0
B
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
B
B
qo
0
0
qo
0
B
B
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
B
qo
0
0
0
qo
B
B
B
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
B
qo
0
0
0
B
qo
B
B
B
Exemplo
L = {0n 1n | n ≥ 0} pode ser decidida por
uma máquina de Turing O(n) a duas fitas
0
0
0
1
1
1
B
B
B
B
B
B
B
B
qa
0
0
0
B
B
qa
B
B
B
Complexidade
• Scan da fita 1 para testar se tem 0 depois de 1 : O(n)
• Scan da fita 1 copiando os zeros na fita 2
• Scan da fita 1 comparando os 1’s com os 0’s da fita 2,
•
marcando os 0’s e 1’s que se correspondem, até que
acabem os 1’s da fita 1, ou acabem os 0’s da fita 2.
Scan das fitas:
– Se tem 0’s não marcados na fita 2 rejeita.
– Se tem 1’s não marcados na fita 1 rejeita.
– Caso contrário, aceita.
Complexidade: O(n) + O(n) + O(n) + O(n) = O(n)
Relação da Complexidade entre
Modelos Deterministas
Seja t(n) ≥ n.
Toda máquina de Turing M a múltiplas
fitas O(t(n)) é equivalente a uma
máquina de Turing S a uma fita O(t2(n))
Como simular uma configuração de
M’ numa máquina com 1 fita:
1
0
B
B
B
B
B
B
B
B
B
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
#
0
0
#
q2
0
q2
1
0
B
q2
#
1
0
0
B
#
1
Construção da Máquina Simples S
S = No input w faça:
1. Escreve na fita de S o input w’ correspondente à
configuração inicial da máquina M (com w na sua fita
1).
2. Para simular cada movimento de M:
1.
2.
3.
Varre a fita de S, a partir do primeiro # até o (k+1) – ésimo, e
“memorize” os k simbolos com pontinhos. Aplique a transição
de M’ correspondente.
Varre a fita de S novamente a partir do primeiro #, aplicando
as modificações ditadas pela transição de M correspondente à
sequência de simbolos memorizada.
Caso um pontinho deva ser colocado em cima de um #,
escreva B com pontinho neste lugar, e dê um shift na fita para
a direita a partir desta posição.
Análise da Máquina S
• Scan para transformar o input w em um input w’ que simula a
configuração inicial da máquina M = O(n)
• Para cada passo da máquina M quantos passos S executa ?
– Varre 1 vez a fita para “memorizar” os pontinhos :
• k. x casas varridas, onde x = tamanho máximo das porções
ocupadas pelas fitas de M ≤ t(n) = O(t(n))
– Varre outra vez a fita para executar um passo de M : O(t(n))
Complexidade :
O(n) + t(n). O(t(n)) = O(n) + O(t2(n)) =
= O(t2(n)) , pois n ≤ t(n)
Fato importante
• Se complexidade é polinomial utilizando
um modelo determinista a múltiplas fitas
então também é polinomial utilizando
um modelo determinista a fita única.
Polinomial a k-fitas <--> Polinomial a 1 fita
Relação da Complexidade entre Modelos
Determinista e não-Deterministas
Seja t(n) ≥ n.
Toda máquina de Turing M nãodeterminista a uma fita O(t(n)) é
equivalente a uma máquina de Turing S
determinista a uma fita 2 O(t(n))
Exemplo
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,B,R)}
0
0
1
1
q0 q0 q0 q0
B
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
q0
q0 q1
q1
0
1 q0
B
qa
B
qr
0
q1
0
0
q1
q1
1
q1
q0
1
q0
q0
q1
B
q1
B
q1
B
qr
looping
1
Análise da Máquina Determinista S
• Para input w de tamanho n
• Tamanho máximo dos caminhos da máquina M =
•
•
t(n)
Quantos caminhos no máximo ? bt(n)
b = número máximo de alternativas da função de
transição de M
Total de passos no pior dos casos =
t(n) . bt(n)
Complexidade = 2O(t(n))
Exemplo : Linguagem Exponencial
E = {<M,w> | M aceita w em até 2|w| passos}
Suponhamos que E  P
A linguagem
E1 = {<M> | M aceita <M> em até 2|<M>| passos} seria polinomial
Logo E1  P.
E1(<M>) = qa  M não aceita <M> em até 2|<M>| passos
E1(<M>) = qr  M aceita <M> em até 2|<M>| passos
Como E1  P então existe máquina de Turing M* que decide E1 em
O(p(n)), p = polinômio
Sabemos que existe n0 tal que para n ≥ n0, p(n) ≤ 2n
Podemos supor que |<M*>| ≥ n0
Logo p(|<M*>| ) ≤ 2
|<M*>|
O que acontece se aplicarmos M* a <M*> ?
M* pára em p(|<M*>| ) passos:
1. Se pára em qa: M* aceita <M*> em p(|<M*>| ) < 2 |<M*>|
passos. Logo, pela definição de M*, M* não aceita <M*>
2. Se pára em qr: M* rejeita <M*> em p(|<M*>| ) < 2 |<M*>|
passos. Logo, pela definição de M*, M* aceita <M*>.
Contradição !!
Logo: E  P