Структурные модели автоматов, используемые в задачах логического управления, описываются совсем в других терминах. Автомат здесь рассматривается не как распознаватель языка, а как устройство управления. Поэтому у всех структурных моделей помимо множества входных воздействий X и множества состояний Y существует и множество выходных воздействий Z (все три множества являются конечными).По этому признаку структурные автоматы больше всего похожи на абстрактный конечный автомат с выходом. Однако имеются и значительные отличия: ДКА с выходом рассматривается как автоматное отображение входных строк конечной длины в выходные строки той же длины. В случае со структурным автоматом число входных воздействий заранее неизвестно и необязательно конечно. Входными воздействиями для системы управления могут быть, например, значения сигнализаторов. В отсутствие непредвиденных ситуаций работа такой системы никогда не завершается. Здесь значение имеет не вся бесконечная выходная «строка», а каждое выходное воздействие в отдельности и именно в тот момент времени (такт), когда оно сгенерировано. Другими словами, модели абстрактных автоматов применяются в трансформирующих системах (вычисляющих функции над строками), а структурные модели — в реактивных системах (формирующих реакцию на входные воздействия от внешней среды).
В задачах логического управления значение имеет не только конечность множеств X, Y и Z, но и их точная размерность, поскольку она влияет на сложность реализации устройства управления. Кроме того, элементы этих множеств принято считать битовыми векторами (иногда вместо битов удобнее использовать, например, целые числа из небольшого диапазона). Теоретически это несущественно, так как символы любого конечного алфавита можно закодировать битовыми строками одинаковой длины. Такой выбор представления определяется скорее практическими соображениями: удобно считать, что устройство управления имеет несколько параллельных двоичных входов и выходов, причем в каждом из них заключен определенный смысл. Например, на один из двоичных входов могут подаваться различные значения в зависимости от того, является ли текущая температура среды допустимой, а на второй — в зависимости от того, является ли допустимым давление. Значения отдельных входов и выходов (компоненты входных и выходных воздействий) называют соответственно входными и выходными переменными, а компоненты состояния — внутренними переменными. Для того чтобы подчеркнуть векторную природу состояний, входных и выходных воздействий, далее в этом разделе будем обозначать их как y, x и z соответственно. Перейдем к описанию структурных моделей конечных автоматов. Автоматы без памяти. Автомат, значения выходов z которого зависят только от значений входов x в данный момент времени и не зависят от предыстории, называется комбинационным (однотактным), или автоматом без памяти. Отметим, что в этом случае термин «память» используется в другом смысле, чем при описании абстрактных автоматов в разделе 1.4.1. Здесь речь идет об основной памяти автомата: его управляющих состояниях, которые накапливают информацию о предыстории. В связи с МП-автоматом и машиной Тьюринга говорилось о дополнительной памяти: той, что дана вычислителю помимо его управляющих состояний. Строго говоря, автомат без памяти не является автоматом в смысле определения, данного в начале параграфа 1.4, где автоматом была названа конечная динамическая система. Более корректный термин для этого класса автоматов — комбинационные схемы (КС). Стандартное обозначение комбинационной схемы приведено на рис. 1.9. Функционирование комбинационных схем описывается соотношением вида
z = f(x).
Функция f в этом соотношении обычно булева (ее аргументы и результат двоичны). Булевы функции принято задавать с помощью полностью или не полностью определенных таблиц, которые в первом случае называются таблицами истинности, а во втором — таблицами решений. Более компактной формой представления булевых функций являются булевы формулы, которые всегда определяют функцию полностью. Возвращаясь к терминам параграфа 1.1, можно сказать, что комбинационная схема (в отличие от автоматов с памятью, рассматриваемых далее) является моделью сущности с простым поведением, поскольку ее выходное воздействие не зависит от состояния. Автоматы с памятью. Автомат, значения выходов z которого зависят не только от значений входов x в данный момент времени, но и от предыстории, называется последовательностным (многотактным), или автоматом с памятью. Автомат с памятью в отличие от комбинационной схемы является автоматом в обозначенном выше смысле — он представляет собой конечную динамическую систему. Отметим, что способ описания последовательностных автоматов, принятый в логическом управлении, отличается от уравнений динамических систем (формулы (1) и (2)). В логическом управлении время в явном виде не используется. Автоматы представляются в виде структурных схем, которые состоят из элементов двух типов: комбинационных схем и элементов задержки (ЭЗ). Для каждого элемента схемы отдельно записывается уравнение преобразования, которое он осуществляет (зависимость выходного сигнала от входного). Элементы задержки на самом деле не преобразуют сигнал: они передают на выход то же, что получили на вход, но через некоторый заданный промежуток времени (в данном случае один такт), однако в уравнениях эта задержка в явном виде не отражается. Ниже рассмотрены наиболее важные классы последовательностных автоматов: автоматы без выходного преобразователя, автоматы Мура, Мили и смешанные автоматы. Автоматы без выходного преобразователя. Структурная схема автомата без выходного преобразователя первого рода приведена на рис. 1.10, слева, а второго рода — на рис. 1.10, справа. Здесь комбинационная схема реализует функцию переходов автомата, а элемент задержки и обратная связь, которая передает сигнал с выхода автомата обратно на вход, обеспечивают его память. Элементы рассмотренных схем описываются следующими соотношениями (уравнения (3) и (4) описывают автоматы первого и второго рода соответственно):Здесь функция ?, вычисляемая комбинационной схемой КС, имеет смысл функции переходов автомата. Можно показать, что эти соотношения эквивалентны уравнениям динамических систем (1) и (2). Если в соотношение (3) в явном виде ввести время, то получим: Обратим внимание читателя на различие терминов «автомат без выхода» и «автомат без выходного преобразователя». Рассматриваемый структурный автомат формирует выходные воздействия. Отсутствие выходного преобразователя означает лишь то, что значения выходных переменных совпадают со значениями внутренних переменных автомата (на языке абстрактных автоматов это значит, что функция выходов зависит только от состояний и является им тождественной). Иначе говоря, в этом случае каждое состояние автомата обозначается (кодируется) значением выходного воздействия в этом состоянии. Такое кодирование состояний называется принудительным Автоматы без выходного преобразователя имеют ограниченную область применения: они пригодны лишь тогда, когда число управляющих состояний автомата не превышает числа различных выходных воздействий. Приведем простой пример автоматизированного объекта управления, который не обладает таким свойством. Рассмотрим счетный триггер, состоящий из кнопки, лампочки и управляющего автомата (рис. 1.11). Управляющий автомат в данном случае имеет одну двоичную входную переменную x, принимающую значение единицы, если кнопка нажата, и нуля в противном случае, и одну двоичную выходную переменную z, устанавливаемую в единицу, если лампочку требуется включить, и в нуль — если выключить .Алгоритм работы счетного триггера таков: каждое нажатие кнопки переводит лампочку из выключенного состояния во включенное, и наоборот (отпускание кнопки не влияет на состояние лампочки). Попытаемся изобразить граф переходов автомата без выходного преобразователя, реализующего этот алгоритм (рис. 1.12).При построении графа было использовано принудительное кодирование состояний: код состояния совпадает со значением выходной переменной z в этом состоянии. Это и стало источником проблемы: полученный граф переходов невозможно реализовать, поскольку состояния, соответствующие каждой паре вершин, обозначенных одинаково, неразличимы. В действительности у этой проблемы есть еще один источник: рассматриваемая система не является событийной. В событийных системах некоторые или все входные воздействия представляют собой события: они инициируются внешней средой и сигнализируют об изменениях ее вычислительного состояния. Если бы входное воздействие счетного триггера состояло из двух событий (первое возникало бы один раз при нажатии кнопки, а второе — один раз при отпускании), то для управления лампочкой достаточно было бы автомата без выходного преобразователя с двумя состояниями, соответствующими состояниям лампочки, и проблемы бы не возникло. Работать с событиями удобно, однако это лишь абстракция, причем достаточно высокого уровня (например, прикладное ПО взаимодействует посредством событий с операционной системой). Задачи логического управления предполагают либо аппаратную, либо низкоуровневую программную реализацию. При этом обеспечить взаимодействие автомата с внешней средой посредством событий удается далеко не всегда. Поэтому чаще всего в логическом управлении используется альтернативный способ взаимодействия: автомат опрашивает вычислительное состояние внешней среды. При применении вместо событий входной булевой переменной x счетному триггеру требуется четыре управляющих состояния для того, чтобы различать одиночные нажатия кнопки. Изменим кодирование состояний так, чтобы они стали различимыми. Самый «экономичный» способ сделать это — добавить к коду каждого состояния еще по одному биту так, чтобы два состояния, обозначаемые одинаково при принудительном кодировании, различались в этом бите (рис. 1.13).Такое кодирование состояний называется принудительно-свободным (один бит кода навязывается значением выходной переменной z, а другой определяется свободно, и для его хранения вводится переменная y ).Для реализации такого автомата, как и автомата с принудительным кодированием состояний, нет необходимости в выходном преобразователе. Поскольку первый бит кода состояния совпадает со значением выходной переменной z, то эту переменную можно без изменений подать на выход автомата (рис. 1.14). Использование принудительно-свободного кодирования состояний расширяет область применения автоматной модели без выходного преобразователя. Поэтому такие автоматы называются универсальными автоматами без выходного преобразователя. Можно пойти еще дальше и ввести вместо двух логических внутренних переменных одну многозначную (целочисленную, символьную, строковую). В этом случае коды состояний выбираются произвольно, например {1, 2, 3, 4}, {‘a’, ‘b’, ‘c’, ‘d? ? ? ? ? ? ? ? ? ? ? ddddddddd’} или {«Кнопка отпущена, лампа выключена», «Кнопка нажата, лампа включена», «Кнопка отпущена, лампа включена», «Кнопка нажата, лампа выключена»}. Такой способ кодирования состояний называется свободным. Он удобен: выходные и внутренние переменные автомата независимы, состояниям можно присваивать мнемонические строковые имена, однако для формирования выходного воздействия в этом случае требуется выходной преобразователь. Именно такой способ кодирования состояний автомата и было предложено в работе [4] применять в программировании и в качестве основного. Автомат Мура. Для преобразования свободно выбранных кодов состояний в значения выходных воздействий введем в автомат выходной преобразователь — еще одну комбинационную схему КС2, реализующую функцию выходов автомата (в отличие от первой комбинационной схемы КС1, реализующей функцию переходов).Понятие структурного автомата Мура аналогично понятию абстрактного автомата Мура, введенному в разделе 1.4.1. В таком автомате выходное воздействие зависит только от состояния и не зависит от входного воздействия. Структурные схемы автоматов Мура первого и второго рода приведены на рис. 1.15. Автомат первого рода формирует выходные воздействия на основе текущих (не обновленных) значений внутренних переменных, а автомат второго рода, наоборот, сначала обновляет состояние, а затем использует его новое значение для вычисления выходного воздействия. Автоматы Мура первого и второго рода описываются соотношениями (5) и (6) соответственно: Здесь функция переходов ? и функция выходов ? вычисляются соответственно схемами КС1 и КС2.
На рис. 1.16 приведен граф переходов автомата Мура счетного триггера с многозначным кодированием состояний. Возможность применения одной переменной для хранения номера состояния при любом числе состояний в автомате позволяет сделать процесс его работы наблюдаемым [4]. Наблюдаемость является одним из важнейших свойств, рассматриваемых в теории автоматического управления [23]. Кроме того, переменная состояния может применяться для обеспечения взаимодействия между автоматами. Для этого при реализации автомата необходимо, чтобы значение переменной состояния после каждого такта работы было доступно всем автоматам системы. Автомат Мили. По аналогии с абстрактными автоматами, структурный автомат, выходные воздействия которого зависят не только от состояния, но и от входных воздействий, называется автоматом Мили (рис. 1.17).Автоматы Мили первого и второго рода описываются соотношениями (7) и (8) соответственно: Известно что для любого автомата Мили можно построить эквивалентный ему автомат Мура. Число состояний в таком автомате будет не меньше, чем в исходном. В качестве примера рассмотрим последовательный двоичный одноразрядный сумматор, который выполняет сложение одноименных бит двух двоичных чисел с учетом переноса. Результатом работы сумматора является одноименный бит суммы и перенос в следующий разряд. На рис. 1.18 приведен автомат Мили, реализующий это «устройство». На этом рисунке xi и yi — складываемые биты, состояния соответствуют значениям переноса, а значение бита суммы формируется как выходное воздействие на переходах. Смешанные автоматы. Если часть выходных переменных автомата зависит только от состояний, а остальные — также и от входных воздействий, удобно разделить функцию выходов ? на две составляющие: 1(y) и 2(x, y). В структурную схему автомата в этом случае вводится не один, как в автоматах Мура и Мили, а два выходных преобразователя (рис. 1.19). Такие автоматы называются смешанными, автоматами Мура—Мили или С-автоматами.