Математическая теория систем. Математические основы теории систем
 Скачать 2.07 Mb.
|
|
R E S Операции умножения и суммирования легко обобщить на случай n автоматов. Для задания операции суперпозиции будем полагать, что алфавит со- стояний первого автомата совпадает с входным алфавитом второго авто- мата, т.е. ( ) 1 , , , A X Q q Q = ∈ P и ( ) 1 , , , B Q V v V = ∈ S , поскольку рассмат- риваются автоматы без выходов. Вероятностный автомат C=(X,W, w 1 ∈W, R) будет являться суперпозицией автоматов А и В (С=А∗В), если W=Q×V; (2.4.49) 1 2 1 2 ( ) ( ) ( ) ( ) ( ) ( ) ... ( ) , n k k k n i k i q q q x q x q x q k q x q k i = × ∪ × ∪ ∪ × = = × R P S P S P S P S ∪ ∪∪ (2.4.50) где i∈{1, 2, … n}, w 1 =( q 1 , v 1 ), а ( ) i k q x P – матрица, полученная из стохасти- ческой матрицы k x P заменой всех столбцов, отличных от q i , нулевыми столбцами. По-прежнему в выражении (2.4.50) подразумевает прямое произведение соответствующих матриц. Пример 2.24. Пусть даны автоматы ( ) 1 , , , A X Q q Q = ∈ P и ( ) 1 , , , B Q V v V = ∈ S . 1 2 2 1 1 2 3 3 3 3 , 1 3 1 1 4 4 2 2 x x = = P P ; 1 2 1 1 1 0 2 2 , 1 4 1 3 5 5 4 4 q q = = S S 109 Найдем автомат ( ) 1 , , , C X W w W = ∈ R , равный суперпозиции автома- тов А и В ( C A B = ∗ ). Согласно формуле (2.4.50), находим 1 2 1 1 1 1 2 ( ) ( ) 2 1 1 1 1 0 0 0 3 3 2 2 1 4 1 3 1 3 0 0 5 5 4 4 4 4 q q x x q x q = × ∪ × = × ∪ × = R P S P S 2 1 1 2 1 1 0 0 0 0 0 0 3 6 6 3 6 6 2 8 1 1 2 8 1 1 0 0 0 0 15 15 12 4 15 15 12 4 3 3 1 3 3 1 0 0 0 0 0 0 8 8 4 8 8 4 1 1 3 9 1 1 3 9 0 0 0 0 20 5 16 16 20 5 16 16 = ∪ = 1 2 2 2 1 2 2 ( ) ( ) 1 2 1 1 1 0 0 0 3 3 2 2 1 4 1 3 1 1 0 0 5 5 4 4 2 2 1 1 1 0 0 0 0 0 3 3 3 1 4 1 1 0 0 0 0 15 15 6 2 1 1 1 0 0 0 0 0 2 4 4 1 2 1 3 0 0 0 0 10 5 8 8 q q x x q x q = × ∪ × = × ∪ × = = ∪ R P S P S 1 1 1 0 3 3 3 1 4 1 1 15 15 6 2 . 1 1 1 0 2 4 4 1 2 1 3 10 5 8 8 = С содержательной точки зрения операции над вероятностными автома- тами означают то же самое, что и над детерминированными автоматами. 2.5 Структурное исследование автоматов Переходим теперь к внутреннему устройству автоматов и к задачам, связанным с их внутренним устройством, то есть к структурному уров- 110 ню. Здесь, как и на абстрактном уровне, главными задачами исследова- ния являются анализ и синтез автоматов. 2.5.1. Комбинационные логические автоматы Для дальнейшего изложения нужно дать несколько определений. Автомат называется комбинационным, если для любого входного символа х∈Х и любых состояний , i j q q Q ∈ выполняется равенство ( ) ( ) , , i j q x q x λ = λ , то есть выход автомата не зависит от его состояния и определяется толь- ко его входом. В таком автомате все состояния эквиваленты и минималь- ный комбинационный автомат имеет только одно состояние. Функция переходов в нем вырождена, а поведение такого автомата задается функ- цией выходов с одним аргументом λ( x i )= y i . Если входной алфавит автомата состоит из 2 m двоичных векторов длины m, а выходной – из 2 n двоичных векторов длины n, то такой авто- мат называется логическим. Понятно, что автомат с произвольными ал- фавитами можно свести к логическому автомату соответствующим коди- рованием его алфавитов. Таким образом, комбинационный логический автомат – это автомат, функция выхода которого – это система n логиче- ских функций от m переменных: ( ) ( ) ( ) 1 1 1 2 2 2 1 2 1 2 , ,... ; , ,... ; , ,... , m m n n m y x x x y x x x y x x x = λ = λ = λ (2.5.1) где i x – логическая переменная (i-я компонента вектора х длины m), а y j – также логическая переменная ( j-я компонента вектора удлины n). Эту же систему уравнений (2.5.1) можно записать и в компактной форме y=Ф(х), где Ф – упорядоченная совокупность функций λ i Логический комбинационный автомат можно представить рис. 2.20. 111 Рис. 2.20. Функциональная схема комбинационного автомата Удобно рассматривать х 1 , х 2 , … х m как входные, а y 1 , y 2 , … y n – как вы- ходные полюсы автомата. Считая, что каждый полюс может находиться в состоянии 0 или 1, приходим к выводу, что в комбинационном логиче- ском автомате каждой комбинации состояний входных полюсов вполне однозначно соответствует комбинация состояний выходных полюсов. Отсюда и название – комбинационный. Система уравнений (2.5.1) и схема на рис. 2.20 – это функциональная модель автомата. 2.5.2. Постановка задач синтеза и анализа на структурном уровне Структурная схема автомата, т. е. его структурная модель, показыва- ет, как он устроен, из каких элементов состоит и как эти элементы соеди- нены (связаны) между собой. Структурная модель дискретного автомата отражает схему реальной дискретной системы, и элементы автомата ставятся в соответствие неко- торым реальным конструктивным элементам. Основное содержание теории автоматов на структурном уровне – это исследование соотношения между функциональной моделью и структур- ной моделью. И по-прежнему здесь возникают две задачи: задача анализа и задача синтеза. Задача анализа – это получение функциональной модели по заданной структурной. Синтез – обратная задача: нахождение структурной модели по заданной функциональной. Вторая задача значительно сложнее, так как ее решение не единственно и среди многих возможных решений требуется выбрать оптимальное (наилучшее) в каком - то смысле. По- скольку задача синтеза более трудная, то и большая часть сил и времени на структурном уровне тратится на решение именно этой задачи. λ 1 λ 2 λ n … x 1 x 2 x m … y 1 y 2 y n … Ф x y 112 Исходная для синтеза информация задается следующим образом. Во- первых, описывается функциональная модель. Во-вторых, указывается из каких элементов нужно автомат синтезировать, то есть задается эле- ментный базис. В-третьих, определяется синтаксис структур, то есть формулируются правила взаимных соединений элементов, выделяющие из всевозможных структур класс допустимых (или правильных). Синтак- сис играет компенсирующую роль: заменяя реальные элементы абстракт- ными, мы допускаем некоторую идеализацию, которая, тем не менее, оказывается допустимой, пока синтезированные из данных элементов структуры являются правильными, т. е. удовлетворяющими синтаксису. Однако как только мы переходим к рассмотрению неправильных струк- тур, может появиться нежелательный эффект идеализации, то есть пове- дение реального устройства может существенно отклониться от поведе- ния его абстрактного двойника (модели). Будем считать, что элементный базис в совокупности с правилами со- единения элементов образуют базис синтеза или просто базис. 2.5.3. Элементный базис В элементный базис могут входить самые разнообразные элементы, которые сами являются простейшими автоматами. Выбор их диктуется как уровнем развития технологии производства реальных элементов, так и требованиями, предъявляемыми к базису со стороны методов синтеза. Основные требования, которым должен удовлетворять элементный базис – это полнота и эффективность. Базис называется полным относительно некоторого класса автоматов, если в нем может быть синтезирован любой автомат этого класса. Требование эффективности достаточно расплывчатое, и его можно сформулировать примерно так: более эффективным будет базис, синте- зируемые в котором структуры будут в каком-то смысле лучшими (про- ще, дешевле, надежнее и т.д.). При определении эффективности базиса нужно учитывать как свойства реальных элементов, так и применяемые методы синтеза: для одних базисов эти методы могут быть развиты силь- нее, для других – слабее. Какие же элементы могут входить в базис? Это, во-первых, логиче- ские элементы и, во-вторых, − элементы памяти. Логическими элементами называются элементарные комбинационные логические автоматы, функциональные свойства которых представляют- ся достаточно простыми логическими функциями: дизъюнкцией, конъ- 113 юнкцией, отрицанием, функцией Шеффера, импликацией, стрелкой Пир- са и т.д. Как правило, ограничиваются элементами И (конъюнкция), ИЛИ (дизъюнкция), НЕ (отрицание), И-НЕ (штрих Шеффера), ИЛИ-НЕ (стрел- ка Пирса) и многовходовыми аналогами соответствующих элементов. Элементами памяти служат некоторые элементарные логические ав- томаты. Наиболее простые и распространенные из них – это элемент за- держки и триггер. Элемент задержки можно рассматривать как элементарный синхрон- ный автомат, функции которого сводятся к задержке на один такт значе- ния одной логической переменной. То есть значение выхода в момент времени t равно значению входа в момент времени t–1. Схематичное изображение и автоматная таблица элемента задержки приведены на рис. 2.21. 0 1 0 0,0 1,0 1 0,0 1,1 Рис. 2.21. Элемент задержки Триггер можно представить себе как асинхронный автомат с двумя внутренними состояниями, которые могут фиксироваться и в каждое из которых при определенных условиях автомат можно перевести. Из раз- личных вариантов автоматов, удовлетворяющих этим условиям, остано- вимся на автомате, графическое изображение и автоматная таблица кото- рого приведены на рис. 2.22. 00 01 10 11 0 0,10 1,01 0,10 1 1,01 1,01 0,10 − − Рис. 2.22. Триггер y(t)=x(t–1) x(t–1) 01 q п q ∧ p п p ∧ 114 Входом и выходом такого автомата являются двоичные векторы дли- ны 2. Первые компоненты этих векторов проиндексированы на рис. 2.22 буквой ∧ (левые полюса), а вторые – буквой п (правые полюса). В связи с тем, что поведение триггера при комбинации 11 на входе не определено, использовать эту комбинацию на входе не рекомендуется. 2.5.4. Автоматные сети Возьмем некоторую совокупность автоматных элементов (безразлич- но, разных или одинаковых). Выделим из множества входных полюсов P всех элементов некоторое подмножество Х⊂P, а из множества Q всех выходных полюсов некоторое подмножество Y. Отобразим разность P\X в Q и будем считать, что это отображение задает множество связей меж- ду элементами множества P с одной стороны и множества Q – с другой. Полученную таким образом структуру будем называть сетью, элементы множества Х – ее входными полюсами, а элементы множества Y – ее вы- ходными полюсами. При небольшом числе элементов в сети можно поль- зоваться графическим представлением, в иных случаях удобнее задавать сеть в форме некоторого списка, содержащего перечень элементов и свя- зей между ними. Очевидно, что структуру любого автомата можно представить неко- торой сетью. Обратное, вообще говоря, неверно. Для подтверждения это- го факта достаточно рассмотреть классический пример сети, изображен- ной на рис. 2.23, а. Рис. 2.23. Пример сети Для х=0 при определении значения y возникает противоречие типа “ес- ли y=0, то y=1, если y=1, то y=0”. Это противоречие можно разрешить, если добавить в обратную связь, например, блок задержки (рис. 2.23, б). В этом случае сеть можно рассматривать как синхронный автомат, в котором при х=0 переменная y принимает последовательно значения 1, 0, 1, 0, …. ∨ х y а) ∨ х y б) 115 Это пример показывает, что сети из логических элементов, содержа- щие контур обратной связи без задержек, могут не иметь конкретной ав- томатной интерпретации. В то же время обратные связи с элементами памяти являются мощным средством построения автоматов. В связи с этим будем рассматривать только правильные сети, то есть такие, кото- рые можно рассматривать как структуры автоматов. Правильная синхронная сеть – это сеть из логических элементов и элементов задержки (назовем и те и другие для краткости блоками), если: 1) к каждому входному полюсу блока присоединен не более, чем один выходной полюс (однако допускается присоединение выходного полюса блока к нескольким входным полюсам, то есть разветвление выходов); 2) в каждом контуре обратной связи, то есть в каждом цикле, есть хотя бы один элемент задержки. Входными полюсами правильной синхронной сети будут полюса, не присоединенные ни к каким выходным полюсам блоков, а выходными полюсами – только те, которые не подсоединены ни к каким входным полюсам. Оказывается, что любой автомат можно представить правильной син- хронной сетью. Об этом говорит следующая теорема. Теорема 2.5.1. Любой конечный автомат при любом двоичном коди- ровании его алфавитов X, Q, Y может быть реализован правильной син- хронной сетью из логических комбинационных автоматов и двоичных задержек, причем число задержек не может быть меньше log 2 Q. Доказательство . Действительно, автомат с произвольными функци- ями q(t+1)=δ(q(t), x(t)), y(t)=λ(q(t), x(t)) может быть представлен сетью на рис. 2.24. Рис. 2.24. Автомат, представленный правильной синхронной сетью λ δ D x(t) y(t) q ' ( t) q(t) 116 Здесь блок λ – комбинационный автомат с входным алфавитом X×Q и выходным алфавитом Y, вычисляющий функцию y(t)=λ(q(t), x(t)), блок δ – комбинационный автомат с тем же входным алфавитом и выходным алфавитом Q. Блок D – это блок, задерживающий поступающие на его вход сигналы на один такт. Его можно представить как автомат Мура, входной и выходной алфавиты которого совпадают и равны Q, алфавит состояний R={r 1 , r 2 , ... r n } имеет ту же мощность, что и Q,λ D ( r i )= q i , δ D ( r i , q j )= r j , i, j∈{1,2,…n}. Сигнал q'(t) на выходе блока δ − это вычисленное значение ( ) ( ) ( ) , q t x t δ , которое, будучи задержанным блоком D на один такт, появляется на входах блоков δ и λ в момент времени t+1, то есть ( ) ( ) ( ) ( ) ( ) ' , 1 q t q t x t q t = δ = + . Осталось превратить сеть, изображенную на рис. 2.24, в правильную. Для этого требуется алфавиты X, Q, Y закодировать двоичными набора- ми, число входов и выходов блоков λ, δ и D согласовать с длинами соот- ветствующих наборов, а блок D реализовать параллельным соединением двоичных задержек. Число этих задержек k равно длине двоичного век- тора q, а наименьшая длина этого вектора при двоичном кодировании n состояний составляет log 2 Q, то есть k=log 2 Q. Что и требовалось дока- зать. Существует и обратная теорема. |