AP2_LC_FTC_2020_1 (1)

Prévia do material em texto

AVALIAÇÃO PARCIAL 2 
FUNDAMENTOS TEÓRICOS DA COMPUTAÇÃO 
 
ANTES DE COMEÇAR A PROVA, POR FAVOR, LEIA AS INSTRUÇÕES ABAIXO 
 
1ª instrução​: LEIA ​TODAS AS INSTRUÇÕES​, sem exceção! 
 
2ª instrução​: Esta é a nossa segunda avaliação parcial da disciplina de Fundamentos 
Teóricos da Computação. Como estamos em período não presencial, você poderá 
realizar esta avaliação em seu local de preferência, mas você deverá enviar suas 
respostas por e-mail ao professor (para o endereço de e-mail ​padovani@uea.edu.br​) 
até as 23h59 do dia 27/09/2020 (​domingo​). ​As respostas dos estudantes que forem 
enviadas após esse prazo serão desconsideradas​. Portanto, é aconselhável que se 
organizem para realizar o envio de forma tranquila, evitando assim inconvenientes. 
 
3ª instrução​: Sua prova pode ser desenvolvida em papel ou diretamente no 
computador. Caso faça no papel, tire foto ou escaneie suas resoluções e ​verifique se a 
imagem está legível​! Envie seu(s) arquivo(s) por e-mail, como orientado na segunda 
instrução. 
 
4ª instrução​: A pontuação do exercício estará entre colchetes junto ao enunciado. 
 
5ª instrução​: Outro aspecto importante da avaliação é a sua realização ​INDIVIDUAL​. 
Apesar da avaliação ser realizada de forma não presencial (por conta da pandemia), 
serão também temporariamente ​desconsideradas ​as respostas enviadas de todos os 
estudantes que apresentarem indícios de terem sido ​copiadas ou ​compartilhadas​. Os 
respectivos estudantes serão arguidos individualmente pelo professor, podendo a nota 
da sua avaliação ser reconsiderada ou permanecer desconsiderada (ou seja, zero), de 
acordo com a avaliação do professor, que será fundamentada e submetida à 
coordenação pedagógica nesse último caso. É compreensível o desejo de auxiliar 
colegas, contudo, este não é o momento, pois a verificação de rendimento precisa ser 
individual. Para também evitar inconvenientes para você e para seus colegas, 
recomendo ​fortemente​ que aja de maneira honesta. 
 
 
* Arte da campanha “Pequenas Corrupções – Diga Não” criada pela Controladoria-Geral da União (CGU) 
 
mailto:padovani@uea.edu.br
 
 
Exercício 1 [2.0 ponto]: Para cada uma das 3 palavras dadas a seguir, apresente qual 
será a sequência de estados percorrida ao processá-la no autômato com pilha 
determinístico abaixo. 
 
a) abcc 
b) aabbccc 
c) aabcc 
 
 
 
 
 
 
 
 
 
Exercício 2 ​[2.0 ponto]: Construa um autômato com pilha (determinístico ou não 
determinístico) capaz de reconhecer a linguagem formada por palavras da seguinte forma 
a​n​bb*c​n+1​. As seguintes palavras são exemplos de palavras aceitas por essa linguagem: 
aaabcccc, aabbccc, abcc. E estes são exemplos de palavras não aceitas: abc, aabcc, 
aabc. 
 
Exercício 3 ​[2.0 ponto]: Para cada uma das 3 palavras dadas a seguir, apresente qual 
será a sequência de estados percorrida ao processá-la na Máquina de Turing abaixo. 
a) xbx 
b) bbbbx 
c) bbbcx 
d) bbbbc 
 
 
 
 
 
 
 
 
 
 
Exercício 4 ​[2.0 ponto]: Construa uma Máquina de Turing determinística que reconheça a 
linguagem formada por palavras do alfabeto {a,b} que o último símbolo ​a seja precedido 
pelo símbolo ​b (ou seja, a palavra só é aceita se antes da última ocorrência da letra ​a 
existir a letra ​b​). Considere que todas as palavras terão, pelo menos, um ​a​. Estes são 
alguns exemplos de palavras aceitas (pois temos um b antes do último a): b​a​, bbbab​a​, 
abbababb​a​bbb, aaaaaab​a​bbb. ​Sugestão: Mova a fita de entrada até o fim e volte lendo-a 
de trás para frente até encontrar um ​a​. Ao encontrar, verifique se o símbolo anterior é ​b​. 
 
 
 
 
Exercício 5 ​[1.5 ponto]: Transforme o Autômato Finito dado abaixo em uma Gramática 
Regular. 
 
 
Exercício 6 ​[1.5 ponto]: Transforme a Expressão Regular dada a seguir em um Autômato 
Finito (considere que o alfabeto dessa ER é {0, 1, 2, 3, 4}): 
 
(2+4)*0(1+3)* 
 
 
Exercício 7 ​[1.0 ponto]: Transforme a Gramática Regular dada abaixo em um Autômato 
Finito. 
 
G=(V,T,P,S) 
V={X,Y,Z} 
T={0,1} 
P={ 
X → 1X | 0Y, 
Y → 1Z, 
Z → 0Y| 1Z | ε 
} 
S=X