Questões resolvidas
Marque a alternativa que contém uma entrada inválida para o Autômato apresentado na figura abaixo:
11111
1000111
01010101
000000
10111
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 é.
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
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 é.
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, ... }.
Somente as afirmativas I, II e III são corretas.
Somente as afirmativas III e IV 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 I e II são corretas.
Considerando o formato da quíntupla, abaixo descrita, de um Autômato finito 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 finais do autômato.
Conjunto finito de símbolos de entrada para o autômato.
Conjunto finito de estados possíveis do autômato.
Representa o estado inicial do autômato.
A partir da Máquina de Turing abaixo, indica a letra que apresenta uma entrada válida:
1111
0110
1010
0111
0000
Assinale a afirmativa 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
101, 0000111, 011101
010001, 101010, 0000111
0100011, 011101, 101010
101101101, 101010, 10101010
011101, 101, 0100011
Considerando a autômato finito determinista abaixo, marque a alternativa que representa o conjunto de dados de entrada que será aceito.
aaa
bbb
aabbbbbb
abb
bbaa
Classifique a figura abaixo de acordo com a Teoria da Computação:
Autômato Infinito 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
Quais estados estão corretos no grafo abaixo?
O grafo possui um estado inicial A.
O estado final é D.
O estado B possui uma transição para o estado C.
O estado C possui uma transição para o estado D.
O estado A possui uma transição para o estado B.
O estado B possui uma transição para o estado A.
O estado C possui uma transição para o estado A.
a) Apenas as afirmativas 1, 2 e 3 estão corretas.
b) Apenas as afirmativas 2, 4 e 5 estão corretas.
c) Apenas as afirmativas 1, 3 e 6 estão corretas.
d) Apenas as afirmativas 2, 3 e 7 estão corretas.
e) Todas as afirmativas estão corretas.
Crie sua conta grátis para liberar esse material. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Crie sua conta grátis para liberar esse material. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Crie sua conta grátis para liberar esse material. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Crie sua conta grátis para liberar esse material. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Crie sua conta grátis para liberar esse material. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
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.');Mais conteúdos dessa disciplina
Videoaula 8 - Gramáticas- SIMULADO 2
- Computabilidade e a máquina de
- Conceitos básicos de autômatos e
- Linguagens livres de contexto
- Classificação de Fenômenos
- Linguagens regulares
- Mapa Mental - Expressões Regulares
- Trabalho LFA 2025 1
- Algoritmo guloso
- Algoritmo guloso
- Assinale a única alternativa que contém a disposição correta da esquerda para a direita, em ordem crescente, dos tipos de gramática que, segundo a ...
- Considerando a hierarquia de Chomsky, leia as seguintes afirmativas:
Assinale a alternativa correta.
I. A hierarquia de Chomsky define quatro class...
- Considere a seguinte L(G) = (V, T, P, S), em que V = {0, 1, S}, T = {0, 1, λ} e P: S → OS1 e S → λ. Assinale a alternativa que contém somente cadei...
- Os símbolos são utilizados para construir __________, que são formadas pela __________ de símbolos. Um _________ é um conjunto finito e não vazio d...
- Palíndromos são cadeias que, lidas da esquerda para a direita ou da direita para a esquerda, têm a mesma sequência de símbolos e podem ser definida...
- Considere o conjunto A com 3 elementos; o B, com 4; e o C, com 5. Nesse caso, verificamos que:
A
tem, no máximo, 2 elementos.
tem, no máximo, 5 ele...
- Sabendo que o conjunto A = {0, 1, 3, 4, 5, 7} e A – B = {1, 3, 5, 7}, então o conjunto B é:
A
{0, 1, 4, 5}
{0, 1, 4, 5, 7}
{0, 4}
{0, 1, 5}
{}
- Uma árvore é um grafo: Simples, Acíclico (não possui ciclos), Conexo (existe caminho entre quaisquer dois de seus vértices).
Quais são as caracterí...
- Os grafos serão muito úteis na construção de autômatos finitos (similares a máquinas de estado).
O que é um grafo e como ele é representado?
- Uma função é uma regra que atribui aos elementos de um conjunto um elemento único de outro conjunto.
Como podemos definir uma função injetora?
- Um conjunto é considerado finito se contém um número finito de elementos; caso contrário, ele é infinito.
Como podemos definir um conjunto unitário?
- As operações algébricas sobre conjuntos usuais são definidas como: União, Interseção, Diferença.
Quais são as propriedades importantes das operaçõe...
- Vamos aprender os conceitos básicos sobre a teoria de linguagens formais e de autômatos, o que inclui a teoria de conjuntos, símbolos e cadeias, as...
- UNIASSELVI - Avaliação II - Individual FLEX ( Cod 456751)
- DESENVOLVIMENTO DE SOFTWARE