Automatos e um pouco de Teoria

Formalmente, um automato é definido como sendo um modelo matemático de uma máquina de estados finitos (MEF).

Um automato funciona como um reconhecedor de uma determinada linguagem e serve para modelar uma máquina ou, se quiserem, um computador simples. É usado, por exemplo, em editores de texto para reconhecer padrões. Um conceito fundamental nos automatos é o conceito de estado. As noções de estado e sistema são tão onipresentes que foi desenvolvido um campo de conhecimento chamado Teoria dos sistemas. Este conceito é aplicado a qualquer sistema, como por exemplo, à nossa televisão.  Uma televisão pode estar ligada(on) ou desligada(off), temos então um sistema com dois estados.

A um nível mais detalhado, podemos desejar diferenciar os canais, caso em que podemos ter centenas de estados: um para desligada e os restantes significando ligada no canal N. (Wikipédia)

Máquinas de estados Finitos – MEF

As MEFs são máquinas abstratas que capturam as partes essenciais de máquinas concretas, que vão desde máquinas de vender jornais ou refrigerantes, passando por relógios digitais, elevadores, programas de computador e até mesmo o próprio computador digital (MENEZES, 2010).

Dentre as principais vantagens de MEFs estão: a sólida base teórica, o poder de expressividade e a existência de inúmeros algoritmos de interação com as máquinas. (PINHEIRO, 2012)

Uma MEF é uma representação de uma máquina composta por estados e eventos. Uma transição é caracterizada por dois eventos: um de entrada e um de saída;  um estado origem e um estado destino. A máquina pode estar em apenas um estado por vez. Ao ocorrer um evento de entrada, a máquina pode responder com um evento de saída e uma transição para outro estado. (PINHEIRO, 2012)

A representação de uma MEF pode ser feita por um diagrama de estados, em que círculos representam os estados e arcos direcionados, as transições (PINHEIRO, 2012). Na Figura 1, pode-se observar um exemplo de uma MEF com quatro estados e oito transições, onde “q0” é o estado inicial.

Figura 1 - Exemplo de MEF

Figura 1 – Exemplo de MEF

Outra representação é a tabela de transição, em que os estados são representados por linhas e as entradas por colunas, como mostrado na Tabela 1.

Tabela 1 - Tabela de transição da MEF Figura 1

Tabela 1 – Tabela de transição da MEF Figura 1

Formalismo

Existem dois tipos de MEFs, Mealy e Moore: na máquina de Mealy, os eventos de saída estão associados às transições, ao ocorrer um evento de entrada, o evento de saída ocorre durante a mesma transição. Na máquina de Moore, os eventos de saída estão associados aos estados; sendo assim, o evento de saída ocorre no seu estado destino (MENEZES, 2010).

Segundo Menezes (2010) a representação de uma MEF é definida como 7-upla: <I, Q, Z, Q0, F, O, Y>.

  • I:  alfabeto de entrada ou símbolos de entrada;
  • Q: conjunto dos estados da máquina;
  • Z: função de transição: Z: Q x I = Q; Mapeia um estado e uma entrada para o próximo estado;
  • Q0: estado inicial da máquina, que deve ser um elemento do conjunto Q;
  • F: conjunto de estados finais, que devem ser elementos do conjunto Q;
  • O: alfabeto de saída;
  • Y: função de saída:
    • para a representação de Mealy: Y: Q x I = O; Mapeia um estado e uma entrada para a saída;
    • para a representação de Moore: Y: Q = O; Mapeia um estado para a saída;

Considerando a MEF da Figura 1, tem-se para o estado “q0” as funções de saída, Y(q0,a) = 1 e Y(q0,b) = 0, e as funções de transição, Z(q0,a) = q1 e Z(q0,b) = q2. Pode-se estender essas notações para sequências de entrada aplicada a partir de um estado. Por exemplo, para o estado “q0”, dada a sequência “abba”, temos Y(q0,abba)=1010 e Z(q0,abba)=q1.

A representação formal para a MEF apresentada na Figura 1 pode ser definida como:

  • alfabeto de entrada I = {a, b};
  • conjunto de estados Q = {q0, q1, q2, q3};
  • estado inicial Q0 = {q0}
  • funções de transição:
    • Z(q0,a)         = q1;
    • Z(q0,b)         = q2;
    • Z(q1,a)         = q1;
    • Z(q1,b)         = q3;
    • Z(q2,a)         = q1;
    • Z(q2,b)         = q0;
    • Z(q3,a)         = q1;
    • Z(q3,b)         = q2;
  • conjunto de estados finais F = {};
  • alfabeto de saída O = {0, 1};
  • funções de saída:
    • Y(q0,a)         = 1;
    • Y(q0,b)         = 0;
    • Y(q1,a)         = 0;
    • Y(q1,b)         = 0;
    • Y(q2,a)         = 0;
    • Y(q2,b)         = 1;
    • Y(q3,a)         = 0;
    • Y(q3,b)         = 1;

Propriedades de MEFs

As MEFs possuem propriedades importantes quanto sua estrutura, como (MENEZES, 2010):

  • Completude: uma MEF é dita complemente especificada, ou completa, se ela trata todas as entradas pertencentes ao domínio de entrada (I) em todos os estados (Q). Caso contrário, a MEF é dita parcial;
  • Conectividade: uma MEF é fortemente conexa se para cada par de estados (qi, qj) existe uma sequência de entrada que executa um caminho de transições com origem em qi e destino a qj. Se a partir do estado inicial for possível atingir todos os demais estados a MEF é inicialmente conexa;
  • Determinismo: uma MEF é dita determinística quando há somente uma transição para cada par evento-estado;
  • Equivalência: dois estados são equivalentes quando não houver sequência de entrada que gere saídas diferentes quando executadas a partir dos respectivos estados.
  • Reduzida ou mínima: a MEF é reduzida ou mínima se não existem estados equivalentes.

A Figura 1 é um exemplo de MEF completa, reduzida, fortemente conexa e determinística.

Statecharts

O principal problema na representação de sistemas reativos (sistemas reais) consiste na dificuldade de descrever o seu comportamento de forma clara, concisa e livre ambiguidade, uma vez que seu comportamento é dirigido por eventos complexos e inter-relacionados. Em alguns casos, o uso de MEFs se torna inviável, por conta de que pequenas variações no comportamento acarretam no crescimento exponencial dos estados (HAREL, 1987).


A técnica de especificação denominada Statecharts proposto por Harel (1987) permitiu uma representação clara e explícita de hierarquia, concorrência e interdependência entre componentes do sistema. (SILVA et al., 2008)

Esta notação é uma extensão do diagrama tradicional de MEFs, ao qual foram adicionadas as características de: hierarquia de estados (profundidade), ortogonalidade (representação de atividades paralelas) e interdependência entre estados (mecanismos de comunicação) (HAREL, 1987).

Os elementos fundamentais para se especificar um sistema reativo em Statecharts são: Estados, Eventos, Condições, Ações, Expressões, Variáveis e Transições (SILVA et al., 2008).

Os estados descrevem componentes (e suas possíveis situações) de um determinado sistema. Os estados podem ser classificados em dois grupos: básicos e não básicos (SILVA et al., 2008).

Os estados básicos são aqueles que não possuem subestados, que não possuem refinamento. Os estados não básicos são decompostos em subestados, classificados em dois tipos: XOR ou AND (HAREL, 1987).

A decomposição do tipo XOR, não permite que um estado não básico assuma mais de um subestado simultaneamente. Entretanto, a decomposição do tipo AND, permite que o estado assuma mais de um subestado simultaneamente (HAREL, 1987).

Os eventos, função de transição em MEFs, são elementos que interferem no estado atual definindo a dinâmica do sistema. Opcionalmente, o evento pode receber uma condição (condição de guarda), que ao ser satisfeita executa a transição ao qual o evento está associado (HAREL, 1987).

Os eventos podem ser classificados em internos e externos. Os eventos internos são gerados pelo próprio sistema, sem a necessidade de um estímulo externo e são detectados automaticamente graças a graças à capacidade de broadcasting implícita ao formalismo Statecharts. Os eventos externos são aqueles gerados fora das fronteiras do sistema, e normalmente ocorrem por estímulo externo (SILVA et al., 2008).

As ações, função de saída em MEFs, ocorrem dentro do sistema a partir da execução de um evento, e podem representar a mudança de uma expressão ou de uma variável (SILVA et al., 2008).

Assim como em MEFs as representações gráficas em arco é que denotam a mudança de um estado para outro. Os rótulos nos arcos de transição definem a notação: evento[condição]/ação. (SILVA et al., 2008). A Figura 2 apresenta um diagrama simples representado por Statecharts.

Figura 2 - Exemplo de Statecharts

Figura 2 – Exemplo de Statecharts

A técnica de especificação Statecharts pode ser considerada uma Máquina de Estados Finitos Estendidas (MEFE) que suporta estrutura hierárquica e concorrente de estados e um mecanismo de comunicação entre componentes através de eventos. (AMARAL; VIJAYKUMAR; MARTINS, 2003)

Download

Deixe uma resposta

Seu endereço de email não será publicado.

This site uses Akismet to reduce spam. Learn how your comment data is processed.