Содержание к диссертации
Введение
Глава I. Конечный детерминированный автомат и классификация подавтоматов. Проходимые автоматы 14
Глава II. Проходимые и частичные проходимые подавтоматы, верхние и нижние границы состояний 35
Глава III. Операции объединения и пересечения проходимых и частичных проходимых подавтоматов 45
Глава IV. Приложение проходимых и частичных проходимых подавтоматов 69
Заключение 105
Список литературы 107
- Конечный детерминированный автомат и классификация подавтоматов. Проходимые автоматы
- Проходимые и частичные проходимые подавтоматы, верхние и нижние границы состояний
- Операции объединения и пересечения проходимых и частичных проходимых подавтоматов
- Приложение проходимых и частичных проходимых подавтоматов
Введение к работе
Одним из свойств процессов функционирования конечных детерминированных автоматов, фундаментально характеризующих реальные процессы в технике, экономике, обучении и т.п., которые недостаточно исследованы, является бесповоротность состояний в процессе их изменения. Это свойство ассоциируется как с теоретическими характеристиками (бесповторность состояний в кратчайших по длине траекториях состояний), так и содержательностью интерпретацией целенаправленных изменений состояний. Пусть, например, технологический процесс определен изменениями в дискретном времени ингредиентов (изделий, комплектующих, сырья, энергоресурсов, станков, работников, транспортных средств и т.д.), параметров процесса и т.п. Если состояние технологического процесса в момент времени t рассматривать как состояния используемых и участвующих в процессе ингредиентов в момент t, то повтор состояния технологического процесса связан с нерациональностью процесса или с дефектами в процессе. Даже в технологическом процессе сборки изделия возврат в пройденное состояние (изделие частично собрано, затем разобрано и опять частично собрано) соответствует устранению дефектов или бесполезным действиям.
Повтор состояний в процессах вычислений, когда предполагается, что в состоянии представлены все составляющие в рассматриваемые моменты времени (данные, средства вычислений, человеческое звено и т.п.), связан с ошибками в вычислениях или с полным повторением уже имевшейся ситуации. Если учитывать затраты ресурсов, то повтор состояний невозможен, так как между состояниями обязательно будет изменения энергетических и других ресурсов.
Математическая модель в виде конечного детерминированного автомата без выходов А = (S,X,S\ где S - конечное множество состояний, X - конечное множество входных сигналов, а д - функция переходов вида 5: SxX-+S, может описывать процессы, если полагать, что
4 -s є S - состояние процесса,
— хєХ — причина изменения состояния,
- S(s,x) — новое состояние процесса, где д определяет свойства процесса.
С использованием автоматной модели бесповоротность состояний
процесса, задаваемого начальным состоянием SQ є S и управляющей
последовательностью р є X*, определяется условием: ^0
где к = \р\ и |_р| < |s|.
В реальных процессах, то есть, в производственных, экономических, биологических и других процессах, циклы в траекториях состояний возможны только если вьщелены и учтены не все параметры, характеристики, свойства состояний. Это означает, что бесповторность состояний в реальных процессах является их естественным свойством и циклы порождаются только в математических моделях в результате огрубления действительности.
Конечный детерминированный автомат как структура с полностью определенной функцией переходов 5: SxX-+S в траектории изменений состояний, не меньшей по длине чем |$| + 1, должен иметь цикл (или петлю).
Следовательно, конечный автомат списывает реальные процессы, у которых на множестве состояний процесса задано отношение эквивалентности с конечным состояний процесса задано отношение эквивалентности с конечным числом классов и бесповторность состояний процесса понимается как бесповторность эквивалентности реальных состояний.
Управление технологическими процессами является одной из основных компонент управления производством. Процесс производства можно рассматривать как отношения на множестве ингредиентов (работников, средств производства, перерабатываемых и получаемых продуктов). Технологические операции устанавливают связи между ингредиентами из них формируются технологические схемы. В конкретном технологическом процессе из исходных продуктов (сырья, полуфабрикатов, комплектующих и т.п.) производятся
5 промежуточные и конечные продукты. При этом потребляются энергетические ресурсы, изнашивается оборудование, расходуются интеллектуальные ресурсы, оказывается воздействие на внешнюю среду.
Конечный детерминированный автомат (типа Мили) A = (S,X,Y,S,X) используется как логико-функциональная модель, формализующая логические и функциональные связи ингредиентов, на основе следующей интерпретации:
— состояние s(t) определяет ингредиенты, используемые и имеющиеся в
технологическом процессе в интервале времени, стянутым в момент
времени t\
входной сигнал x(t) соответствует технологической операции;
выходной сигнал y(t) рассматривается как информация обратной связи, характеризующая (производственный) процесс, порождаемый s(t) и x(t);
состояние s(t + l) = S(s(t), x(t)) соответствует ингредиентам, полученным из s(t) в результате реализации x(t).
Такая интерпретация представлена схемой:
технологическая
набор v операция . набор
ингредиентов \ / ингредиентов
и отличается от схем, исследуемых в большинстве работ, например, Первозванский А.А. ([59], 1975) исследует схему вида
технологическая \ продукт / технологическая
операция \ V операция
в которой связь устанавливается между операциями через продукты, т.е. затрачиваемые или выпускаемые ингредиенты. В этой же работе полагаются типовыми следующие структуры: - последовательная,
сходящаяся,
сходящаяся - расходящаяся,
структура с реверсом (материальной обратной связью (с. 21). «Функционирование производственной системы может быть
математически описано как процесс изменения состояния агрегатов системы (переходов с одной операции на другую) и процесс изменения состояния складов (изменения количества продуктов, хранящихся в них . ([59], с.37)>>.
В диссертации основными полагаются траектории изменения ингредиентов, а не траектории операций. Такой подход позволяет выделить основное положение: При принятой интерпретации конечных детерминированных автоматов технологическим процессам соответствуют траектории изменений состояний, не содержащие повторение состояний.
Обоснование выделенного основного положения состоит в том, что повторение состояния s(t) через к тактов (s(t) = s(t + k)) в траектории изменений состояний автомата А соответствует:
— «лишней» части технологического процесса, так как в состоянии
автомата представлены все ингредиенты, включая промежуточные или
конечные продукты;
увеличение длительности технологического процесса (который моделирует автомат А);
затрата ресурсов на «лишние» технологические операции;
преодоление трудностей при организации возврата к моменту t + k к тем же ингредиентам, которые имелись в момент t.
В работе Ч.Хоара [78] исследуются взаимодействующие последовательные процессы. Как отмечает автор «основная идея заключается в том, что эти системы (вычислительные системы, непрерывно действующие и взаимодействующие со своим окружением - пояснение соискателя) без труда можно разложить на параллельно работающие подсистемы... (с.9).» Это другая постановка задач, отличная от цели диссертации. Имеется совпадение в
7 некоторых исследуемых вопросах, например, Ч.Хоар рассматривает свой подход, как основу для избежания таких ошибок как зацикливание ([78], с. 10.). Им даются «строгие определения понятия процесса и способов построения процессов ([78], с. 10.)». Сравнение подхода к анализу процессов, проведенного Ч.Хоаром, и подхода, принятого в диссертации, показывает их существенное различие. Более четко позиция Ч.Хоара представлена в его понимании «процесса как математической абстракции взаимодействия системы и ее окружения ([78], с. 14).» В диссертации технологический процесс предполагается полностью определенным свойствами конечного детерминированного автомата, являющегося математической моделью возможных вариантов отношений ингредиентов и технологических операций.
Каждый реальный ингредиент (работник и т.п.) имеет интервал времени, в течение которого он существует и эффективно участвует в процессе производства. В автоматной модели этот интервал стянут в точку и, следовательно, стянут в точку и, следовательно, совмещен во времени с другими ингредиентами. Аналогичное предположение принимается для технологических операций и является достаточно распространенным («Считается, что конкретное событие в жизни объекта происходит мгновенно, т.е. является элементарным действием, не имеющим протяженности во времени (Ч.Хоар, [78], с. 18)». Этим предположением реальная протяженность существования (или использования) ингредиентов и действия технологических операций исключается из рассмотрения и основным полагается следование операций относительно принятого абстрактного времени.
Исследованию и представлению математическими средствами производственных процессов посвящено большое количество статей и монографий. В работе Н.П. Бусленко ([18], глава VIII) рассматривается моделирование производственных процессов, где анализируются дискретные и производственные процессы и разрабатываются средства формализации производственных операций и предметов их воздействия. Основу составляют
8 математические модели, определяющие связи числовых параметров операции, полуфабрикатов, деталей, узлов и т.п. В диссертации числовые параметры не являются объектами рассмотрения, они поглощаются обобщениями, после которых от реальных характеристик остается только факт их неявного наличия.
Для решения вопросов анализа, синтеза, оптимизации и распознавания траекторий состояний, технологических процессов одного свойства предшествования и следования во времени технологических операций недостаточно. В связи с этим отношение порядка предшествования и следования во времени для операций дополняется отношением «близости» между состояниями технологического процесса.
В основу идей и средств, с помощью которых состояния технологических процессов характеризуются как «близкие» (допускающие переход технологического процесса из одного состояния в другое) или как не допустимые для непосредственного следования, состояний друг за другом, в диссертации взяты работы М. Арбиба [1], [2] и [5]. Идея М. Арбиба построить дискретный аналог непрерывности на базе отношения толерантности, то есть, рефлексивного и симметричного отношения, может быть использована для определения близких, допустимых переходов, состояний. Для этого в диссертации рассматриваются бинарные отношения толерантности р1,р2,...,ра>, каждое из которых задается пары «близких» для переходов состояний. Если, например, бинарное отношение р{ вида p^SxS содержит пару {pv,sM)eplt то
изменение в технологическом процессе состояния sv на состояние s
допустимо по смыслу технологических действий. Набор бинарных отношений р1,р2,...,ра вида PidSxS, где 1 < / ^ со, имеющих содержательную интерпретацию как «близость» состояний (набор ингредиентов) технологических процессов, позволяет давать достаточно глубокую и полную характеристику технологическим схемам. Используя бинарное отношение на множестве состояний s технологического процесса можно, например, задавать
«близость» состояний, которые только по одному из градиентов различаются количественно. Переходы между такими состояниями определяются возможностями транспортных средств и наличием должного количества ингредиента для транспортировки. Покрытие технологической схемы бинарными отношениями, характеризующими содержательные варианты «близости» состояний, принципиально углубляет возможности использования предлагаемого формализма для решения задач поиска, анализа, оптимизации и распознавания стратегии управления производством.
Одним из основных свойств автоматов, выбираемых в качестве математических моделей технологических процессов является проходимость состояний и наличие фискальных состояний.
В первой главе диссертации рассматриваются известные дискретные структуры: конечные детерминированные автоматы типов Мили и Мура; проходящие, тупиковые и изолированные подавтоматы. На содержательном уровне вводятся новые виды подавтоматов: проходимые подавтоматы и частичные проходимые подавтоматы. Определяются /С-проходимые и абсолютно iC-проходимые состояния автоматов. Здесь же анализируется возможность применения известных методов теории экспериментов с конечными детерминированными автоматами к распознаванию технологических процессов и поясняется невозможность применения таких методов: известные методы теории экспериментов с автоматами базируются на изменениях состояний автомата в целях эксперимента. В технологических процессах изменения состояний определяются спецификой технологического процесса.
Во второй главе диссертации содержатся результаты по исследованию свойств проходимых подавтоматов и частично проходимых автоматов, свойств операций объединения и пересечения подавтоматов, свойств границ состояний подавтоматов.
Теоремой 2.1. определяется связь верхней границы состояний объединения проходимых автоматов с верхними границами состояний компонентов и аналогичная связь нижних границ состояний.
Проходимые автоматы являются собственным подклассом класса всех автоматов. Поэтому возможность выделения в конечном детерминированном автомате проходимого подавтомата представляет интерес. Возможность представления проходимого автомата как композиции частичного проходимого подавтомата и нижней границы состояний определяет потребность к выделению в произвольном автомате частичного проходимого подавтомата. Существенным оказывается разрыв контуров в автомате.
Теорема 2.2 определяет варианты нижних границ состояний, возникающих при разрывах контура в диаграмме Мура для автомата. В теореме 2.3. показано, то сильно связный автомат не имеет проходимых подавтоматов. Глава завершается замечанием о построении всех проходимых подавтоматов заданного автомата.
Основные результаты, характеризующие свойства операций объединения и пересечения в классах проходимых и частичных проходимых подавтоматов представлены в третьей главе диссертации.
В теореме 3.1 показана замкнутость класса частичных проходимых подавтоматов относительно операции пересечения и незамкнутость класса по объединению подавтоматов. В примере 3.1 показано, как разрывом контура в автомате может выделяться частичный проходимых подавтомат.
В теоремах 3.2 выявляется свойства фундаментальных характеристик проходимых и частичных проходимых подавтоматов:
верхней границы состояний,
нижней границы состояний,
множества проходимых состояний.
Теорема 3.2 показывает, что ни одна из фундаментальных характеристик не определяет однозначно частичный проходимый подавтомат. Здесь же
устанавливается, что нижняя граница состояний и множество проходимых состояний не определяют однозначно частичный проходимый подавтомат. В теореме 3.2. утверждается, что пары фундаментальных характеристик (верхняя и нижняя границы), (верхняя граница и множество проходимых состояний) однозначно определяют частичный проходимый подавтомат.
В теореме 3.3 показано, то класс проходимых подавтоматов замкнут по операциям объединения и пересечения.
В теоремах 3.4 и 3.5 содержатся правила вычисления верхних и нижних границ состояний для проходимых подавтоматов. Разделены два случая: границы подавтоматов содержатся в границе автомата и границы подавтоматов выделяются в автомате произвольно.
Понятия частичного проходимого и проходимого подавтоматов определены на основе свойств диаграммы Мура. В теореме 3.6 эти свойства конкретизированы как свойства состояний подавтоматов. В теореме 3.7 содержится существенная характеристика строения проходимого подавтомата:
существование у автомата частичного проходимого подавтомата,
существование у автомата рефлексивного (состояния с петлями) изолированного подавтомата,
возможность разложения функций переходов и выходов автомата на специфические части.
Рассмотрен пример (таблица 3.1 и рис.3.4) проходимого автомата с указанием верхней и нижней границ состояний, множества проходимых состояний. Глава 3 завершается методом построения множества всех подмножеств состояний автомата, которые являются нижними границами состояний проходимых подавтоматов.
В главах 1-3 содержится результаты, определяющие свойства частичных проходимых и проходимых подавтоматов, позволяющие выделять их в
12 конечных детерминированных автоматах. Эти результаты также позволяют из подавтоматов класса строить новые подавтоматы того же класса.
В четвертой главе диссертации рассматривается приложение проходимых конечных детерминированных автоматов как моделей технологических процессов. Дается соответствующая интерпретация состояний, входных и выходных сигналов автомата его функций переходов и выходов, процесса функционирования.
Содержится анализ возможности использования понятия -непрерывности Арбиба для усиления характеристик процесса функционирования автомата дополнительной связью состояний автомата.
Проводится анализ последовательностей входных сигналов автомата, последовательностей выходных сигналов автомата и последовательностей состояний автомата с целью их согласования с представлением дефектов состояний технологических процессов и дефектов технологических операций. Сделаны формальные постановки задач проверки диагностируемости состояний технологического процесса и технологических операций. Здесь используется аппарат построения предикатов и проверки выполнимости предикатов.
Теоремой 4.1 показывается алгоритмическая разрешимость предикатов, которые представляют решения задач.
В этой главе приводятся разработанные методы:
Метод проверки диагностируемости технологического процесса,
Метод проверки контролепригодности технологического процесса,
Метод анализа и получения диагностической информации для контроля и диагностирования технологических процессов.
Для каждого метода используемые в методе процедуры представлены расчетными формулами и диаграммами связи действий, то есть, методы формализованы и завершают исследования, включающие
- постановку проблемы,
разработку математических моделей,
выяснение свойств моделей и процессов, порождаемых моделями,
постановку задач и разработку методов их решения.
Конечный детерминированный автомат и классификация подавтоматов. Проходимые автоматы
В работе Ч.Хоара [78] исследуются взаимодействующие последовательные процессы. Как отмечает автор «основная идея заключается в том, что эти системы (вычислительные системы, непрерывно действующие и взаимодействующие со своим окружением - пояснение соискателя) без труда можно разложить на параллельно работающие подсистемы... (с.9).» Это другая постановка задач, отличная от цели диссертации. Имеется совпадение в некоторых исследуемых вопросах, например, Ч.Хоар рассматривает свой подход, как основу для избежания таких ошибок как зацикливание ([78], с. 10.). Им даются «строгие определения понятия процесса и способов построения процессов ([78], с. 10.)». Сравнение подхода к анализу процессов, проведенного Ч.Хоаром, и подхода, принятого в диссертации, показывает их существенное различие. Более четко позиция Ч.Хоара представлена в его понимании «процесса как математической абстракции взаимодействия системы и ее окружения ([78], с. 14).» В диссертации технологический процесс предполагается полностью определенным свойствами конечного детерминированного автомата, являющегося математической моделью возможных вариантов отношений ингредиентов и технологических операций.
Каждый реальный ингредиент (работник и т.п.) имеет интервал времени, в течение которого он существует и эффективно участвует в процессе производства. В автоматной модели этот интервал стянут в точку и, следовательно, стянут в точку и, следовательно, совмещен во времени с другими ингредиентами. Аналогичное предположение принимается для технологических операций и является достаточно распространенным («Считается, что конкретное событие в жизни объекта происходит мгновенно, т.е. является элементарным действием, не имеющим протяженности во времени (Ч.Хоар, [78], с. 18)». Этим предположением реальная протяженность существования (или использования) ингредиентов и действия технологических операций исключается из рассмотрения и основным полагается следование операций относительно принятого абстрактного времени.
Исследованию и представлению математическими средствами производственных процессов посвящено большое количество статей и монографий. В работе Н.П. Бусленко ([18], глава VIII) рассматривается моделирование производственных процессов, где анализируются дискретные и производственные процессы и разрабатываются средства формализации производственных операций и предметов их воздействия. Основу составляют математические модели, определяющие связи числовых параметров операции, полуфабрикатов, деталей, узлов и т.п. В диссертации числовые параметры не являются объектами рассмотрения, они поглощаются обобщениями, после которых от реальных характеристик остается только факт их неявного наличия.
Для решения вопросов анализа, синтеза, оптимизации и распознавания траекторий состояний, технологических процессов одного свойства предшествования и следования во времени технологических операций недостаточно. В связи с этим отношение порядка предшествования и следования во времени для операций дополняется отношением «близости» между состояниями технологического процесса.
В основу идей и средств, с помощью которых состояния технологических процессов характеризуются как «близкие» (допускающие переход технологического процесса из одного состояния в другое) или как не допустимые для непосредственного следования, состояний друг за другом, в диссертации взяты работы М. Арбиба [1], [2] и [5]. Идея М. Арбиба построить дискретный аналог непрерывности на базе отношения толерантности, то есть, рефлексивного и симметричного отношения, может быть использована для определения близких, допустимых переходов, состояний. Для этого в диссертации рассматриваются бинарные отношения толерантности р1,р2,...,ра , каждое из которых задается пары «близких» для переходов состояний. Если, например, бинарное отношение р{ вида p SxS содержит пару {pv,sM)eplt то изменение в технологическом процессе состояния sv на состояние s допустимо по смыслу технологических действий. Набор бинарных отношений р1,р2,...,ра вида PidSxS, где 1 / со, имеющих содержательную интерпретацию как «близость» состояний (набор ингредиентов) технологических процессов, позволяет давать достаточно глубокую и полную характеристику технологическим схемам. Используя бинарное отношение на множестве состояний s технологического процесса можно, например, задавать «близость» состояний, которые только по одному из градиентов различаются количественно. Переходы между такими состояниями определяются возможностями транспортных средств и наличием должного количества ингредиента для транспортировки. Покрытие технологической схемы бинарными отношениями, характеризующими содержательные варианты «близости» состояний, принципиально углубляет возможности использования предлагаемого формализма для решения задач поиска, анализа, оптимизации и распознавания стратегии управления производством.
Одним из основных свойств автоматов, выбираемых в качестве математических моделей технологических процессов является проходимость состояний и наличие фискальных состояний.
Проходимые и частичные проходимые подавтоматы, верхние и нижние границы состояний
Оба варианта проходимых подавтоматов имеют интерпретацию при их рассмотрении в качестве математических моделей технологических процессов: - нижняя граница Sa содержит состояния, представляющие такие наборы ингредиентов, которые соответствуют окончанию специфических технологических операций (например, окончанию транспортных операций, окончанию последовательности операций сборки, окончанию специфической последовательности операций обработки и т.п.); - нижняя граница Sa выделяет частичный проходимый подавтомат (при заданной верхней границе Sa) при выборе подавтомата, для преобразования подавтомата, для анализа автомата и т.п. В связи с тем, что проходимые подавтоматы, определены только на основе свойств функции переходов 8 в дальнейшем при изучении таких подавтоматов будут использоваться структуры A = (S,X,S) и а = (Sa,Xa,Sa). Пусть A = (S,X,S) - конечный детерминированный автомат (без выходов) и a = (Sa,X,Sa), b = (Sb,X,Sb) - его проходимые подавтоматы. Если Sa о Sb = 0, то совмещение подавтоматов айв новый подавтомат образует подавтомат C = (SauSb,X,Sau5b),y которых Sc=s"vSb, Sc=SauSe, Jc = Sa u SC. В случае, когда подавтоматы а и Ь имеют множества входных сигналов Ха и Хь, где Ха Xbi подавтомат с оказывается частично определенным и некоторые математические процедуры (например, умножение матриц при матричном задании подавтоматов) выполняются с дополнительными условиями и ограничениями. Предположим, что для подавтоматов a = {Sa,X,Sa) и b = (Sb,X,Sb) автомата A = (S,X,S), выполняется условие Sa nSb =0. Рассмотрим возможные отношения границ и множеств неграничных состояний подавтомата, порождаемые этим неравенством. Систематизацию действий по анализу осуществим с помощью таблицы. Таблица 2.1. Варианты связей характеристических множеств состояний двух подавтоматов перенумерованы клетки и номер п, 1 , п , 9, обозначает вариант анализа для случая непустого пересечения множества строки и множества столбца таблицы. (Например, число 6 обозначает следствие, получаемое из неравенства SanSb 0). Проходимый подавтомат выделяется в структуре автомата на основе определения верхней и нижней границ состояний. Границы являются подмножествами, которые могут при некоторых условиях расширятся. Взаимосвязи нижних, верхних границ и неграничных состояний оказываются сложными. При совмещении подавтоматов в новый подавтомат возникают ситуации, для разрешения которых должны приниматься дополнительные соглашения. На рисунке 2.1 изображен случай, когда имеется пересечение верхней границы одного подавтомата с множеством неграничных состояний другого подавтомата.
Пересечение верхней границы одного подавтомата с множеством неграничных состояний другого подавтомата. Для верхней границы Sb = «, и Д подавтомата Ъ выполняется отношение fiaSa, а для нижней границы Sa=a2\j/32 подавтомата а отношение a2aSb. Примем соглашение, что множество /?, и множество а2 исключаются соответственно из верхней границы и нижней границы подавтомата с с множеством состояний Sc=Sa(jS„. В случае, когда Sbr\Sa =а и а 0, множество а исключается и множество граничных состояний автомата с (рис. 2.2)
Случай пересечения нижней и верхней границ состояний. Для конечного детерминированного автомата A = (S,X,S) нижняя граница состояния SA определяется однозначно с помощью следующих двух процедур:
Операции объединения и пересечения проходимых и частичных проходимых подавтоматов
Проходимые и частичные проходимые подавтоматы обладают свойством, имеющим важную прикладную интерпретацию: при функционировании такие подавтоматы не имеют возвратов в пройденные состояния. Нижние границы состояний таких подавтоматов интерпретируются как обозначение сечения, например, в диаграмме Мура, автомата, отделяющего свойство проходимости состояний от возможных их повторений (для частичного проходимого подавтомата) или от перехода в повторы состояний, только обозначающих . завершение этапа функционирования.
Несмотря на кажущуюся простоту строения таких автоматов, они обладают рядом специфических свойств, проявляющихся в свойствах взаимосвязей верхних и нижних границ состояний подавтоматов, множеств (внутренних) проходимых состояний.
Проходимые и частичные проходимые подавтоматы являются частями целого, то есть, частями автоматов. В связи с этим определяющими являются вопросы как из частей образуется целое и как в целом выделять части с рассматриваемым свойством. Автоматы являются теоретико-множественными структурами, так как образованы из трех множеств S,XuY и отношениями на них. Функции переходов 8 и функции выходов Л и/л как отношения могут рассматриваться в виде аргументов для теоретико-множественных операций объединения "U " и пересечения "П Эти операции могут быть взяты за основу для декомпозиции автомата в подавтоматы и композиции подавтоматов. Существенными являются отношения между границами состояний подавтоматов.
Теорема 3.1. Пусть А= (S,X,5) - конечный детерминированный автомат и a = (Sa,X,5a), b = (Sb,X,Sb) - частичные проходимые подавтоматы автомата А. Тогда 1) подавтомат ,=(5,(1 , , 0) является частичным проходимым подавтоматом; 2) подавтомат В2 = (Sa\JSb,X,8a\JSb) может содержать циклы, то есть, не являться частичным проходимым подавтоматом. Доказательство. Очевидное включение 6в Г\5ьс5а показывает, что функция переходов подавтомата В1 получена ограничением функции 8а (ограничением функции 8Ь) и, следовательно, возникновение циклов состояний у подавтомата 5, невозможно. Покажем, что наличие у частичных проходимых подавтоматов а и Ъ нижних границ состояний, из которых у автомата А есть переходы, а у подавтоматов а и Ъ переходы не определены (по построению подавтоматов а и Ъ ). В подавтомате В2 могут возникнуть циклы в диаграмме Мура. границ частичных проходимых подавтоматов характеризуются так же, как и у проходимых подавтоматов. Верхняя граница состояний Sa частичного проходимого подавтомата a = (Sa,X,Sa) автомата A = (S,X,S) определяется как подмножество W cSa, обладающее следующими свойствами: Свойство 1 исключает переходы между состояниями, принадлежащими верхней границе состояний. Отсутствие переходов в состояния, принадлежащие верхней границе состояний, представлено свойством 3. Достижимость каждого состояния se Sa-W из некоторого состояния, принадлежащего верхней границе состояний, определена свойством 2. Абсолютная верхняя граница состояний для подавтоматов автомата A = (S,X,5) определяется как множество состояний UA, где Множество UA при табличном задании автомата А выделяется, как множество таких состояний, которые отсутствуют во внутренних клетках таблицы для функции 8. В общем случае верхняя граница состояний частичного проходимого подавтомата не определяет однозначно подавтомат, так как нижняя граница состояний частичного проходимого подавтомата определяется двумя свойствами, которые могут выполняться для нескольких множеств состояний. Первое свойство - выбор нижней границы не должен допускать контуров в диаграмме Мура для подавтомата. Второе свойство состояний, определённых как элементы нижней границы частичных проходимых подавтоматов, не иметь переходов в состояния подавтомата. Эти свойства не определяют однозначно частичный проходимый подавтомат.
Приложение проходимых и частичных проходимых подавтоматов
При построении автоматной модели технологических процессов предполагается, что состояние s(t) технологического процесса в абстрактный момент времени t является полной (относительно принятого уровня точности модели) характеристикой. В связи с этим, как уже отмечалось, повторный переход технологического процесса в пройденное состояние не соответствует нормальному протеканию процесса. Смежные технологические операции могут принадлежать одному и тому же классу однотипных операций (класс транспортных операций, класс операций сборки, класс операций обработки изделий и т.п.). Такие операции можно рассматривать как «близкие» операции. К классу «близких» операций можно относить также операции, для которых переход от одной операции к другой требует минимальных затрат времени и других ресурсов.
В работах Арбиба [12], [13], [14] рассматривается дискретный аналог числовой непрерывности, базирующийся на отношении толерантности. Такое отношение определяется свойствами рефлексивности и симметричности. Свойство симметричности для технологических операций а. и cDj требует содержательной интерпретации равнозатратного расходования ресурсов для подготовки операции со} после операции а, и для подготовки операции щ после операции со j. Это соответствует содержательному представлению о «переналадке» средств при переходах между технологическими операциями со,. и a j. Следовательно, формальное задание с помощью толерантного отношения следования технологических операций может быть использовано для минимизации расхода ресурсов подготовки операций. Пусть для множества технологических операций Q имеется разбиение на непустые подмножества Q,,Q2,...,QA и заданы бинарные отношения толерантности р.,\ j k, вида р. = Qy хQy. Каждому технологическому процессу v , содержащему операции из множества операций Q, соответствует последовательность классов технологических процессов в форме конечного детерминированного автомата A = {S,X,Y, S,X) основывается на сопоставлении состояниям технологического процесса состояний автомата, а технологическим операциям входных сигналов автомата. Это означает, что последовательности технологических операций coh, a)h ок соответствует последовательность входных сигналов хл,х ,...,хл определяемая некоторым взаимооднозначным отображением Ч/: Q -» X. Задачи анализа и синтеза технологических процессов, диагностирования и оптимизации процессов могут быть поставлены как задачи в понятиях теории автоматов. Математической моделью производства является автомат A = (S,X,Y,S,X), изготовлению конкретного изделия при конкретных начальных ингредиентах S0 соответствует инициальный автомат {A,S0), а конкретный технологический процесс определяется схемой:
Существуют методы и средства управления технологическими процессами, включая контроль за качеством технологического процесса и диагностирование нарушений и дефектов процесса. Соответствующие им задачи также могут быть сформулированы на языке теории экспериментов с конечными детерминированными автоматами. Выделим три типа задач, которые можно отнести к задачам технологического диагностирования технологических процессов в целом. Первый тип задач связан с нарушением технологического процесса, когда в некоторый момент времени t состояние технологического процесса не соответствует предлагаемому. Это может быть в случаях, определяемых влиянием внешней среды, дефектами используемых ингредиентов, проявлением неучтенных факторов технологического процесса и т.д.
Второй тип задач выделим как задачи, связанные с неправильными технологическими операциями: неисправности в технологических средствах, ошибки в планировании технологического процесса, нарушение режима реализации операции и т.д. В третьем типе задач будем предполагать совмещение задач первого и второго типов. Автоматная модель позволяет формализовать постановки задач указанных типов.
На содержательном уровне задача диагностирования состояний технологического процесса заключается в том, чтобы по наблюдаемым признакам реального технологического процесса, определить, произошла ли замена в некоторый момент времени t одного состояния на другое, которое не предусмотрено математической моделью технологического процесса. В соответствии с принятой интерпретацией конечный детерминированный автомат Л = (5,Х,У,5,Л), его начальное состояние .s(o) = .s0 и последовательность входных сигналов p = xix,xh...x,t определяют технологический процесс как систему четырех компонентов:
