Графические представления конечного автомата

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

Как известно, основным источником информации для человека является визуальное восприятие. Более 80 % всей информации человек получает с помощью органов зрения. Недаром девизом фирмы Microsoft является: «Лучше одна картинка, чем 1024 слова». Поэтому человечество разрабатывало графические средства описания работы автоматов. Рассмотрим их более подробно.

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

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

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

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

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

  • 1. Автомат не запоминает историю перемещения из состояния в состояние. С точки зрения моделируемого поведения определяющим является сам факт нахождения объекта в том или ином состоянии, но никак не последовательность состояний, в результате которой объект перешел в текущее состояние. Другими словами, автомат «забывает» все состояния, ко торые предшествовали текущему в данный момент времени. Образно говоря, существует непрозрачная стена, отделяющая текущее состояние от прошлого поведения объекта.
  • 2. В каждый момент времени автомат может находиться в одном и только в одном из своих состояний. Это означает, что формализм автомата предназначен для моделирования последовательного поведения, когда объект в течение своего жизненного цикла последовательно проходит через все свои состояния. При этом автомат может находиться в отдельном состоянии как угодно долго, если не происходит никаких событий.
  • 3. Хотя процесс изменения состояний автомата происходит во времени, явно концепция времени не входит в формализм автомата. Это означает, что длительность нахождения автомата в том или ином состоянии, а также время достижения того или иного состояния никак не специфицируются. Другими словами, время на диаграмме состояний присутствует в неявном виде, хотя для отдельных событий может быть указан интервал времени и в явном виде.
  • 4. Количество состояний автомата должно быть обязательно конечным (в языке UML рассматриваются только конечные автоматы), и все они должны быть специфицированы явным образом. При этом отдельные псевдосостояния могут не иметь спецификаций (начальное и конечное состояния). В этом случае их назначение и семантика полностью определяются из контекста модели и рассматриваемой диаграммы состояний.
  • 5. Граф автомата не должен содержать изолированных состояний и переходов. Это условие означает, что для каждого из состояний, кроме начального, должно быть определено предшествующее состояние. Каждый переход должен обязательно соединять два состояния автомата. Допускается переход из состояния в себя, такой переход еще называют «петлей».
  • 6. Автомат не должен содержать конфликтующих переходов, то есть таких переходов из одного и того же состояния, когда объект одновременно может перейти в два и более последующих состояния (кроме случая параллельных подавтоматов). В языке UML исключение конфликтов возможно на основе введения так называемых сторожевых условий, которые будут рассмотрены далее.

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

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

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

1. Множество состояний. Состояние - положение объекта, в котором применяется определенный набор правил, линий поведения, предписаний и физических законов. Состояние на диаграмме изображается прямоугольником со скругленными вершинами (рисунок 3.13). Этот прямоугольник, в свою очередь, может быть разделен на две секции горизонтальной линией.

Имя состояния

Имя состояния

Список внутренних действий в данном

состоянии

Рисунок 3.13 - Графические изображения состояния на диаграмме состояний

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

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

<метка действия 7' выражение действиях

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

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

entry - указывает на действие, специфицированное следующим за ней выражением действия, которое выполняется в момент входа в данное состояние (входное действие);

exit - указывает на действие, специфицированное следующим за ней выражением действия, которое выполняется в момент выхода из данного состояния (выходное действие);

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

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

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

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

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

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

а) б)

Рисунок 3.14 - Графические изображения начального и конечного состояний на диаграмме состояний

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

Переход осуществляется при наступлении некоторого события: окончания выполнения деятельности (do activity), получении объектом сообщения или приемом сигнала. На переходе указывается имя события. Кроме того, на переходе могут указываться действия, производимые объектом в ответ на внешние события при переходе из одного состояния в другое. Срабатывание перехода может зависеть не только от наступления некоторого события, но и от выполнения определенного условия, называемого сторожевым условием. Объект перейдет из одного состояния в другое в том случае, если произошло указанное событие и сторожевое условие приняло значение «истина».

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

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

<сигнатура события>'['<сторожевое условно']/' <выражение действиях

При этом сигнатура события описывает некоторое событие с необходимыми аргументами:

<имя события>'('<список параметров, разделенных запятыми>')'.

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

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

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

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

Сторожевое условие (guard condition), если оно есть, всегда записывается в прямых скобках после события-триггера и представляет собой некоторое булевское выражение. Напомним, что булевское выражение должно принимать одно из двух взаимно исключающих значений: «истина» или «ложь». Из контекста диаграммы состояний должна явно следовать семантика этого выражения.

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

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

Выражение действия (action expression) выполняется в том и только в том случае, когда переход срабатывает. Представляет собой атомарную операцию (достаточно простое вычисление), выполняемую сразу после срабатывания соответствующего перехода до начала каких бы то ни было действий в целевом состоянии. Атомарность действия означает, что оно не может быть прервано никаким другим действием до тех пор, пока не закончится его выполнение. Данное действие может оказывать влияние, как на сам объект, так и на его окружение, если это с очевидностью следует из контекста модели. Выражение записывается после знака «/» в строке текста, присоединенной к соответствующему переходу.

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

Диаграмма состояний является наиболее емким и концентрированным описанием поведения конечного автомата. Поэтому стандартный язык программирования ПЛК SFC представляет собой просто диаграмму состояний.

Рассмотрим правила построения диаграммы состояний на простейшем примере включения и выключения асинхронного электродвигателя с помощью ПЛК LOGO! (рисунок 3.15). Состояние показывается прямоугольниками со скругленными углами. В нашем примере двигатель может иметь только два состояния: включен и выключен. Переходы между состояниями показываются стрелками любой формы. Поскольку состояний два, то и переходов тоже два. Состояния и переходы нумеруются произвольным образом.

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

На первый взгляд может показаться, что задачу управления асинхронным двигателем можно решить простейшим комбинационным автоматом с логической формулой у = SBl - SB2. Однако, поскольку SB] и SB2 являются кнопками, то задача несколько усложняется. Ведь контакты кнопки замкнуты или разомкнуты только тогда, когда мы нажали на кнопку пальцем и держим ее. Если отпустить кнопку, то ее контакты опять разомкнутся (замкнутся). Поэтому необходимо запоминать состояние кнопок, то есть, для решения данной задачи нужен конечный автомат с памятью.

Существует простое правило: диаграммы переходов состояний можно построить из элементов памяти, количество которых на единицу меньше числа состояний. Поскольку у нас два состояния, то будем использовать один элемент памяти. Для ПЛК LOGO! основным элементом памяти является RS-триггер, поэтому подключим выход Q1 к нему (рисунок 3.16). Как известно, RS-триггер имеет два входа (Set и Reset). При подаче единицы на

вход S триггер устанавливается в 1, которая сохраняется до того, когда на вход R поступает единица. При наличии нулей на обоих входах триггер сохраняет то состояние (1 или 0) в которое он был установлен ранее.

Кнопка SB2 нажата

Двигатель был включен Выключение двигателя

Рисунок 3.15 - Диаграмма состояний для электродвигателя

Память

Программа на языке FBD для рассматриваемого примера

Рисунок 3.16 - Программа на языке FBD для рассматриваемого примера

Как следует из диаграммы состояний (рисунок 3.15), переход 1 инициируется нажатием кнопки SBi, то есть подачей логической единицы со входа II. При выполнении этого перехода должен включиться двигатель (на выход Q1 должна попасть логическая единица), а это означает, что должна податься 1 на вход S триггера. Поэтому соединяем вход II с входом S триггера. Это обеспечит нам выполнение перехода 1 диаграммы состояний.

По технологическим условиям, кнопка SB2 в нормальных условиях работы всегда замкнута (рисунок 3.15). Это означает, что на вход 12 всегда поступает логическая единица, которая, при нажатии на кнопку SB2, меняется на логический ноль. Переход 2 инициируется нажатием кнопки SB2, то есть подачей 0 на вход 12. При выполнении этого перехода должен выключиться двигатель (на выход Q1 должен попасть логический ноль).

Поскольку логический 0 на выходе RS-триггера получается только при подаче на его вход R логической 1, а со входа 12 в этот момент времени идет логическая 1, то воспользуемся инвертором (операция НЕ, элемент В002 на схеме рисунка 3.16). В этом случае, в нормальном режиме работы, когда кнопка SB2 замкнута, на входе 12 будет 1, которая, с помощью инвертора, преобразуется в логический 0 на входе R триггера. Логическая 1 на входе R триггера только тогда, когда будет нажата кнопка SB2, на вход 12 попадет логический 0, а с выхода инвертора на вход R триггера пойдет логическая единица. Триггер установиться в логический 0 и двигатель выключится.

Рассмотренный пример достаточно простой, и программу управления можно построить интуитивным путем. Более сложные случаи требуют большей формализации действий. Рассмотрим другой пример - систему управления башенной водокачкой (рисунок 3.17).

В данной примере, также как и в предыдущем, имеются два входных сигнала, датчик верхнего уровня и датчик нижнего уровня х2 воды, но если в примере с электродвигателем кнопки могли давать только два сигнала (SB 1=1, SB2=Q и SB 1=0, SB2= 1), и соответственно, два такта и два перехода, то в случае водокачки мы имеем четыре возможных комбинаций сигналов, четыре такта и четыре перехода, как это изображено на диаграмме состояний - рисунке 3.17.

Диаграмма состояний для насоса башенной водокачки

Рисунок 3.17 - Диаграмма состояний для насоса башенной водокачки

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

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

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

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

Переход

S

R

Q

В001 Q1 2001

Таблица сигналов с триггера в зависимости от перехода

Рисунок 3.18 - Таблица сигналов с триггера в зависимости от перехода

Для получения аналитического выражения для этой таблицы истинности (рисунок 3.196) воспользуемся той же методикой, что и раньше: будем считать, что единица в каждой клетке образована произведением входов. Получим S = х, • х2. Воспользовавшись тождеством алгебры логики

(13) имеем S = х, • х2 = х, + х2,

что есть не что иное,

как таблица истинно

сти операции ИЛИ-НЕ.

В002

Переход

XI

х2

1

0

0

2

0

1

3

1

1

4

0

1

XI

Х2

S

  • 0 10
  • а)

ВООЗ

&

  • 0 10
  • 111
  • 0 10
  • б)

Рисунок 3.19 - Таблицы истинности для входов триггера

Аналогичным образом строим таблицу истинности для входа R триггера (рисунок 3.19в). Как можно убедиться, это таблица истинности операции логического умножения.

Таким образом, программа для реализации конечного автомата управления насосом водокачки состоит из блоков: И, ИЛИ-HE и RS-триггера (рисунок 3.20).

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

Х1

И

Программа управления насосом башенной водокачки

Рисунок 3.20 - Программа управления насосом башенной водокачки

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >