: Linguagem Formais e Autômato

QUESTÃO 01 [Adaptado de UFMG, 2015]: O grafo de interseção de uma coleção de conjuntos A1, A2, . . . An é o grafo que tem um vértice para cada um dos conjuntos da coleção e tem uma aresta conectando os vértices se esses conjuntos têm uma interseção não vazia. Entretanto, cada estrutura depende da organização dos pontos que reportam o alinhamento de cada elemento dos conjuntos, que, juntos, ou interligados, garantem que o grafo esteja classificado e inerente aos dados. Considere a lista de conjuntos abaixo, que utiliza esta lógica: A1 = {0,2,4,6,8} A2 = {0,1,2,3,4} A4 = {5,6,7,8,9} A5 = {0,1,8,9} A construção do grafo pode obedecer em geral a três etapas. A primeira é o entendimento da regra que pode garantir que o design do grafo esteja correto, seguido da criação da relação entre os conjuntos, e concluindo, o esboço completo do desenho. Desta forma, construa um grafo, classifique e explique o porquê da sua resposta no espaço abaixo. CENTRO UNIVERSITÁRIO DE JOÃO PESSOA - UNIPÊ Curso: Eletiva - Período: 4 - Noite Disciplina: Linguagem Formais e Autômatos Professor: MS.c. Hugo Vieira Lucena de Souza QUESTÃO 02 [Adaptado de UTPR, 2015]: Uma empresa de distribuição de gás deseja distribuir gás nas capitais de alguns estados brasileiros, definidos conforme pode ser visualizado na figura abaixo. Para tanto, será necessário construir gasodutos entre tais cidades e a empresa deseja gastar o mínimo de recursos possível neste projeto, algo que dependerá da análise da estrutura geral, que está representada através de um grafo. Os custos de construção dos dutos estão indicados sobre os mesmos no mapa. O que a empresa está buscando é encontrar uma forma de localizar a central de construção em um local que se torne ao mesmo tempo viável tanto para o contexto de custo, quanto de desempenho [ c u s t o x d i s t â n c i a percorrida] nas capitais que estão indicadas no mapa do Brasil. Diante da análise que você poderá realizar no grafo gerado ao lado, responda as questões que seguem, e em seguida justifique o que está se pedindo. a. A implementação poderia ser realizada por um algoritmo comum, muito utilizado na internet. Como você resolveria este problema, e em qual capital a sede poderia ser construída? CENTRO UNIVERSITÁRIO DE JOÃO PESSOA - UNIPÊ Curso: Eletiva - Período: 4 - Noite Disciplina: Linguagem Formais e Autômatos Professor: MS.c. Hugo Vieira Lucena de Souza b. Observando o grafo, é possível classificá-lo? Como você poderia melhorar este grafo, baseado na resposta da primeira pergunta, e se esta melhoria, iria alterar o tipo do grafo? Explique sua resposta. QUESTÃO 03 [Adaptado de UFRS, 2015]: O crescimento do Turismo após a copa do Mundo da Rússia de 2018 despertou o interesse de várias escolas de línguas investirem em mais profissionais para capacitação. Uma nova unidade de uma escola conhecida internacionalmente está sendo instalada na Europa, conhecida pela grande concentração de turistas, incluindo brasileiros, que viajam para passeios, estudos ou trabalho. Os Turistas Raphael, Leuzingner, Paul e Medeiros se encontram em um bar de Moscou e começam a conversar. As línguas disponíveis são o inglês, o francês, o russo e o alemão. Paulo fala todas. Leuzingner não fala apenas o russo. Raphael fala francês e alemão. Medeiros fala inglês e russo. Diante da situação entendida por você no cenário, responda as questões abaixo a. A forma de representação de um problema é algo difícil a ser realizado. Entretanto, há estruturas computacionais que justamente viabilizam a relação de entradas e saídas de dados em cenários como este para representar uma solução viável. Como você resolveria o problema de comunicação e compreensão, criando uma regra para que todos pudessem conversar sem problemas? b. Com a solução da resposta da letra a, como estaria esboçado o grafo do problema com sua solução?