gabarito Av1Teoria da Computação

Prévia do material em texto

QUESTÕES OBJETIVAS E DISCURSIVAS 
PROVA AV1 – DISCIPLINA: TEORIA DA COMPUTAÇÃO – TURMA: 132 
 
1. A AV1 deve ser entregue individualmente no local apropriado do AVA 
2. As resoluções da atividade devem ser digitadas 
3. A atividade deve conter: 
1. Nome da disciplina 
2. Código da Turma 
3. Nome e matrícula do aluno 
4. A data de entrega é até 03/10/2020. 
5. A nota máxima dessa atividade é 7,0. 
6. Todas as respostas devem ter duas etapas explícitas: desenvolvimento e 
resultado. 
 
Questão 1 (1,4 pontos) 
Considerando uma linguagem cujo alfabeto é dado por {a,b}, marque Falso ou Verdadeiro 
para as afirmações abaixo. 
a) {a}* ⊂ {aa}* V ( ) F ( ) 
b) {aa}* ⊂ {a}* V ( ) F ( ) 
c) {a}{a}* ⊂ {a}{a,b}* V ( ) F ( ) 
d) {a}* ∪ {b}* = {a,b}* V ( ) F ( ) 
e) { a }* ∩ { b }* = ∅ V ( ) F ( ) 
f) { a }* – { b }* ≠ { a }* V ( ) F ( ) 
 
 
DESENVOLVIMENTO: 
 
Resposta 
a) {a}* ⊂ {aa}* V ( ) F ( X ) pois a ∈ {a}*, mas a ∉ {aa}* 
b) {aa}* ⊂ {a}* V ( X ) F ( ) 
c) {a}{a}* ⊂ {a}{a,b}* V ( X ) F ( ) 
d) {a}* ∪ {b}* = {a,b}* V ( ) F ( X ) pois ab ∉ {a}* ∪ {b}* (veja questão II.b) mas 
ab ∈ {a,b}* 
e) { a }* ∩ { b }* = ∅ V ( ) F ( X ) pois { a }* ∩ { b }* = { λ } ≠ { } 
f) { a }* – { b }* ≠ { a }* V ( X ) F ( ) pois { a }* – { b }* = { a, aa, aaa, … }, não 
possuindo λ como elemento. 
 
 
RESULTADO: 
 
 
Questão 2 (1,4 pontos) 
Para o AFD abaixo, onde e o estado inicial é e0, o alfabeto de entrada é I = { 0, 1 } e o alfabeto 
de saída é O = { a, b }: 
e0/ e1/
e2/
 
a. Complete o seu grafo de estados, sabendo que a sequência de entrada 111 gera a saída 
abba. 
b. Enumere TODAS as sequências de entrada que geram a saída abbb. 
 
 
DESENVOLVIMENTO: 
 
 
 
 
 
RESULTADO: 
 
 
 
Questão 3 (1,4 pontos) 
 
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 – veja o 
exemplo. 
 
 
a,b
a,b
e0 e1
 
Resposta: Sequências de comprimento par. 
 
a) 
 
Sequências de quaisquer combinações de 0’s e 1’s , L = { ε , 0, 1, 01, 10, 11, 010, ....} 
b) 
 
Sequências de quaisquer combinações de 0’s e 1’s , L = { ε , 0, 1, 01, 10, 11, 010, ....} 
 
 
 
DESENVOLVIMENTO: 
 
 
RESULTADO: 
 
 
Questão 4 (1,4 pontos) 
 
Para I = { a, b }, construa AFD’s que reconheçam as linguagens a seguir. 
i. L(M) = palavras de comprimento ímpar. 
ii. L(M) = { λ, 0, 1, 00, 11, 000, 111, 0000, 1111, 00000, 11111, … } 
 
DESENVOLVIMENTO: 
 
solução 
 
e0 e1
a,b
a,b 
 
 
 
a,ba
b
a
a
b
b
e0
e1
e2
e3
 
RESULTADO: 
 
 
Questão 5 (1,4 pontos) 
 
3) Escreva as expressões regulares que caracterizem as linguagens a seguir. Considere o 
alfabeto { a, b }. 
a) Sequências de comprimento ímpar que contenham todos os símbolos iguais. 
b) Sequências de comprimento par e iniciadas pelo símbolo a. 
 
DESENVOLVIMENTO: 
 
Resposta 
 
a) Sequências de comprimento ímpar que contenham todos os símbolos iguais. 
Resp.: a(aa)* v b(bb)* 
 
b) Sequências de comprimento par e iniciadas pelo símbolo a. 
Resp.: a (a v b) ( (a v b) (a v b) )* 
 
RESULTADO: