Lista 3

Prévia do material em texto

Lista de Exercícios 3 
 
A lista de exercícios é individual é deverá ser entregue em formato manuscrito. 
Data de Entrega: 06/12/2018 
 
1. Dada as seguintes linguagens: 
a) L = {anbncn | n ≥ 1} 
b) L = {a*bc*} 
c) L = {ambncm+n | n,m ≥ 0} 
d) L = {wwR | w é qualquer string de 0’s e 1’s} 
Construa a máquina de Turing e sua gramática sensível ao contexto de cada uma delas. 
2. Dada as seguintes linguagens: 
a) L = {anbmanbm | n,m ≥ 0} 
b) L = {anb2nan | n ≥ 1} 
c) L = {anbnanbn | n ≥ 1} 
d) L = {ww | w ∈ {a,b}*} 
Construa a máquina de Turing e sua gramática irrestrita de cada uma delas. 
3. Dada as regras de produção de uma gramática G: 
 S → aAB 
 aA → a | cA 
 aaB → b 
 B → bS 
Construa a máquina de Turing e indique se é uma gramática sensível ao contexto ou 
irrestrita e porque? 
4. Desenhe o diagrama de transição e descreva as linguagens associadas a cada uma das 
máquinas de Turing abaixo: 
a) M1 = ({q0,q1,q2,qf}, {0,1}, {0,1,B},δ1, q0, B,{qf}), com as transições: 
δ1 (q0,0) = (q1,1,R); 
δ1 (q1,1) = (q0,0,R); 
δ1 (q1,B) = (qf,B,R). 
 
 
b) M2 = ({q0,q1,q2,qf}, {0,1}, {0,1,B},δ2, q0, B,{qf}), com as transições: 
δ2 (q0,0) = (q1,1,R); 
δ2 (q1,1) = (q2,0,L); 
δ2 (q2,1) = (q0,1,R); 
δ2 (q1,B) = (qf,B,R).