LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES - AV1

Prévia do material em texto

qN3qN3683
		Disc.: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES   
	Aluno(a): JULIO CESAR FERREIRA DE ALUSTAU
	202101355296
	Acertos: 2,0 de 2,0
	02/10/2023
		1a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
Qual é o maior número de tipo para a gramática dada pelas seguintes regras de produção S → Aa, A → c | Ba, B → abc.
		
	
	Zero
	
	Um
	
	Quatro
	
	Três
	
	Dois
	Respondido em 02/10/2023 20:35:28
	
	Explicação: 
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção atendendo às seguintes restrições: 1. Todas as regras de produção devem ser do tipo (Não-terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 1. A gramática do enunciado atende a essas duas restrições.
	
		2a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	A expressão regular que permite reconhecer a digitação correta de CPF no Brasil é:
		
	
	^\\d{3}\\.\\d{3}\\.\\d{3}\\.\\d{2}$
	
	^\\d{3}\\-\\d{3}\\-\\d{3}\\-\\d{2}$
	
	^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{3}$
	
	^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
	
	\\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2}
	Respondido em 02/10/2023 20:38:23
	
	Explicação: 
Gabarito: ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
Justificativa: Sabemos que a expressão deverá iniciar com 3 dígitos separados por um ponto: ^\\d{3}\\. Devemos repetir três vezes esse padrão, colocar o separador "-", e mais dois dígitos verificadores. Lembrando que o '^' marca o início e o '$' o final da expressão regular. Assim, a expressão regular em Java para CPF será:
^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
	
		3a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	Seja a seguinte gramática S → aSa | bSb | a | b
Palíndromos são cadeias do tipo wwr, ou seja, aqueles que lidos da esquerda para a direita ou vice e versa, são iguais. A linguagem gerada pela gramática acima sobre o alfabeto {a, b) é o conjunto de:
		
	
	Todos os palíndromos de comprimento ímpar.
	
	Todos os palíndromos.   
	
	Cadeias que começam e terminam com símbolos diferentes.
	
	Todos os palíndromos de comprimento par.
	
	A gramática não gera palíndromos.
	Respondido em 02/10/2023 20:39:36
	
	Explicação: 
Gabarito: Todos os palíndromos de comprimento ímpar.
Justificativa: Realizando algumas derivações como exemplo pode-se perceber que a alternativa b é a correta, por exemplo: S → aSa → S → aaa; S → aSa → S → abSba → ababa.
	
		4a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	. Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral. Acerca de suas características principais, qual item não faz parte do diagrama mecânico da máquina de Turing?
		
	
	Fita de entrada.
	
	Controle finito.
	
	Pilha.
	
	Direção de leitura..
	
	Cabeça de leitura-escrita.
	Respondido em 02/10/2023 20:40:40
	
	Explicação: 
O diagrama não contempla uma pilha. Todos os outros itens podem ser visualizados na figura do diagrama mecânico.
	
		5a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	Considere as seguintes regras de gramática, onde "|" representa "ou", λ representa a cadeia vazia e undrscr é o caractere "_".
 
1. → 
2. →   
3. → 
4. →   
5. →   
6. →  λ
7. → a | b | ... | z | A | B | ... | Z
8. → 0 | 1 | ... | 9
9. → _
 
Assinale a cadeia que pode ser gerada pela aplicação das produções na seguinte ordem:1, 7, 3, 7, 5, 9, 4, 8, 6
		
	
	a0
	
	ab_9
	
	ab_
	
	7b1
	
	_ab9
	Respondido em 02/10/2023 20:41:32
	
	Explicação: 
Sabemos que as cadeias são geradas a partir do emprego das regras de produção. Aplicando a regra 1 temos ⇒. Na sequência aplica-se a regra 7 onde foi substituída por uma letra, portanto, fica estabelecido que essa cadeia irá iniciar por uma letra, o que já elimina as alternativas "d" e "e". Neste ponto estamos em a, supondo que a letra que foi substituída é "a" já que todas as alternativas iniciam com a letra "a". Em seguida, é aplicada a regra 3   e ficamos com a cadeia a< resto >.
Aplicando a regra 7 substituímos a por "b", o que elimina a alternativa "b". Neste ponto estamos com a cadeia ab. Aplicando a regra 5 ficamos com ab . Pela regra 9 geramos ab_. Pela regra 4 ab_. A regra 8 aplicada gera ab_9, ou qualquer outro dígito, mas para o caso em questão nos interessa o 9.
Ao aplicar a regra 6 substituímos pela cadeia nula (λ) e geramos ab_9.
As produções podem ser desenvolvidas como segue:
⇒⇒a⇒a ⇒ ab ⇒ ab
⇒ab_⇒ab_ ⇒ab_9.
	
		6a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	A expressão regular que permite reconhecer a digitação correta de CEP no Brasil no modelo ddddd-ddd é:
		
	
	^\\d{5,5}\\-\\d{3,1}$
	
	^\\d{5,5}\\-\\d{3,3}$
	
	^\\d{3,5}\\-\\d{5,3}$
	
	^\\d{5,1}\\-\\d{3,1}$
	
	^\\d{3,3}\\-\\d{5,5}$
	Respondido em 02/10/2023 20:42:42
	
	Explicação: 
Gabarito: ^\\d{5,5}\\-\\d{3,3}$
Justificativa: O padrão de CEP no Brasil é composto de 5 dígitos numéricos separados por um traço e mais três dígitos. A única alternativa que satisfaz esse padrão é a alternativa "^\\d{5,5}\\-\\d{3,3}$"
	
		7a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	Considere a seguinte propriedade sobre uma linguagem formal L: ¿Existe um número natural n ≥ 0, tal que para qualquer palavra w ∈ L:
1. Todo z ∈ L com z ≥ n pode ser escrito como w = uvwxy, para algumas cadeias u,v,w,x,y.
2. |vx| ≥ 1
3. |vwx| ≤ n
4. uvkwxky ∈ L para todo k ≥ 0
 
Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F (falso) para as afirmativas a seguir.
· (   ) Se L é aceita por PDA, então L satisfaz a propriedade acima.
· (   ) L = {0p; onde p é primo} não satisfaz a propriedade acima.
· (   ) A propriedade acima é falsa para a linguagem L = {WcWR | W ∈ (a, b)*}
· (   ) A linguagem {anbncn; n ≥ 0} não satisfaz a propriedade acima.
· (   ) O lema do bombeamento para linguagem livre de contexto é usado ​​para provar que certos conjuntos são livres de contexto.
Assinale a alternativa que contém, de cima para baixo, a sequência correta:
		
	
	V, F, V, F, F.
	
	F, V, F, V, V.
	
	V, V, F, V, F.
	
	V, V, V, V, F.
	
	F, V, V, F, V.
	Respondido em 02/10/2023 20:44:32
	
	Explicação: 
Gabarito: V, V, F, V, F.
Justificativa:
1. Esse é o lema do bombeamento para LLC e toda LLC é reconhecida por um PDA.
2. Aplicando o lema é possível provar que 0p não é livre de contexto e não satisfaz a propriedade.
3. WcWR é LLC, logo a propriedade é verdadeira e a afirmativa é falsa.
4. Está correta conforme pode ser lido no Módulo 4, núcleo conceitual 1.
5. O lema do bombeamento para linguagem livre de contexto é usado ​​para provar que certos conjuntos não são livres de contexto. Alternativa falsa.
	
		8a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	Seja uma MT T dada pelas quíntuplas:
1. (0, 1, 1, 0, D)
                2. (0, b, 1, 1, H)Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. 
Qual a função que calcula essa MT?
		
	
	2n+1
	
	2n +1
	
	2n -1
	
	2n
	
	2n+1 - 1
	Respondido em 02/10/2023 20:45:31
	
	Explicação: 
Esse exemplo mostra o poder de computação das MT. Deve-se começar utilizando a quíntupla 1. Enquanto a MT ler 1 na fita, escreve 1, continua no estado 0 e anda para a direita (D). Ao encontrar um branco, escreve 1, muda para o estado final 1 e para (H). A cadeia final é 1111. A cadeia inicial era 111 = 23-1, foi transformada em 1111 = 24-1. Logo a MT calcula 2n+1 - 1
	
		9a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	Câmara Municipal de Marabá- Engenheiro Civil - FADESP-2021
A função exponencial y = ax+1 é tal que a imagem de 2 é 27. A imagem de 4 será:729
	
	64
	
	243
	
	256
	
	81
	Respondido em 02/10/2023 20:46:23
	
	Explicação: 
Quando x = 2, ax+1 é igual a a3. O número que elevado ao cubo gera 27 é 3. Logo a função é: y = 3x+1 e a imagem de 4 será: 243 = 35
	
		10a
            Questão  /   
	Acerto: 0,2  / 0,2 
	
	(POSCOMP / 2013) Sobre o Lema do Bombeamento (pumping lemma) para linguagens regulares, considere as afirmativas a seguir.
 
I. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L1 = {w ∈ Σ* | w termina com b} não é regular.
II. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L2 = {(an)2 | n ≥ 1} não é regular.
III. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que as linguagens L3 = {an! | n ≥ 1}, L4 = {anbamban+m | n, m ≥ 1} e L5 = {am+1bn+1 | 2 ≤ n ≤ m ≤ 3n} não são regulares.
IV. Se a linguagem for do tipo 3, então aplica-se o Bombeamento.
 
Assinale a alternativa correta.
		
	
	Somente as afirmativas I e II são corretas.
	
	Somente as afirmativas I, II e III são corretas.
	
	Somente as afirmativas II, III e IV são corretas.
	
	Somente as afirmativas I e IV são corretas.
	
	Somente as afirmativas III e IV são corretas.
	Respondido em 02/10/2023 20:47:14
	
	Explicação: 
Gabarito: Somente as afirmativas II, III e IV são corretas.
Justificativa: vamos aplicar o lema do bombeamento no item I. w é qualquer cadeia de 'a' e 'b' que termina em b. Seja a cadeia w = abaab. Vamos dividir essa em três: x = 'a', y = 'ba' e z = 'ab'. Claramente o nosso comprimento de bombeamento é y = 2 ('ba') e p = 5. Assim vamos satisfazer as condições do lema:
1. |y| ≥ 1
2. |xy| ≤ p
3. para todo i ≥ 0, xyiz ∈ L
y é a subcadeia que pode ser bombeada (removida ou repetida arbitrariamente).
Removendo y temos a cadeia aab que pertence a L1. Repetindo y duas vezes temos a cadeia ababaab que pertence a L1, uma vez que pertence a Σ* e termina em 'b'. É fácil perceber que a repetição de y dentro de w vai continuar satisfazendo a condição de pertencer a Σ* e terminar em 'b'. Portanto, não foi possível provar que L1 não é regular. Como o lema foi satisfeito para L1, então L pode ou não ser regular. Nada se pode afirmar e a afirmativa I é falsa. Todas as outras são verdadeiras
683