19
Можно показать, что понятие «конечный автомат» охватывает и те конечные
системы, состояния которых определяются предысторией любой наперед заданной
конечной длины. Однако оно не охватывает системы, в которых состояние
определяется статистически или же зависит от всей предыстории. Таким образом,
класс конечных динамических систем, которые «помнят» конечное число
предыдущих тактов не шире класса систем, которые «помнят» только один такт. В
этой книге рассматриваются только автоматы с задержкой не более чем на один такт.
Любую автоматную модель можно описать как динамическую систему, однако, такое
описание слишком абстрактно. Для того чтобы исследовать свойства
автоматизированного объекта управления, необходимо рассмотреть различные
существующие автоматные модели в деталях.
Далее будут рассмотрены две практически независимые «системы» автоматных
моделей: одна заимствована из теории формальных языков, а другая – из области
логического управления. Как упоминалось выше, в обеих областях традиционно
используются конечные автоматы, однако, понимаются они очень по-разному:
применяются различные системы терминов, различные классификации, сферы
интересов двух областей практически не пересекаются.
В теории формальных языков изучаются, так называемые, абстрактные автоматы
(называемые также абстрактными машинами или абстрактными вычислителями).
Внутренняя структура абстрактных автоматов не раскрывается. Интерес при их
изучении представляет только вычислительная мощность – класс языков, которые
может распознавать машина. Модели абстрактных автоматов рассматриваются в
разд. 1.4.1.
В логическом управлении рассматриваются структурные автоматы. Они
выступают в роли управляющих устройств в системах управления. Интерес здесь
представляет число параллельных входов и выходов автомата, его связи с объектом
управления и другими элементами системы, простота реализации. Модели
структурных автоматов рассматриваются в разд. 1.4.2.
Автоматное программирование, с одной стороны, объединяет в себе опыт двух
указанных разделов теории автоматов [20], а с другой – является совершенно
самостоятельной областью. При использовании автоматов в программировании не
имеют значения ни исследования вычислительной мощности, ни, например,
минимизация числа состояний. В этой области нас интересует только то, как
использовать конечные автоматы для построения корректных программ.
В разд. 1.4.3 приводится формальное описание модели автоматизированного объекта
управления. Эта модель является, в некотором смысле, обобщением других
автоматных моделей, и соединяет в себе черты как абстрактных, так и структурных
автоматов. В то же время, рассмотрению подлежат именно те свойства модели,
которые имеют значение для ее применения в программировании.
1.4.1. Абстрактные автоматы
Абстрактные конечные автоматы принято описывать в следующих терминах. Задано
конечное множество символов
, которое называется (входным) алфавитом.
Множество всех возможных цепочек (последовательностей, строк, слов),
составленных из символов алфавита
обозначается
*
. Пустая