В этом разделе формализуются концепции, на которых основано автоматное программирование. Цель раздела — исследовать свойства автоматизированного объекта управления как основной модели, используемой в автоматном программировании, и определить его место среди традиционных автоматных моделей.
Материал данного раздела способствует более глубокому пониманию философии автоматного программирования, однако из-за формального изложения он более труден для понимания, чем остальные разделы книги. При первом прочтении его можно пропустить. В настоящее время предложены, исследованы и с успехом применяются различные математические модели, в названиях которых используется слово «автомат». Они имеют много общего в своих основах, но существенно различаются в деталях. Причина разнообразия автоматных моделей объясняется широтой области их применения (пример различного понимания природы автоматов при создании компиляторов и в задачах логического управления приведен в параграфе 1.1). Автоматы являются незаменимым инструментом в таких далеких друг от друга областях, как, например: математическая лингвистика; логическое управление;yy моделирование поведения человека; коммуникационные протоколы; теория формальных языков, вычислимости и вычислительной сложности. Выявить общее в различных автоматных моделях можно, если рассмотреть автоматы как частный случай динамических систем. Обычно термином «динамическая система» в технике, природе, жизни и т. д. обозначают систему, процессы которой развиваются во времени. Состояние системы в каждый момент времени характеризуют некоторым множеством обобщенных координат. Процессы в динамической системе описываются уравнениями разных типов относительно обобщенных координат Динамические системы можно подразделить на несколько классов в зависимости от следующих факторов. Модель времениyy. Время может считаться текущим непрерывно или дискретно. В первом случае время изменяется на континууме, во втором — на счетном множестве, элементы которого называются тактами. Размерность системы. Число обобщенных координат может быть конечным или счетным. Мощность множеств координат. Каждая из обобщенных координат может принимать значения из конечного, счетного или континуального множества. В физике и технике часто используются системы, в которых время непрерывно и обобщенные координаты также изменяются на континууме. Для описания процессов в таких системах используются дифференциальные уравнения. Если же время дискретно, но обобщенные координаты принимают значения из континуальных множеств, то для описания процессов используются разностные уравнения. Те системы, в которых время дискретно, число обобщенных координат конечно и каждая координата может принимать значения из конечного множества, называют конечными динамическими системами. Конечные автоматы принадлежат к классу конечных динамических систем. Системы, которые отличаются от конечных тем, что число обобщенных координат или же множество значений координат может быть бесконечно, образуют более общий класс. К этому классу принадлежат, например, машины Тьюринга. Рассмотрим конечную динамическую систему с дискретным временем, состояние которой в каждый такт t характеризуется конечным числом обобщенных координат Y(t) (|Y | = n). На вход системе подается конечное число входных воздействий X(t) (|X | = m). Такая конечная динамическая система называется конечным автоматом, если состояние системы в каждый такт однозначно определяется состоянием системы в предыдущий такт и значениями входных воздействий либо в текущий (1), либо в предыдущий (2) такт:
Таким образом, для описания поведения конечных автоматов используются рекуррентные соотношения определенного вида. Если используется рекуррентное соотношение (1), то автомат называется автоматом первого рода, а если соотношение (2) — автоматом второго рода Можно показать, что понятие «конечный автомат» охватывает и те конечные системы, состояния которых определяются предысторией любой наперед заданной конечной длины. Однако оно не охватывает системы, в которых состояние определяется статистически или же зависит от всей предыстории. Таким образом, класс конечных динамических систем, которые «помнят» конечное число предыдущих тактов, не шире класса систем, которые «помнят» только один такт. В этой книге рассматриваются только автоматы с задержкой не более чем на один такт. Любую автоматную модель можно описать как динамическую систему, однако такое описание слишком абстрактно. Для того чтобы исследовать свойства автоматизированного объекта управления, необходимо рассмотреть различные существующие автоматные модели в деталях. Далее будут рассмотрены две практически независимые «системы» автоматных моделей: одна заимствована из теории формальных языков, а другая — из области логического управления. Как упоминалось выше, в обеих областях традиционно используются конечные автоматы, однако понимаются они по-разному: применяются различные системы терминов, различные классификации, сферы интересов двух областей практически не пересекаются.
В теории формальных языков изучаются так называемые абстрактные автоматы (называемые также абстрактными машинами, или абстрактными вычислителями). Внутренняя структура абстрактных автоматов не раскрывается. Интерес при их изучении представляет только вычислительная мощность — класс языков, которые может распознавать машина. Модели абстрактных автоматов рассматриваются в разделе 1.4.1.В логическом управлении рассматриваются структурные автоматы. Они выступают в роли управляющих устройств в системах управления. Интерес здесь представляет число параллельных входов и выходов автомата, его связи с объектом управления и другими элементами системы, простота реализации. Модели структурных автоматов рассматриваются в разделе 1.4.2.Автоматное программирование, с одной стороны, объединяет в себе опыт двух указанных разделов теории автоматов , а с другой — является совершенно самостоятельной областью. При использовании автоматов в программировании не имеют значения ни исследования вычислительной мощности, ни, например, минимизация числа состояний. В этой области нас интересует только то, как использовать конечные автоматы для построения корректных программ. В разделе 1.4.3 приводится формальное описание модели автоматизированного объекта управления. Эта модель является, в некотором смысле, обобщением других автоматных моделей и соединяет в себе черты как абстрактных, так и структурных автоматов. В то же время рассмотрению подлежат именно те свойства модели, которые имеют значение для ее применения в программировании.