2022 2 APS para a AV1 - Teoria Computação

Prévia do material em texto

CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA DA COMPUTAÇÃO – PROF.: JÚLIO SILVEIRA – 2022/2 
ATIVIDADE SUPERVISIONADA PARA A AV1 
 
 Trabalho em grupo: entre QUATRO e SEIS ALUNOS: SOMENTE aceitarei os trabalhos com esta configuração. 
 FORMA DE ENTREGA: postagem de arquivo EXCLUSIVAMENTE no formato PDF, no link disponível no AVA. 
 DATA DA ENTREGA: informada no próprio link para a postagem do arquivo. 
 FORMATO DO TRABALHO: 
O PDF deve ser gerado a partir de editores eletrônicos para textos e gráficos (para desenho dos grafos). 
NÃO SERÃO CONSIDERADAS postagens com FOTOS ou com TEXTO MANUSCRITO. 
 LEIA ATENTAMENTE AS INSTRUÇÕES: o DESENVOLVIMENTO DA QUESTÃO É OBRIGATÓRIO, quando solicitado! 
 ATENÇÃO: o cabeçalho do arquivo deve conter a turma e o nome completo dos integrantes. 
 MUITO IMPORTANTE: trabalho com indícios de similaridade, todos serão avaliados com grau ZERO. 
 
Questão 1 (0.4 pontos) TEMA 1 
 
i. Enumere TODAS as sequências DISTINTAS de comprimento CINCO que pertençam à linguagem { 0, 11 }*. 
Obs.: Separe as sequências com vírgula. 
 
Questão 2 (0.8 pontos) TEMA 2 
 
Para o AFD M abaixo, onde I = { a, b } e O = { 0, 1 }, faça o que se pede: 
 
e0/ e1/ 
e2/ 
 
 
i. (0.2) Complete o seu grafo de estados, sabendo que a sequência de entrada aaa gera a saída 0110. 
ii. (0.6) Desenhe a ÁRVORE DE PROCESSAMENTO para M gerar a sequência de saída 0111. 
A seguir, enumere TODAS as sequências de entrada que geram a saída 0111. 
ATENÇÃO: Sua resposta SOMENTE será considerada COM A ÁRVORE DE PROCESSAMENTO! 
 
Questão 3 (0.8 pontos) TEMA 3 
 
Para cada AFD reconhecedor M abaixo, caracterize CORRETAMENTE, em português, a linguagem L(M): 
Não precisa indicar qual é o alfabeto de entrada; assuma que ele já está implícito. 
 
a) M1 
a
b
e3
e1
a,b
e4
a,b
a,b
a
e0
b
e6e5
b
a,b
a
e2
 
 
b) M2 
0
1
0
e4
1
0,1
0
1
e5e0
e1 e2
e3
1
0
0 1
 
 
 
 
CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA DA COMPUTAÇÃO – PROF.: JÚLIO SILVEIRA – 2022/2 
ATIVIDADE SUPERVISIONADA PARA A AV1 
 
c) M3 
a
b
a
b
b
b
e0
e1
e2
e3
a
e4
a
ba
 
 
d) M4 
0
1
0,1
e1 e2
e4e0
e3
0
0,1
1
0,1
 
 
 
 
Questão 4 (0.8 pontos) TEMA 4 
 
Para o alfabeto de entrada I = { a, b }, construa os AFD’s que reconheçam as linguagens abaixo: 
 
i. Sequências que contenham duas ocorrências da subsequência ab. 
ii. Sequências que contenham duas ocorrências CONSECUTIVAS da subsequência ab. 
iii. Sequências em que o segundo símbolo seja igual ao último símbolo. Ex.: aa, ab, baa, babbbbba. 
iv. Sequências de comprimento par e finalizadas por dois símbolos iguais. Ex.: aa, aabb, babb. 
 
Questão 5 (0.6 pontos) TEMA 5 
 
Escreva as expressões regulares que caracterizem as linguagens a seguir. Considere o alfabeto { 0, 1 }. 
 
i. Sequências que contenham o símbolo 0 na 2ª posição e que tenham comprimento PAR. 
ii. Sequências iniciadas e finalizadas pelo símbolo 0, e de comprimento ÍMPAR. 
iii. Sequências que NÃO SEJAM finalizadas por dois símbolos iguais. Ex.: λ, 0, 1, 01, 010, 0001, … 
 
Questão 6 (0.6 pontos) TEMA 5 
 
Para a expressão regular abaixo, caracterize EM PORTUGUÊS a linguagem correspondente. 
Considere que o alfabeto já está implícito: {a,b} ou {0,1} 
 
i. 01(11)*0 
ii. (00)*1(11)* 
iii. 01(11)* v 10(00)* 
 
BONS ESTUDOS!