Prévia do material em texto
1a 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 tipo da seguinte gramática? S → aS/A aS → aa A → a Sensível ao Contexto Regular Irrestrito Livre de Contexto Com estrutura de frase Respondido em 07/10/2022 20:05:17 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. 2a 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 → aSb e S → ab Livre de Contexto Regular Irrestrito Com estrutura de frase Sensível ao Contexto Respondido em 07/10/2022 20:06:13 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. 3a 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. Zero Três Dois Um Quatro Respondido em 07/10/2022 20:38:27 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. 4a Questão Acerto: 1,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{2}$ ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$ \\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2} ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{3}$ ^\\d{3}\\.\\d{3}\\.\\d{3}\\.\\d{2}$ Respondido em 07/10/2022 20:41:00 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}$ 5a Questão Acerto: 1,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 II, III e IV são corretas. Somente as afirmativas I e IV são corretas. Somente as afirmativas I, II e III são corretas. Somente as afirmativas III e IV são corretas. Somente as afirmativas I e II são corretas. Respondido em 07/10/2022 20:43:41 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 6a Questão Acerto: 0,0 / 1,0 Considere o seguinte AF com saída A cadeia de saída desse AF para uma entrada 0011000 é: 1000111 0010000 0011000 1101111 1111111 Respondido em 07/10/2022 20:44:07 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. 7a Questão Acerto: 1,0 / 1,0 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 exatamente três terminais) (NT) → (Cadeia de cinco ou mais NT) (NT) → (Cadeia de exatamente dois NT) (NT) → (Cadeia de um terminal e três não terminais) Respondido em 07/10/2022 20:17:39 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. 8a Questão Acerto: 0,0 / 1,0 O que é verdadeiro para a seguinte GLC? S → aA | λ A → bA | a A produção nula pode ser removida. Como A não produz λ, λ pode ser removido. Como A não produz λ, λ não pode ser removido. A produção nula não pode ser removida. Como S produz λ, λ pode ser removido. Respondido em 07/10/2022 20:15:48 Explicação: Gabarito: A produção nula não pode ser removida. Justificativa: Se S pode ser derivado em λ, então a produção nula não pode ser removida. 9a Questão Acerto: 0,0 / 1,0 Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA. Todo problema que está na classe P também está na classe NP. Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente enumerável, então L é 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. A união de duas linguagens recursivas é uma linguagem recursiva.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. Respondido em 07/10/2022 20:38:11 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. 10a Questão Acerto: 1,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 é um subconjunto de uma linguagem recursivamente enumerável. 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 e uma recursivamente enumerável são equivalentes. Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva. Respondido em 07/10/2022 20:14:40 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.