Diagrama de estado - State diagram

Um diagrama de estado para uma porta que só pode ser aberta e fechada

Um diagrama de estado é um tipo de diagrama usado em ciência da computação e campos relacionados para descrever o comportamento dos sistemas. Os diagramas de estado requerem que o sistema descrito seja composto de um número finito de estados ; às vezes, este é realmente o caso, enquanto outras vezes esta é uma abstração razoável . Existem muitas formas de diagramas de estado, que diferem ligeiramente e têm semânticas diferentes .

Visão geral

Os diagramas de estado são usados ​​para fornecer uma descrição abstrata do comportamento de um sistema . Esse comportamento é analisado e representado por uma série de eventos que podem ocorrer em um ou mais estados possíveis. Por meio deste, "cada diagrama geralmente representa objetos de uma única classe e rastreia os diferentes estados de seus objetos através do sistema".

Os diagramas de estado podem ser usados ​​para representar graficamente máquinas de estados finitos (também chamados de autômatos finitos). Isso foi introduzido por Claude Shannon e Warren Weaver em seu livro de 1949 The Mathematical Theory of Communication . Outra fonte é Taylor Booth em seu livro de 1967 Sequential Machines and Automata Theory . Outra representação possível é a tabela de transição de estado .

Gráfico direcionado

Uma forma clássica de diagrama de estado para um autômato finito (FA) é um gráfico direcionado com os seguintes elementos (Q, Σ, Z, δ, q 0 , F):

  • Vértices Q : um conjunto finito de estados, normalmente representados por círculos e rotulados com símbolos designadores exclusivos ou palavras escritas dentro deles
  • Símbolos de entrada Σ : uma coleção finita de símbolos ou designadores de entrada
  • Símbolos de saída Z : uma coleção finita de símbolos de saída ou designadores

A função de saída ω representa o mapeamento de pares ordenados de símbolos de entrada e estados Onto símbolos de saída, indicadas matematicamente como ω  : Σ × Q Z .

  • Bordas δ : representam as transições de um estado para outro causadas pela entrada (identificadas por seus símbolos desenhados nas bordas). Uma aresta é geralmente desenhada como uma seta direcionada do estado atual para o próximo estado. Este mapeamento descreve a transição de estado que deve ocorrer na entrada de um símbolo específico. Isso é escrito matematicamente como δ  : Q × Σ Q , então δ (a função de transição) na definição de FA é dada pelo par de vértices conectados por uma aresta e pelo símbolo em uma aresta em um diagrama que representa este FA . O item δ (q, a) = p na definição do FA significa que do estado denominado q sob o símbolo de entrada a , a transição para o estado p ocorre nesta máquina. No diagrama que representa este FA, isso é representado por uma aresta marcada por um apontamento do vértice marcado por q para o vértice marcado por p .
  • Estado inicial q 0 : (não mostrado nos exemplos abaixo). O estado inicial q 0 ∈ Q é geralmente representado por uma seta sem origem apontando para o estado. Em textos mais antigos, o estado inicial não é mostrado e deve ser inferido do texto.
  • Estado (s) de aceitação F : Se usado, por exemplo, para aceitar autômatos, F ∈ Q é o estado de aceitação . Geralmente é desenhado como um círculo duplo. Às vezes, o (s) estado (ões) de aceitação funcionam como estados " F inal" (interromper, interceptado).

Para um autômato finito determinístico (DFA), autômato finito não determinístico (NFA), autômato finito não determinístico generalizado (GNFA) ou máquina de Moore , a entrada é denotada em cada aresta. Para uma máquina Mealy , a entrada e a saída são representadas em cada aresta, separadas por uma barra "/": "1/0" denota a mudança de estado ao encontrar o símbolo "1", causando a saída do símbolo "0". Para uma máquina de Moore, a saída do estado é geralmente escrita dentro do círculo do estado, também separada do designador do estado com uma barra "/". Existem também variantes que combinam essas duas notações.

Por exemplo, se um estado tem um número de saídas (por exemplo, "a = motor no sentido anti-horário = 1, b = luz de advertência inativa = 0"), o diagrama deve refletir isso: por exemplo, "q5 / 1,0" designa o estado q5 com produz a = 1, b = 0. Este designador será escrito dentro do círculo do estado.

Exemplo: máquina DFA, NFA, GNFA ou Moore

S 1 e S 2 são estados e S 1 é um estado de aceitação ou um estado final . Cada aresta é identificada com a entrada. Este exemplo mostra um aceitador para números binários que contêm um número par de zeros.

DFAexample.svg

Exemplo: máquina Mealy

S 0 , S 1 e S 2 são estados. Cada aresta é rotulada com " j / k ", onde j é a entrada ek é a saída.

Diagrama de estado de uma máquina Mealy simples

Harel statechart

Diagrama mostrando como os Statecharts de Harel contribuíram para métodos orientados a objetos e notação

Os gráficos de estados Harel, inventados pelo cientista da computação David Harel , estão ganhando uso generalizado, uma vez que uma variante se tornou parte da Unified Modeling Language (UML). O tipo de diagrama permite a modelagem de superestados , regiões ortogonais e atividades como parte de um estado.

Os diagramas de estado clássicos requerem a criação de nós distintos para cada combinação válida de parâmetros que definem o estado. Isso pode levar a um grande número de nós e transições entre nós para todos, exceto o mais simples dos sistemas ( explosão de estado e transição ). Essa complexidade reduz a legibilidade do diagrama de estado. Com os gráficos de estado Harel, é possível modelar vários diagramas de estado multifuncionais dentro do gráfico de estado. Cada uma dessas máquinas de estado interfuncional pode fazer a transição internamente sem afetar as outras máquinas de estado no gráfico de estados. O estado atual de cada máquina de estado multifuncional no gráfico de estados define o estado do sistema. O gráfico de estado Harel é equivalente a um diagrama de estado, mas melhora a legibilidade do diagrama resultante.

Semântica alternativa

Existem outros conjuntos de semânticas disponíveis para representar diagramas de estado. Por exemplo, existem ferramentas para modelar e projetar lógica para controladores incorporados. Esses diagramas, como as máquinas de estado originais de Harel, oferecem suporte a estados aninhados hierarquicamente, regiões ortogonais, ações de estado e ações de transição.

Diagramas de estado versus fluxogramas

Os recém-chegados ao formalismo da máquina de estado costumam confundir diagramas de estado com fluxogramas . A figura abaixo mostra uma comparação de um diagrama de estado com um fluxograma. Uma máquina de estado (painel (a)) executa ações em resposta a eventos explícitos. Em contraste, o fluxograma (painel (b)) não precisa de eventos explícitos, mas transições de nó para nó em seu gráfico automaticamente após a conclusão das atividades.

Diagrama de estado (a) e fluxograma (b)

Nós de fluxogramas são arestas no gráfico de estados induzido. O motivo é que cada nó em um fluxograma representa um comando do programa. Um comando de programa é uma ação a ser executada. Portanto, não é um estado, mas quando aplicado ao estado do programa, resulta em uma transição para outro estado.

Em mais detalhes, a listagem do código-fonte representa um gráfico do programa. A execução do gráfico do programa (análise e interpretação) resulta em um gráfico de estado. Portanto, cada gráfico de programa induz um gráfico de estado. A conversão do gráfico do programa em seu gráfico de estado associado é chamada de "desdobramento" do gráfico do programa.

O gráfico do programa é uma sequência de comandos. Se nenhuma variável existir, então o estado consiste apenas no contador do programa, que mantém o controle de onde no programa estamos durante a execução (qual é o próximo comando a ser aplicado).

Neste caso, antes de executar um comando, o contador do programa está em alguma posição (estado antes de o comando ser executado). Executar o comando move o contador do programa para o próximo comando. Como o contador do programa é o estado completo, segue-se que a execução do comando alterou o estado. Portanto, o próprio comando corresponde a uma transição entre os dois estados.

Agora considere o caso completo, quando as variáveis ​​existem e são afetadas pelos comandos do programa sendo executados. Então, entre diferentes locais do contador do programa, não apenas o contador do programa muda, mas as variáveis ​​também podem mudar os valores, devido aos comandos executados. Conseqüentemente, mesmo se revisitarmos algum comando do programa (por exemplo, em um loop), isso não significa que o programa está no mesmo estado.

No caso anterior, o programa estaria no mesmo estado, porque todo o estado é apenas o contador do programa, portanto, se o programa se contrapõe à mesma posição (próximo comando), basta especificar que estamos no mesmo estado. No entanto, se o estado inclui variáveis, então se esses valores mudam, podemos estar no mesmo local do programa com valores de variáveis ​​diferentes, ou seja, em um estado diferente no espaço de estado do programa. O termo "desdobramento" origina-se dessa multiplicação de locais na produção do gráfico de estado a partir do gráfico do programa.

Uma autotransição é uma transição em que o estado inicial e o estado final são iguais.

Um exemplo representativo é um loop do incrementando algum contador até estourar e se tornar 0 novamente. Embora o loop do execute o mesmo comando de incremento iterativamente, o gráfico do programa executa um ciclo, mas em seu espaço de estado não há um ciclo, mas uma linha. Isso resulta do estado ser a localização do programa (aqui em ciclo) combinado com o valor do contador, que é estritamente crescente (até o estouro), de modo que diferentes estados são visitados em sequência, até o estouro. Após o estouro, o contador torna-se 0 novamente, então o estado inicial é revisitado no espaço de estado, fechando um ciclo no espaço de estado (assumindo que o contador foi inicializado em 0).

A figura acima tenta mostrar essa inversão de papéis alinhando os arcos dos diagramas de estado com os estágios de processamento do fluxograma.

Você pode comparar um fluxograma a uma linha de montagem na manufatura porque o fluxograma descreve a progressão de alguma tarefa do início ao fim (por exemplo, transformar a entrada do código-fonte em saída de código-objeto por um compilador). Uma máquina de estado geralmente não tem noção dessa progressão. A máquina de estado da porta mostrada no início deste artigo, por exemplo, não está em um estágio mais avançado quando está no estado "fechado", em comparação com o estado "aberto"; ele simplesmente reage de maneira diferente aos eventos de abertura / fechamento. Um estado em uma máquina de estado é uma maneira eficiente de especificar um determinado comportamento, em vez de um estágio de processamento.

Outras extensões

Uma extensão interessante é permitir que os arcos fluam de qualquer número de estados para qualquer número de estados. Isso só faz sentido se o sistema puder estar em vários estados ao mesmo tempo, o que implica que um estado individual apenas descreve uma condição ou outro aspecto parcial do estado geral global. O formalismo resultante é conhecido como rede de Petri .

Outra extensão permite a integração de fluxogramas em gráficos de estados Harel. Esta extensão suporta o desenvolvimento de software que é orientado por eventos e por fluxo de trabalho.

Veja também

Referências

links externos