GABARITO PROVA AV2 TEORIA DA COMPUTAÇÃO

Prévia do material em texto

02/06/23, 20:04 EPS
https://simulado.estacio.br/alunos/ 1/5
Disc.: TEORIA DA COMPUTAÇÃO Turma: 3021
Aluno: JORDANE MAURELLI GARCIA Matr.: 201808199553
Prof.: ROBERTO ROSENHAIM Gabarito após: 03/06/2023 19:26
6339280393 02/06/2023 19:26:47
 1. Ref.: 7628449
Assinale a alternativa correta quanto a de�nição de um Autômato Finito Não-Determinístico (AFND):
 
Mesmo que possua mais de um estado �nal, a função vai escolher sempre o mesmo caminho até o estado �nal
O alfabeto de entrada pode ser alterado durante o movimento da �ta de leitura e gravação
Pode apresentar vários estados iniciais e �nais
Possui apenas um estado �nal
Possui mais de um estado �nal
Respondido em 02/06/2023 19:54:29
 2. Ref.: 7703299
Marque a alternativa que contém uma entrada inválida para o Autômato apresentado na �gura abaixo:
11111
1000111
01010101
000000
10111
Respondido em 02/06/2023 19:52:45
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7628449.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7703299.');
02/06/23, 20:04 EPS
https://simulado.estacio.br/alunos/ 2/5
 3. Ref.: 7706123
Sobre as linguagens regulares, considere as a�rmativas a seguir.
I. As linguagens regulares formam a classe de linguagens mais simples, dentro da hierarquia de Chomsky.
II. As linguagens regulares podem ser expressas por um autômato �nito.
III. Se A e B são linguagens regulares, então A ∩ B também é.
IV. Seja B = {ba, na}. Pode-se dizer que B* = {ε, ba, na, ab, an, baba, bana, naba, anab, nana, aban, bababa,
babana, banaba, banana, nababa, nabana, nanaba, nanana, abanba, babababa, ... }.
Assinale a alternativa correta
Somente as a�rmativas I, II e III são corretas.
Somente as a�rmativas III e IV são corretas.
Somente as a�rmativas I e IV são corretas.
Somente as a�rmativas II, III e IV são corretas.
Somente as a�rmativas I e II são corretas.
Respondido em 02/06/2023 19:50:54
 4. Ref.: 6107150
Considerando o formato da quíntupla, abaixo descrita, de um Autômato �nito determinista:
M = (S, Q, d, q0, F)
marque a alternativa que apresente o objetivo do elemento S.
Função programa ou função de transição do autômato.
Representa o conjunto de estados �nais do autômato.
Conjunto �nito de símbolos de entrada para o autômato.
Conjunto �nito de estados possíveis do autômato.
Representa o estado inicial do autômato.
Respondido em 02/06/2023 19:50:21
 5. Ref.: 7624773
Sobre a Máquina de Turing podemos a�rmar, exceto:
O programa comanda as leituras e gravações, o sentido de movimento da cabeça e de�ne o estado da máquina
O Símbolo de início de �ta ocorre exatamente uma vez e sempre na célula mais à esquerda da �ta
Permite movimentos para leitura da �ta em somente em uma direção
É constituída de �ta, unidade de controle e programa ou função de transição
Foi criada em 1936 por Alan Turing sendo conhecida como a formalização de um algoritmo
Respondido em 02/06/2023 19:32:46
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7706123.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6107150.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7624773.');
02/06/23, 20:04 EPS
https://simulado.estacio.br/alunos/ 3/5
 6. Ref.: 7703295
A partir da Máquina de Turing abaixo, indica a letra que apresenta uma entrada válida:
1111
0110
1010
0111
0000
Respondido em 02/06/2023 20:03:25
 7. Ref.: 7618911
Assinale a a�rmativa que contém apenas entradas válidas para o AFD abaixo:
011101, 101, 0100011
101, 0000111, 011101
010001, 101010, 0000111
0100011, 011101, 101010
101101101, 101010, 10101010
Respondido em 02/06/2023 20:00:24
 8. Ref.: 6108284
Considerando a autômato �nito determinista abaixo:
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7703295.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7618911.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6108284.');
02/06/23, 20:04 EPS
https://simulado.estacio.br/alunos/ 4/5
marque a alternativa que representa o conjunto de dados de entrada que será aceito.
aaa
bbb
aabbbbbb
abb
bbaa
Respondido em 02/06/2023 19:52:23
 9. Ref.: 7705593
Considere o Autômato Finito Não Determinístico (AFN) abaixo, onde A é o estado inicial e D o único estado �nal.
Qual Autômato Finito Deterministico (AFD), com  d como sua função de transição, aceita a mesma linguagem?
Estado Inicial: A
Estados Finais: C e D
d(A, b) = B
d(B, a) = C
d(C, a) = D
-----------------------
 
 
É impossível converter esse autômato �nito não determinístico em um autômato �nito determinístico
-----------------------
 
Todos os autômatos indicados em outras alternativas estão corretos
-----------------------
Estado Inicial: A
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7705593.');
02/06/23, 20:04 EPS
https://simulado.estacio.br/alunos/ 5/5
Estados Finais: D
d(A, b) = B
d(B, a) = D
d(B, b) = C
d(C, a) = D
-----------------------
 
Estado Inicial: A
Estados Finais: C
d(A, b) = B
d(B, a) = C
d(C, a) = C
-----------------------
 
Respondido em 02/06/2023 19:50:32
 10. Ref.: 7619201
Classi�que a �gura abaixo de acordo com a Teoria da Computação:
Autômato In�nito Determinístico
Representação de uma Expressão Regular
Autômato Finito Determinístico
Máquina de Turing
Autômato Finito Não-Determinístico
Respondido em 02/06/2023 19:58:22
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7619201.');