2019 1 APS Teoria da Computação (1)
2 pág.

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


Disciplina04º - Teoria da Computacao31 materiais123 seguidores
Pré-visualização1 página
CENTRO UNIVERSITÁRIO CARIOCA \u2013 UNICARIOCA 
TEORIA DA COMPUTAÇÃO \u2013 PROFESSOR: JÚLIO SILVEIRA 
ATIVIDADE SUPERVISIONADA PARA A AV2 \u2013 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: 
\uf0b7 DATA DA ENTREGA: no dia da PROVA ESCRITA da AV2. 
\uf0b7 RELATÓRIO IMPRESSO, entregue em mãos. 
\uf0b7 DIGITADO em FOLHA A4; em ENCADERNAÇÃO ESPIRAL. 
\uf0b7 FONTE Arial \u2013 tamanho 11; texto com espaçamento 1.5 entrelinhas. 
\uf0b7 SERÃO DESCONSIDERADOS os trabalhos contendo textos MANUSCRITOS. 
\uf0b7 Para os desenhos dos grafos dos autômatos, usar programas encontrados na web. 
Algumas sugestões são listadas no final do enunciado. 
\uf0b7 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 \u393 = { 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: 
 \u3bb, a, b, ab, ba, aba, abb, bab, bbb, ... 
1) Desenhe os grafos correspondentes às seguintes linguagens sobre o alfabeto \u393 = { a, b }: (0.8) 
a) LA 
b) LB 
c) LC 
d) L [ ( (aa)* \u2228 (bb)* ) ( a* \u2228 b* ) ] 
e) L [ ( (aa)* \u2228 (bb)* ) ( a* \u2228 b* ) ] \u2013 L [ (a* \u2228 b* ) ] 
2) Escreva as expressões regulares das seguintes linguagens sobre o alfabeto \u393 = { a, b }: (0.8) 
a) LA = 
b) LB = 
c) LC = 
d) L [ ( (aa)* \u2228 (bb)* ) ( a* \u2228 b* ) ] \u2229 L [ ( (a \u2228 b) (a \u2228 b) )* ] = 
e) L [ ( (aa)* \u2228 (bb)* ) ( a* \u2228 b* ) ] \u2013 L ( a* \u2228 b* ) = 
CENTRO UNIVERSITÁRIO CARIOCA \u2013 UNICARIOCA 
TEORIA DA COMPUTAÇÃO \u2013 PROFESSOR: JÚLIO SILVEIRA 
ATIVIDADE SUPERVISIONADA PARA A AV2 \u2013 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: 
\uf0b7 https://automata-editor.soft112.com/ 
\uf0b7 http://www.jflap.org/ 
\uf0b7 https://download.cnet.com/Visual-Automata-Simulator/3000-2053_4-54760.html 
 
BONS ESTUDOS!