Cтраница 3
Формальные операции над абстрактными автоматами, заданными в виде графоидов или матриц соединений, и их свойства, будут описаны ниже, а в этом параграфе подробнее остановимся на содержательном смысле операций и покажем, как связаны отображения, индуцируемые результирующими автоматами с отображениями, индуцируемыми исходными автоматами. [31]
С каждым МП-автоматом ассоциируется абстрактный автомат, состояниями которого являются пары: состояние управления - наполнение магазина. Языки из класса DET0 являются ультраконечными. Пусть DET обозначает класс всех детерминированных КС-языков. Нетрудно доказать, что класс DET замкнут относительно операции теоретико-множественного дополнения. Напомним, что автомат называется d - допускающим, если он не может совершать s - переходы в заключительных состояниях. Также нетрудно проверить, что для детерминированного МП-автомата с ограниченным наполнением магазина в заключительных конфигурациях существует эквивалентный детерминированный d - допускающий МП-автомат с ограниченным наполнением. [32]
Как указывалось выше, абстрактный автомат рассматривается нами как устройство для реализации автоматных отображений. [33]
Покажем теперь, что любой абстрактный автомат, разложимый по операции умножения X, разложим также и по операции умножения, иначе говоря, парал лельная декомпозиция автоматов с разделением входов является частным случаем параллельной декомпозиции автоматов с общим входом. [34]
Параллельная декомпозиция соответствует разложению абстрактного автомата в произведение или сумму двух или большего числа абстрактных автоматов, каждый из которых проще, чем исходный автомат. В зависимости от разложения автомата по операции умножения или суммирования можно говорить о параллельной одновременной и о параллельной неодновременной ( no - очередной ] декомпозиции абстрактных автоматов. [35]
Все перечисленные случаи декомпозиции абстрактных автоматов представляют собой так называемые чистые случаи декомпозиции автоматов. Таких автоматов, которые раскладываются только в параллельную или в последовательную или даже в смешанную работу автоматов, незначительное число по сравнению с множеством автоматов, которые не представимы параллельной, последовательной или смешанной декомпозицией. В связи с этим вводится понятие общей декомпозиции абстрактного автомата, которая понимается как представление абстрактного автомата совместной работой элементарных абстрактных автоматов со связями между ними. Общая декомпозиция соответствует разложению абстрактного автомата в композицию двух или большего числа абстрактных автоматов. Заметим, что в качестве элементарных абстрактных автоматов могут быть выбраны абстрактные автоматы с любым числом состояний, а параллельную, последовательную и смешанную декомпозиции абстрактных автоматов можно рассматривать как частные случаи общей декомпозиции автоматов. [36]
При определении закона функционирования абстрактного автомата предполагалось, что порядок переключения состояний задается входными сигналами. Автомат переключается в следующее очередное состояние, если входные переменные, входящие в некоторую конъюнкцию, принимают значения, обращающие конъюнкцию в единицу. Входные сигналы микропрограммного автомата в большинстве случаев определяются состояниями операционных устройств, и порядок их изменения не связан с порядком следования микроопераций. Для задания моментов перехода в автомате необходимо использовать другие сигналы, определяющие ход машинного времени. [37]
В качестве главных свойств абстрактных автоматов выступают так называемые поведения. Выделяются следующие основные типы поведений автоматов. [38]
Рассмотрим матричный способ задания абстрактных автоматов. [39]
Состояние qi e Q абстрактного автомата называется достижимым, если оно совпадает с начальным состоянием или если существует такое достижимое состояние qk Q и такая буква входного алфавита Xi X, что qi ( Xi) e Fqh. В противном случае состояние qi называется недостижимым. Абстрактный автомат, все состояния которого достижимы, называется связным. [40]
В итоге построена декомпозиция абстрактного автомата Мили А на три элементарных абстрактных автомата Ai A2i Azz, показанных соответственно на рис. 8.10, а, б, в, каждый из которых содержит два состояния. [41]
VIII рассмотрена оптимальная декомпозиция произвольных абстрактных автоматов на элементарные абстрактные автоматы, в качестве которых могут быть выбраны любые абстрактные автоматы с простым числом состояний, в частности, автоматы с двумя состояниями. В результате декомпозиции получаем матрицы соединений элементарных абстрактных автоматов, совместная работа которых эквивалентна функционированию исходного абстрактного автомата. Получение функций возбуждения и выходов конкретных элементарных автоматов, как известно, является заключительным этапом структурного синтеза, так как по ним однозначно определяется структурная схема автомата. Поэтому структурный синтез автоматов, по сути дела, выносится на абстрактный этап и сводится к оптимальной декомпозиции автомата. [42]
Ниже будет показано, что любой абстрактный автомат может быть построен из элементарных абстрактных автоматов, в качестве которых можно выбрать автоматы с любым числом состояний, используя две формальные операции - умножение автоматов и запреты переходов. С содержательной точки зрения это означает, что произвольный автомат может быть представлен совместной работой более простых автоматов с некоторым числом связей между ними, при помощи которых реализуются запреты переходов. Приводится алгоритм декомпозиции произвольного абстрактного автомата на элементарные абстрактные автоматы, который соответствует представлению произвольного автомата композицией элементарных абстрактных автоматов. Решается задача оптимальной декомпозиции, при которой число связей между элементарными автоматами, представляющими работу произвольного автомата, минимально. [43]
Задачи параллельной и последовательной декомпозиции абстрактных автоматов можно сформулировать как задачи разложения абстрактных автоматов по операциям умножения, суммирования и суперпозиции автоматов по аналогии с графами, как это было сделано в гл. Поэтому изучение свойств формальных операций над абстрактными автоматами, задаваемых на языке теории графов, имеет большое значение в теории автоматов. [44]
Задача проектирования формулируется как перевод абстрактного автомата Г из некоторого исходного состояния ( SB) a в состояние ( SB) h удовлетворяющие требования, предъявляемые к спроектированному изделию, например 100 % - и реализации всех соединений в соответствии с ЭЗ, при заданном конструктиве ПП и известных технологических ограничениях. Это осуществляется выбором входной последовательности из IS, переходящей автоматически из ( SB) 0 в ( SB) f за минимально возможное время. [45]