Познакомившись с языком спецификации структуры системы, вернемся к языку спецификации ее поведения: уже известным читателю графам переходов. Поскольку неформальное знакомство читателя на примерах с этой нотацией уже состоялось, в данном разделе опишем графы переходов более формально и уделим внимание тем деталям и возможностям, которые ранее не упоминались. Диаграмма переходов автомата представляет собой ориентированный граф, вершинам которого соответствуют управляющие состояния, а дугам — переходы между состояниями. Вершины графа принято изображать в виде прямоугольников со скругленными углами, внутрь которых помещается номер, название состояния и описание выходного воздействия в этом состоянии. Выходное воздействие описывается путем перечисления идентификаторов выходных переменных, вложенных или вызываемых автоматов. Дуга графа переходов помечается условием перехода и выходным воздействием на переходе. Условие перехода имеет вид произвольной булевой формулы над входными переменными, событиями и (в случае взаимодействия путем обмена номерами состояний) предикатами от номеров состояний других автоматов. Громоздкими булевыми формулами бывает неудобно помечать переходы. В таком случае формулу можно заменить сокращенным идентификатором, а его расшифровку дать рядом с графом переходов. Условие перехода отделяется от выходного воздействия горизонтальной чертой. В целях повышения наглядности графов переходов необходимо по возможности выполнять их плоскую укладку. На диаграммах переходов к переменным, событиям и автоматам системы принято обращаться через их краткие символические идентификаторы. Причина использования этого соглашения в том, что на больших диаграммах длинные, мнемонические имена либо вообще не помещаются, либо «засоряют» граф, мешая формированию у разработчика целостной картины поведения системы. Как уже упоминалось, расшифровка идентификаторов производится на схеме связей. Автоматизированное средство проектирования может избавить разработчика от необходимости обращаться к схеме связей, например, показывая словесное описание символа при наведении на него курсора мыши. Обычно для автоматов используются идентификаторы вида Ai, для событий — ei, для входных переменных — xi, для состояний автоматов — yi, для выходных переменных — zi, для сокращенных условий переходов — Сi (где i — натуральное число). Можно использовать и любые другие идентификаторы, лишь бы они были короткими: из одной или двух букв. Так в примере с эмулятором часов события, соответствующие нажатиям кнопок, назывались буквами H, M и A. Обозначить их так было логично, так как по условию задачи теми же буквами назывались кнопки часов. Одна из тех возможностей обсуждаемой нотации, которые не были до сих пор использованы ни в одном примере, — это группировка состояний. Если несколько состояний автомата имеют одинаковые исходящие переходы (с одним и тем же условием, выходным воздействием и целевой вершиной), то такие состояния можно объединить в группу и заменить несколько одинаковых переходов одним — групповым. Группировку применяют в тех случаях, когда некоторый набор состояний логически объединен общим поведением, однако выделять эти состояния в отдельный автомат нецелесообразно. Графически группа состояний обозначается рамкой. Другая неиспользованная возможность нотации — переходы с приоритетами. Она позволяет задать приоритеты на дугах, исходящих из некоторого состояния. Приоритеты определяют порядок, в котором проверяется возможность перехода по каждой из этих дуг (первым будет проверяться условие на дуге с высшим приоритетом, последним — на дуге с низшим приоритетом). Назначение приоритетов — один из способов борьбы с неоднозначностью (противоречивостью) в описании автомата1. Граф переходов, в котором условия на нескольких дугах, исходящих из одного состояния, могут быть одновременно истинными, является некорректным. Во время выполнения возможна ситуация, в которой автомат, описываемый таким графом, не сможет определить, по какой из дуг ему перейти. Использование переходов с приоритетами разрешает это противоречие в пользу дуги с большим приоритетом. Несколько исходящих дуг могут иметь одинаковый приоритет, но в этом случае между ними не должно быть противоречия. На графе переходов приоритет обозначается натуральным числом перед меткой перехода. При этом по соглашению меньшие числа соответствуют более высоким приоритетам (иначе говоря, числа соответствуют порядку, в котором проверяются переходы).Наконец, упомянем еще одно полезное соглашение в нотации диаграмм переходов. Допустим, имеется один или несколько переходов из некоторого состояния, таких, что противоречия между ними не возникает. Однако для обеспечения полноты2 требуется добавить еще один переход, который осуществится в том случае, если ни одно из условий других переходов не будет выполнено. Новую дугу следовало бы пометить отрицанием дизъюнкции условий, написанных на всех остальных исходящих дугах. Такая неприятная необходимость уже встречалась: вспомните петли в автоматах, управляющих клапанами. Громоздкие условия, обеспечивающие полноту, не только скучно и неприятно писать, они еще и покушаются на святая святых автоматного программирования — наглядность графов переходов. Вместо этого можно было бы ввести безусловный переход и присвоить ему более низкий приоритет, чем у всех остальных. Однако вводить приоритеты для всех остальных дуг (если их не было) неудобно. Кроме того, при модификации автомата может потребоваться изменять приоритет дуги, обеспечивающей полноту, поскольку он всегда должен быть наименьшим. Поэтому для обозначения такой дуги в нотации диаграмм переходов введена специальная конструкция — пометка «иначе». Переход с такой пометкой всегда выполняется, только если условия всех остальных переходов из данного состояния ложны. Это его свойство сохраняется при добавлении любых новых дуг и любом изменении приоритетов. На рис. 2.24 приведен пример графа переходов, в котором использованы почти все возможности нотации.1* Множество условий переходов, исходящих из одного состояния, называется противоречивым, если при некотором значении входного воздействия более одного условия может иметь значение «истина».2* Множество условий переходов, исходящих из одного состояния, называется неполным, если при некотором значении входного воздействия ни одно из условий не имеет значения «истина».