Teoria da computação

Prévia do material em texto

1. Ref.: 7619242 
 
Assinale a afirmativa que contém uma entrada válida para o AFND abaixo: 
 
 
 
aaaabbbb 
 
aaaab 
 
baaabbaa 
 
aaabaabbbb 
 ababbab 
 
 
Marque a alternativa que contém uma entrada inválida para o Autômato apresentado 
na figura abaixo: 
 
 
000000 
 
11111 
 
1000111 
 01010101 
 
10111 
Respondido em 28/04/2023 20:43:49 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207619242.');
Respondido em 28/04/2023 20:23:46 
 
 
 2. Ref.: 7703299 
 
 3. Ref.: 7792279 
 
Sobre o AFD representado pela quíntupla - M = ({a,b}, {q0,q1,q2,q3}, δ, q0, {q3}) e pela tabela de 
transição: abaixo, podemos afirmar que: 
 a b 
q0 {q1} ø 
q1 ø {q2} 
q2 {q1} {q3} 
q3 ø ø 
 
 
 reconhece palavras com começam com ab e terminam com 2 b's 
 
reconhece palavras com começam com b e terminam com 2 a' 
 
reconhece palavras com começam com abb e terminam com 2 ba's 
 
reconhece palavras com começam com aa e terminam com 2 b's 
 
reconhece palavras com começam com aba e terminam com 2 b's 
Respondido em 28/04/2023 20:44:03 
 
 
 4. Ref.: 7648813 
 
Tendo como base o autômato finito não determinístico abaixo, assinale a alternativa 
incorreta. 
 
 
 
 
O autômato possui os estados q0, q1, q2 e q3.. 
 
O alfabeto do autômato é formato pelos elementos ¿a¿ e ¿b¿. 
 O elemento inicial é representado pelo estado q0. 
 O elemento final é representado pelo estado q0. 
 
Quando for feita a leitura do elemento ¿a¿, o autômato estará correto se estiver em q0, q1 ou 
q3. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207703299.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207792279.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207648813.');
Respondido em 28/04/2023 19:41:43 
 
 
 5. Ref.: 7624773 
 
Sobre a Máquina de Turing podemos afirmar, exceto: 
 
 
Foi criada em 1936 por Alan Turing sendo conhecida como a formalização de um algoritmo 
 
O programa comanda as leituras e gravações, o sentido de movimento da cabeça e define o 
estado da máquina 
 
O Símbolo de início de fita ocorre exatamente uma vez e sempre na célula mais à esquerda 
da fita 
 Permite movimentos para leitura da fita em somente em uma direção 
 
É constituída de fita, unidade de controle e programa ou função de transição 
Respondido em 28/04/2023 20:24:56 
 
 
 6. Ref.: 6108284 
 
Considerando a autômato finito determinista abaixo: 
 
marque a alternativa que representa o conjunto de dados de entrada que será aceito. 
 
 
abb 
 
aaa 
 bbb 
 
bbaa 
 
aabbbbbb 
Respondido em 28/04/2023 20:23:07 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207624773.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206108284.');
 7. Ref.: 7628449 
 
Assinale a alternativa correta quanto a definição de um Autômato Finito Não-Determinístico 
(AFND): 
 
 
 
Pode apresentar vários estados iniciais e finais 
 Possui mais de um estado final 
 
Possui apenas um estado final 
 
O alfabeto de entrada pode ser alterado durante o movimento da fita de leitura e gravação 
 
Mesmo que possua mais de um estado final, a função vai escolher sempre o mesmo caminho 
até o estado final 
Respondido em 28/04/2023 20:33:38 
 
 
 8. Ref.: 7792181 
 
A partir do AFD abaixo, indique a quíntupla correspondente: 
 
 
 
M = ({a,b}, {q0,q1,q2}, δ, q0, {q3}) 
 M = ({a,b}, {q0,q1,q2,q3}, δ, q0, {q3}) 
 
M = ({a,b,0}, {q0,q1,q2,q3}, δ, q0, {q2}) 
 
M = ({a,b}, {q0,q1,q2,q3}, δ, q0, {q1,q3}) 
 
M = ({a,b}, {q1,q2,q3}, δ, q0, {q3}) 
Respondido em 28/04/2023 20:42:13 
 
 
 9. Ref.: 7706123 
 
Sobre as linguagens regulares, considere as afirmativas 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 finito. 
III. Se A e B são linguagens regulares, então A ∩ B também é. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207628449.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207792181.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207706123.');
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 afirmativas I, II e III são corretas. 
 
Somente as afirmativas I e II são corretas. 
 
Somente as afirmativas I e IV são corretas. 
 
Somente as afirmativas II, III e IV são corretas. 
 
Somente as afirmativas III e IV são corretas. 
Respondido em 28/04/2023 20:43:01 
 
 
 10. Ref.: 6107150 
 
Considerando o formato da quíntupla, abaixo descrita, de um Autômato finito determinista: 
M = (, Q, , q0, F) 
marque a alternativa que apresente o objetivo do elemento . 
 
 
Representa o estado inicial do autômato. 
 
Conjunto finito de estados possíveis do autômato. 
 
Representa o conjunto de estados finais do autômato. 
 
Função programa ou função de transição do autômato. 
 Conjunto finito de símbolos de entrada para o autômato. 
Respondido em 28/04/2023 20:23:26 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206107150.');