LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES

Prévia do material em texto

Simulado 
 
 
 Regular 
 Livre de Contexto 
Respondido em 21/10/2022 11:27:07 
 
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. 
 
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett 
Learning, 2016. 
 
 
Acerto: 0 , 0 / 1 , 0 
 
 
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. 
 Quatro 
Zero 
Um 
Dois 
Três 
Respondido em 21/10/2022 11:28:07 
 
 
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. 
 
 
 
 
 
 
 
(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 
linguagemL1 = {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 
linguagemL2 = {(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 
aslinguagens 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. 
 
Acerto: 0 , 0 / 1 , 0 
A expressão regular que permite reconhecer a digitação correta de CPF no Brasil é: 
^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{3}$ 
 ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$ 
\\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2} 
 ^\\d{3}\\.\\d{3}\\.\\d{3}\\.\\d{2}$ 
^\\d{3}\\-\\d{3}\\-\\d{3}\\-\\d{2}$ 
Respondido em 21/10/2022 11:31:51 
 
 
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}$ 
 
Acerto: 0 , 0 / 1 , 0 
 
 
 
∈ 
Somente as afirmativas III e IV são corretas. 
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. 
Respondido em 21/10/2022 11:41:55 
 
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, xy
i
z 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 
 
 
 0011000 
1111111 
1000111 
0010000 
1101111 
Respondido em 21/10/2022 11:41:35 
 
 
Explicação: 
Gabarito: 1101111 
Justificativa: O AF lê o primeiro zero, permanece em q1 e emite um "1". Ao ler o segundo zero emite 1 e 
permanece em q1. O caractere seguinte é "1" ele e muda para o estado q2 e emite "0". No estado q2 lê o 
próximo "1", volta para o estado q1 e emite "1". No estado q1 são lidos os caracteres "0" e o AF permanece em 
q1 emitindo a saída "1" por mais três vezes. 
 
 
Com base nas afirmativas abaixo assinale a resposta correta: 
 
Acerto: 1 , 0 / 1 , 0 
Considere o seguinte AF com saída 
A cadeia de saída desse AF para uma entrada 0011000 é: 
 
 
 
Acerto: 1 , 0 / 1 , 0 
 
 
 
 
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 e IV, apenas. 
I, II e III, apenas. 
II e III, apenas. 
I, II e IV, apenas. 
Respondido em 21/10/2022 11:41:44 
 
 
 
 
 
A Forma Normal de Chomsky é um outro tipo de forma normal, além da BNF. Qual das seguintes 
produções está em CNF (NT = Não Terminal)? 
(NT) → (Cadeia de exatamente quatro terminais) 
(NT) → (Cadeia de cinco ou mais NT) 
(NT) → (Cadeia de um terminal e três não terminais) 
(NT) → (Cadeia de exatamente dois NT) 
(NT) → (Cadeia de exatamente três terminais) 
Respondido em 21/10/2022 11:39:48 
 
 
 
 
 
 
A hierarquia de Chomsky representou um marco na classificação das linguagens e uma grande evolução 
para a computação. Acerca das características das diferentes linguagens e as respectivas máquinas 
reconhecedoras dessas linguagens, Aassinale a alternativa falsa. 
Todo Conjunto Finito é enumerável. 
O conjunto de todas as Expressões Regulares é enumerável. 
O conjunto de todas as Máquinas de Turing é enumerável. 
Toda Linguagem Regular é enumerável. 
Nenhum Conjunto Finito é enumerável. 
Respondido em 21/10/2022 11:37:39 
 
Explicação: 
Explicação: 
Gabarito: I, II e IV, apenas. 
Justificativa: Gramáticas são especificações finitas de linguagens infinitas. A afirmativa III está errada. 
 
Acerto: 0 , 0 / 1 , 0 
 
Explicação: 
Gabarito: ( NT) → (Cadeia de exatamente dois NT) 
Justificativa: A forma normal CNF é aquela em que o número de símbolos à direita de uma produção é 
estritamente limitado. Em particular, a cadeia à direita de uma produção consiste em não mais que dois 
símbolos. 
 
Acerto: 1 , 0 / 1 , 0 
 
 
 
 
 
Os conjuntos enumeráveis são os superconjuntos de todas as linguagens tratáveis por autômatos (no caso a 
máquina de Turing). Portanto, há linguagens infinitas cujas gramáticas são uma especificação finita e são 
enumeráreis e aceitas por Máquinas de Turing. Outo contraexemplo é o conjunto dos números naturais. 
 
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 × Σ) 
Q × Γ → (Q × Γ × {L, R, H}) 
Q ×Σ→ (Q × Σ × {L, R, H}) 
Q × Γ → (Q × Σ × {H}) 
Q ×Σ→ (Q × {L, R, H}) 
Respondido em 21/10/2022 11:35:13 
 
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áquinaem seguir para a esquerda, direita ou parar {L, R, H}. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Acerto: 1 , 0 / 1 , 0