Lista de Exercícios - LFA 02

Prévia do material em texto

Lista de Exercícios – Valor 7 pts. 
Autômatos Finitos – Equivalências AFDA e FND / Máquina Turing 
 
1) De acordo com a sequência de estados abaixo: 
a) Desenhe o AFD, analise as palavras e defina se é aceita ou 
rejeitada. 
b) Transforme em um AFND, desenhe tabela de transição e sua 
quíntupla. Explique. 
 
a) L= {010010} 
b) L= {101000} 
c) L= {010111} 
 
M = ({0,1}, {q0, q1, q2, q3}, δ, {q0}, {q3}), onde δ é dado abaixo: 
 
 
 
 
2) Analise os AFNDs abaixo, transforme em AFD e teste as linguagens? 
Defina a tabela de transição simplificada e a quíntupla de cada autômato 
AFD. 
 
a) L= {a} 
b) L= {aa} 
c) L= {aab} 
d) L= {ab} 
e) L= {abab} 
f) L= {aba} 
 
 
 
 
 
 
 
 
 
3) Transforme o AFND em AFD e teste as linguagens? Defina a tabela de 
transição simplificada e a quíntupla do AFD. 
 
Testes as linguagens: 
L= {abbab} 
L= {bbaa} 
L= {aabba} 
 
 
 
 
 
 
 
 
 
 
 
 
 
4) Realize a conversão do AFND para AFD com sua tabela de transição 
simplificada e quíntupla: 
seja M = ({q0, q1, q2}, {0, 1}, δ, q0, {q2}) 
 
δ 0 1 
q0 {q0 q1} {q0} 
q1 Ø {q2} 
q2 Ø Ø 
 
 
 
5) Converta o AFND para AFD com sua tabela de transição simplificada e 
quíntupla. Testes as linguagens abaixo: 
 
a) L= {0110} 
b) L= {0011} 
c) L= {0101} 
d) L= {1111} 
 
 
 
 
 
 
6) Dados dois números positivos x e y. Construa uma Máquina de Turing 
que calcule x + y. 
Seja x = |z(x)| com z(x) ∈ {1}*, ou seja, o número será representado pela 
quantidade de dígitos 1 (por exemplo, 3 = 111). 
 
a) 2 + 3 = 
b) 1 + 2 = 
c) 3 + 4 = 
 
 
7) Analise a máquina de turing abaixo, desenhe sua tabela de transição, a 
fita da máquina de turing e teste as linguagens. 
 
a) ab 
b) aba 
c) aaba 
d) aaabbb 
 
 
 
Obs: 
o - Início da fita 
 β – Também conhecido como branco.