itc exerc 1aVA(Ellen Souza)

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL RURAL DE PERNAMBUCO 
UNIDADE ACADÊMICA DE SERRA TALHADA 
BACHARELADO EM SISTEMAS DE INFORMAÇÃO 
 
UFRPE 
 
Exercício Introdução à Teoria da Computação – 1ª VA 
1. Qual o objetivo da Teoria da Computação? 
2. Defina os termos abaixo: 
a) Linguagem formal 
b) Autômato 
c) Alfabeto 
d) Palavra 
e) Gramática 
3. Utilizando a expressão regular R = (a.b)+, forneça: 
a) Um AFD que reconheça a linguagem representada por R. 
b) Especifique a quíntupla para o AFD criado. 
c) Uma cadeia que é reconhecida pela linguagem representada por R. 
d) Uma cadeira que não é reconhecida pela linguagem representada por R. 
 
4. Construa o AFD para o AFN descrito abaixo. Forneça a quíntupla do AFD construído. 
M = {{q0, q1, q2, qf}, {a,b}, δ, q0, {qf}} 
δ(q0,a) = {q0, q1} δ(q1,a) = {qf} δ(qf,a) = {qf} 
δ(q0,b) = {q0, q2} δ(q2,b) = {qf} δ(qf,b) = (qf} 
 
5. Encontre o AFD mínimo para o autômato descrito abaixo. Forneça a quíntupla do AFD 
mínimo. 
M = {{q0, q1, q2, q3, q4}, {0,1}, δ, q0, {q4}} 
δ(q0,0) = q1 δ(q1,0) = q2 δ(q2,0) = q1 δ(q3,0) = q2 δ(q4,0) = q4 
δ(q0,1) = q3 δ(q1,1) = q4 δ(q2,1) = q4 δ(q3,1) = q4 δ(q4,1) = q4 
 
6. Com relação à Linguagem Regular, responda: 
a. De que forma o estudo linguagem em questão pode ser abordado? 
b. Qual gramática gera a linguagem em questão? Como suas regras são 
formadas? Cite exemplos?