2019 1 APS Teoria da Computação (1)

Prévia do material em texto

CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA DA COMPUTAÇÃO – PROFESSOR: JÚLIO SILVEIRA 
ATIVIDADE SUPERVISIONADA PARA A AV2 – 2019/1 
INSTRUÇÕES 
I. SIGAM ATENTAMENTE as instruções e convenções definidas no enunciado do trabalho. 
II. IMPORTANTE: 
GRUPOS entre QUATRO e SEIS componentes. 
SOMENTE aceitarei grupos com esta configuração. 
III. O relatório será entregue de acordo com as instruções abaixo: 
 DATA DA ENTREGA: no dia da PROVA ESCRITA da AV2. 
 RELATÓRIO IMPRESSO, entregue em mãos. 
 DIGITADO em FOLHA A4; em ENCADERNAÇÃO ESPIRAL. 
 FONTE Arial – tamanho 11; texto com espaçamento 1.5 entrelinhas. 
 SERÃO DESCONSIDERADOS os trabalhos contendo textos MANUSCRITOS. 
 Para os desenhos dos grafos dos autômatos, usar programas encontrados na web. 
Algumas sugestões são listadas no final do enunciado. 
 SERÃO DESCONSIDERADOS relatórios contendo FOTOGRAFIAS ou COLAGENS. 
IV. ATENÇÃO: 
Trabalhos que apresentem fortes indícios de similaridade com os trabalhos de outros grupos 
serão todos (os envolvidos) avaliados com grau ZERO. 
Considere as seguintes linguagens sobre o alfabeto Γ = { a, b }: 
LA : Todas as sequências que contenham uma QUANTIDADE PAR de ocorrências do símbolo a, E EXATAMENTE 
DUAS ocorrências do símbolo b. Exemplos: 
bb, abab, abaaba, baaaba, ... 
LB : Toda sequência que contenha no mínimo dois símbolos, e cujo prefixo de comprimento dois seja igual ao 
seu sufixo de comprimento dois. Exemplos: 
aa , baba , baaba , abbbabbbab , ... 
LC : Todas as sequências que NÃO contenham a subsequência aa. Exemplos: 
 λ, a, b, ab, ba, aba, abb, bab, bbb, ... 
1) Desenhe os grafos correspondentes às seguintes linguagens sobre o alfabeto Γ = { a, b }: (0.8) 
a) LA 
b) LB 
c) LC 
d) L [ ( (aa)* ∨ (bb)* ) ( a* ∨ b* ) ] 
e) L [ ( (aa)* ∨ (bb)* ) ( a* ∨ b* ) ] – L [ (a* ∨ b* ) ] 
2) Escreva as expressões regulares das seguintes linguagens sobre o alfabeto Γ = { a, b }: (0.8) 
a) LA = 
b) LB = 
c) LC = 
d) L [ ( (aa)* ∨ (bb)* ) ( a* ∨ b* ) ] ∩ L [ ( (a ∨ b) (a ∨ b) )* ] = 
e) L [ ( (aa)* ∨ (bb)* ) ( a* ∨ b* ) ] – L ( a* ∨ b* ) = 
CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA DA COMPUTAÇÃO – PROFESSOR: JÚLIO SILVEIRA 
ATIVIDADE SUPERVISIONADA PARA A AV2 – 2019/1 
3) Converta o AFN abaixo no seu AFD correspondente, considerando I = { a, b }. (0.4) 
 
ATENÇÃO: utilize RIGOROSAMENTE as mesmas convenções e notação adotadas nas aulas/slides. 
q0
a
q2
a,b
q1
a,b
 
 
 
 
Alguns links para softwares de edição de autômatos: 
 https://automata-editor.soft112.com/ 
 http://www.jflap.org/ 
 https://download.cnet.com/Visual-Automata-Simulator/3000-2053_4-54760.html 
 
BONS ESTUDOS!