Диаграмма состояний - State diagram

Диаграмма состояний двери, которую можно только открывать и закрывать

А диаграмма состояний это тип диаграмма используется в Информатика и связанные поля для описания поведения систем. Диаграммы состояний требуют, чтобы описываемая система состояла из конечного числа состояния; иногда это действительно так, а в других случаях это разумный абстракция. Существует множество форм диаграмм состояний, которые немного отличаются и имеют разные семантика.

Обзор

Диаграммы состояний используются для абстрактного описания поведение из система. Это поведение анализируется и представляется серией событий, которые могут происходить в одном или нескольких возможных состояниях. Таким образом, «каждая диаграмма обычно представляет объекты одного класса и отслеживает различные состояния его объектов в системе».[1]

Диаграммы состояний могут использоваться для графического представления конечные автоматы (также называемые конечными автоматами). Это было введено Клод Шеннон и Уоррен Уивер в их книге 1949 года Математическая теория коммуникации. Другой источник Тейлор Бут в его книге 1967 года Последовательные машины и теория автоматов. Другое возможное представление - это таблица переходов между состояниями.

Направленный граф

А ориентированный граф

Классическая форма диаграммы состояний конечного автомата (ФА) - это ориентированный граф со следующими элементами (Q, Σ, Z, δ, q0, F):[2][3]

  • Вершины Q: конечный набор состояний, обычно представленный кружками и помеченный уникальными обозначениями или словами, написанными внутри них.
  • Входные символы Σ: конечный набор входных символов или обозначений
  • Выходные символы Z: конечный набор выходных символов или обозначений

Функция вывода ω представляет собой отображение упорядоченных пар входных символов и состояний на выходные символы, математически обозначаемые как ω : Σ × Q→ Z.

  • Ребра δ: представляют переходы из одного состояния в другое, вызванные вводом (обозначены их символами, нарисованными по краям). Край обычно изображается в виде стрелки, направленной от текущего состояния к следующему состоянию. Это отображение описывает переход состояния, который должен произойти при вводе определенного символа. Математически это записывается как δ : Q × Σ → Q, поэтому δ (функция перехода) в определении FA задается как парой вершин, соединенных ребром, так и символом на ребре на диаграмме, представляющей эту FA. Предмет δ (q, a) = p в определении ФА означает, что от государства, названного q под символом ввода а, переход в состояние п происходит в этой машине. На диаграмме, представляющей этот FA, он представлен ребром, помеченным как а указывающий из вершины, помеченной q в вершину, помеченную п.
  • Начальное состояние q0: (не показано в примерах ниже). Начальное состояние q0 ∈ Q обычно обозначается стрелкой без начала координат, указывающей на состояние. В старых текстах[2][4] начальное состояние не отображается и должно выводиться из текста.
  • Принятие состояния (состояний) F: Если используется, например, для приема автоматов, F ∈ Q является принимающее государство. Обычно его рисуют в виде двойного круга. Иногда состояние принятия функционирует как "Final "(остановка, ловушка) состояния.[3]

Для детерминированный конечный автомат (DFA), недетерминированный конечный автомат (NFA), обобщенный недетерминированный конечный автомат (GNFA) или Машина Мура, вход обозначен на каждом краю. Для Мучная машина, вход и выход обозначены на каждом краю, разделены косой чертой «/»: «1/0» обозначает изменение состояния при встрече с символом «1», вызывающее вывод символа «0». Для Машина Мура вывод состояния обычно записывается внутри круга состояния, также отделенного от обозначения состояния косой чертой «/». Есть также варианты, сочетающие эти два обозначения.

Например, если состояние имеет несколько выходов (например, «a = двигатель против часовой стрелки = 1, b = сигнальная лампа неактивна = 0») диаграмма должна отражать это: например, «q5 / 1,0» обозначает состояние q5 с выходами a = 1, b = 0. Это обозначение будет написано внутри круга государства.

Пример: DFA, NFA, GNFA или Машина Мура

S1 и S2 государства и S1 является принимающее государство или конечное состояние. Каждое ребро помечено входом. В этом примере показан акцептор для двоичных чисел, содержащих четное количество нулей.

DFAexample.svg

Пример: Мучная машина

S0, S1, и S2 состояния. Каждый край помечен знаком "j / k" где j это вход и k это выход.

Диаграмма состояний простой машины Мили

Диаграмма состояний Харела

Диаграмма, показывающая, как диаграммы состояний Харела способствовали развитию объектно-ориентированных методов и обозначений

Диаграммы состояний Харела,[5] изобрел компьютерный ученый Дэвид Харел, получают широкое распространение, так как вариант стал частью Единый язык моделирования (UML).[неосновной источник необходим ] Тип диаграммы позволяет моделировать сверхдержавы, ортогональные области, и деятельность как часть состояния.

Классические диаграммы состояний требуют создания отдельных узлов для каждой допустимой комбинации параметров, определяющих состояние. Это может привести к очень большому количеству узлов и переходов между узлами для всех систем, кроме простейших (взрыв состояний и переходов ). Эта сложность снижает читаемость диаграммы состояний. С помощью диаграмм состояний Harel можно моделировать несколько схем кросс-функциональных состояний внутри диаграммы состояний. Каждый из этих универсальных конечных автоматов может выполнять внутренний переход, не влияя на другие конечные автоматы в диаграмме состояний. Текущее состояние каждого универсального конечного автомата в диаграмме состояний определяет состояние системы. Диаграмма состояний Харела эквивалентна диаграмме состояний, но улучшает читаемость полученной диаграммы.

Альтернативная семантика

Есть и другие наборы семантики, доступные для представления диаграмм состояний. Например, есть инструменты для моделирования и проектирования логики для встроенных контроллеров.[6] Эти диаграммы, как и оригинальные конечные автоматы Хареля,[7] поддерживают иерархически вложенные состояния, ортогональные области, действия состояния и действия перехода.[8]

Диаграммы состояний в сравнении с блок-схемами

Новички в формализме государственной машины часто путают диаграммы состояний с блок-схемы. На рисунке ниже показано сравнение диаграмма состояний с блок-схемой. Конечный автомат (панель (а)) выполняет действия в ответ на явные события. В отличие от этого, блок-схема (панель (b)) не требует явных событий, а скорее переходит от узла к узлу в своем графе автоматически после завершения действий.[9]

Диаграмма состояний (а) и блок-схема (б)

Узлы блок-схем - это ребра в индуцированном графе состояний. Причина в том, что каждый узел в блок-схеме представляет собой программную команду. Программная команда - это действие, которое нужно выполнить. Таким образом, это не состояние, а когда оно применяется к состоянию программы. , это приводит к переходу в другое состояние.

Более подробно, листинг исходного кода представляет собой граф программы. Выполнение графа программы (синтаксический анализ и интерпретация) приводит к графу состояний. Таким образом, каждый граф программы индуцирует граф состояний. Преобразование графа программы в связанный с ним граф состояний называется " разворачивание »графа программы.

Граф программы представляет собой последовательность команд. Если переменных не существует, то состояние состоит только из счетчика программы, который отслеживает, где в программе мы находимся во время выполнения (какая следующая команда будет применена).

В этом случае перед выполнением команды счетчик программы находится в некоторой позиции (состояние до выполнения команды). Выполнение команды перемещает счетчик программы к следующей команде. Поскольку счетчик программы является всем состоянием, из этого следует, что выполнение команды изменили состояние, поэтому сама команда соответствует переходу между двумя состояниями.

Теперь рассмотрим полный случай, когда переменные существуют и на них влияют выполняемые программные команды. Тогда между различными местоположениями счетчика программ не только изменяется счетчик программы, но и переменные могут также изменять значения из-за выполняемых команд. Следовательно, даже если мы повторно посещаем какую-либо команду программы (например, в цикле), это не означает, что программа находится в том же состоянии.

В предыдущем случае программа была бы в том же состоянии, потому что все состояние - это всего лишь счетчик программы, поэтому, если программа указывает на ту же позицию (следующая команда), достаточно указать, что мы находимся в том же состоянии. , если состояние включает переменные, то при изменении значения этих переменных мы можем находиться в одном месте программы с разными значениями переменных, то есть в другом состоянии в пространстве состояний программы. Термин «разворачивание» происходит от этого умножения местоположений при создании граф состояний из графа программы.

Типичным примером является цикл do, увеличивающий некоторый счетчик до тех пор, пока он не переполнится и снова не станет 0. Хотя цикл do выполняет ту же команду увеличения итеративно, поэтому граф программы выполняет цикл, в его пространстве состояний находится не цикл, а строка. Это происходит из-за того, что состояние является местоположением программы (здесь цикл) в сочетании со значением счетчика, которое строго увеличивается (до переполнения), поэтому различные состояния посещаются последовательно, пока не произойдет переполнение. После переполнения счетчик снова становится 0, поэтому начальное состояние повторно посещается в пространстве состояний, закрывая цикл в пространстве состояний (при условии, что счетчик был инициализирован на 0).

На рисунке выше предпринята попытка показать эту смену ролей путем совмещения дуг диаграмм состояний с этапами обработки блок-схемы.

Вы можете сравнить блок-схему со сборочной линией на производстве, потому что блок-схема описывает прогрессирование некоторой задачи от начала до конца (например, преобразование входного исходного кода в выходной код объектного кода компилятором). Конечный автомат обычно не имеет представления о таком прогрессе. Конечный автомат двери, показанный в верхней части этой статьи, например, не находится на более продвинутой стадии, когда он находится в состоянии «закрыто», по сравнению с состоянием «открыто»; он просто по-разному реагирует на события открытия / закрытия. Состояние в конечном автомате - это эффективный способ определения определенного поведения, а не этап обработки.

Прочие расширения

Интересным расширением является разрешение дугам переходить из любого количества состояний в любое количество состояний. Это имеет смысл только в том случае, если системе разрешено находиться в нескольких состояниях одновременно, что подразумевает, что отдельное состояние описывает только условие или другой частичный аспект общего глобального состояния. Полученный формализм известен как Сеть Петри.

Другое расширение позволяет интегрировать блок-схемы в диаграммы состояний Harel. Это расширение поддерживает разработку программного обеспечения, управляемого событиями и рабочими процессами.

Смотрите также

Рекомендации

  1. ^ Индекс архива на Wayback Machine
  2. ^ а б Тейлор Бут (1967) Последовательные машины и теория автоматов, Джон Уайли и сыновья, Нью-Йорк.
  3. ^ а б Джон Хопкрофт и Джеффри Уллман (1979) Введение в теорию автоматов, языки и вычисления, Издательство Addison-Wesley Publishing Company, Reading Mass, ISBN  0-201-02988-X
  4. ^ Эдвард Дж. МакКласки, Введение в теорию коммутационных цепей, McGraw-Hill, 1965.
  5. ^ Дэвид Харел, Диаграммы состояний: визуальный формализм для сложных систем. Наука компьютерного программирования, 8 (3): 231–274, июнь 1987 г.
  6. ^ Тивари, А. (2002). Формальная семантика и методы анализа для Simulink Stateflow.
  7. ^ Харел, Д. (1987). Визуальный формализм для сложных систем. Наука компьютерного программирования, 231–274.
  8. ^ Алур, Р., Канаде, А., Рамеш, С., и Шашидхар, К. С. (2008). Символьный анализ для улучшения покрытия симуляцией моделей Simulink / Stateflow. Международная конференция по встроенному программному обеспечению (стр. 89–98). Атланта, Джорджия: ACM.
  9. ^ Самек, Миро (2008). Практические диаграммы состояний UML на C / C ++, второе издание: событийно-ориентированное программирование для встроенных систем. Newnes. п. 728. ISBN  978-0-7506-8706-5.

внешняя ссылка