Modelagem e solução de problemas através de modelos formais

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
DEPARTAMENTO ACADÊMICO DE INFORMÁTICA
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO

MODELAGEM E SOLUÇÃO DE PROBLEMAS ATRAVÉS DE MODELOS FORMAIS: GOING TOGETHER

RELATÓRIO

MODELAGEM E SOLUÇÃO DE PROBLEMAS ATRAVÉS DE MODELOS FORMAIS: GOING TOGETHER

Relatório de modelagem e solução de problemas através de modelos formais, apresentado com objetivo a obtenção parcial de nota na disciplina de Linguagens Formais, Autômatos e Computabilidade.

SUMÁRIO

1. INTRODUÇÃO
Máquinas de Estado ou Autômato é um modelo matemático capaz de modelar diversas situações do mundo real ou não, para uma linguagem de formalismos e capaz de ser computada. Neste trabalho será usado um Autômato Finito NãoDeterminístico para a modelagem de um problema (Going Together, fonte URI), no qual a partir do processamento das palavras o estado final indicará a chegada de todos os personagens na célula alvo.

2. OBJETIVO
A modelagem do Jogo Going Together compete à representação das células em que os personagens (robôs) podem estar ao longo do jogo. Sendo essas células obstáculos, células vazias ou células alvo.
Ao final do processamento do autômato com uma palavra que seja aceita pelo mesmo, o resultado será o final do jogo onde os três personagens devem estar em células alvo.

3. DESCRIÇÃO DO PROBLEMA
Chegando junto trata-se de um jogo que se passa em um cenário de labirinto, cujo objetivo é fazer com que todos os personagens (Aneed, Ben, Cindy) cheguem às células alvo, o que significaria que eles conseguiram escapar.
No labirinto existem três tipos de células, as células vazias, que indicam que o robô esta livre para passar por ela, as células com obstáculos, que não permitem o avanço, portanto o robô mantém sua posição na célula anterior e por fim as células alvo, que indicam a chegada do robô ao seu objetivo.
Os robôs podem se movimentar para a