Exercicio_1_Automato_Resposta_1

Prévia do material em texto

AFD: 
Composição da quíntupla do AFD: M = (alfabeto, estados, função, estado inicial, estado final) 
Para cada autômato finito determinístico M de entrada W descreva a linguagem L que pode 
ser reconhecida pela função programa apresentada na figura: 
Com base nos AFNs abaixo, faça o que se pede 
a) Apresente a quíntupla do AFD: 
b) De acordo com as entradas apresentadas nas tabelas correspondentes, informe se são “aceitas” 
ou “rejeitadas”: 
c) Qual a linguagem reconhecida pelo AFD (Qual o objetivo?) 
 
Exercício 1: 
 
a) M = (, Q, , q0, F)  M = ({a,b}, {q0, q1, q2], 3, q0, q1) 
3 a b 
q0 q0 q1 
q1 - q2 
q2 - q1 
 
b) 
aa Rejeitada 
bb Rejeitada 
abaa Rejeitada 
bba Rejeitada 
bbaa Rejeitada 
bbbb Rejeitada 
aaaa Rejeitada 
baa Rejeitada 
abb Rejeitada 
bbb Aceito 
baab Rejeitada 
abba Rejeitada 
bbbbb Aceito 
 
c) Número ímpar de “b” no final da cadeia. 
d) Quais os estados que são percorridos para reconhecer a palavra? bbb – qo, q1, q2, q1 
aabbb – q0, q0, q0, q1, q2, q1