2019 2 APS Teoria da Computação

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/2 
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 não contenham nenhuma ocorrência “isolada” do símbolo a. 
Em outras palavras: sequências em que todo símbolo a contém algum vizinho que também seja o símbolo a. 
Exemplos de α ∈ LA: λ, b, bbbaa, aaabaa, baaab, ... 
Exemplos de α ∉ LA: a, abbb, bbba, bbbab, , ... 
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 em que quantidade de ocorrências da subsequência ab e igual à quantidade de 
ocorrências da subsequência ba. Exemplos: 
 λ, aba, baaaaab. 
LD : Todas as sequências em que quantidade de ocorrências da subsequência ab é par. Exemplos: 
 λ, a, bbbb, bbbaaaa, abab, bbabbbababaaabb. 
1) Desenhe os grafos correspondentes às seguintes linguagens sobre o alfabeto Γ = { a, b }: (1.2) 
a) LA b) LB c) LC d) LD 
e) L [ ( a* v b* ) ( (aa)* v (bb)* ) ] 
f) L [ ( a* v b* ) ( a* v b* ) ] 
2) Escreva as expressões regulares das seguintes linguagens sobre o alfabeto Γ = { a, b }: (0.8) 
a) LA = b) LB = c) LC = d) LD = 
e) L [ a*(bb)* v b*(aa)* ] ∩ L [ (a v b) ( (a v b) (a v b) )* ] = 
f) L [ (a* v b* ) (a* v b* ) ] – L ( a* v b* ) = 
 
CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA DA COMPUTAÇÃO – PROFESSOR: JÚLIO SILVEIRA 
ATIVIDADE SUPERVISIONADA PARA A AV2 – 2019/2 
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!