Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 54
Текст из файла (страница 54)
Данное пресбрааованне не нарушает функпнзннравзння автомата талька в тем случае, если каждый новый граф гзмеемзрфен предшествуюшему. Практически вреебрззаванне сводятся к дебавленшо новыд вершин в некеторые ребра каждого запрешеннага графа, являюшегеся пздграфом даянога графа переходов. Этим самым вводим неустойчивые внутренние состояния автомата. Прн ептюкальяем прзектнрованнн число вводнмып неустойчнвып сосгеяннй должна быль мнннмальным.
298 Гл. 4. Теорию формальных грамматик и аетомотпоо 299 Таблица 4.7 !з = (ом оз) !з = (сз,оз) !з = (оз, сз) !з = (оз, оз) Ь = (оз,ое) !з = (ом ое) !7 = (оз, ит) !а и (от,оэ) !з = (оз, оэ) !и = (ом оа) йз: Пз 112" оз 'Ь зтз оа оа, озо) оз, ого) оэ, ого) оэ, озз) шо, озз» озэ, ом) озз, ом) ом, озз) оз ом) ом,оы) оы, озз) оы,оы) !и =( !!з ( !зз = ( !и=( !ы = ( !зз =( !и =( !.=( !зэ =( !зэ =( !., =( !зз =( н оз о, оз йэ ом "н Я~'. Яз.' ззт з1з цз э1з ои '1о оз оз озэ о !гз = (шз, ом) !зз — — (оы, оы» !зз = (озз, озз) !га = (озз, озз) — озз, им заза Двухмерная таблица (табл. 4.7) распрелеления ребер по запрещенным фигурам (рис.
4.25) покрывается двумя строками (Пз, !и». Добавляя менку вершинами оэ, озэ и оы, ом вершнны, соответствуюшие неустойчивым состояниям, вкладываем полученный граф в булево пространство (рис. 4.26». При ввелении дополнительных вершин в граф раарешенные фнтурм (циклы четной длины) ие были нарушены. П р и м е р 4.4. Построим соседние коды для внутренних состояний автомата, граф переходов которого ивобраиеи на рис. 4.27, о. Прн влоиеини рассматриваем граф без петель, без ориентации дуг н кратные ребра вамеияем одним ребром.
С учетом этого кодируемый граф содерннт аацрешенные фигуры вида: ь)з = (гм Уз»~ К = (оз, оз, оз) У! = ((Я! оз) (оз~ ~з)~ (оз оз))! !9з =(Й~, Уг», 1з'= (сз, сз, сз», Уз = ((Яз, Яз)~ (сз, са», (Юэ, Яе)»~ Яз = (1~з, Уз», 1гз = (Яз, Яз, сз), Уз = ((сз, Яз), (Яз, Яе), (сз, се»); а =Я,У», 12=(Я,~,~.,~,М Уз = (%, М, %, ~з), Рз, ~з), Рз, М, (оз, ~з»); зе! Рис. 4.2б 1 1 1 1 1 1 1 1 1 1 1 1 1 0 . 0 0 0 0 0 0 О 0 0 О 0 0 0 О О 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 О 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 О 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 О 0 1 1 0 0 1 1 1 0 0 0 0 0 0 О 0 О 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 2 4.5.
Кодирование онушренких сосшоюниб !9, = (У„У,», 1, = (Я„Я„Я„Я„М, Уз = ((Яз, Яз), (Ям Яз), (Яз, Яз) (оз, Яэ), (Яз, Яэ»); б)з = (Ъв, Уе», Ыа = (5з, Яз, ~з, ~з М Уз = ((Яз, оз), (оз, оз), (оз, оз), (аз~ ое)~ (оз~ оз)»! Ят = (7т, Ут», !'т = Рз, Яз, Яз, Яз, 8э», Ут = ((Яз, Яз), (Яг, сз», (сз, Яз)~ (с», сз», (сз, оз) (сз, сз»).
300 Гл.4. Творил формальных громмотик и оатомотоа аоьон аоо, эо> Рис. 4.27 Рэарешвивыни фпгурвмв при вловввви графа в гппврвуб явлтстся циклы чвгвой ллннм аида: нз = (Уз, ГУз» Уз = (ог оз> ов> оэ)> г>э = ((сг, 8<), (уг, оэ)> (сэ, сэ), (ов, оэ))~ >>>г = (Уг, Гтг>, Уз = (Уэ, Ув, Уэ, Уэ), Гтг = ((уг> ув), (ув> уэ)> (уэ, ов), (Юг> оэ)); Вз = (Уэ г>э>, Уз = (ог, оэ, Уэ, оэ), ГУэ = ((Уг, Юэ), (Уз, Уэ), (Уэ, Ув), (уз, Ув)); й = (У Ггв» Уз = (3 / э = » ..., б), Гув = ((оз> оэ), (оз> оэ)> (оэ, оз), (оэ, ов), (ов, оэ)> (оэ, Яв)). Таблицу, показывающую распределение компонент в запрещенных и/или разрешенных фигурах, как и выше, будем называть семантической.
Таблица 4.8 Строим семантическую таблицу (табл. 4.8). При введении неустойчивых состояний в графе переходов возможно преобразование циклов четной длины в циклы нечетной длины, поэтому слева 14.3. Кодирование внутлранних составной 301 от собственно семантической таблицы расположим таблицу циклов четной длины. Согласно структуре запрещенных фигур вложения графа в гиперкуб для соседнего кодирования внутренних состояний автомата необходимо, чтобы покрытие семантической таблицы было сформировано с учетом принципа четности: каждое покрытие включает четное число ребер, принадлежащих каждому циклу четной длины и нечетное число ребер, принадлежащих каждому циклу нечетной длины. Эта таблица имеет 28 покрытий: (а+Ь+с) (ээ+с+к) (у+Ь+т) (а+Ь+з(+у+у) х х (а + Ь + е + у'+ т) ° ( с+ Н + У+ Ь + т) ° (с+ т(+ г + 1 + у + т) = = над + Ыд + суэ(у + асу у + Ьсуу + сед + айс + аээк + аМс + + айу + аlст + а/с у + Ьсй + ЫЬ + Ьс1с + ЬЬу + Ьйт + Ьку + с(ссЬ + + тэтск + сйу + сйдт+ аНт + Ыт + сйт+ аст + Ьет + сет).
Оценим покрытия.. Первому покрытию (а, И, у) соответствует вектор 0 2 2 2 Д 1 1 1 3 1 1 2, указывающий частоту вхождения элементов покрытия в разрешенные и запрещенные фигуры. Спектр частот удовлетворяет критерию вложимости графа в гиперкуб.
Следовательно, первое покрытие порождает граф (рис. 4.27, б), гомеоморфный заданному, вложимый в гиперкуб и имеющий на три вершины больше, чем исходный граф переходов. Аналогичная проверка остальных 27 покрытий не улучшает решение, полученное по первому покрытию. Следовательно, введение трех неустойчивых состояний, Я, Яд, Я.„на переходах Яэ -+ Ят, Ят -+ Яэ, Яэ -+ Яб позволяет закодировать граф переходов соседними кодами минимальным образом: Я, — 1010, Я, — 0000, Я, — 0010, Я, — 0101, Я, — 0110, Яб — 0100, Я вЂ” 1000, Яд — 0001,  — 0111.
Граф, гомеоморфный графу переходов (рис. 4.27, а) с введенными неустойчивыми состояниями и соседними кодами, представлен на рис. 4.27, е. Пример 4.5. Рассмотрим соседнее водировавне еше одного автомата, заданного графом переходов ээ (рис. 4.28, о). Удаляя веса иа дугах и позли, снимая ориаитвцизо дуг, объединяя пвраллглзныа ребра ((эс.
4.29, о), находим, что граф содервигг запрошенные 4игуры Оз и Ог (рис. 4.29,6>: 4),(Уы и,>, У = (У;! '= » 2, ...,9), г>з = ((оз, Уэ), (Уы Уэ), (оы ов), (ог, гз) (оз, ов) (ог, 3т), (оз> ув), (ов> оэ), (ов> ов)> (ов, от), (оэ> ов)> (оэ> ов)); б)г<Уг, этг>, Уг = (Уы оз, оэ, оэ, ов), >>г = ((оз оэ), (оз, оэ), (оз, оэ), (оэ, ув), (Йэ, ув), (ув, ув)).
302 Гл.4. Теория формальных грамматик и автоматов 303 14.5, Кодирование внуглренних состояний Для их устранения дастатечне расшепить адно нз ребер, аашелших в пересечение этих запрещенных фигур, двумя вершинами (введение адней вершины на ребро перендает иввую запрешенную фигуру — пиал нечетней длины). Для апределеннв сти расшедляем ребро (Яв, Яв ) введением двух неустойчивых се стояний, Я, ЯЛ.
В результате получаем граф С, гемевмарфный заданному графу 1ал (7, в) 6 Рнс. 4.28 ьа Рис. 4.29 перехвдвв св и влвннмый в пвперпуб (см. рис. 4.2б,б): 31 — 0110, Яв — 0101, Яв — 0111, Яв — 0000, зв — 00Ш, яв — 0001, 3т — 010О, бв — Шо, бв — 00Ы, 3. — Ш10, Ял — 1ОП. Зная структуры запрещенных фигур соседнего кодирования и используя локальные характеристики графа С, мощности мно- жеств вершин Щ и ребер ]сУ[, плотность графа р(С) и его степень в(С), предложим алгоритм фактического вложения графа перехо- дов в гиперкуб. По характеристикам графа )1г[, )(У[, р(С), в(С) определяем вип запрещенных фигур, которые могут содержаться в заданном графе переходов и по структуре которых можно оценить количество вводимых неустойчивых состояний.
Утверждение. Размерность гиперкуба, в который вкла- дывается граф, гомеоморфный графу переходов С, не меньше сгпепени в(С) графа С. Используя это утверждение, предложим приближенный алго- ритм соседнего кодирования. Перед проведением соседнего копирования введем понятие ок- рестности радиуса Л вершины о;. Окрестпностью радиуса Я вершины и называется множество вершин (и1), цля каждой иэ которых минимальная длина цепи [и,..., о1] равна В. Предлагаемый алгоритм соседнего копирования состоит из сле- дующих шагов 1. В графе переходов С находим вершину ио максимальной степени в „, причем прн подсчете степени вершин параллельные ребра, т.
е. ребра, имеющие одинаковые концы, различные между собой, условно считаем за одно ребро; петли графа переходов прн подсчете в(и) не учитываем. В дальнейшем будем называть най- денную вершину оо центром соседнего копирования. Центр со- седнего кодирования ио образует окрестность радиуса гв (Л = О) вершины ио. Кодируем произвольным образом вершину ио. 2. Рассматриваем окрестность радиуса гв на 1 больше, чем ра- диус предыдущей закодированной окрестности. При рассмотрении вершин окрестности радиуса И возможны три случая, когда необходимо вводить дополнительные вершины, соответствующие неустойчивым состояниям автомата: а) и вершин рассматриваемой окрестности попарно смежны, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
