LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES SIMULADO 2

Prévia do material em texto

Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & 
Bartlett Learning, 2016.
Qual o tipo da seguinte gramática: S aSb → e S ab→
Sensível ao Contexto
Irrestrito
  Livre de Contexto
Com estrutura de frase
  Regular
Respondido em 30/10/2022 02:27:38
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.
          Questão Acerto: 0,0 / 1,0
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.→
  Dois
  Zero
Um
Três
Quatro
Respondido em 30/10/2022 02:29:02
Explicação:
10a
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.
          Questão Acerto: 1,0 / 1,0
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & 
Bartlett Learning, 2016.
Qual o tipo da seguinte gramática?
 
S aS/A→
aS aa→
A a→
Regular
Irrestrito
Com estrutura de frase
  Sensível ao Contexto
Livre de Contexto
Respondido em 30/10/2022 02:31:08
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 tem uma regra que 
torna sensível ao contexto, ao ter um símbolo não-terminal do lado esquerdo da produção.
          Questão 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{3}\\.\\d{3}\\.\\d{3}\\.\\d{2}$
  \\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2}
  ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
Respondido em 30/10/2022 02:32:02
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}$
          Questão Acerto: 0,0 / 1,0
(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, 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.
Respondido em 30/10/2022 02:32:59
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
          Questão Acerto: 1,0 / 1,0
Considere o seguinte AF com saída
A cadeia de saída desse AF para uma entrada 0011000 é:
0010000
0011000
1111111
1000111
  1101111
Respondido em 30/10/2022 02:33:38
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.
          Questão Acerto: 0,0 / 1,0
Alguns tipos de símbolos e produções aumentam o número de etapas na geração de uma linguagem a 
partir de uma GLC. Nesse sentido, símbolos inúteis em uma Gramática Livre de Contexto são:
Produções nulas.
Símbolos não terminais.
  Alfabetos nulos.
Cadeia nula.
  Símbolos não geradores e símbolos não alcançáveis.
Respondido em 30/10/2022 02:34:34
Explicação:
Gabarito: Símbolos não geradores e símbolos não alcançáveis.
Justificativa: Os dois tipos de símbolos inúteis incluem os símbolos não geradores, aqueles símbolos que 
não produzem nenhuma cadeia terminal, e os símbolos não alcançáveis, aqueles símbolos que não podem 
ser alcançados a qualquer momento a partir do símbolo inicial. Toda linguagem livre de contexto pode ser 
gerada por uma gramática livre de contexto em que não há símbolos inacessíveis ou inúteis.
          Questão Acerto: 0,0 / 1,0
Considere as seguintes produções da gramática da linguagem C e assinale a opção que não está em 
BNF:
  < logical-or-expression > →
                          | < logical-or-expression > || < logical-and-expression >
< conditional-expression > ::= < logical-or-expression >
                           | < logical-or-expression > ? < expression > : < conditional-expression >
  < logical-and-expression > ::= < inclusive-or-expression >
                           | < logical-and-expression > && < inclusive-or-expression >
< inclusive-or-expression > ::= < exclusive-or-expression >
                            | < inclusive-or-expression > | < exclusive-or-expression >
< and-expression > ::= < equality-expression >
                   | < and-expression > & < equality-expression >
Respondido em 30/10/2022 02:35:03
Explicação:
Gabarito:
< logical-or-expression > < logical-and-expression >→
                          | < logical-or-expression > || < logical-and-expression >
Justificativa: Não se usa na BNF. A forma correta quando se utiliza BNF é a utilização do símbolo ::=→
          Questão Acerto: 0,0 / 1,0
Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA.
  Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente,X é 
redutível em tempo polinomial para qualquer outro problema Y na classe NP.
Todo problema que está na classe P também está na classe NP.
  A união de duas linguagens recursivas é uma linguagem recursiva.
Segundo a Tese de Church, a capacidade de computação representada pela máquina de 
Turing é o limite máximo que pode ser atingido por qualquer modelo de computação.
Seja L uma linguagem recursivamente enumerável, se o complemento de L for 
recursivamente enumerável, então L é uma linguagem recursiva.
Respondido em 30/10/2022 02:35:45
Explicação:
Um problema é NP completo quando está na classe NP, e todo problema NP completo conhecido pode ser 
reduzido a ele. O correto seria Y é redutível a X em tempo polinomial, porque, pela definição, todo 
problema NP-Completo poderia ser redutível a X. As demais alternativas estão corretas.
          Questão Acerto: 0,0 / 1,0
Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase
sem qualquer restrição. Dentro dessa hierarquia estão classificadas a linguagem recursiva e a
linguagem recursivamente enumerável. Acerca de suas características assinale a afirmação
verdadeira.
 
Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
  Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para 
sempre na entrada de uma máquina de Turing.
  Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente 
enumerável.
Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem 
recursiva.
Respondido em 30/10/2022 02:36:10
Explicação:
As linguagens recursivas estão contidas no conjunto das linguagens recursivamente enumeráveis. 
Portanto, não são equivalentes. Uma linguagem recursiva é uma linguagem aceita por uma Máquina de 
Turing. Ambas as linguagens são aceitas por Máquinas de Turing. Quando uma linguagem é rejeitada a MT 
para, não entra em loop infinito.