2018.1 AV1 Teoria da Computação

Prévia do material em texto

Prova: AV1( X ) AV2 ( ) AV3( ) – Teoria da Computação 
 
Questão 1 (1,2 pontos) 
 
Assinale quantas sequências DISTINTAS de comprimento QUATRO pertencem à linguagem { a, ab, bbb }* 
 
a) Menos que 5. b) Exatamente 5. c) Exatamente 6. d) Exatamente 7. e) Oito ou mais. 
 
 
Questão 2 (1,2 pontos) 
 
Seja M um AFD de processamento qualquer, que processa sequências de entrada α ∊ I*, e gera sequências de 
saída β ∊ O*. Considere as seguintes afirmações sobre M: 
 
I. M pode ler a sequência de entrada λ, mas não pode gerar a sequência de saída λ. 
II. Se o alfabeto de entrada I for igual ao alfabeto de saída O, teremos | α | = | β |. 
III. É possível M processar duas sequências α distintas e gerar a mesma sequência β. 
 
Das afirmações acima. 
 
a) Exatamente uma é verdadeira. 
b) Todas as três são verdadeiras. 
c) São verdadeiras apenas I e II. 
d) São verdadeiras apenas II e III. 
e) São verdadeiras apenas I e III. 
 
 
Questão 3 (1,3 pontos) 
 
Seja o AFD M abaixo, onde as transições de estados são dadas pela função δ(e,i): 
 
Estado 
atual 
δ(e,i) 
Saída 
a b 
e0 e0 e1 0 
e1 e2 e1 1 
e2 e1 e0 1 
 
Assinale a única opção em que todas as sequências de entrada, processadas por M, geram a saída 0111: 
 
a) bab e bba. 
b) bbb e bab. 
c) baa e bba. 
d) aba e abb. 
e) aab e abb. 
 
Questão 4 (1,3 pontos) 
 
Quantas sequências de comprimento SETE são reconhecidas pelo AFD abaixo? 
e0
a
b
a
e1
b
 
e0 é o estado inicial 
a. Menos que 41 sequências. 
b. Entre 41 e 50 sequências. 
c. Entre 51 e 60 sequências. 
d. Entre 61 e 70 sequências. 
e. Mais do que 70 sequências. 
 
 
Questão 5 (1,4 pontos) 
 
Descreva em português as linguagens reconhecidas por cada AFD abaixo. 
 
a) 
0
1
1
0
e1
e2
e3e0
1
0
0,1
 
Resposta: 
b) 
e0
0
1
1
0
1
e1 e2
0
1
e4e3
0
0
1
 
Resposta:
 
Questão 6 (3,6 pontos) 
 
Para I = { a, b } construa AFD’s que reconheçam as seguintes linguagens: 
 
a) Sequências não vazias em que o número de TODAS as ocorrências do símbolo inicial é par. 
b) Sequências de comprimento par, que contenham DOIS OU MAIS símbolos, sendo todos eles iguais. 
 
GABARITO 
 
Questão 1 d) Exatamente 7. Sequências: abbb, bbba, abab, aaab, aaba, abaa, aaaa 
Questão 2 e) São verdadeiras apenas I e III. 
Questão 3 c) baa e bba. Apenas as sequências baa, bba e bbb geram a saída 0111. 
Questão 4 d) Entre 61 e 70 sequências. Temos 26 sequências finalizadas por b. 
Questão 5 a) Sequências com pelo menos uma ocorrência de cada símbolo do alfabeto { 0, 1 }. 
 b) Sequências finalizadas com dois símbolos distintos: 01 ou 10. 
Questão 6 
 
a) 
 
e3
a
e2
e4
a
b
b
e1
a
b
b
e10
b
aa
 
 
b) 
e3
a
e2
e4
a
b
e1
a
b
b
e10 a,be5
b b
a a
 
 
 
BOA PROVA!