Simulador de Máquina de Coca-Cola utilizando Teoria dos Autômatos

Prévia do material em texto

Simulador de uma " Coke Machine" utili zando 
Teor ia dos Autômatos 
 
Anderson de Rezende Rocha 
Flávio Luis Alves 
Júlio César Alves 
Rodrigo Nazaré da Silva Leite 
 
{ undersun, alves, jcalves, canniggia@comp.ufla.br} 
 
Disciplina de Linguagens Formais e Autômatos 
Prof. Jones de Oliveira Albuquerque 
 
 
RESUMO: 
 
 Aplicando os conceitos básicos da Teoria dos Autômatos, procuramos simular, neste trabalho, uma "Coke 
Machine", doravante "Máquina de Coca-Cola®” . O funcionamento tanto da máquina física quanto da máquina simulada 
seguem a mesma premissa: receber moedas, disponibili zar refrigerantes e voltar troco. 
 
 
DESCRIÇÃO DA IMPLEMENTAÇÃO: 
 
 Para a implementação deste simulador pressupomos que: a nossa máquina sempre possui troco e refrigerantes, 
não aceita moeda de R$ 0,01, bem como, aceita, no máximo, R$ 2,00. 
 
 Representação da máquina como um autômato: 
O problema consiste em traduzir as operações e os estados de uma máquina real para um autômato, 
mais precisamente uma Máquina de Moore. Dado que um autômato consiste de um conjunto de 
estados, um alfabeto e uma função de transição, partimos para a representação da Máquina de Coca-
Cola neste contexto. 
 
 Deste modo, interpretamos que na máquina: 
 
a) O alfabeto consiste em todas as ações que o usuário pode realizar na máquina, tais como: inserção 
de moedas, requisição de troco e de refrigerantes, bem como, a ação de pegar os mesmos. 
 
b) Os estados consistem nos estados reais que a máquina pode assumir, tais como: quantidade de 
dinheiro, falta de dinheiro, liberaçãdo de refrigerantes, etc. 
 
c) A função de transição consiste na relação entre cada ação que o usuário pode executar com cada 
estado que máquina pode assumir. Por exemplo: se a máquina está em um estado em que não foi 
inserida nenhuma moeda e o usuário insere uma moeda de R$ 1,00, a máquina deve passar para o 
estado correspondente a R$ 1,00. E se, logo após, o usuário pede um refrigerante que custe R$ 
0,85, a máquina deve passar para um estado que fornece o refrigerante e, tão logo, o usuário 
pegue o refrigerante, a máquina deve passar para outro estado, no qual ainda há R$ 0,15. 
 
Veja um exemplo da representação do autômato: 
Partindo do que foi dito, pensamos, primeiramente, em solucionar o problema de modo direto, com a utili zação 
de uma matriz estados por alfabeto. Por um lado, esta seria uma boa abstração, uma vez que, a matriz seria completa, ou 
seja, todo estado tem produção para qualquer símbolo do alfabeto. Entretanto, esta seria uma solução dependente deste 
problema, o que limitaria a reusabili dade do trabalho. 
 
 Deste modo, resolvemos implementar um autômato finito genérico, ou seja, um autômato útil para qualquer 
problema inerente a ele. A solução do problema está, então, numa aplicação especializada que utili zaria o autômato 
desenvolvido. 
 
A nível de implementação pensamos na representação de um autômato por um conjunto de estados e pela 
função delta (consumir um símbolo). O estado, seria representado por uma mensagem de saída (Máquina de Moore), um 
conjunto de ligações para outros estados e uma identificação de estado final ou não. Já a ligação entre um estado e outro 
teria um símbolo a ser consumido e uma referência ao estado de destino. E, por fim, o autômato é template em relação 
ao alfabeto, ou melhor, o alfabeto pode ser definido pelo usuário da classe autômato. 
 
 Com isso poderemos reutili zar a classe autômato para implementar qualquer autômato finito determinístico, 
modificando apenas a classe de aplicação e a classe que define o Alfabeto. Fizemos uma aplicação também genérica 
para testar o autômato desenvolvido. Esta aplicação construía o autômato a partir de arquivos de dados. Assim testamos 
vários autômatos modificando apenas os arquivos de dados. Os resultados obtidos serão apresentados na próxima seção. 
 
 Partimos, então, para a implementação da Máquina de Coca-Cola® propriamente dita. Para isso criamos uma 
classe clSimbolo (representação do Alfabeto) que abstrai as ações de um usuário em relação à máquina. Além de, é 
claro, modicarmos a base de dados para este problema. 
 
 Finalmente, decidimos criar uma interface gráfica (GUI), utili zando a biblioteca portável wxWindows, 
lembrando que todo o projeto foi feito em C++. 
 
 
ANÁLISE DOS RESULT ADOS 
 
 Ao implementarmos o autômato genérico, fizemos testes com vários autômatos diferentes. Alguns exemplos 
foram: autômatos que reconhecem linguagens do tipo: começa com 'aa', termina com 'abc', contém 'aba', não contém 'bb', 
a antepenúltima letra é 'a', etc., no alfabeto da língua portuguesa. 
 
 À medida que os testes foram sendo feitos, corrigimos vários erros, aperfeiçoando gradualmente o autômato. 
 
 A partir do momento que certificamos o bom funcionamento da implementação do autômato, partimos para o 
simulador. Deste ponto em diante os únicos erros encontrados eram inerentes à base de dados e não ao funcionamento 
do autômato. Por exemplo, esquecemos de tratar o estado no qual a máquina possui R$ 0,65; para resolver este 
problema bastou incluir as linhas necessárias nos arquivos de dados. 
 
 Com a implementação da interface gráfica surgiram problemas relacionados à aprendizagem da biblioteca 
wxWindows, os quais foram solucionados sem maiores traumas. 
 
 
CONCLUSÕES 
 
 Concluímos que o mais interessante neste trabalho foi a implementação do autômato genérico, uma vez que a 
Máquina de Coca-Cola® é apenas uma instância do mesmo. 
 
 Vimos, então que nosso trabalho é reutili zável para outros fins, bastando mudar as classe de aplicação e de 
definição do alfabeto, além da base de dados. 
 
 Sugestões para trabalhos futuros: 
 
i) Ao projetarmos a máquina verificamos, por exemplo que: em um estado no qual o usuário não 
inseriu dinheiro suficiente para comprar um refrigerante, e, mesmo assim, ele pede este 
refrigerante, a máquina deve passar para um outro estado que devolve uma mensagem dizendo que 
falta dinheiro. Tal estado possui as mesmas produções do primeiro, diferenciando-se apenas pela 
mensagem exibida, eles poderiam ser chamados de estados “espelho” (quase que redundantes). 
Assim uma sugestão seria a implementação de um autômato que unificasse a abordagem das 
máquinas de Mealy e de Moore. A vantagem decorre de que bastaria uma ligação do primeiro 
estado para ele mesmo, com uma mensagem na ligação (Mealy) informando a falta de dinheiro. 
 
 
 
 
 
 
 
 
ii ) O autômato poderia ser modificado de modo que as mensagens de saída (Moore) fossem templates, 
permitindo maior liberdade de representação das saídas. 
 
 
REFERÊNCIAS 
 
 MENEZES, Paulo Blauth. "Linguagens Formais e Autômatos", ed. Sagra Luzatto, RS - Brasil . 
 SUDKAMP, Thomas. "Languagens and Machines", ed. Addison Wesley, USA. 
 Documentação da biblioteca wxWindows [www.wxwindows.org]