Для чего предназначены диаграммы конечных автоматов

8) Конечный автомат Диаграмма UML

ГОСУДАРСТВЕННАЯ ДИАГРАММА используется для захвата поведения программной системы. Диаграммы конечного автомата UML можно использовать для моделирования поведения класса, подсистемы, пакета или даже всей системы. Она также называется диаграммой состояний или переходов между состояниями.

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

Диаграммы диаграмм состояний используются для описания различных состояний объекта в прикладной системе.

Всего существует два типа диаграмм состояний:

1. Поведенческий государственный автомат

• Он фиксирует поведение сущности, присутствующей в системе.
• Он используется для представления конкретной реализации элемента.
• Поведение системы может быть смоделировано с использованием диаграмм состояния машин поведения.

1. Протокол конечного автомата

• Эти диаграммы используются для захвата поведения протокола.
• Это представляет, как состояние протокола изменяется относительно события. Это также представляет соответствующие изменения в системе.
• Они не представляют конкретную реализацию элемента.

В этом уроке UML вы узнаете,

• Почему State Machine Diagram?
• Обозначение и символ для конечного автомата
• Типы государства
• Как нарисовать диаграмму Statechart?
• Когда использовать диаграммы состояний?
• Пример конечного автомата
• Конечный автомат против блок-схемы

Почему State Machine Diagram?

Диаграмма диаграммы состояний используется для отображения динамического аспекта системы. Диаграммы конечного автомата используются для представления поведения приложения. Объект проходит через различные состояния в течение своей жизни. Продолжительность жизни объекта сохраняется до завершения программы. Объект выходит из нескольких состояний в зависимости от события, которое происходит внутри объекта. Каждое состояние представляет собой уникальную информацию об объекте.

Диаграммы диаграммы состояний используются для разработки интерактивных систем, которые реагируют на внутренние или внешние события. Диаграмма диаграммы состояний визуализирует поток выполнения из одного состояния в другое состояние объекта.

Он представляет состояние объекта от создания объекта до его уничтожения или прекращения.

Основная цель диаграммы диаграммы состояний – моделировать интерактивные системы и определять каждое состояние объекта. Диаграммы диаграмм состояний предназначены для отображения динамического поведения системы приложений. Эти диаграммы используются для представления различных состояний системы и объектов внутри системы.

Обозначение и символ для конечного автомата

Ниже приведены различные обозначения, которые используются на диаграмме диаграммы состояний. Все эти обозначения, когда объединены, составляют единую диаграмму.

Начальное состояние

Символ начального состояния используется для обозначения начала диаграммы конечного автомата.

Конечное состояние

Этот символ используется для обозначения конца диаграммы конечного автомата.

Окно решений

Содержит условие. В зависимости от результата оцениваемого защитного условия для выполнения программы выбирается новый путь.

переход

Переход – это изменение одного состояния в другое, которое происходит из-за какого-либо события. Переход вызывает изменение состояния объекта.

Государственная коробка

Это определенный момент в жизни объекта. Он определяется с использованием некоторого условия или оператора в теле классификатора. Он используется для представления любых статических и динамических ситуаций.

Обозначается прямоугольником с закругленными углами. Название государства написано внутри скругленного прямоугольника.

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

Состояние может быть активным или неактивным. Когда состояние находится в рабочем режиме, оно активно, как только оно прекращает выполнение и переходит в другое состояние, предыдущее состояние становится неактивным, а текущее состояние становится активным.

Типы государства

Unified Modeling Language определяет три типа состояний:

• Простое состояние
  • Они не имеют субстрата.
  • Эти типы состояний могут иметь один или несколько субстратов.
  • Составное состояние с двумя или более подсостояниями называется ортогональным состоянием.
  • Эти состояния семантически равны составным состояниям.
  • В отличие от составного состояния, мы можем повторно использовать состояния автомата.

  Как нарисовать диаграмму Statechart?

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

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

  Следующие правила должны быть учтены при построении диаграммы состояния диаграммы:

  1. Имя перехода состояния должно быть уникальным.
  2. Название государства должно быть легко понятным и описывать поведение государства.
  3. Если имеется несколько объектов, то должны быть реализованы только основные объекты.
  4. Собственные имена для каждого перехода и события должны быть даны.

  Когда использовать диаграммы состояний?

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

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

  Используются графики состояния,

  1. Для моделирования объектов системы.
  2. Моделировать и внедрять интерактивные системы.
  3. Для отображения событий, которые вызывают изменения в состояниях.

  Пример конечного автомата

  Следующая диаграмма состояний представляет процесс аутентификации пользователя.

  

  Всего существует два состояния, и первое состояние указывает, что OTP должен быть введен первым. После этого в окне принятия решений отмечается OTP, если оно верное, тогда произойдет только переход состояния, и пользователь будет проверен. Если OTP неверен, то переход не произойдет, и он снова вернется в начальное состояние, пока пользователь не введет правильный OTP.

  Конечный автомат против блок-схемы

  Государственный аппарат	блок-схема
  Он представляет различные состояния системы.	Блок-схема иллюстрирует поток выполнения программы.
  Конечный автомат имеет концепцию WAIT, т. Е. Ожидание действия или события.	Блок-схема не имеет дело с ожиданием концепции.
  Конечные автоматы используются для работающей системы.	Блок-схема визуализирует последовательности ветвления системы.
  Конечный автомат представляет собой диаграмму моделирования.	Блок-схема представляет собой поток последовательности или диаграмму DFD.
  Конечный автомат может исследовать различные состояния системы.	Блок-схема имеет дело с путями и потоком управления.

  Резюме

  • Диаграммы диаграммы состояний также называются диаграммами конечных автоматов.
  • Эти диаграммы используются для моделирования системы, основанной на событиях.
  • Состояние объекта контролируется с помощью события.
  • Существует всего два типа диаграмм конечного автомата: 1) Поведенческий 2) Конечный автомат 3) Протокол конечного автомата
  • Диаграмма диаграммы состояний используется для отображения динамического аспекта системы.
  • Состояние – это определенный момент в продолжительности жизни объекта.

  Для чего предназначены диаграммы конечных автоматов

  На этом шаге рассмотрим термины и понятия конечных автоматов в UML.

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

  Автоматы используются для моделирования динамических аспектов поведения системы. Большей частью этот процесс подразумевает спецификацию жизненного цикла экземпляров класса, варианта использования или системы в целом. Эти экземпляры могут реагировать на такие события, как сигналы, операции либо истечение некоего периода времени. Когда происходит событие, в зависимости от текущего состояния объекта наблюдается некоторый эффект. Эффект – это спецификация поведения, реализуемого внутри автомата. В конечном счете эффекты проявляют себя в выполнении действий, изменяющих состояние объекта или возвращающих какое-либо значение. Состояние объекта – это период времени, в течение которого он удовлетворяет заданным условиям, выполняет некую деятельность или ожидает определенного события.

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

  Хорошо структурированные автоматы подобны хорошо структурированным алгоритмам: они эффективны, просты, адаптируемы и понятны.

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

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

  Динамические аспекты системы в UML моделируются конечными автоматами (state machines). В то время как взаимодействие моделирует сообщество объектов, совместно работающих для выполнения некоторых действий, автомат моделирует жизненный цикл отдельного объекта – будь то экземпляр класса, варианта использования или даже всей системы. За время жизненного цикла в объекте может происходить множество разнообразных событий, таких как передача и прием сигналов, вызовы операций, создание и уничтожение объекта, истечение периодов времени, отведенного на некое действие, либо изменение каких-то условий. В ответ на эти события объект выполняет определенное действие, представляющее собой вычисление, а затем изменяет свое состояние на другое. Поэтому поведение такого объекта зависит от прошлого, по крайней мере в той степени, в которой оно влияет на его текущее состояние. Объект может принять событие, ответить на него действием, затем изменить свое состояние. Когда же он принимает другое событие, его реакция может быть другой – в зависимости от текущего состояния, которое является результатом предыдущего события.

  Автоматы используются для моделирования поведения любого элемента – чаще всего класса, варианта использования или всей системы. Автоматы могут быть визуализированы на диаграммах состояний. Вы можете сосредоточиться на поведении объекта, зависящем от последовательности событий, что особенно удобно для моделирования реактивных систем.

  Графическое представление состояний, переходов, событий и эффектов в UML продемонстрировано на рис. 1. Эта нотация позволяет показать поведение объекта таким образом, чтобы выделить важные элементы его жизненного цикла.

  Приведем определение основных терминов и понятий.

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

  Состояние – ситуация во время жизни объекта, в которой он удовлетворяет заданным условиям, осуществляет некую деятельность либо пребывает в ожидании событий.

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

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

  Деятельность (activity) – происходящий в данный момент неатомарный процесс внутри автомата.

  Действие (action) – исполняемое вычисление, в результате которого изменяется состояние модели или возвращается некоторое значение. Изображается в виде прямоугольника с закругленными углами.

  На следующем шаге рассмотрим определение состояния автомата объекта в UML.

  53. Диаграмма конечного автомата: псевдосостояния, их виды и применение

  Псевдосостояния (pseudo state)- абстрактный элемент модели, который включает в себя различные типы вспомогательных вершин в графе конечного автомата Начальное псевдосостояние (initial pseudo state) представляет вершину графа конечного автомата, которая по умолчанию является состоянием источником для начального перехода моделируемого поведения Узел завершения (terminate node) является псевдосостоянием, вход в который означает завершение выполнения поведения конечного автомата в контексте его объекта Финальное состояние (final state) – специальный вид состояния, предназначенное для моделирования завершения конечного автомата или региона, в котором оно содержится. Выбор и соединение Псевдосостояние выбора (choice pseudo state) предназначено для моделирования нескольких альтернативных ветвей при реализации поведения конечного автомата Псевдосостояние соединения (junction pseudo state) является вершиной со свободной семантикой, которая используется для соединения вместе нескольких переходов Разделение и слияние Вершина разделения (fork vertex) – псевдосостояние, предназначенное для разделения входящего перехода на два или более перехода, которые имеют в качестве своих целей вершины в ортогональных регионах композитного состояния. Вершина слияния (join vertex) – псевдосостояние, предназначенное для соединения нескольких переходов, которые имеют в качестве своих источников вершины из различных ортогональных регионов композитного состояния. Точки входа и выхода Точка входа (entry point) – псевдосостояние, предназначенное для моделирования входа в некоторый конечный автомат или композитное состояние Точка выхода (exit point) – псевдосостояние, предназначенное для моделирования выхода из некоторого конечного автомата или композитного состояния Псевдосостояние неглубокой истории (shallow pseudo state) Псевдосостояние неглубокой истории (shallow pseudo state) предназначено для представления самого последнего активного подсостояния композитного состояния после выхода из него. Псевдосостояние глубокой истории (deep pseudo state) Псевдосостояние глубокой истории (deep pseudo state) предназначено для представления последней активной конфигурации композитного состояния после выхода из него.

  54. Протокольные конечный автомат: назначение, элементы и принципы построения

  • для протокольных конечных автоматов не существуют отдельные характеристики конечного автомата поведения (entry, do, exit);
  • состояния в протокольных конечных автоматах могут иметь некоторый инвариант.
  • протокольный конечный автомат может иметь только контекст классификатора, но не контекст характеристики поведения;
  • все переходы протокольного конечного автомата должны быть протокольными переходами;
  • состояния протокольного конечного автомата не могут иметь действий входа, выхода или выполнения;
  • протокольные конечные автоматы не могут иметь псевдосостояния глубокой или неглубокой истории.

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

  

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

  4. Моделирование поведения

  При создании программной системы недостаточно ответить на вопросы что делает система? ( глава 2) и из чего она состоит? (глава 3) — требуется ответить на вопрос как работает система?. Ответ на этот вопрос дает модель поведения. Поведение реальной программы целиком и полностью определяется ее кодом — как программа составлена, так она и выполняется (с точностью до сбоев) — «от себя» компьютер ничего не придумывает. Но программа — это просто запись алгоритма. Таким образом, мы приходим к следующему определению.

  Модель поведения (behavior model) ‒ это описание алгоритма работы системы.

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

  Средства моделирования поведения в UML, ввиду разнообразия областей применения языка, должны удовлетворять набору различных и частично противоречивых требований. Перечислим некоторые из них.

  • Модель должна быть достаточно детальной для того, чтобы послужить основой для составления компьютерной программы — компьютер не сможет самостоятельно «додумать» опущенные детали.
  • Модель должна быть компактной и обозримой, чтобы служить средством общения между людьми в процессе разработки системы и для обмена идеями.
  • Модель не должна зависеть от особенностей реализации конкретных компьютеров, средств программирования и технологий, чтобы не сужать область применения языка UML.
  • Средства моделирования поведения в UML должны быть знакомыми и привычными для большинства пользователей языка и не должны противоречить требованиям наиболее ходовых парадигм программирования.

  Удовлетворить сразу всем требованиям в полной мере, видимо, практически невозможно — средства моделирования поведения UML являются результатом многочисленных компромиссов. Многие авторы критикуют UML за то, что он недостаточно хорош с точки зрения того или иного конкретного критерия ∇ . Но если принять во внимание сразу все противоречивые требования, то, по нашему мнению, следует признать, что на сегодняшний день UML является решением, очень близким к оптимальному. В будущем, по мере развития теории и практики программирования, будет эволюционировать и UML — для этого в языке предусмотрены все необходимые средства.

  ∇ Мы тоже по ходу дела стараемся отмечать слабые, по нашему мнению, конструкции UML.

  Описание средств моделирования поведения в UML мы начнем с небольшого отступления на тему одного из разделов дискретной математики — теории автоматов — который послужил теоретической основой средств моделирования поведения в UML.

  4.1.1. Конечные автоматы

  Конечным автоматом (Мили) называется совокупность пяти объектов:

  • конечного множества \(A=\\), называемого входным алфавитом; элементы множества \(A\) называются входными символами, сигналами, событиями, стимулами или воздействиями;
  • конечного множества \(Q=\\), называемого алфавитом состояний; элементы множества \(Q\) называются состояниями;
  • конечного множества \(B=\\), называемого выходным алфавитом; элементы множества \(B\) называются выходными символами, реакциями или воздействиями;
  • тотальной (всюду определенной) функции \(\delta : A \times Q \to Q\), называемой функцией переходов;
  • тотальной функции \(\lambda : A \times Q \to B\), называемой функцией выходов.

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

  Автоматное преобразование. Пусть задан автомат \(S\), некоторое состояние \(q\) из алфавита \(Q\) этого автомата и входное слово \(\alpha\) в алфавите \(A\). По этой информации однозначно определяется выходное слово \(\beta\) в алфавите \(B\). А именно, по состоянию \(q\) и первому символу слова \(\alpha\) с помощью функции выходов \(\lambda\) определяется первый символ слова \(\beta\) и с помощью функции переходов \(\delta\) определяется следующее состояние автомата. Затем по новому состоянию и второму символу входного слова \(\alpha\) определяется второй символ выходного слова \(\beta\) и следующее состояние. И так далее. Поскольку функции \(\lambda\) и \(\delta\) тотальны, автомат \(S\) и состояние \(q\) определяют некоторый алгоритм преобразования слов в алфавите \(A\) в слова в алфавите \(B\).

  Преобразование слов в алфавите \(A\) в слова алфавите \(B\) с помощью автомата \(S\) называется автоматным преобразованием и обычно обозначается той же буквой \(S\), что и автомат.

  Автоматные преобразования обладают рядом полезных свойств, в частности:

  • автоматное преобразование сохраняет длину, то есть результат преобразования состоит из такого же числа символов, что и аргумент, \(\mid\alpha\mid = \mid S(\alpha)\mid\);
  • автоматное преобразование обладает свойством префикса ∇ , \(S(\alpha + \beta) = S(\alpha) + S(\beta)\), где \(+\) — операция конкатенации (сцепления строк).

  ∇ Другими словами, автоматное преобразование является гомоморфизмом, «уважающим» конкатенацию.

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

  Реактивные системы. Конечный автомат можно интерпретировать и другим образом, а именно, можно считать, что элементы множества \(A\) — это стимулы (события), а элементы множества \(B\) — это реакции (обработчики событий). В таком случае, если задан автомат \(S\) и некоторое состояние \(q\) этого автомата, то описано автоматное поведение, то есть последовательность (возможно, бесконечная) пар «стимул — реакция».

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

  Машина Тьюринга. Одна из самых популярных моделей вычислимости — машина Тьюринга — фактически является расширением модели конечного автомата, в которой допускается чтение и запись информации в потенциально бесконечную память.

  В настоящее время общепринятым является тезис Чёрча–Тьюринга — фундаментальное утверждение, высказанное Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов. В самой общей форме оно гласит, что любая интуитивно вычислимая функция может быть вычислена некоторой машиной Тьюринга, и таким образом, понятие машины Тьюринга равнообъемно понятию алгоритма.

  Таким образом, оказывается, что класс алгоритмов, которые можно описать автоматом, весьма широк, хотя и не всеобъемлющ ∇ .

  ∇ Подсказка для заинтригованного читателя: конечные автоматы не позволяют описать, например, такое поведение, которое может включать потенциально бесконечное число шагов, и при этом очередной шаг зависит от всех предшествующих шагов. Конечный автомат потому и называется конечным, что может «помнить» только конечное число шагов — не больше, чем число состояний в автомате. Машину Тьюринга «выручает» бесконечная лента — на ней можно запомнить все, что нужно.

  Обычно при применении конечных автоматов используют некоторые дополнительные соглашения, которые не меняют сути дела и принимаются для удобства.

  Во-первых, сразу выделяют одно состояние, которое считается начальным (обычно ему дают номер 0 или 1 ).

  Автомат с выделенным начальным состоянием называется инициальным.

  Инициальный автомат всегда начинает работу в одном и том же состоянии, поэтому специально это состояние указывать не нужно.

  Во-вторых, можно рассмотреть случай, когда функция выходов \(\lambda\) имеет только один параметр — состояние — и выходной символ зависит только от состояния и не зависит от входного символа.

  Автомат называется автоматом Мура, если функция выходов зависит только от состояния. В этом случае данная функция обычно обозначается \(\mu : Q \to B\) и называется функцией пометок.

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

  В-третьих, иногда выделяют одно или несколько состояний, которые называются заключительными. Если автомат переходит в заключительное состояние, то работа автомата завершается — он больше не реагирует на события и не выдает выходных символов, хотя, быть может ещё остались необработанные входные символы. Заключительное состояние не является полноценным состоянием, поскольку для него не имеет смысла определять функции переходов и выходов, поэтому заключительное состояние считают псевдосостоянием.

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

  Три перечисленных выше соглашения используются в UML. Однако этим не исчерпывается список возможных модификаций конечных автоматов. Мы перечислим некоторые, в том числе достаточно экстравагантные, хотя они и не применяются в UML.

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

  ∇ Распространен предрассудок, что конечные автоматы применяются только для синтаксического анализа. Это не так. Действительно, первые результаты и первые применения теории автоматов были получены именно в синтаксическом анализе. Но потом появились другие результаты и другие области применения.

  Вторая модификация состоит в том, чтобы рассматривать сети взаимодействующих конечных автоматов. Идея состоит в том, чтобы из элементарных автоматов строить более сложные конструкции. Элементарными можно считать автоматы, имеющие одно состояние.

  Автомат, имеющий одно состояние, называется комбинационным.

  Ясно, что в комбинационном автомате функция переходов тривиальна, и фактически комбинационный автомат$nbsp;— это просто функция, которая сопоставляет входному символу выходной.

  ∇ Напомним, что исходя из определения, данного в начале этого параграфа, конечный автомат имеет конечное число состояний.

  Рис. Сеть интерпретатора конечного автомата

  Впрочем, верно и обратное утверждение: для любой сети можно построить эквивалентный конечный автомат.

  ∇ Эти модификации относятся к классу экстравагантных и редко реализуются на практике, возможно, потому, что к ним еще не привыкли.

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

  Если отношение перехода \(\delta\) является многозначным, \(\delta : A \times Q \to 2^Q\), то автомат называется недетерминированным.

  Недетерминированный ∇ автомат на каждом такте своей работы находится в одном или одновременно в нескольких состояниях. На первый взгляд такая конструкция кажется неустойчивой и даже невозможной, но это впечатление обманчиво. Теорема детерминизации утверждает, что для любого недетерминированного конечного автомата существует эквивалентный ему детерминированный. Идея конструктивного доказательства этой теоремы проясняет ситуацию. Пусть дан недетерминированный автомат с множеством состояний \(Q\) . Рассмотрим детерминированный автомат с множеством состояний \(2^Q\), т.е. новое множество состояний — это множество всех подмножеств исходного. Остается только заменить многозначные переходы из одного подмножества старых состояний в другое подмножество однозначными переходами из одного нового состояния в другое. Отсюда видно, что недетерминированное описание поведения может быть экспоненциально короче детерминированного описания того же самого поведения.

  ∇ Недетермированность часто путают со случайностью или неопределенностью, и пугаются этого слова. Напрасно. В данном контексте в недетерминированном поведении нет ничего случайного или неопределенного.

  4.1.2. Применение автоматов

  Количество рассмотренных (и детально исследованных!) вариаций на тему конечных автоматов весьма велико — их обзор не является предметом данной книги. Нас интересует, почему теория конечных автоматов была использована авторами UML в качестве средства моделирования поведения. По нашему мнению, основных причин три:

  • теоретическая;
  • историческая;
  • практическая.

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

  • проблема эквивалентности: имеются две записи алгоритмов. Вычисляют ли они одну и ту же функцию или нет?
  • проблема остановки: имеется запись алгоритма. Завершает ли этот алгоритм свою работу при любых исходных данных или нет?

  Этот список можно продолжать неограниченно: первое слово в теореме Райса — «все». Значит ли это, что вообще все неразрешимо и про алгоритмы ничего нельзя узнать? Разумеется, нет. Если дана конкретная запись алгоритма, то путем ее индивидуального изучения, скорее всего, можно установить наличие или отсутствие нужных свойств. Речь идет о том, что невозможен единый метод, пригодный для всех случаев.

  Обратите внимание, что теорема Райса справедлива в случае использования любой, но универсальной модели вычислимости (способа записи алгоритмов). Если же используется не универсальная модель вычислимости, то теорема Райса не имеет места. Другими словами, существуют подклассы алгоритмов, для которых некоторые важные свойства оказываются алгоритмически разрешимыми. Конечные автоматы являются одним из важнейших таких подклассов. С одной стороны, данный формализм оказывается достаточно богатым, чтобы выразить многие практически нужные алгоритмы (примеры см. ниже), с другой стороны, целый ряд свойств автоматов можно проверить автоматически, причем найдены весьма эффективные алгоритмы. В частности, проблемы эквивалентности и остановки для автоматов эффективно разрешимы. В случае использования универсального языка программирования мы не можем автоматически убедиться в правильности программы: нам остается только упорно тестировать ее в смутной надежде повысить свою уверенность в надежности программы. В случае же использования конечных автоматов многое можно сделать автоматически, надежно и математически строго — поэтому теория конечных автоматов столь интересна для разработки программных систем.

  Историческая причина популярности конечных автоматов состоит в том, что данная техника развивается уже достаточно давно и теоретические результаты были с успехом использованы при решении многих практических задач. В частности, системы проектирования, спецификации и программирования, основанные на конечных автоматах и их модификациях, активно развиваются и применяются уже едва ли не полвека. Особенно часто конечные автоматы применяются в конкретных предметных областях, где можно обойтись без использования универсальных моделей вычислимости. В результате очень многие пользователи, инженеры и программисты хорошо знакомы с конечными автоматами и применяют их без затруднений. Мы не готовы дать исчерпывающий обзор предметных областей, где применяются конечные автоматы, и ограничимся одним достаточно показательным примером. В области телекоммуникаций уже более 15 лет активно применяется промышленный стандарт — язык спецификации и описания алгоритмов SDL (Specification and Description Language).

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

  Первый способ — табличный. Автомат записывается в форме таблицы, столбцы которой помечены символами входного алфавита, строки помечены символами алфавита состояний, а в ячейках таблицы записаны соответствующие значения функций \(\delta\) и \(\lambda\). Рассмотрим пример, речь в котором пойдет об автомате, который вычисляет натуральное число, следующее по порядку за данным, по представлению данного числа в позиционной двоичной системе счисления. Входной и выходной алфавиты состоят из символов 0 , 1 и s (пробел). Для упрощения примера будем считать, что двоичные цифры записи числа поступают на вход автомата в обратном порядке — справа налево, то есть первым поступает младший разряд. Автомат имеет три состояния, которые для ясности мы назовем «начальное», «перенос» и «копирование». Пусть на вход конечного автомата, заданного таблицей, расположенной ниже, поступает число 1101 , а результат, который мы должны получить – 1110 , т.е. натуральное число, следующее за исходным.

  Ниже приведена таблица соответствующего конечного автомата.

  Табл. Таблица конечного автомата

  0	1	s
  начальное	копирование, 1	перенос, 0	начальное, s
  перенос	копирование, 1	перенос, 0	начальное, 1
  копирование	копирование, 0	копирование, 1	начальное, s

  На вход автомата символы поступают в обратном порядке, т.е. сначала 1 , затем 0 , 1 и 0 . Изначально автомат находится в состоянии «начальное» и при поступлении первого входного символа 1 переходит в состояние «перенос», передавая на выход 0 (первая строка, третий столбец). Далее на вход поступает 0 и автомат из состояния «перенос» переходит в состояние «копирование» (вторая строка, второй столбец). Обработку двух последних входных символов оставим в качестве упражнения для читателя.

  Второй способ — графический. Автомат изображается в виде диаграммы ориентированного графа, узлы которого соответствуют состояниям и помечены символами алфавита состояний, а дуги называются переходами и помечены символами входного и выходного алфавита следующим образом. Допустим, \(\delta(a_i, q_j)=q_u\), \(\lambda(a_i, q_j)=b_v\). Тогда проводится дуга из узла \(q_j\) в узел \(q_u\) и помечается символами \(a_i, b_v\). Такой граф называется диаграммой состояний-переходов. На следующем рисунке приведена диаграмма графа состояний-переходов для примера, заданного предыдущей таблицей.

  Рис. Диаграмма состояний-переходов

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

  В процессе применения в программировании автоматная техника обогатилась рядом приемов, которые не совсем укладываются в исходную математическую модель, но очень удобны на практике. Например, помимо функций переходов и выходов, можно включить в описание автомата еще одну составляющую — процедуру реакции. Смысл добавления состоит в следующем: при выполнении перехода из одного состояния в другое вызывается соответствующая процедура реакции, которая выполняет еще какие-то действия (имеет побочный эффект, см. параграф 3.2.4), помимо вывода выходного символа и смены состояния. Если процедура реакции ничем не ограничена, например, может читать и писать в потенциально бесконечную память, то конечный автомат превращается, фактически, в универсальную модель вычислимости подобную машине Тьюринга. При этом, разумеется, утрачиваются теоретически привлекательные свойства разрешимости, однако программировать с помощью процедур реакции очень удобно. Разработаны и различные промежуточные варианты: например, если побочный эффект процедур реакции ограничен работой со стеком, то получается так называемый магазинный автомат. Магазинные автоматы позволяют запрограммировать существенно более широкий класс алгоритмов и в то же время сохраняют некоторые из важнейших теоретических преимуществ.

  Наконец, важным практическим обстоятельством является тот факт, что автоматы очень легко программируются средствами обычных языков программирования. Например, пусть нужно запрограммировать работу автомата с состояниями 1, 2, …, k , где 1 — начальное состояние и k — заключительное состояние, а входные стимулы: A, B, … Z можно получить с помощью функции get() . В таком случае можно использовать код следующей структуры:

  state := 1 while state ≠ k stimulus := get() switch state case 1 switch stimulus case A // какие-то действия state := s // новое состояние case B . . . end switch stimulus . . . end switch state end while

  Мы закончим этот параграф небольшим примером из информационной системы отдела кадров.

  ИЗМЕНЕНИЯ В ТЕХНИЧЕСКОМ ЗАДАНИИ После приема на работу соискатель становится штатным сотрудником. Штатный сотрудник может быть переведен с одной должности на другую. Штатный сотрудник может быть уволен.

  Итак, сотрудник в организации, очевидно, может находиться в различных состояниях: вначале он является кандидатом, в результате выполнения операции приема на работу он становится штатным сотрудником. При переводе с одной должности на другую сотрудник остается в штате. И, наконец, сотрудник может быть уволен. Жизненный цикл сотрудника естественно описать конечным автоматом, например, в виде таблицы, в которой строки поименованы состояниями, столбцы — стимулами, а в ячейках выписаны процедура реакции и новое состояние.

  Табл. Жизненный цикл сотрудника

  Принять hire()	Перевести move()	Уволить fire()
  Кандидат Applicant	Принять(), В штате	Ошибка(), Кандидат	Ошибка(), Кандидат
  В штате Employed	Ошибка(), В штате	Перевести(), В штате	Уволить(), Уволен
  Уволен Unemployed	Принять(), В штате	Ошибка(), Уволен	Ошибка(), Уволен

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

  Рис. Жизненный цикл сотрудника в ИС ОК

  Обратите внимание, что диаграмма на данном рисунке содержит меньше информации по сравнению с соответствующей таблицей.

  4.1.3. Сети Петри

  Предыдущие два параграфа могут создать впечатление, что конечные автоматы — единственный теоретический механизм, который используется для моделирования поведения. Это не совсем так. Конечные автоматы и их многочисленные модификации действительно используются чаще всего, но есть и другие формализмы, которые также применяются на практике, в том числе и в UML.

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

  Известно множество различных модификаций сетей Петри, предложенных для решения конкретных задач. Мы рассмотрим самый простой вариант. В этом варианте сеть Петри определяется как ориентированный двудольный граф, имеющий вершины двух видов, которые называются позиции и переходы. На диаграмме позиции обычно изображаются в виде небольших кружков, а переходы в виде горизонтальных черточек. Для сети Петри определяется понятие маркировки, которая сопоставляет каждой позиции неотрицательное целое число. На диаграмме маркировка обозначается с помощью маленьких черных кружков, которые помещаются внутрь позиций. Разные авторы называют эти кружки по-разному: точки, маркеры, отметки, ярлыки, фишки и т. п. У каждого перехода в сети Петри есть некоторое количество (может быть ноль) входных позиций (из которых дуги ведут в переход) и некоторое количество (может быть ноль) выходных позиций (в которые дуги ведут из перехода). Переход в сети Петри называется разрешенным, если все его входные позиции не пусты (т. е. их маркировка строго больше нуля). Любой разрешенный переход может сработать. В результате срабатывания перехода маркировка всех входных позиций уменьшается на 1 , а маркировка всех выходных позиций увеличивается на 1 . На диаграмме количество маркеров во входных позициях уменьшается, а в выходных — увеличивается. В результате срабатывания перехода маркировка сети Петри изменяется: некоторые переходы могут стать разрешенными или, наоборот, перестать быть таковыми.

  Сеть Петри является удобным формализмом для описания поведения, в особенности асинхронного, параллельного и недетерминированного. Рассмотрим, например, простую вычислительную систему (процессор), последовательно обрабатывающую задания, которые поступают во входную очередь. Когда процессор свободен и во входной очереди имеется задание, оно обрабатывается процессором, а затем выводится в выходную очередь. На следующем рисунке приведена сеть Петри, моделирующая эту систему. Если в условиях начальной маркировки, показанной слева, сработают переходы \(t_1, t_2, t_1, t_1\), то сеть будет иметь маркировку, показанную на рисунке справа. Обратите внимания, что срабатывание переходов \(t_1, t_1, t_2, t_1\) или \(t_1, t_1, t_1, t_2\) даст тот же самый результат, а срабатывание переходов \(t_2, t_1, t_1, t_1\) невозможно, потому что переход \(t_2\) не разрешен в начальной маркировке.

  Рис. Сеть Петри

  По сравнению с конечными автоматами сети Петри обладают рядом особенностей, которые объясняют их широкое применение для моделирования параллелизма. Прежде всего, сети Петри асинхронны — в них отсутствует понятие времени. Время срабатывания и относительный порядок срабатывания разрешенных переходов никак не указываются. Тем не менее, сама структура сети позволяет в некоторых случаях отвечать на важнейший вопрос: какими свойствами будет обладать маркировка, получаемая в результате произвольной последовательности срабатываний переходов. Например, нетрудно доказать, что позиция \(p_2\) никогда не будет иметь маркировку больше 1 (что, очевидно, имеет явный практический смысл — процессор может обрабатывать только одно задание). Далее, в сетях Петри очень наглядно и четко моделируется параллелизм (переходы, входные позиции которых не пересекаются, параллельны), конфликты (переходы, входные позиции которых пересекаются, конфликтуют), тупики (переходы, которые не разрешены в данной маркировке и всех достижимых из нее) и т. д. Наконец, теория сетей Петри за последние десятилетия была разработана достаточно глубоко и детально, чтобы давать ответы на многие трудные вопросы практического параллельного программирования.

  Основной механизм сетей Петри дает повод упомянуть одну важную теоретическую идею, которая хотя и не образует отдельного формализма, но иногда бывает очень полезна для моделирования поведения как в UML, так и в других случаях. Заметим, что переход в сети Петри может сработать, если все его входные позиции не пусты — в них что-то есть. Никто снаружи «не подталкивает» переход к срабатыванию — переход «сам» определяет, что есть условия для его срабатывания.

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

  ∇ Еще нужно не забыть передать аргументы!

  4.1.4. Средства моделирования поведения

  В UML предусмотрено несколько различных средств для описания поведения. Выбор того или иного средства диктуется типом поведения, которое нужно описать.

  Мы разделили все средства моделирования поведения в UML на четыре группы

  • описание поведения с явным выделением состояний;
  • описание поведения с явным выделением потоков данных и управления;
  • описание поведения как последовательности сообщений во времени;
  • описание параллельного поведения.

  Заметим, что полного взаимно-однозначного соответствия между выделенными группами и каноническими диаграммами UML не наблюдается. Действительно, если первые две группы средств однозначно отображаются диаграммами автомата и диаграммами деятельности, то для описания последовательности сообщений применяется несколько различных типов диаграмм, а описание параллельного поведения «размазано» по всем типам канонических диаграмм. Рассмотрим эти четыре группы средств в целом, «с высоты птичьего полета», не углубляясь пока в детали нотации и семантики.

  Явное выделение состояний. При использовании объектно-ориентированного подхода, программная система представляет собой множество объектов, взаимодействующих друг с другом.

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

  Жизненный цикл (lifecycle) — последовательность изменений состояния объекта.

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

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

  Поток управления и поток данных. Надо отметить, что в любом поведении в той или иной мере присутствует поток управления, только не всегда он описывается явно.

  Поток управления ‒ это последовательность выполнения операторов (команд) в программе.

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

  Во-первых, на поток управления оказывают влияние различные управляющие конструкции: операторы перехода, условные операторы, операторы цикла и т.д.

  Во-вторых, в большинстве практических систем программирования используется понятие подпрограммы: при выполнении оператора вызова подпрограммы выполнение операторов программы приостанавливается, управление передается в подпрограмму, т. е. в поток управления попадают операторы подпрограммы, а при выходе из подпрограммы возобновляется выполнение операторов программы. Аналогичная ситуация возникает при синхронном обмене сообщениями между взаимодействующими в программе объектами.

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

  Помимо потока управления в UML также используется поток данных.

  Поток данных ‒ это описание связи выходных результатов одних действий с входными аргументами других действий.

  К сожалению, средства описания потока данных в UML 1 достаточно скудны. Прежде всего, это так называемые объекты в состоянии (см. параграф 4.3.2 и параграф 4.3.4), которые могут использоваться на диаграммах деятельности и диаграммах взаимодействия. В UML 2 ситуация несколько улучшилась и потоки данных стали равноправны с потоками управления на диаграмме деятельности.

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

  Именно диаграммы взаимодействия претерпели наибольшее расширение и усовершенствование в UML 2 по сравнению с UML 1.

  Параллельное поведение. Касательно представления потоков управления в UML остается сказать, что в реальных программных системах потоков управления может быть несколько. Все типы поведенческих диаграмм умеют в той или иной степени отражать данный факт.

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

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

  В следующих разделах рассматриваются все указанные средства более детально.

  Похожие публикации:

  1. Как обновить requirements txt python
  2. Как посмотреть таблицу в sql
  3. Как установить ansys
  4. Мета теги что это