Baixe o app para aproveitar ainda mais
Prévia do material em texto
03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS 1. Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é: 16 64 10 5 32 Data Resp.: 04/12/2023 17:29:52 Explicação: Como sabemos, o número de subconjuntos de um conjunto com n elementos é igual a 2n. Assim, o número de subcadeias de uma cadeia de tamanho 5 será igual a 25 = 32 2. 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, mas 'a' virá primeiro Qualquer combinação de a, b excluindo nulo Qualquer combinação de a, b incluindo nulo Qualquer combinação de a, b, mas 'b' virá primeiro λ Data Resp.: 04/12/2023 17:30:02 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, não 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)+ 3. 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 II e III estão corretas Apenas a alternativa II está correta Apenas as alternativas I e II estão corretas Apenas a alternativa III está correta As alternativas I, II e III estão corretas Data Resp.: 04/12/2023 17:32:09 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. 4. Sejam os conjuntos A com 2 elementos, B com 4 elementos, C com 5 elementos, então: A ∩ B tem no máximo 1 elemento A ∪ C tem no máximo 5 elementos A ∩ ∅ tem 3 elementos pelo menos (A ∪ B) ∪ C tem no máximo 2 elementos (A ∩ B) ∩ C tem no máximo 2 elementos Data Resp.: 04/12/2023 17:32:59 Explicação: A intersecção de A com B tem no máximo dois elementos, uma vez que o conjunto A só tem dois elementos. Essa intersecção pode ter zero, um ou dois elementos. Isto pode ser visto desenhando um diagrama de Venn. A U B terá seis elementos e A U C terá sete elementos. Como C tem 5 elementos, mas a intersecção de A com B tem, no máximo dois elementos, então (A ∩ B) ∩ C tem, no máximo 2 elementos. 5. A análise sintática é usualmente implementada a partir de uma gramática: Irrestrita Com estrutura de frase Livre de contexto Regular Sensível ao contexto Data Resp.: 04/12/2023 17:33:33 Explicação: As gramáticas regulares são utilizadas para a análise léxica em compiladores de linguagens de programação. A parte gramatical da linguagem é verificada por meio de árvores de derivação geradas a partir de gramáticas livres de contexto. 6. 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 Regular Irrestrito Livre de Contexto Com estrutura de frase Sensível ao Contexto Data Resp.: 04/12/2023 17:34:49 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. 7. BIO-RIO - 2014 - ETAM - Curso de Formação de Técnicos - 2º Semestre Dados três conjuntos, A = {1,2,3}, B = {4,5} e C = {1,2,4}, observe os pares ordenados apresentados graficamente na figura abaixo. Esses pares correspondem, graficamente, a: (A U C) X B B X (A U C) (A ∩ C) X B B X (A ∩ C) C X (A U B) Data Resp.: 04/12/2023 17:35:41 Explicação: A fim de que o produto cartesiano de B com qualquer outro conjunto fosse representado, os pares ordenados devem, necessariamente, iniciar com os elementos do conjunto B = {4, 5}. Como os pares da figura começam com os elementos 1 e 2, as alternativas a e d estão incorretas. A alternativa ¿e¿ nos obrigaria a ter um par ordenado começando com elemento 4. A intersecção dos conjuntos A e C contém os elementos comuns {1, 2}, uma vez que 3 não está contido em C. O produto cartesiano desse conjunto intersecção com o conjunto B é: {(1, 4); (1, 5); (2, 4); (2, 5)} 8. 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 7b1 _ab9 ab_9 ab_ Data Resp.: 04/12/2023 17:35:58 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. 9. 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á: 64 81 243 729 256 Data Resp.: 04/12/2023 17:36:04 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 10. Considere, a seguir, a gramática livre de contexto G = (V, T, P, S), onde V = {S}, T = {a,b,c}, e P: S → aS|Sb|c Qual expressão regular gera a mesma linguagem que a gramática definida acima? an c bm, onde n, m ≥ 1 an c bm, onde n, m ≥ 0 a+ b+ c ca+ b+ anc bn, onde n ≥ 0 Data Resp.: 04/12/2023 17:36:12 Explicação: Aplicando algumas regras de produção podemos inferir a lei geral de formação de cadeias dessa linguagem. S → c. Isso equivale a λcλ. Logo n, m ≥ 0, eliminamos as alternativas de a) até c), uma vez que pode haver cadeias sem símbolos ¿a¿ e/ou ¿b¿. Sejam os exemplos: S → aS⇒ac e S → Sb⇒cb. Esses dois exemplos nos mostram que as cadeias dessa linguagempodem ter números diferentes de símbolos ¿a¿ e ¿b¿, indicando que a alternativa d está errada.
Compartilhar