2022 1 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/1 
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 { 1, 001 }*. 
Obs.: Separe as sequências com vírgula. 
ii. Enumere TODAS as sequências DISTINTAS de comprimento OITO que pertençam à linguagem { 00, 110 }*. 
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/1 
b
b
b
e1/0 
e2/0 
a
a
a
 
 
i. (0.2) Escreva a sequência de saída gerada por M ao processar a sequência de entrada aababb. 
ATENÇÃO: desenhe também a tabela que mostre todas as transições de estados, conforme visto no Tema 1. 
ii. (0.6) Enumere todas as sequências de entrada que levam M a gerar a sequência de saída 10000. 
ATENÇÃO: gere a A ÁRVORE DE PROCESSAMENTO de M (veja item 2.4.1 do TEXTO DE APOIO). 
Sua resposta será considerada somente com a ÁRVORE DE PROCESSAMENTO! 
 
Questão 3 (0.8 pontos) TEMA 3 
 
Para cada AFD reconhecedor M abaixo, faça o que se pede: 
 
i. Enumere todas as sequências α ∈ L(M) tais que |α| = 4. 
ii. Enumere todas as sequências α ∉ L(M) tais que |α| = 4. 
iii. Descreva a linguagem L(M) em português. 
 
a) M1 
0
1
0,1
1
e3e2e1e0
1 0
0
 
 
b) M2 
a
b
b
e6e0
b
a
a e4
e1
e3
a,b
a
b
e2
e5
a,b
a
b
 
 
 
Questão 4 (1.0 ponto) 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 dois a’s consecutivos (aa) OU dois b’s consecutivos (bb). 
ii. Sequências que contenham dois a’s consecutivos (aa) E dois b’s consecutivos (bb). 
iii. Sequências que contenham uma quantidade par de símbolos ‘a’ e exatamente um símbolo ‘b’. 
iv. Sequências não vazias de comprimento par, em que o símbolo inicial só ocorra uma vez. 
 
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 possuam no máximo dois símbolos 1. 
ii. Sequências de comprimento ímpar e exatamente uma ocorrência do símbolo inicial. 
iii. Sequências de comprimento par em que os símbolos inicial e final sejam iguais. 
 
Questão 6 (0.4 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. abb* v baa* 
ii. (aa v bb) (avb) (avb)* 
iii. (aa v bb) ( (avb)(avb) )* 
iv. ( (avb) (avb) )* (ab v ba) 
 
BONS ESTUDOS!