1a 6 Linguagens Formais e Autômatos Atividade de Sistematização 10 09 24

Prévia do material em texto

<p>Atividade de Sistematização – Unidade I</p><p>Pergunta 1</p><p>Uma linguagem formal pode ser considerada como mecanismos formais para a</p><p>representação e especificação de linguagens. Esta representação pode ser</p><p>realizada por reconhecedores e geradores. Os geradores são mecanismos formais</p><p>que permitem gerar palavras de uma linguagem. O principal gerador é a gramática</p><p>de Chomsky. Formalmente, a definição de gramática de Chomsky é dada como</p><p>uma quadrupla ordenada;</p><p>G =(V, T, P, S), onde:</p><p>B. V é um conjunto finito de símbolos variáveis ou não-terminais; T é um</p><p>conjunto finito de símbolos terminais; P são as regras de produções; S é o</p><p>símbolo inicial ou variável inicial.</p><p>Pergunta 2</p><p>A operação de intersecção de dois conjuntos é uma operação elementar na teoria</p><p>dos conjuntos. Assinale a alternativa que contenha TODAS as informações</p><p>corretas sobre a operação intersecção.</p><p>B.</p><p>Pergunta 3</p><p>C. {1,2,3,4,5,6,7,8,9,11,15,22,0}</p><p>Pergunta 4</p><p>D. {c,d}.</p><p>Observe as afirmações a seguir;</p><p>I. Um símbolo é uma entidade abstrata básica sem definição formal.</p><p>II. Um alfabeto é definido como um conjunto finito de símbolos.</p><p>III. Uma palavra é uma sequência infinita de símbolos (do alfabeto).</p><p>Qual afirmação esta incorreta? Assinale a alternativa que contém a afirmação</p><p>INCORRETA..</p><p>C. A afirmação III está incorreta.</p><p>Pergunta</p><p>Assinale a alternativa que contém TODAS as informações corretas sobre</p><p>derivação.</p><p>E. As regras de produção denotam as condições de geração das palavras da</p><p>linguagem, ou seja, definem</p><p>como as palavras serão geradas. A aplicação de uma regra de produção é</p><p>chamada de derivação de</p><p>uma palavra.</p><p>Pergunta</p><p>Atividade de Sistematização – Unidade II</p><p>Pergunta 1</p><p>C. I-2; II-2; III-3.</p><p>Pergunta 2</p><p>E. é aceita, aba não é aceita e bba é aceita.</p><p>Pergunta 3</p><p>A. I-1; II-2.</p><p>Pergunta 4</p><p>A. não é aceita, abaaa é aceita e aa não é aceita.</p><p>Ao ler um símbolo, um Autômato:</p><p>I Finito Determinístico (AFD) pode assumir um conjunto de estados possíveis.</p><p>II Finito Não Determinístico (AFN) pode assumir um conjunto de estados</p><p>possíveis.</p><p>III Com movimento vazio pode assumir um conjunto de estados possíveis.</p><p>É VERDADEIRO o que se afirma em</p><p>D. II e III, apenas.</p><p>Pergunta</p><p>aaaa</p><p>a</p><p>Atividade de Sistematização – Unidade III</p><p>Pergunta 1</p><p>B. (aa+bb).</p><p>Pergunta 2</p><p>Dado o alfabeto ∑ = {a,b}, a ER ba*, quais palavras são geradas?</p><p>C. Todas as palavras que iniciam por b, seguido por zero ou mais a.</p><p>Pergunta 3</p><p>Dado o alfabeto ∑ = {a,b}, a ER (a+b)*aa(a+b)*, quais palavras são geradas?</p><p>D. Todas as palavras contendo aa como subpalavra.</p><p>Pergunta 4</p><p>As operações mais elementares na Linguagem Regular são:</p><p>C. União, Concatenação, Complemento e Intersecção.</p><p>Pergunta</p><p>Dado o alfabeto ∑ = {a,b}, a ER (a+b)*(aa+bb), quais palavras são geradas?</p><p>D. Todas as palavras que terminam com aa e bb.</p><p>Pergunta</p><p>Uma gramática linear pode possuir 4 formas diferentes de produções. Quais</p><p>são essas?</p><p>Assinale a alternativa que contenha TODAS as informações CORRETAS:</p><p>A</p><p>Gramática Linear à Direita (GLD), Gramática Linear à Esquerda (GLE),</p><p>Gramática Linear Unitária à Direita (GLUD) e Gramática Linear Unitária à</p><p>Esquerda (GLUE).</p><p>Atividade de Sistematização – Unidade IV</p><p>Pergunta 1</p><p>A simplificação de uma Gramática Livre de Contexto (GLC) é composta por</p><p>quais etapas?</p><p>D.</p><p>Eliminação de símbolos inacessíveis e inúteis; eliminação de</p><p>produções vazias; produções que substituem variáveis.</p><p>Pergunta 2</p><p>Uma Gramática Livre de Contexto (GLC) pode ser representada por uma</p><p>quadrupla G, onde:</p><p>• __________ é o conjunto finito dos símbolos não terminais;</p><p>• __________ é o conjunto finito dos símbolos terminais que correspondem ao</p><p>alfabeto da linguagem definida pela gramática;</p><p>• __________ é o conjunto das regras de produção da gramática;</p><p>• __________ é a raiz da gramática – variável inicial.</p><p>Assinale a alternativa que preenche CORRETA e RESPECTIVAMENTE as</p><p>lacunas destas afirmações:</p><p>D.</p><p>V; T; P; S.</p><p>Pergunta 3</p><p>QUESTÃO ANULADA!!</p><p>POR FAVOR, SELECIONE QUALQUER UMA DAS ALTERNATIVAS PARA</p><p>GANHAR OS PONTOS DELA NA SUA TENTATIVA.</p><p>Considerando a gramática livre de contexto G = ({S, A, B}, {0, 1}, P, S)</p><p>P = {S -> A1B,</p><p>A -> 0A,</p><p>A -> 0,</p><p>B -> 0B,</p><p>B -> 1B,</p><p>B -> 1</p><p>B -> 0}</p><p>As palavras:</p><p>- 000111</p><p>- 11</p><p>- 1</p><p>São, RESPECTIVAMENTE:</p><p>POR FAVOR, SELECIONE QUALQUER UMA DAS ALTERNATIVAS PARA</p><p>GANHAR OS PONTOS DELA NA SUA TENTATIVA.</p><p>QUESTÃO ANULADA!!</p><p>D</p><p>Aceita, rejeitada e rejeitada.</p><p>Pergunta 4</p><p>Uma gramática é considerada ambígua quando</p><p>C. para uma mesma palavra é possível obter duas ou mais</p><p>árvores de derivação.</p><p>Explicação das alternativas fornecidas</p><p>1. aaaaaabbbbbb: Começa com uma sequência de "a's" (aceito).</p><p>Depois, segue com uma sequência de "b's" (aceito). Portanto,</p><p>essa palavra é aceita.</p><p>2. aaaabbbbb: Começa com uma sequência de "a's" (aceito). No</p><p>entanto, em seguida, segue com uma sequência de "b's"</p><p>(aceitado). Portanto, essa palavra é aceita.</p><p>3. abbbb: Não começa com uma sequência de "a's" (rejeitado).</p><p>Portanto, essa palavra é rejeitada.</p><p>4. Aaaaaaaabb: rejeitado</p><p>Atividade de Sistematização– Unidade VI</p><p>Pergunta 1</p><p>Observe as afirmações a seguir.</p><p>I. As classes de complexidade visam classificar problemas computacionais de</p><p>acordo com sua dificuldade, e relacionar essas classes entre si.</p><p>II. Na classe P encontra-se o conjunto de problemas que são resolvidos em tempo</p><p>polinomial por uma por uma máquina de Turing determinística.</p><p>III. A classe NP possui o conjunto de problemas que são solucionados em tempo</p><p>polinomial por uma máquina de Turing também determinística.</p><p>Assinale a alternativa que contenha TODAS as informações corretas.</p><p>B</p><p>Somente as afirmações I e II estão corretas.</p><p>Pergunta 2</p><p>O que diz a tese de Church?</p><p>Assinale a alternativa que contenha TODAS as informações corretas.</p><p>B</p><p>Esta tese diz que a capacidade de computação representada pela máquina de</p><p>Turing é o limite máximo que pode ser atingido por qualquer dispositivo de</p><p>computação.</p><p>Pergunta 3</p><p>A classe de complexidade P contém:</p><p>D</p><p>O conjunto de problemas que são resolvidos em tempo polinomial por uma</p><p>máquina de Turing determinística.</p><p>Pergunta 4</p><p>Considerando o processo de compilação na análise sintática, qual elemento da</p><p>teoria da linguagem formal é usado?</p><p>D</p><p>Árvore de derivação (gramática livre de contexto).</p><p>Pergunta</p><p>A classe NP possui o conjunto de problemas que:</p><p>Assinale a alternativa que contém TODAS as informações corretas.</p><p>B</p><p>São solucionados em tempo polinomial por uma máquina de Turing não-</p><p>determinística.</p><p>Pergunta</p><p>A hierarquia de Chomsky é composta pelas linguagens:</p><p>Assinale a alternativa que contenha TODAS as informações corretas.</p><p>B</p><p>Linguagem regulares, Livres de do Contexto, Sensíveis ao Contexto e</p><p>Recursivamente Enumeráveis.</p>