Lista de Exercícios - LFA 01

Prévia do material em texto

Lista de Exercícios 
Autômatos Finitos – Determinísticos (AFD) e não Determinísticos (AFND) 
 
1) De acordo com a sequência de estados abaixo, desenhe o AFD, analise 
as palavras e defina se é aceita ou rejeitada. Justifique. 
 
a) L= {010010} 
b) L= {101000} 
c) L= {111010} 
d) L= {010111} 
 
M = ({0,1}, {q0, q1, q2, q3}, δ, {q0}, {q3}), onde δ é dado abaixo: 
 
 
 
2) Defina a quíntupla e a tabela de transição de cada autômato abaixo. Diga 
se é um AFD ou AFND: 
 
a) 
 
 
 
 
 
 
 
 
 
 
b) 
 
 
 
 
c) 
 
 
 
 
 
 
3) Analisando os autômatos no exercício anterior ( 2 ) teste em cada um dos 
autômatos as linguagens abaixo e diga quais são aceitas e rejeitadas. 
Justifique. 
 
a) L= {abbad} 
b) L= {aabbc} 
c) L= {bbab} 
d) L= {adbc} 
e) L= {ababaa} 
 
4) Quais dos seguintes AFNs abaixo reconhecem cada uma das seguintes 
linguagens? Defina a quíntupla de cada autômato. 
 
a) L= {a} 
b) L= {aa} 
c) L= {aab} 
d) L= {ab} 
e) L= {abab} 
f) L= {aba} 
g) L= {abaa} 
 
 
 
 
 
 
 
5) Diga se a linguagens L= {abbab} é reconhecida no autômato abaixo. Qual 
tipo desse autômato? Justifique. 
 
 
 
 
6) Desenvolva um AFD que reconhece a linguagem de números binários 
com quantidade ímpar de 1s. Desenhe quíntupla e tabela de transição. 
 
7) Analise a AFND e teste as seguintes linguagens abaixo. Desenhe tabela 
e a árvore de transição de estados. 
 
a) L= {110} 
b) L= {0110} 
c) L= {0011} 
d) L= {0101} 
e) L= {1111} 
 
8) Defina um autômato finito determinístico sobre o alfabeto {0,1} que aceite 
todas as palavras terminadas em 00. Defina a tabela de transição. 
 
9) Construa um autômato finito não determinístico sobre o alfabeto {0,1} que 
aceite todas as palavras iniciadas com 1 e terminadas em 0. Defina a 
tabela de transição. 
 
10) Em um restaurante o almoço tem o custo de R$5,00, os clientes só 
poderão efetuar o pagamento com moedas de R$1,00, notas de R$2,00 
ou R5,00. A soma das moedas e notas não deverão exceder o valor do 
almoço. 
 
Analise o cenário acima e desenvolva uma AFND que aceite ou rejeite 
qualquer combinação de moedas e notas (respeitando a definição acima) 
para o problema. Construa tabela de transição. Defina sua quíntupla.