Математическая теория систем. Математические основы теории систем
 Скачать 2.07 Mb.
|
|
x такое, что 1 2 ( ( , ), ) ( ( , ), ) S S j S S j q x q x δ δ ≠ δ δ x x . Тогда, учитывая соотношение (2.1.2), будем иметь 1 2 ( , ) ( , ) j j S q x S q x ≠ x x , то есть, 1 2 и j j q q не эквивалентны, что противоре- чит условию. Теперь определим автомат 0 0 0 0 ( , , , , ) S S S S S S X Q Y = δ λ следу- ющим образом: { } 0 1 2 , ,... S k Q C C C = ; для любого C i и любой входной бук- 57 вы х 0 ( , ) S i j C x C δ = , где C j − класс эквивалентности, содержащий состоя- ние δ S ( q ir , x) (q ir ∈C i − любое состояние из класса C i ); 0 ( , ) ( , ) S i S ir C x q x λ = λ Ясно, что автомат 0 S эквивалентен S и по построению не имеет экви- валентных состояний. Покажем теперь, что автомат 0 S минимален. Предположим, что это не так и имеется эквивалентный автомату 0 S автомат 0 S ′ с меньшим чис- лом состояний. Тогда по определению неотличимости для каждого со- стояния 0 S найдется эквивалентное ему состояние 0 S ′ , а поскольку в автомате 0 S ′ состояний меньше, чем в 0 S , то каким-то двум состояниям 0 S окажется эквивалентным одно состояние 0 S ′ . В силу транзитивности эти два состояния 0 S будут эквивалентны, а это противоречит отсут- ствию в 0 S эквивалентных состояний. Следовательно, 0 S минимален. Осталось показать, что любой другой минимальный автомат 0 S ′′ изо- морфен 0 S . Действительно, раз 0 S ′′ минимален, он имеет такое же число состояний, что и 0 S , то есть различным состояниям 0 S соответствуют различные же состояния 0 S ′′ . Это соответствие и есть искомый изомор- физм. Что и требовалось доказать. Только что доказанная теорема, к сожалению, не конструктивна, по- скольку не дает метода нахождения классов эквивалентности. Само опре- деление неотличимости также не дает такого метода, поскольку предпола- гает перебор по бесконечному множеству входных слов. Среди многочис- ленных алгоритмов минимизации наибольшее распространение получил алгоритм Мили, который и приводится ниже (он описан индуктивно). Дан автомат S=(X,Q,Y,δ,λ) с n состояниями. На каждом шаге алгорит- ма строится некоторое разбиение Q на классы, причем разбиение на каж- дом последующем шаге получается расщеплением некоторых классов предыдущего шага. Шаг 1. Два состояния q и q′′′′относим в один класс 1 j C , если и только если для любого x∈X λ(q,x)=λ(q′′′′,x). Шаг i+1. Два состояния q и q′′′′из одного класса , i j C относим в один класс 1, i j C + , если и только если для любого х∈Х состояния δ(q,x) и δ(q ′′′′,x) 58 принадлежат одному и тому же классу C i,l . Если i+1-й шаг не меняет раз- биения, то алгоритм заканчивает свою работу и полученное разбиение является разбиением на классы эквивалентных состояний, в противном случае применяем шаг i+1 к полученному разбиению. Так как на каждом шаге число классов увеличивается (а всего их не более n), то приведенный алгоритм заканчивается не больше, чем за ( ) 1 n − шагов. Нетрудно показать, что алгоритм действительно дает раз- биение на классы эквивалентности. Пример 2.8. Для автомата А с восемью состояниями и двумя выход- ными буквами, заданного табл. 2.13, алгоритм строит следующую после- довательность разбиений: 1-й шаг: {1,5}, {2,3,8}, {4,6,7}, 2-й шаг: {1,5}, {2}, {3,8}, {4,6,7}, 3-й шаг: {1,5}, {2}, {3,8}, {4,7}, {6}, 4-й шаг: {1,5}, {2}, {3}, {8}, {4,7}, {6}. Т а б л и ц а 2 . 1 3 q\x x 1 x 2 x 3 1 4,1 2,2 5,1 2 5,2 1,1 4,2 3 3,2 5,1 4,2 4 5,1 8,2 4,2 5 7,1 2,2 1,1 6 1,1 2,2 4,2 7 5,1 8,2 7,2 8 3,2 5,1 6,2 Последнее разбиение является искомым, т.е. минимальный автомат имеет шесть состояний. Если найденные классы переобозначить, напри- мер, по порядку: {1,5}→1; {2}→2, {3}→3, {8}→4, {4,7}→5, {6}→6, то автоматная таблица минимального автомата будет следующей: 59 q\x x 1 x 2 x 3 1 5,1 2,2 1,1 2 1,2 1,1 5,2 3 3,2 1,1 5,2 4 3,2 1,1 6,2 5 1,1 4,2 5,2 6 1,1 2,2 5,2 2.2.7. Частичные автоматы и их свойства Представим себе, что хотя бы одна из двух функций δ или λ является не полностью определенной, то есть для некоторых пар (состояние-вход) функция перехода или выхода не определена. Это отражается наличием прочерков в соответствующих местах автоматной таблицы или матрицы соединений. В графе переходов, где функция δ не определена, нарушено условие полноты. В таких случаях автомат называется частичным,или не полностью определенным. Для частичного автомата задание функций δ и λ нуждаются в уточнении. Удобно при этом пользоваться значком ≅ : запись А≅Возначает,что либо А и В одновременно не определены, либо определены и равны. Функция перехода ( ) , i q δ x : 1) для каждой входной буквы функция ( , ) j i j x q x δ задана автоматной таблицей, 2) если функция ( ) , i q δ x определена, то ( ) ( ) ( ) , , , i j i j q x q x δ ≅ δ δ x x ; 3) если функция ( ) , i q δ x не определена, то ( ) , i j q x δ x не определена для всех x j . Выходная функция ( ) , i q λ x : ( ) ( ) ( ) , , , i j i j q x q x λ ≅ λ δ x x Автоматный оператор ( ) , i j S q x : 60 1) ( ) ( ) , , i j i j S q x q x = λ (если функция ( , ) i j q x λ не определена, то зна- чение ( , ) i j S q x – это прочерк); 2) ( ) ( ) ( ) ( ) ( ) , , , , , если , i j i i j i S q x S q q x q = λ δ δ x x x x определена. В случае если не определена ( ) ( ) , , i j q x λ δ x , справа от ( ) , i S q x ставится прочерк; 3) если не определена функция ( ) , i q δ x , то не определено и отобра- жение ( ) , i j S q x x Отсюда видна неравноправность функций δ и λ: если δ не определена на слове x, то она не определена и на всех его продолжениях, а для функ- ции λ это не обязательно. На графе это наглядно видно: если функция ( ) , i q δ x не определена, то это значит, что не определен путь x из верши- ны q i , поэтому не ясно, как его продолжить. Если же ( ) , i q δ x определена, следовательно, определен путь x из вершины q i , то, идя по этому пути, можно прочесть и выходное слово (возможно, с прочерками там, где функция выхода не определена). Входное слово x , для которого автомат- ное отображение ( ) , i S q x определено, называется допустимым для q i Таким образом, отображение, индуцируемое частичным автоматом, явля- ется не чем иным, как частичным отображением, областью определения которого является множество допустимых слов данного автомата. Понятие неотличимости для частичных автоматов также нуждается в корректировке. Наиболее простое обобщение этого понятия следующее. Состояния q i автомата S и r j автомата Т называются псевдонеотличимы- ми, если для любого слова x ( ) ( ) , , i j S q T r ≅ x x , то есть если области определения операторов S и Т совпадают и в этих областях q i и r j эквива- лентны. Автоматы S и Т псевдонеотличимы, если для любого состояния S найдется псевдонеотличимое состояние Т и наоборот. Достоинство тако- го определения в том, что оно совпадает с обычным определением неот- личимости для вполне определенных автоматов и, кроме того, является отношением эквивалентности. Недостаток же этого определения в том, что оно искусственно сужает рассматриваемые классы псевдонеотличи- мых автоматов, требуя совпадения областей определения сравниваемых состояний. То есть понятие псевдонеотличимости слишком слабое и не учитывает всех возможностей, скажем, минимизации автоматов. 61 Для частичных автоматов часто используются понятия эквивалентно- го и изоморфного продолжения (покрытия) автоматов. Для иллюстрации этих понятий рассмотрим автомат, заданный табл. 2.14 Т а б л и ц а 2 . 1 4 q\x x 1 x 2 x 3 1 2,0 - 3,- 2 - 1,- 3,0 3 2,1 1,- 3,0 Возьмем состояние 2 и 3 ( q 2 и q 3 ). Область определения для q 2 содер- жится в области определения для q 3 и, кроме того, в области определения для q 2 выполняется условие ( ) ( ) 2 3 , , S q S q = x x для любого слова x, так как при любой входной букве x ( ) ( ) 2 3 , , q x q x λ = λ и ( ) ( ) 2 3 , , q x q x δ = δ Поскольку область определения для q 3 включает в себя область опреде- ления для q 2 , то можно сказать, что возможности состояния q 3 больше, чем q 2 , на тех словах, на которых ( ) 2 , S q x не определено, а ( ) 3 , S q x определено. Если заменить теперь состояние q 2 на q 3 (просто вычеркнуть строку q 2 , а переходы в q 2 поменять на переходы в q 3 ), то получим авто- мат S ′′′′ , который «делает больше, чем S ». Говорят, что автомат S ′′′′ по- крывает автомат S , или является продолжением автомата S , или автомат S ′′′′ содержит (включает) автомат S. В этом случае S ′′′′ есть эквивалентное продолжение, покрытие или надавтомат автомата S , а S – эквивалентное сужение или подавтомат автомата S ′′′′ . Это обозначается как ' или ' S S S S ⊆ ⊇ Дадим более строгое определение покрытия. Состояние q i автомата S покрывает (включает) состояние r j автомата Т ( S и Т могут совпадать), если для любого слова x из того, что ( ) , j T r x определено, следует, что ( ) , i S q x определено и ( ) ( ) , , j i T r S q = x x . Автомат S включает (покрыва- ет) автомат Т, если для любого состояния Т найдется покрывающее его состояние S . Таким образом, автомат ( ) , , , , S S S S S S X Q Y = δ λ покрывает автомат ( ) , , , , T T T T T T X Q Y = δ λ , если , T S T S X X Y Y ⊆ ⊆ , а автоматное 62 отображение ( ) , S S S q x * ( , ) S S S S q Q X ∈ ∈ x продолжает отображение ( ) , T T T q x ( , T T q Q ∈ * ) T T X ∈ x на множестве X S * Пусть теперь S,Т и W – автоматы, удовлетворяющие условиям S∼Т и Т⊆W. Тогда автомат S является изоморфно вложенным в W . Можно так- же сказать, что W является изоморфным продолжением S , а автомат S является изоморфным сужением автомата W. Обозначается это S W ⊂ ɶ . Можно показать, что отношение покрытия (равно как и изоморфного вложения) автоматов обладает следующими свойствами: − A A ⊆ (рефлексивность); − ( ) & ( ) A B B A A B ⊆ ⊆ = ֏ (антисимметричность), − ( ) & ( ) A B B C A C ⊆ ⊆ ⊆ ֏ (транзитивность), т. е. являются отношениями нестрогого порядка. Вернемся к табл. 2.14 и обратим теперь внимание на состояния 1 и 2. Они примечательны тем, что можно придумать состояние, покрывающее и q 1 , и q 2 . Например, это будет некоторое состояние 4: 2,0; 1, - ; 3,0. Такие состояния q 1 и q 2 называются совместимыми. Состояния q i автомата S и r j автомата Т (может быть S = T ) совмести- мы , если существует состояние p k (возможно, какого-то третьего автома- та W ), покрывающее и q i и r j . Автоматы S и Т совместимы , если суще- ствует автомат W , включающий S и Т . Можно дать определение совме- стимости автоматов, рассматривая автоматные отображения: состояния q j и r j совместимы, если для любого слова x либо одно из отображений ( ) , i S q x и ( ) , j T r x не определено, либо выходные слова ( ) , i S q x и ( ) , j T r x (они могут содержать прочерки) непротиворечивы, т.е. не со- держат на одинаковых местах разных букв. Используя понятия совместимости и покрытия, можно предложить план минимизации частичных автоматов, аналогичный методу миними- зации вполне определенных автоматов: находим совместимые состояния и заменяем их покрывающим состоянием. Однако здесь имеются некото- рые трудности. Отношение совместимости в отличие от неотличимости и отношения включения нетранзитивно и не является отношением эквива- лентности. Это означает, что классы совместимости могут пересекаться. Назовем систему классов совместимости полной, если 1 2 k C C C Q ∪ ∪ ∪ = и замкнутой, если из того, что состояния q и q′′′′ находятся в одном классе совместимости, например в С i ( , ) i i q C q C ∈ ∈ ′′′′ , 63 следует, что состояния ( ) , q δ x и ( ) , q δ x ′′′′ также находятся в одном классе совместимости, например в С j , всякий раз, когда соответствующие функ- ции перехода определены. Имеется теорема (Полла–Ангера), аналогичная теореме 2.2.3: Теорема 2.2.4. Если для частичного автомата имеется полная и за- мкнутая система классов совместимости С 1 … С k , то существует автомат S ′′′′ , включающий S. Автомат ( ) , , , , S S S S S S X Q Y δ λ ′ = ′ = ′ = ′ = строится следую- щим образом. Множество состояний равно { } 1 2 , ,..., S k Q C C C = . Для лю- бого С i и любой буквы x∈X S функция ( , ) S i j C x C δ = ′′′′ , если для некоторых i q C ∈ функция перехода ( , ) j q x C δ ∈ ; ( , ) S i C x δ ′′′′ не определена, если для всех q∈C i функция перехода ( , ) S q x δ не определена. Функция выхода ( ) , S i C x y λ = ′′′′ , если для некоторых состояний q∈C i функция выхода ( ) , S q x y λ = и ( ) , S i C x λ ′′′′ не определена, если для всех q∈C i функция ( , ) S q x λ не определена. Нетрудно видеть, что состояние C i автомата S ′′′′ покрывает все состоянияиз класса совместимости C i автомата S и, следо- вательно (ввиду полноты системы классов { } i C ), автомат S ′′′′ покрывает автомат S . Что и требовалось доказать. Если автомат S полностью определен, обе теоремы (2.2.3 и 2.2.4) сов- падают. Для минимизации частичных автоматов можно использовать и алго- ритм Мили. При этом нужно сначала построить различные доопределе- ния частичного автомата до полных автоматов (конечно, они будут по- крывать исходный автомат), а затем минимизировать полученные полные автоматы по алгоритму Мили. Реализация этого пути на практике сталкивается со значительными, порой непреодолимыми трудностями. По крайней мере, две из них за- служивают особого внимания. 1. Доопределить частичный автомат S можно различным образом. При этом получаются автоматы, скажем S 1 , … S N , неэквивалентные между со- бой. Соответствующие минимальные автоматы 10 0 ,..., N S S могут иметь различное число состояний, и также неэквивалентны между собой, т. е. их нельзя получить друг из друга эквивалентными преобразованиями. Поэтому результат минимизации будет сильно зависеть от того, насколь- ко удачно мы доопределим исходный частичный автомат. Кроме того, полученный результат нельзя улучшить эквивалентными преобразовани- 64 ями и необходимо весь путь проделывать заново: доопределять автомат по-другому, находить классы эквивалентных состояний и т.д. Число раз- личных вариантов доопределения достаточно велико: нетрудно подсчи- тать, что если |Q S | = n , |Y S | = k , функция перехода δ S не определена в p клет- ках автоматной таблицы, а функция выхода S λ – в r клетках, то это число равно p r n k ⋅ 2. Даже полный перебор всех вариантов доопределения может не при- вести к минимальному автомату. Алгоритм Мили дает систему непересе- кающихся классов совместимости, но ведь эти классы могут пересекаться. Из-за возможности пересечения классов совместимости число различных вариантов минимизации еще больше числа вариантов доопределения. |