Diagrama de estado - State diagram
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.
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.
Harel statechart
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.
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
- David Harel
- DRAKON
- SCXML é uma linguagem XML que fornece um ambiente de execução genérico baseado em máquina de estado com base em gráficos de estado Harel.
- Máquina de estado UML
- YAKINDU Statechart Tools é um software para modelagem de diagramas de estado (gráficos de estados Harel, máquinas Mealy, máquinas Moore), simulação e geração de código-fonte.
Referências
links externos
- Introdução aos diagramas de máquina de estado UML 2 por Scott W. Ambler
- UML 2 State Machine Diagram Guidelines de Scott W. Ambler
- Intelliwizard - UML StateWizard - Uma estrutura de modelagem / desenvolvimento dinâmica UML semelhante a ClassWizard e ferramenta rodando em IDEs populares sob licença de código aberto.
- YAKINDU Statechart Tools - uma ferramenta de código aberto para a especificação e desenvolvimento de sistemas reativos orientados a eventos com a ajuda de máquinas de estado .
- Compreendendo e usando máquinas de estado MATLAB Tech Talks sobre máquinas de estado
- FSM: Open Source Finite State Machine Generation in Java por Alexander Sakharov FSM
- scxmlcc Uma máquina de estado scxml eficiente para compilador C ++.
- SMC: um compilador de máquina de estado de código aberto que gera FSM para várias linguagens como C, Python, Lua, Scala, PHP, Java, VB, etc. SMC
- Diagrama de estado - uma biblioteca C ++ de código aberto e gratuita que oferece suporte à especificação e execução de máquinas de estado finito que contêm hierarquia e simultaneidade.