Из Википедии, свободной энциклопедии
  (Перенаправлено из графа состояний )
Перейти к навигации Перейти к поиску

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

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

Обзор [ править ]

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

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

Направленный график [ править ]

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

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

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

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

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

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

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

Пример: DFA, NFA, GNFA или машина Мура [ править ]

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

Пример: машина Мили [ править ]

S 0 , S 1 и S 2 - состояния. Каждое ребро помечено « j / k », где j - вход, а k - выход.

Диаграмма состояний Харела [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Другие расширения [ править ]

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

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

См. Также [ править ]

  • Дэвид Харел
  • ДРАКОН
  • SCXML - язык XML, который обеспечивает общую среду выполнения на основе конечного автомата, основанную на диаграммах состояний Харела.
  • Конечный автомат UML
  • YAKINDU Statechart Tools - это программное обеспечение для моделирования диаграмм состояний (диаграммы состояний Харела, машины Мили, машины Мура), моделирования и генерации исходного кода.

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Введение в диаграммы конечных автоматов UML 2 , Скотт У. Амблер
  • Рекомендации по диаграммам конечных автоматов UML 2 , Скотт В. Амблер
  • Intelliwizard - UML StateWizard - похожий на ClassWizard фреймворк для динамического моделирования / разработки UML и инструмент, работающий в популярных IDE под лицензией с открытым исходным кодом.
  • YAKINDU Statechart Tools - инструмент с открытым исходным кодом для спецификации и разработки реактивных, управляемых событиями систем с помощью конечных автоматов .
  • Понимание и использование государственных машин MATLAB Tech Talks о государственных машинах
  • FSM: Генерация конечных автоматов с открытым исходным кодом на Java от Александра Сахарова FSM
  • scxmlcc Эффективный конечный автомат scxml для компилятора C ++.
  • SMC: компилятор конечного автомата с открытым исходным кодом, который генерирует FSM для многих языков, таких как C, Python, Lua, Scala, PHP, Java, VB и т. Д. SMC
  • Диаграмма состояний - бесплатная библиотека C ++ с открытым исходным кодом, которая поддерживает определение и выполнение конечных автоматов, содержащих иерархию и параллелизм.