Teoria da computação - Estácio 2023

Prévia do material em texto

Exercício
 avalie sua aprendizagem
BIO-RIO - 2014 - ETAM - Curso de Formação de Técnicos - 2º Semestre
Dados três conjuntos, A = {1,2,3}, B = {4,5} e C = {1,2,4}, observe os pares ordenados apresentados gra�camente na
�gura abaixo.
 
 
Esses pares correspondem, gra�camente, a:
TEORIA DA COMPUTAÇÃO
Lupa  
 
CCT0832_201901020223_TEMAS
Aluno: ERSON MACEDO Matr.: 201901020223
Disc.: TEORIA DA COMPUTAÇÃO  2023.3 EAD (G) / EX
Prezado (a) Aluno(a),
Você fará agora seu EXERCÍCIO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua avaliação. O
mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
03491CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
 
1.
C X (A U B)
(A ∩ C) X B
B X (A ∩ C)
(A U C) X B
B X (A U C)
Data Resp.: 02/10/2023 20:45:02
Explicação:
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:diminui();
javascript:aumenta();
javascript:aumenta();
Referência: elaborado pelo autor, adaptado do livro Linz, Peter. An Introduction to Formal Languages and
Automata, 6. Ed. Jones & Bartlett Learning, 2016.
 
Assinale a alternativa correta
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning,
2016.
Qual a linguagem gerada pela gramática: G = {(S, A), (0, 1), (S→0S1, S→A, A→0A), S}.
A �m de que o produto cartesiano de B com qualquer outro conjunto fosse representado, os pares ordenados
devem, necessariamente, iniciar com os elementos do conjunto B = {4, 5}. Como os pares da �gura começam com
os elementos 1 e 2, as alternativas a e d estão incorretas. A alternativa ¿e¿ nos obrigaria a ter um par ordenado
começando com elemento 4. A intersecção dos conjuntos A e C contém os elementos comuns {1, 2}, uma vez que
3 não está contido em C. O produto cartesiano desse conjunto intersecção com o conjunto B é: {(1, 4); (1, 5); (2,
4); (2, 5)}
 
2.
a+ = a*. a
a+ = a*. a*
a* = a+. a+
a = a + a
a* = a+. a*
Data Resp.: 02/10/2023 20:46:09
Explicação:
De acordo com o fecho de Kleene, a* são todas as cadeias formadas por um número indeterminado de "a",
incluindo a cadeia nula λ. Todas as cadeias formadas por um número indeterminado de "a", não incluindo a cadeia
nula λ, é representado por a+. a+ é, exatamente, "a*.a", evitando que a cadeia nula venha a aparecer nessa
linguagem.
 
3.
λ
0m1n
0m1m
1m0n
1m0m
Data Resp.: 02/10/2023 20:49:34
Explicação:
Observe que não existe uma regra de produção que possa nos levar a um símbolo terminal apenas. Todas as
regras de produção, se aplicadas, nos levam a cadeias compostas de terminais e não terminais. Sendo impossível
gerar cadeias formadas apenas de terminais, essa é uma linguagem vazia.
03492LINGUAGENS REGULARES
 
(POSCOMP / 2008) Considere o autômato �nito mostrado na �gura abaixo (os círculos em negrito representam
estados terminais)
A esse respeito, assinale a a�rmativa FALSA.
Com base nas a�rmativas abaixo assinale a resposta correta:
I.  As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos �nitos.
II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0.
III. Em todo autômato �nito existe sempre um estado inicial �xo.
IV. Gramáticas têm um número �nito de regras de produção.
(POSCOMP / 2008 - adaptada) Analise as seguintes igualdades de expressões regulares:
I. a* = (a)*
II. (a+b)* = (b+a)*
4.
A palavra ababa não é reconhecida pelo autômato.
A palavra aba é reconhecida pelo autômato.
A palavra aaa é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
A palavra baba é reconhecida pelo autômato.
Data Resp.: 02/10/2023 20:48:33
Explicação:
Gabarito: A palavra aba é reconhecida pelo autômato.
Justi�cativa: Esse AFN realiza uma transição em ε para um estado �nal, logo reconhece a palavra vazia. Essa
mesma transição permite o reconhecimento de baba. Existe um caminho para o reconhecimento de aaa e ababa
não é reconhecida. Logo, todas essas alternativas são verdadeiras.  A palavra aba não é reconhecida pelo
autômato porque não há caminhos que levem a um estado �nal. Essa alternativa é falsa.
 
5.
I e IV, apenas.
I, II e IV, apenas
II e IV, apenas
II e III, apenas
I, III e IV, apenas
Data Resp.: 02/10/2023 20:51:16
Explicação:
Gabarito: I, III e IV, apenas
Justi�cativa: As linguagens regulares são as do tipo 3 e não do tipo 0. As demais alternativas estão corretas.
 
6.
III. a*+b* = (a+b)*
A análise permite concluir que
Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das
regras de produção dessa GLC, é denominada de:
Gramáticas de�nem linguagens, sendo especi�cações �nitas de regras de geração de cadeias.  Nesse sentido,
assinale a alternativa incorreta.
somente a igualdade II é verdadeira.
somente a igualdade I é verdadeira.
somente as igualdades I e II são verdadeiras.
somente as igualdades II e III são verdadeiras.
somente a igualdade III é verdadeira.
Data Resp.: 02/10/2023 20:52:25
Explicação:
Gabarito: somente as igualdades I e II são verdadeiras.
Justi�cativa: a* + b* signi�ca qualquer combinação de 'a' ou qualquer combinação de 'b', ou seja, as cadeias são
formadas apenas por 'a' ou por 'b'. (a + b)* consiste em qualquer combinação de 'a' e 'b', ou seja, as cadeias podem
conter os símbolos 'a' e 'b' em sua formação, logo a alternativa III é falsa. A alternativa II é verdadeira porque
segundo o fecho de Kleene podemos considerar Σ = {a, b} e Σ* de�nido como o conjunto de todas as cadeias,
incluindo a cadeia nula, portanto as linguagens são iguais e geradas por expressões equivalentes. A alternativa I
é, claramente, verdadeira, bastando retirar os parênteses da expressão à direita.
03493LINGUAGENS LIVRES DE CONTEXTO
 
7.
Sem contexto.
Irrestrita (sem restrições).
Finita.
Recursiva.
In�nita.
Data Resp.: 02/10/2023 20:53:59
Explicação:
Gabarito: Finita.
Justi�cativa: Uma linguagem L gerada a partir de uma dada GLC é �nita se não houver ciclos no grafo
direcionado gerado a partir das regras de produção dessa GLC.
 
8.
a + b denota {a} U {b} = {a, b}
λ ∈ Σ*
V ∩ T = Σ*
V ∩ T = ∅
V U T = Σ
Data Resp.: 02/10/2023 20:54:55
Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto �nito de estados, Σ é o conjunto
�nito de alfabetos de entrada, Γ é o símbolo de �ta permitido, L signi�ca esquerda, R signi�ca direita e H signi�ca
parada).
Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução
do segundo problema possa ser usada para resolver o primeiro problema. Em particular, a redutibilidade pode ser
usada para demonstrar que problemas são indecidíveis ou decidíveis. Nesse contexto, avalie as seguintes
a�rmativas:
I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução
de A na presença de um método para resolver B.
II. Reduções apresentam um importante papel em classi�car os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
 
Quais as a�rmativas verdadeiras?
Explicação:
Gabarito: V ∩ T = Σ*
Justi�cativa: Observe que V é o conjunto dos não terminais e T é o conjunto dos terminais. São dois conjuntos
disjuntos, logo sua intersecção é vazia. Todas as demais alternativas estão corretas.
03494COMPUTABILIDADE E A MÁQUINA DE TURING
 
9.
Q × Γ → (Q × Γ × {L, R, H})
Q × Γ → (Q × Σ)
Q ×Σ→ (Q × {L, R, H})
Q ×Σ→ (Q × Σ × {L, R, H})
Q × Γ → (Q × Σ × {H})
Data Resp.: 02/10/2023 20:56:04
Explicação:
A função de transição de estados para MT é de�nida como um produto cartesiano de Q × Γ, onde Γ é alfabeto da
�ta, levando em uma imagem de�nida por outro produto cartesiano de Q × Γ multiplicado pelasações da
máquina em seguir para a esquerda, direita ou parar {L, R, H}.
 
10.
III.
II e III.
I e III.
I, II e III.
I e II.
Data Resp.: 02/10/2023 21:02:33
Explicação:
Na a�rmativa III, se A é redutível a B e B é um problema indecidível, então A é um problema indecidível.
    Não Respondida      Não Gravada     Gravada
Exercício inciado em 02/10/2023 20:43:14.