Antik (1082243), страница 7
Текст из файла (страница 7)
Нулевой индексобратной связи означает, что обратных связей (контуров) нет.Простейшей реализацией автомата без обратных связей является42автомат с регистром сдвига на входе (рис.8), запоминающий (записывающий) входную последовательность определенной длины.Этот записанный отрезок последовательности входных символови является текущим кодом состояния автомата.synARGRG-1-nCLBРис.8. Реализация автомата без обратной связиНапример, таким образом можно реализовать автомат, распознающий дефинитный язык (см. гл.I.п.7.1.6).Что бы проверить возможность такой реализации в самомобщем случае, используем так называемый универсальный парный граф переходов (УниПарГраф).
УниПарГраф автомата М состоит из1) вершин, соответствующих каждой неупорядоченной паре различимых между собой состояний (si,sj) i<j автомата М;2) дуг, помеченных входным символом ak и направленныхиз вершины (si,sj) к вершине (sp,sq), если существуют вавтомате М переходы по ak либо (siÆsp)&(sjÆsq), либо(siÆsq)&(sjÆsp).Утверждение. Автомат М может быть реализован без обратных связей тогда и только тогда, когда в УниПарГрафе автомата отсутствуют контуры.Необходимость. Если в УниПарГрафе есть контур и входная последовательность проводит автомат по этому контуру, токакой бы длины не был отрезок входной последовательности, понему нельзя однозначно определить финальное состояние.Достаточность. Если в УниПарГрафе нет контуров, а самая длинная цепь составлена из k вершин, то это означает, чтолюбой отрезок из k или более входных символов, однозначно43определяет текущее состояние автомата.
Если автомат реализуется без обратных связей, то k входных символов запоминаются врегистре сдвига.Для определения кодов состояний в реализации с регистромсдвига можно воспользоваться деревом–преемника, в котором вершины это–подмножества Si множества S состояний автомата; корень – соответствует множеству S всех состояний автомата;для каждого входного значения ah строится ветвь, направленная от Si к узлу преемнику, представляющему множество всехследующих состояний, если исходное состояние включено в Si иприложен вход ah.Не обязательно строить полное дерево с k уровнями, где kчисло вершин в самой длинной цепи в УниПарГрафе.
Информация о преемниках будет достаточной, если заканчивать деревовершинами идентичными вершинам более раннего уровня и вершинами, состоящими из одного состояния.Дерево–преемника удобнее представлять в табличном виде,см. пример ниже.Одному состоянию автомата могут соответствовать болееодного кода. Интерпретировать это можно двояко либо как многозначное кодирование одного состояния, либо как существование в автомате эквивалентных состояний.Пример 2.1.-1. Автомат задан автоматной таблицей (выходные значения не указаны).Автоматная таблицаa b c1 1 5 52 1 4 53 2 5 54 3 4 55 3 4 66 3 4 6Таблица дерева–преемникаabc123456123 45 561231245 54534565634612145 5После построения УниПарГрафа ясно, что автомат можнореализовать без обратных связей. При такой реализации входной44регистр сдвига должен запоминать 5 входных символов.После построения дерева–преемника рис.10 для определения кодов состояний, последовательно увеличивая число информативных разрядов, до тех пор, когда состояния станут различимыми, получаем все варианты кодов каждого из состояний.16 acb24 a 25 a 26 b 34 a b 35 a b 36acca2313aa12b4645cc56Рис.9.
Универсальный парный граф14 ab15 ac b123456b45a b c3 4 56aa1a 123b 45c 56c12356ab cab c12 45 53 4 6b c45 56Рис.10. Дерево–преемникаaaabacbabbbccacbcca123a45a56b123b45b56c123c45c56123345445566aaaaabaacbaababbaccbacbbcbca12a3a3b12b3b3c45c4c412245555655baaabaabbaaccbaacbabcbacb1b2b2c45c5c5cbaaa c5cbaab c4cbaac c4544566665545Сведем коды всех состояний в следующую таблицу:12–3–4–––aaaxxaabxxaacxxabxxxacxxxbbxxxbcxxxbaabxbaacx5–––––––caxxxbabxxbacxxcbbxxcbcxxbaaaxcbaabcbaac6–––ccxxxcbabxcbacxcbaaa2.2.
Автомат с бинарной функцией обратной связиЕсли в УниПарГрафе автомата есть контуры, то такой автомат нельзя реализовать без обратных связей. Задача ставится следующим образом – реализовать автомат с единичным индексомобратной связи или иначе с бинарной функцией обратной связи, сиспользованием регистров сдвига, как на входе, так и для обратной связи рис.11.synARGRG-1-nCLBβsynTT-1-mРис.11. Автомат с единичным индексом обратной связиПример 2.2.-1.
Автомат задается таблицей46a0,21,10,31,41234b1,40,31,21,3УниПарГраф этого автомата представлен на рис.12. слева.Парный граф (ПарГраф) аналог УниПарГрафа, но с учетом значений обратной связи, в этом примере совпадающих с выходными, представлен на том же рисунке справа. В ПарГрафе нет контуров, и самая длинная цепь состоит из 5 вершин, рис.12.b232334 b/134 b1212baaab14 aab2413b/114aa/0a/1 24b/113Рис.12. Универсальный парный и Парный графыЭто означает, что последовательность из 5 входных и двоичных символов обратной связи идентифицируют все состоянияавтомата со структурой рис.1. Что бы найти коды состояний построим дерево–преемника (таблицу) с учетом значений функцииобратной связи.1234231423434a/023323a/1141414b/033–3b/12342342334–23Действуя аналогичным предыдущему примеру образом, получим следующие коды состояний см.
таблицу.УниПарГраф может быть использован для определенияфункции обратной связи Ψ(s,d), как функции состояния и входа.Обозначим значение этой функции xsd=Ψ(s,d). Если для какой либо дуги, помеченной входным символом d и выходящей из вершины (h,k), выбрать значения функции Ψ такими, чтобы xhd≠xkd,то этой дуги в ПарГрафе уже не будет. Для определения функции47обратной связи надо для значений этой функции составить систему неравенств, решение которой позволяет избавиться от контуров в ПарГрафе.Таблица кодов состояний:aaxxxbxxxxaaxxx1 10xxx3 0xxxx4 11xxxabaxxaaxxxabaxx– 110xx- 00xxx- 111xxabbxxabxxxbaaxx– 110xx- 00xxx- 110xxabbxxabxxxbabax– 111xx- 01xxx- 1110xaaxxxbaaxxbabbx2 01xxx- 111xx- 1110xbaxxxbabaxbabbx- 10xxx- 1111x- 1111xbbxxxbbaax- 10xxx- 1110xbbbxxbbaba- 111xx- 11110bbaaxbbabb- 1111x- 11110bbababbabb- 11111- 11111Запишем систему неравенств для примера 1:x1a ≠ x2a –разрывает контур {12 a },x3a ≠ x4a –разрывает контур {34 a },x2b ≠ x3b –разрывает контур {23 b },(x1a ≠ x4a) v (x2a ≠ x4a) –разрывает контур {14 a 24 a },(x1a ≠ x3a) v (x2a ≠ x3a) –разрывает контур {13 a 23 a },последние два условия должны выглядеть сложнее – не должнобыть так же контура {13 b 24 a 14 b 34 b 23 a }.Для двоичных значений переменных xsi система неравенствможет не иметь решения или иметь одно или более решений.
Впоиске решения (двоичного) будем записывать, если это возможно, неравенства так, чтобы одна и та же переменная находилась водной и той же части (левой или правой) неравенства. Для указанной выше функции решение выглядит так48x1a ≠ x2ax2b ≠ x3bx3a ≠ x4ax1a ≠ x4ax3a ≠ x2aПрисваивая переменным левой части неравенства значение 0, аправой – 1, получаем решение. Поскольку у исходной системынеравенств много решений, то можно выбрать такое, чтобы длинацепей в ПарГрафе, а значит и разрядность регистров сдвига, быламинимальной, например:x1a ≠ x2ax4a ≠ x3ax4a ≠ x2ax1a ≠ x3ax2b ≠ x3bx1b ≠ x3b , удаляя дугу (13Æ24)x4b ≠ x3b , удаляя дугу (34Æ23)Результатом решения является бинарная функция обратной связи.ПарГраф соответствующий такому решению имеет цепи максимальной длины – 2, рис.13.функция обратнойсвязи a b1 0 02 1 03 1 14 0 012 b/03423a/1b/0241314 a/0Рис.13.
Парный графРассмотрим пример, в котором для двоичных значений переменных система неравенств не имеет решения.Пример 2.2.-2: Автомат задан таблицей (без выхода). УниПарГраф – на рис.14.Автоматнаятаблица a b1 2 32 1 43 4 14 3 2a 12 bb 34 ab 13 aa 24 b14 a,b a,b 23Рис.14. Универсальный парный граф49Система неравенств для значений функции ψ:x1a ≠ x2a ,x3a ≠ x4a ,(x1a ≠ x3a) v (x2a ≠ x4a),x1b ≠ x3b ,x2b ≠ x4b ,(x1b ≠ x2b) v (x3b ≠ x4b),(x1a ≠ x4a) & (x1b ≠ x4b) v (x2a ≠ x3a) & (x2b ≠ x3b).Для двоичных значений у этой системы неравенств нет решения.Рассмотрим метод, используя который можно для любогоавтомата получить бинарную функцию обратной связи. Назовемs-словом последовательность из пар (ВходнойСимвол, ЗначениеФункцииОбратнойСвязи).Сформулируем, непосредственно следующее из правил построения ПарГрафа и используемое в методеутверждение: Для того, что бы в ПарГрафе не было контуров, необходимо и достаточно, что бы не существовало s-слова,которое переводит автомат из состояния i в i и оно же из состояния j в j (для какой-либо пары состояний).Если система неравенств для значений функции ψ не имеетрешения, то метод получения бинарной функции обратной связиψ состоит в следующем:1.
Перечислить все элементарные контуры в автоматномграфе.2. Добавить эквивалентные состояния и значения ψ функции так, что бы слова в контурах удовлетворяли вышеуказанному УТВЕРЖДЕНИЮ.Для рассматриваемого примера:Автоматнаятаблица a b1 2 32 1 43 4 14 3 21 bab 3aa2 bab 4Рис.15. Диаграмма переходов50Элементарныеконтуры{1 a 2 a }{3 a 4 a }{1 b 3 b }{2 b 4 b }{1 a 2 b 4 a 3 b }{1 b 3 a 4 b 2 a }Исправленные контуры{1 a/0 2 a/1 }{3 a/1 4 a/0 3+ a/0 4+ a/0 }{1 b/0 3 b/1 }{2 b/1 4 b/0 2+ b/0 4+ b/0 }{1 a/0 2 b/1 4 a/0 3+ b/0 }{1 b/0 3 a/1 4 b/0 2+ a/0 }Автоматнаятаблица сфункцией ψab1 0,20,32 1,11,4+2 0,10,4+3 1,41,1++3 0,40,1+4 0,30,2+4+ 0,30,22.3.
Независимость от состоянийОб автоматах, которые могут быть реализованы либо безобратных связей, либо выходная функция может быть функциейобратной связи, можно говорить как об автоматах, независящихот состояний, т.е. зависимость выхода от входа может быть выражена без привлечения понятия состояние.bk=f(ak , ak-1 , … , ak-n)bk=f(ak , ak-1 , … , ak-n , bk-1 , … , bk-n)3.Автоматы без потери информацииАвтомат можно рассматривать как устройство, котороеосуществляет кодирование входных последовательностей в выходные. Если после такого кодирования можно путем декодирования восстановить исходную информацию, то такие автоматыназывают автоматами без потери информации, IL-автоматами(Information Lossless).Рассмотрим только такие IL-автоматы, для которых можнопостроить инверсный автомат, т.е. автомат, восстанавливающийисходную информацию. Это1) IL(B)-автомат, для которого входную последовательность можно определить по его начальному состоянию ивыходной последовательности.2) IL(E)-автомат, для которого входную последовательность можно определить по его конечному состоянию ивыходной последовательности.Если автомат – IL(B)-автомат, то не разумно использовать его как51IL(E)-автомат, так как кодирование то же, а декодирование сложнее.3.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
