CCT0737 NC Av2 20221

Prévia do material em texto

CURSO: CAMPUS: DISCIPLINA: 
Tecnologia da Informação Nova América CCT0737 – Teoria da Computação 
ASS.: NOME: 
 
DATA: Prova Turma: Grau: MATRÍCULA: 
 
14 / 06 / 2022 
 
Nova Chance 
 
3003 
 
 
 
 
1 / 6 – NC Av. 2 – CCT0737 – 3003 – 2022.1 
1ª Questão (1,0 Pto.) 
Assinale a afirmativa que contém apenas entradas válidas para o AFD abaixo: 
 
a) 0110001, 101010, 00000111 
b) 01000, 1010110, 000100110 
c) 0101, 101010, 000100110 
d) 0011101, 0101, 011101 
e) 1010110, 0110001, 0011101 
 
2ª Questão (1,0 Pto.) 
Assinale a alternativa que contém a quíntupla (S, Q, d, q0, F) correta para o autômato: 
 
 
 
a) ({a, b, λ}, {q0, q1, q2}, d, q0, {q1}) 
b) ({a, b}, {q0, q1}, d, q0, {q2}) 
c) ({a, b}, {q0, q1, q2}, d, q0, {q2}) 
d) ({a, b, λ}, {q0, q1, q2, q3}, d, q0, {q1}) 
e) ({a, b}, {q0, q1, q2}, d, q0, {q1}) 
 
2 / 6 – NC Av. 2 – CCT0737 – 3003 – 2022.1 
3ª Questão (1,0 Pto.) 
Considerando a tabela de transição de estado abaixo, marque a alternativa que represente o 
autômato equivalente. Considere q0 como o estado inicial. 
 
estado a b 
q0 q1 - 
q1 - q2 
q2 {q1, q3} - 
q3 - q3 
 
a) 
 
b) 
 
c) 
 
d) 
 
 
e) 
 
 
 
 
 
 
3 / 6 – NC Av. 2 – CCT0737 – 3003 – 2022.1 
4ª Questão (1,0 Pto.) 
Marque a opção com os estados que são percorridos até o estado final na entrada 
101101101: 
 
a) q0, q1, q2, q5, q5, q4, q3, q1, q2, q5 
b) q0, q1, q3, q5, q5, q4, q3, q1, q2, q5 
c) q0, q1, q3, q4, q5, q4, q3, q1, q2, q5 
d) q0, q1, q3, q5, q3, q4, q3, q1, q2, q5 
e) q0, q1, q3, q5, q5, q2, q3, q1, q2, q5 
 
5ª Questão (1,0 Pto.) 
Assinale a alternativa correta quanto a definição de um Autômato Finito Não-Determinístico 
(AFND): 
 
a) Possui apenas um estado final. 
b) O alfabeto de entrada pode ser alterado durante o movimento da fita de leitura e gravação. 
c) Pode apresentar vários estados iniciais e finais. 
d) Possui mais de um estado final. 
e) Mesmo que possua mais de um estado final, a função vai escolher sempre o mesmo caminho 
até o estado final. 
 
6ª Questão (1,0 Pto.) 
Sobre a Máquina de Turing podemos afirmar, exceto: 
 
a) É constituída de fita, unidade de controle e programa ou função de transição 
b) Foi criada em 1936 por Alan Turing sendo conhecida como a formalização de um algoritmo 
c) O programa comanda as leituras e gravações, o sentido de movimento da cabeça e define o 
estado da máquina 
d) Permite movimentos para leitura da fita em somente em uma direção 
e) O Símbolo de início de fita ocorre exatamente uma vez e sempre na célula mais à esquerda 
da fita 
 
 
4 / 6 – NC Av. 2 – CCT0737 – 3003 – 2022.1 
7ª Questão (1,0 Pto.) 
Tendo como base o autômato abaixo, marque a alternativa que represente a sua tabela de 
transição: 
 
a) 
estado a b 
q0 - {q1,q2} 
q1 q2 - 
q2 - {q1, q3} 
q3 - q3 
 
b) 
estado a b 
q0 - q1 
q1 q2 - 
q2 - {q1, q3} 
q3 q3 - 
 
c) 
estado a b 
q0 - q1 
q1 - q2 
q2 {q1, q3} - 
q3 q3 - 
 
d) 
estado a b 
q0 q1 - 
q1 q2 q2 
q2 {q1, q3} q1 
q3 q3 - 
 
e) 
estado a b 
q0 q1 - 
q1 (q2,q3} 
q2 {q1, q3} - 
q3 - q3 
 
 
5 / 6 – NC Av. 2 – CCT0737 – 3003 – 2022.1 
8ª Questão (1,0 Pto.) 
Considerando a Máquina de Turing abaixo marque a alternativa que indica os resultados 
obtidos ao término da execução das seguintes filas de entrada: aaaaaa e ababbba. 
 
a) bbbbb e babbaba 
b) bbaba e babbaab 
c) bbbab e babaaab 
d) babbb e bbaabba 
e) aabbb e aaabbbb 
 
9ª Questão (1,0 Pto.) 
Com base no autômato de pilha abaixo, informe a quantidade de interações que irão ocorrer 
para que sejam aceitos a sequência: 1112111. 
 
a) 4 
b) 5 
c) 7 
d) 8 
e) 9 
 
 
6 / 6 – NC Av. 2 – CCT0737 – 3003 – 2022.1 
10ª Questão (1,0 Pto.) 
Considerando o autômato de Máquina de Turing abaixo, marque a alternativa com os dados 
que serão aceitos. 
 
 
a) 131211 
b) 133211 
c) 1333211 
d) 13321 
e) 133122