Simulado 2 Linguagens Formais

Prévia do material em texto

1a 
 Questão 
Acerto: 0,0 / 1,0 
 
Referência: elaborado pelo autor, adaptado do livro Linz, Peter. An Introduction to 
Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016. 
 
(a, b)* significa 
 
 Qualquer combinação de a, b incluindo nulo 
 Qualquer combinação de a, b excluindo nulo 
 
Qualquer combinação de a, b, mas 'b' virá primeiro 
 
Qualquer combinação de a, b, mas 'a' virá primeiro 
 
λ 
Respondido em 29/10/2022 18:54:06 
 
Explicação: 
Utilizando o fecho de Kleene, sabemos que a expressão (a, b)* gera qualquer combinação 
de cadeias compostas pelos símbolos a e b e, necessariamente, inclui a cadeia nula λ. 
Neste caso, a ordem em que aparecem os símbolos nas cadeias não requer que "a" venha 
antes de "b". Se isso fosse necessário escreveríamos (ab)* 
 
 
2a 
 Questão 
Acerto: 0,0 / 1,0 
 
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 
 
 
a* = a+. a+ 
 a = a + a 
 a+ = a*. a 
 
a+ = a*. a* 
 
a* = a+. a* 
Respondido em 29/10/2022 18:57:57 
 
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. 
 
 
3a 
 Questão 
Acerto: 1,0 / 1,0 
 
Considere as afirmativas abaixo e marque a única alternativa correta: 
 
I. um conjunto finito e não vazio Σ de símbolos, é chamado de alfabeto. 
II. A partir dos símbolos individuais nós construímos cadeias, que são sequências finitas 
ou infinitas de símbolos do alfabeto, concatenados. 
III. Uma linguagem formal é um conjunto, finito ou infinito, de cadeias, formadas pela 
concatenação de elementos de um alfabeto finito e não-vazio. 
 
 
Apenas as alternativas I e II estão corretas 
 
Apenas a alternativa III está correta 
 
Apenas as alternativas II e III estão corretas 
 
Apenas a alternativa II está correta 
 As alternativas I, II e III estão corretas 
Respondido em 29/10/2022 19:02:12 
 
Explicação: 
Um alfabeto é um conjunto finito e não vazio de símbolos. Os símbolos formam as cadeias 
por meio da operação de concatenação. Um conjunto, finito ou infinito, de cadeias, 
formadas pela concatenação de elementos de um alfabeto finito e não-vazio é uma 
linguagem formal. De acordo com o exposto no texto, todas as alternativas estão corretas. 
 
 
4a 
 Questão 
Acerto: 0,0 / 1,0 
 
Dado que A = {x ∊ ℕ | 1 < x < 3} e B = {x ∊ ℕ | 2 < x < 20}, então A ∩ B = 
 
 {2} 
 
{3,4} 
 
{3} 
 { } 
 
{2,3} 
Respondido em 29/10/2022 19:07:19 
 
Explicação: 
Gabarito: { } 
Justificativa: O conjunto A = {2} e o conjunto B = {3..19}. Logo a intersecção de ambos 
é vazia, uma vez que não há elementos comuns entre A e B 
 
 
5a 
 Questão 
Acerto: 1,0 / 1,0 
 
Analise as seguintes afirmativas. 
I. Um Autômato Finito fornece o modelo mais simples de um dispositivo de 
computação. 
II. A principal utilidade da teoria dos autômatos está no projeto do computador. 
III. Um AF é um modelo matemático usado para representar programas de 
computador. 
A análise permite concluir que 
 
 
Somente as afirmativas II e III são falsas. 
 Somente a afirmativa II é falsa. 
 
Somente a afirmativa III é falsa. 
 
Somente a afirmativa I é falsa. 
 
Somente as afirmativas I e II são falsas. 
Respondido em 29/10/2022 19:11:34 
 
Explicação: 
Gabarito: Somente a afirmativa II é falsa. 
Justificativa: A principal utilidade da teoria dos autômatos está no projeto do compilador. 
 
 
6a 
 Questão 
Acerto: 0,0 / 1,0 
 
Considere o autômato finito mostrado na figura abaixo (q0 é o estado inicial e q1 é o 
único estado final) e assinale a afirmativa correta. 
 
 
 
 A palavra 010 é reconhecida pelo autômato. 
 Este é um autômato finito com saída. 
 
A palavra vazia é reconhecida pelo autômato. 
 
A palavra 101011 é reconhecida pelo autômato. 
 
A palavra 101 é reconhecida pelo autômato. 
Respondido em 29/10/2022 19:13:36 
 
Explicação: 
Gabarito: A palavra 010 é reconhecida pelo autômato. 
Justificativa: Como o estado inicial é diferente do estado final, esse autômato não 
reconhece a palavra vazia. Este não é um autômato finito com saída porque as saídas não 
estão registradas na tabela. Esse autômato reconhece cadeias com um número impar de 
'1'. 
 
 
7a 
 Questão 
Acerto: 1,0 / 1,0 
 
Qual é a linguagem gerada pela gramática S → aSb, S → A, A → aA 
 
 
ajbi 
 
ambm 
 
anbm 
 ∅ 
 
ambn 
Respondido em 29/10/2022 19:14:39 
 
Explicação: 
Gabarito: ∅ 
Justificativa: As regras de produção não geram uma cadeia composta apenas de símbolos 
terminais. Portanto, a linguagem gerada é vazia. 
 
 
8a 
 Questão 
Acerto: 1,0 / 1,0 
 
Com base nas afirmativas abaixo assinale a resposta correta: 
I. Alfabeto ou vocabulário "V" é um conjunto finito e não vazio de símbolos. 
II. Uma palavra sobre o alfabeto "V" é uma cadeia de comprimento finito de símbolos de 
"V". 
III. Gramáticas são especificações infinitas de linguagens finitas. 
IV. A classe das linguagens regulares é um subconjunto próprio da classe das linguagens 
livres de contexto. 
 
 
II e IV, apenas. 
 
I, II e III, apenas. 
 
I e IV, apenas. 
 
II e III, apenas. 
 I, II e IV, apenas. 
Respondido em 29/10/2022 19:18:57 
 
Explicação: 
Gabarito: I, II e IV, apenas. 
Justificativa: Gramáticas são especificações finitas de linguagens infinitas. A afirmativa III 
está errada. 
 
 
9a 
 Questão 
Acerto: 0,0 / 1,0 
 
Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto finito 
de estados, Σ é o conjunto finito de alfabetos de entrada, Γ é o símbolo de fita permitido, 
L significa esquerda, R significa direita e H significa parada). 
 
 Q × Γ → (Q × Γ × {L, R, H}) 
 
Q × Γ → (Q × Σ) 
 Q ×Σ→ (Q × {L, R, H}) 
 
Q ×Σ→ (Q × Σ × {L, R, H}) 
 
Q × Γ → (Q × Σ × {H}) 
Respondido em 29/10/2022 19:20:58 
 
Explicação: 
A função de transição de estados para MT é definida como um produto cartesiano de Q × Γ, 
onde Γ é alfabeto da fita, levando em uma imagem definida por outro produto cartesiano de 
Q × Γ multiplicado pelas ações da máquina em seguir para a esquerda, direita ou parar {L, 
R, H}. 
 
 
10a 
 Questão 
Acerto: 1,0 / 1,0 
 
Existem dois tipos principais de complexidade computacional para um algoritmo: 
complexidade de tempo e complexidade do espaço. Nesse sentido, o que é falso para o 
problema da classe P? 
 
 P é definido como o conjunto de todos os problemas de decisão para os quais 
existe um algoritmo que pode ser realizado por uma máquina de Turing não-
determinística em tempo polinomial. 
 
O número de passos (ou tempo) necessários para completar o algoritmo é uma 
função polinomial de n. 
 
É computável por uma máquina de Turing determinística em tempo polinomial. 
 
Em geral, a classe P contém todos os problemas que são resolvidos facilmente 
usando computadores. 
 
Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um 
algoritmo cujo tempo de execução é limitado por um polinômio. 
Respondido em 29/10/2022 19:21:59 
 
Explicação: 
P é definido como o conjunto de todos os problemas de decisão para os quais existe um 
algoritmo que pode ser realizado por uma máquina de Turing determinística em tempo 
polinomial.