Automatos e linguagem_ AO2 -

Prévia do material em texto

AO2
Iniciado: 1 dez em 14:28
Instruções do teste
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
0,6 ptsPergunta 1
Analise as informações abaixo:
Definição formal
Um autômato de pilha é formalmente definido por uma 6-upla:
Onde:
• é um conjunto finito de estados.
• é um conjunto finito de símbolos, denominado alfabeto de entrada.
• é um conjunto finito de símbolos, denominado alfabeto da pilha.
• é a relação de transição.
• é o estado inicial.
• é o conjunto de estados finais (ou de aceitação).
Um elemento (p,a,α,q,β) é uma transição de M. Ela significa que M, estando no
estado p, com o símbolo a na cadeia de entrada e com o símbolo α no topo da
pilha, pode consumir o símbolo a, transitar para o estado q e desempilhar α
substituindo-o por β.O ∑* e o Γ* denotam o fecho de Kleene do alfabeto de
entrada e da pilha, respectivamente. Portanto, estes componentes são utilizados
para formalizar que o autômato de pilha pode consumir qualquer quantidade de
símbolos da cadeia de entrada e da pilha.
Fonte: AUTÔMATO de pilha. In: Dicionário Sensagent. On-line, 2022. Disponível em:
http://dicionario.sensagent.com/Aut%C3%B4mato%20de%20pilha/pt-pt/. Acesso em: 09 mar.
2023.
Com base nas informações sobre os autômatos de pilha, avalie as seguintes
asserções e a relação proposta entre elas.
I. Um autômato pushdown, ou autômato de pilha, é uma máquina de estado
infinito que possui um armazenamento de pilha adicional.
A+
A
A-
PORQUE
II. Um autômato de pilha é um autômato com estados infinitos que também
pode usar uma pilha limitada de memória.
Com base nas asserções, assinale a opção correta:
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da
I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições falsas.
0,6 ptsPergunta 2
Leia o trecho a seguir:
Teoria das Linguagens Formais e dos autômatos é o estudo de modelos
matemáticos que possibilitam a especificação e o reconhecimento de linguagens
(no sentido amplo da palavra), suas classificações, estruturas, propriedades,
características e inter-relacionamentos.
Uma linguagem formal é um conjunto de palavras, isto é, um conjunto finito de
letras ou símbolos com um conjunto de regras para combinar estes elementos. O
inventário destas letras é chamado de alfabeto na qual esta linguagem é definida.
O modo formal como uma linguagem é definida é chamada de gramática formal.
Assim, podemos dizer que "Linguagens formais" são mecanismos formais para
representação e especificação de linguagens, baseados na chamada "Teoria da
Computação". As representações podem ser feitas por reconhecedores e
geradores. Os reconhecedores são dispositivos formais que servem para verificar
se uma sentença pertence ou não à determinada linguagem. São os autômatos:
autômatos finitos, autômatos de pilha e Máquina de Turing. Os sistemas
geradores são dispositivos formais que permitem a geração sistemática de todas
as sentenças de uma linguagem. Os principais sistemas geradores disponíveis
são as gramáticas, onde se destacam as gramáticas de Chomsky. Então,
linguagens formais podem ser representadas de maneira finita e precisa através
de sistemas com sustentação matemática.
A+
A
A-
Fonte: CONSTRUÇÃO de compiladores/Teoria das linguagens formais. Wikilivros, [s.d.].
Disponível em: https://pt.wikibooks.org/wiki/Constru%C3%A7%C3%A3o_de_
compiladores/Teoria_das_linguagens_formais. Acesso em: 08 mar. 2023.
Com base nas informações sobre a teoria das Linguagens Formais, avalie as
seguintes asserções e a relação proposta entre elas.
I. Um símbolo é o nosso bloco de construção básico nas linguagens formais,
geralmente um caractere ou um dígito, pois um alfabeto é um conjunto finito
de símbolos.
PORQUE
II. Uma string é uma sequência infinita de símbolos do alfabeto, pois uma
linguagem formal é um conjunto de strings possivelmente infinitas, todas
sobre o mesmo alfabeto.
Com base nas asserções, assinale a opção correta:
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições falsas.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da
I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
0,6 ptsPergunta 3
Veja as informações abaixo:
A máquina de Turing não se destina a ser uma tecnologia de computação
funcional; em vez disso, pretende ser uma máquina hipotética que representa
uma máquina de computação. A máquina de Turing pode ajudar os cientistas da
computação a compreender os limites da computação mecânica.
As máquinas de Turing modelam matematicamente um dispositivo que é
executado mecanicamente usando uma fita. Esta fita inclui símbolos, que a
máquina pode escrever e ler, um após o outro, com a ajuda de uma cabeça de
fita.
Mais especificamente, uma máquina de Turing inclui o seguinte:
A+
A
A-
Fita: Uma fita que é dividida em células, uma ao lado da outra. Cada célula
inclui um símbolo de um determinado alfabeto finito. O alfabeto inclui um
símbolo em branco exclusivo, bem como um ou mais outros símbolos. O
volume de fita necessário para o cálculo é sempre incluído na máquina de
Turing.
Cabeça: Uma cabeça capaz de escrever e ler símbolos na fita. Em alguns
modelos, a cabeça se move enquanto a fita está fixada.
Registro de estado: um registro de estado para armazenar o estado da
máquina de Turing. Há um estado inicial especial através do qual o registro de
estado é inicializado.
Tabela finita: uma tabela finita (às vezes chamada de função de transição ou
tabela de ação) de instruções, que geralmente são quíntuplos, mas
ocasionalmente quádruplos.
 
Fonte: O QUE é uma máquina de turing? Theastrology Page, 2023. Disponível
em: https://pt.theastrologypage.com/turing-machine. Acesso em: 21 mar. 2023.
 
Assinale a alternativa que representa o principal objetivo das máquinas de
Turing:
Oferecer um sistema formal.
Criar computadores digitais.
Listar a natureza dos símbolos.
Ser uma máquina abstrata.
Verificar jogadas de xadrez.
0,6 ptsPergunta 4
Leia o texto:
Impacto no tempo de computação
O conceito de máquina de Turing não determinística não estende a noção de
computabilidade. Portanto, as máquinas de Turing não determinísticas computam
exatamente as mesmas funções que as máquinas de Turing determinísticas,
porque uma máquina de Turing não determinística pode ser simulada por uma
máquina de Turing determinística. No entanto, a complexidade dos cálculos
A+
A
A-
difere: a classe de complexidade polinomial associada a eles é a classe de
complexidade NP, que contém a classe correspondente para máquinas de Turing
determinísticas. É por isso que uma denominação desta classe, a saber NP, vem
de seu nome e significa N em olinômio P determinístico, ou seja, classe de
problemas que podem ser resolvidos em um tempo polinomial por máquinas de
Turing não determinísticas. Note que não sabemos se esta classe NP é ou não
igual à classe P de problemas que podem ser resolvidos em um tempo polinomial
por máquinas de Turing determinísticas: este é o famoso problema P = NP.
Fonte: MÁQUINA de Turing não determinística. Frwiki, [s.d]. Disponível em:
https://pt.frwiki.wiki/wiki/Machine_de_Turing_non_d%C3%A9terministe. Acesso em: 13 fev. 2023.
Com base nas informações sobre a máquina de Turing não determinística, avalie
as seguintes asserções e a relação proposta entre elas.
I. Uma máquina de Turing não determinística é uma generalização de uma
máquina de Turing determinística padrão, em que passamos de uma
sequência de etapas de computação determinada para várias sequências
possíveis.
PORQUE
II.Reduzir a quantidade de trabalho computacional do paradigma
determinístico permite que as máquinas de processamento não
determinísticas abram caminho para a computação artificialmente
inteligente.
Com base nas asserções, assinale a opção correta:
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da
I.
As asserções I e II são proposições falsas.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
0,6 ptsPergunta 5
Leia o texto a seguir:
A+
A
A-
[...] A beleza do trabalho de Turing foi ter definido com rigor matemático o que é
um programa, na forma da máquina de Turing, configurado como transições entre
estados finitos. E o conceito de uma máquina universal que consegue executar
quaisquer máquinas de Turing, que é o que ele chama de máquina de Turing
Universal e na prática chamamos isso de computador. Uma máquina Universal de
Turing é uma máquina de Turing cuja tarefa é simular outra máquina de Turing
arbitrária, com uma entrada de dados arbitrária.
O que chamamos de computador moderno tem uma característica muito
importante: ela consegue carregar e armazenar configurações, ou o que
chamamos de programas. Essa é uma distinção que eu considero importante.
Recentemente me perguntaram isso: o que diferencia um ábaco ou uma
calculadora mecânica de um "computador" de verdade? A definição é se ela é ou
não é uma máquina universal de Turing, particularmente com a característica de
não distinção entre programa e dados no armazenamento, na tal fita infinita, o
que permite a universalidade dele poder simular outra máquina de Turing.
Antes de Turing existem diversos experimentos que alguns chamam de
"computador" mas que na realidade seria mais correto chamar de máquinas de
calcular grandes. E aqui eu vou usar trechos do artigo "Quem Inventou o
Computador" do site do próprio autor da biografia do Turing, o Andrew Hodges.
Ele diz, e eu concordo, por exemplo, que não podemos chamar o Engenho
Analítico de Charles Babbage de computador. Ele não incorpora a ideia vital de
armazenar programas da mesma forma que os dados [...].
Fonte: AKITA, F. O Computador de Turing e Von Neumann: Por que calculadoras não são
computadores?. AkitaOnRails, 23 out. 2020. Disponível em:
https://www.akitaonrails.com/2020/10/23/akitando-86-o-computador-de-turing-e-von-neumann-por-
que-calculadoras-nao-sao-computadores. Acesso em: 09 mar. 2023.
Com base no trecho sobre as máquinas de Turing universais, avalie as
afirmações abaixo:
I. Uma máquina Universal simularia a máquina observando a saída na fita e
o estado da máquina, pois o que determina como o conteúdo da fita muda é
uma máquina de estado não finito dentro da máquina de Turing.
II. O modelo da máquina de Turing consiste em uma entrada e uma saída, e
o principal problema com elas é que uma diferente deve ser construída para
cada nova computação a ser realizada.
III. A máquina de Turing (TM, em inglês) é o nível de máquina equivalente a
um computador digital.
É correto o que se afirma em:
A+
A
A-
I e II, apenas.
I e III, apenas.
II, apenas.
II e III, apenas.
III, apenas.
0,6 ptsPergunta 6
Leia o texto a seguir:
[...] Autômato finito é um sistema de estados finitos (portanto possui um número
finito e predefinido de estados) o qual constitui um modelo computacional do
tipo sequencial muito comum em diversos estudos teórico-formais da
computação e informática, com destaque para linguagens formais,
compiladores, semântica formal e modelos para concorrência. Trata-se de um
formalismo operacional ou reconhecedor, o qual pode ser: 
• determinístico: para o estado corrente e o símbolo lido da entrada, o
sistema assume um único estado bem determinado; 
• não determinístico: para o estado corrente e o símbolo lido da entrada,
o sistema assume um estado Pertencente a um conjunto de estados
alternativos: 
• com movimentos vazios: para o estado corrente e, independentemente
de ler um símbolo ou não da entrada, o sistema assume um estado
pertencente a um conjunto de estados alternativos (portanto é não
determinístico). O movimento é dito movimento vazio se o sistema muda
de estado sem uma correspondente leitura de símbolo. Movimentos
vazios podem ser vistos como transições encapsuladas nas quais,
excetuando-se por uma eventual mudança de estado, nada mais pode ser
observado, de forma análoga à noção de encapsulação das linguagens
orientadas a objetos. 
Prova-se que os três tipos de autômatos acima são equivalentes em termos de
poder computacional [...](MENEZES, 2010, p. 69).
Fonte: MENEZES, P. B. Linguagens Formais e Autômatos: Volume 3. 6. ed. Bookman. 2010.
[Minha Biblioteca].
Com base nos conceitos sobre autômatos, assinale a alternativa que
apresenta um de seus tipos:
A+
A
A-
De pilha.
Estados.
Modelo computacional.
Compilador.
Linguagem formal.
0,6 ptsPergunta 7
Analise a imagem abaixo:
De acordo com a hierarquia de Chomsky, as gramáticas são divididas em quatro
tipos: 
Fonte: HIERARQUIA de Chomsky em teoria da computação. Acervo Lima, [s. d.] Disponível em:
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao-1/. Acesso em: 21 mar.
2023.
Considerando o texto sobre a hierarquia de Chomsky, avalie as afirmações
abaixo:
A+
A
A-
I. As linguagens gramaticais do tipo 0 são reconhecidas pela Máquina de
Turing, pois não há restrição nas regras gramaticais desses tipos de
linguagens.
II. As gramáticas do tipo 3 geram linguagens regulares, que são aquelas
linguagens que podem ser descritas usando expressões regulares. 
III. As gramáticas do tipo 2 geram linguagens livres de contexto e a
gramática do tipo 1 é conhecida como gramática sensível ao contexto.
IV. As do tipo 1 são a forma mais restrita de gramática, pois as gramáticas
do tipo 1 são conhecidas como gramáticas irrestritas.
É correto o que se afirma em:
II e IV, apenas.
I, II e IV, apenas.
I, II e III, apenas.
II e III, apenas.
I e IV, apenas.
0,6 ptsPergunta 8
Leia o texto abaixo:
Conjuntos
Um conjunto é uma coleção de símbolos, também denominados átomos ou
elementos, em que não são consideradas ocorrências múltiplas dos mesmos nem
há relação de ordem entre eles.
Exemplo 1.1 A inclusão do símbolo ♦ no conjunto {♣,♦,♥,♠} resulta no próprio
conjunto{♣,♦,♥,♠}, pois o mesmo já faz parte do conjunto e, portanto, não deve ser
considerado novamente. Por outro lado, o conjunto {♣,♦,♥,♠} é igual ao conjunto
{♦,♣,♠,♥}, uma vez que não existe relação de ordem entre os elementos que os
compõem.
Um símbolo corresponde a uma representação gráfica única e indivisível. Se
formado por caracteres, um símbolo pode ser composto por um número arbitrário
deles.
 
A+
A
A-
Exemplo 1.2 São exemplos de símbolos: “a”, “abc”, “♠”, “1” etc.
Alguns conjuntos podem ser especificados através da simples enumeração de
todos os seus elementos, denotados entre chaves e separados por vírgulas.
 
Exemplo 1.3 O conjunto formado pelos elementos 0, 1, 2, 3 é representado por {0,
1, 2, 3}. O conjunto {a, b, c, d, e, f } é formado pelas seis primeiras letras do
alfabeto romano. O conjunto {01, 231, 33, 21323} contém os elementos 01, 231,
33 e 21323.
Conjuntos podem ser referenciados através de nomes, arbitrariamente
escolhidos.
 
Exemplo 1.4 X = {0, 1, 2, 3}, Y = {a, b, c, d, e, f }. Assim, os nomes X e Y passam
a denotar os conjuntos correspondentes. 2
O número de elementos contido em um conjunto A é denotado por |A|.
 
Exemplo 1.5 No exemplo 1.4, |X| = 4, |Y| = 6. 2
Os símbolos ∈ e 6∈ servem para denotar se um determinado elemento pertence
ou não pertence a um conjunto, respectivamente.
 
Exemplo 1.6 No exemplo 1.4, 0 ∈ X, 5 6∈ X, 2 6∈ Y , b 6∈ X, c ∈ Y, h 6∈ Y.
Conjuntos podem conter um número finito ou infinito de elementos. No primeiro
caso, o conjunto pode ser denotado enumerando-se (relacionando-se
explicitamente) todos os elementos que o compõem,como foi feito para os
conjuntos X e Y do exemplo 1.4, que são conjuntos finitos.
Fonte: INTRODUÇÃO às Linguagens Formais e Autômatos/Fundamentos Matemáticos.
Wikiversidade, [s. d.]. Disponível em:
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%A
(https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A)
0s_Linguagens_Formais_e_Aut%C3%B4matos/Fundamentos_Matem%C3%A1ticos. Acesso em:
08 mar. 2023.
Considerando as informações sobre conjuntos em linguagens formais,
assinale a opção correta:
Agrupar os objetos em um conjunto é um ato de unir esses objetos com os membros
ou elementos de outro conjunto.
A+
A
A-
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
Um conjunto é geralmente representado por letras minúsculas e um elemento do
conjunto por letras maiúsculas.
Um conjunto é a representação de uma coleção de objetos, esses são objetos
distintos com uma ou mais propriedades comuns.
Um conjunto sem elementos ou conjuntos vazios também é chamado de conjuntos
nulos e é denotado apenas por Φ.
Conhecer o tipo de um conjunto é irrelevante para entender as operações de conjunto
apropriadas aplicáveis a esse conjunto específico.
0,6 ptsPergunta 9
Analise as informações a seguir:
Uma gramática regular pode ser "esquerda" ou "direita".
Uma gramática esquerda regular é um conjunto de regras da forma:
onde, são símbolos não terminais e um símbolo terminal. 
Uma gramática correta regular é um conjunto de regras da forma:
onde, são símbolos não terminais e um símbolo terminal. Além disso, como para
todas as gramáticas, consideramos um determinado não terminal chamado
axioma e anotamos. 
Exemplo
A gramática a seguir é uma gramática correta regular:
A+
A
A-
Com a gramática anterior, podemos gerar a palavra. De fato: 
Equivalência entre autômatos finitos e gramáticas regulares
Podemos efetivamente transformar uma gramática regular correta em um
autômato finito determinístico e vice-versa. Os não terminais correspondem aos
estados do PLC.
Exemplo
Considere a gramática acima. O autômato correspondente é o seguinte:
A sequência de derivações corresponde à leitura da palavra no autômato onde se
passa sucessivamente nos estados: S, A, S, A, S, C, S.
Fonte: GRAMÁTICA regular. Frwiki, [s.d.]. Disponível em:
https://pt.frwiki.wiki/wiki/Grammaire_r%C3%A9guli%C3%A8re. Acesso em: 10 mar. 2023.
Considerando os aspectos relacionados às gramáticas regulares, avalie as
afirmações abaixo:
I. Uma linguagem regular pode ser expressa usando um autômato finito
determinístico ou não determinístico, uma expressão regular ou uma
gramática regular.
A+
A
A-
II. Gramáticas regulares é outra maneira de descrever linguagens regulares.
Uma gramática é composta por terminais, variáveis e regra de produção.
III. Gramáticas regulares representam exatamente o conjunto de linguagens
regulares para mostrar que podemos converter qualquer autômato finito não
determinístico em uma gramática regular.
É correto, apenas, o que se afirma em:
I.
I, II e III.
II e III.
I e II.
II.
0,6 ptsPergunta 10
Analise o texto abaixo sobre normalização e formas normais:
[...] Uma forma normal, no contexto de bancos de dados, refere-se à uma diretriz,
uma convenção com o objetivo de prevenir anomalias e inconsistências em meio
às atualizações frequentes que uma base irá sofrer, minimizando a redundância
ao preço de uma menor eficiência entre consultas [...]. 
A normalização é um fator que toma como pressuposto que a base sofrerá
constantes atualizações. Se trata-se de uma base estática e muito consultada,
não há fortes motivos para se normalizar.
Primeira Forma Normal
A Primeira Forma Normal (ou 1FN) refere-se ao formato de um registro. Esta
diretriz exclui a possibilidade de haver campos que possuem mais de um atributo,
ou seja, um vetor ou grupo de atributos [...].
Segunda Forma Normal
Esta forma normal refere-se ao relacionamento entre atributos dentro de uma
determinada tabela, mais especificamente entre atributos chave e não-chave,
tomaremos daqui em diante “chave” como chave primária, não considerando
chaves estrangeiras [...].
Terceira Forma Normal
A Terceira Forma Normal (3FN) é bastante semelhante a segunda e também se
A+
A
A-
Nenhum dado novo para salvar. Última verificação às 14:37 
refere a chaves. Além disso, ela também requer que antes a Primeira Forma
Normal seja satisfeita. Esta diretriz é violada quando um atributo não chave
refere-se a outro atributo que também não é chave dentro de uma tabela [...].
Quarta Forma Normal
Até este ponto nosso banco de dados já está bastante organizado e eliminamos
diversos débitos técnicos que poderiam nos gerar dores de cabeça. Porém ainda
podemos ir mais longe [...].
Quinta Forma Normal
Por fim, a Quinta Forma Normal. Direto ao ponto, para que um esquema se
enquadre nesta diretriz, primeiramente ele deve estar em todas as formas
normais vistas anteriormente e, se estiver na 4FN, muito provavelmente estará
também na quinta [...].
Fonte: ROSA, L. G. F. As cinco formas normais e porque você deve utilizá-las. Medium, 22 set.
2017. Disponível em: https://medium.com/@luizguilhermefr/cinco-formas-normais-8f238bc30189.
Acesso em: 14 mar. 2023.
Considerando as informações apresentadas acima, assinale a opção correta
sobre normalização e formas normais:
A normalização envolve a organização das colunas com as relações, e tabelas com
os atributos.
A normalização é o processo de estruturar um banco de dados relacional de acordo
com as formas normais.
A normalização é realizada sempre ao criar um novo design de banco de dados, o
que chamamos de decomposição.
Um modelo hipotético de forma normal de nível 2 é mais normalizado que um de nível
4 ou 5.
Se temos um modelo na 3ª forma normal, isso significa que ele também atende aos
níveis 4 e 5.
Enviar teste
A+
A
A-