XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 89
Текст из файла (страница 89)
Так, при р = 15 не будет использовано число 1111 (двоичный код числа 15). Тогда размерности булевых векторов Х (кодов входных символов), У (кодов выходных символов), У и Я (кодов текущего и нового состояний) соответственно будут равны: и = =]1обз]У][, еп =]1обз]й~][ и Й =]1обзгЯ][. Предлагается следующий алгоритм определения булевых операторов Р и С в (7.13). 1. Составляется таблица для функций переходов и выходов исходного конечного автомата с выходом (табл. 7.1).
Таблица 7.1 2. По составленной таблице (см. табл. 7.1) строят так называемую стпрунтпррную тпаблицу (табл. 7.2), в которой каждый символ (входной и выходной) и каждое состояние замеюпотся их двюичным кодом, причем так, что если набор Таблица 7.9 560 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ (нь ..., нь) есть код текущего состояния д, набор (хь ..., хи) есть код входного символа а, то тогда и только тогда, когда набор (уь ..., у,и) есть код выход- ного символа Ь= р(д,а), а ( ь ", яь) = Р((пь ", пь),( ь ", )) тогда и только тогда, когда набор (гь ..., хв) есть код состояния г = б(д,а).
Структурная таблица есть не что иное, как таблица, задающая некоторый булез оператор (вообще говоря, часщичкыб, так как не все векторы соответствующей размерности служат кодами элементов множеств У,ФР,Я) из В"+" в В~+я. Этот оператор может быть реализован некоторой схемой из функциональных элементов (как правило, над свпандартиным базисом).
Вектор Я поступает (в некоторый момент времени 1) на входы к триггеров, с прямых выходов которых (в момент времени $+ 1) снимается вектор У, т.е. Ц$+ 1) = Я(8). Таким образом, если в начальный момент времени 1 = 0 с выхода запоминающей части снимается вектор Уе, код начального состояния де и на вход комбинационной части поступит вектор Х(0), то на вход запоминающей части в этот же момент времени поступит вектор в (О) = Р(У(0),Х(0)) = У(1) и триггеры запоминающей части будут хранить уже информацию о новом состоянии до момента времени $ = 1 и т.д.
В этом небольшом дополнении мы никак не можем сколько нибудь подробно и строго обсуждать математическую теорию реализации ОД-функций „схемами" с элементами задержки'. Разумеется, нет и речи о каких-либо доказательствах. Также мы не решаем „инженерно гехническиео проблемы структурного синтеза, в частности проблемы „аппаратной реализации" 'См., ваиример: Ябвококиа С.В:, Гввривов Г.П., Свиожеико А.А.
Д.Т.2. Ковечвые автоматы с аытолоы. Струатураый сивтез 561 триггеров. Наша цель здесь — показать в рамках самого элементарного изложения связь между теорией конечных автоматов и теорией булевых функций. Эта связь состоит в том, что теория булевых функций дает аппарат для структурного синтеза конечных автоматов (с выходом), т.е. длл перехода от описания функции, вычисляемой конечным автоматом, к его структуре, реализующей его „схеме", построенной на функциональных элементах и элементах задержки.
В заключение разберем простой пример структурного синтеза. Пример 7.14. Конечный автомат с выходом задан диаграммой, изображенной на рис. 7.42. С содержательной точки зрения этот автомат работает как простейший „лексический анализатор", распознавав все це- а/О, Ь/О, О/1, 1/1 почки во входном алфавите У = = (а, Ь, О, 1), которые начинаются а/О, Ь/О с „буквы", т.е. с символа а или Ь, как „правильные", тогда как це- О/?, 1/? почки, начинающиесв с „цифры" (т.е. с 0 или 1), классифицируются а/О, Ь/О, О/1, 1/1 как „неправильные", о чем выда- % ется сообщение в виде выходного символа е Рис. 7.42 Кодируя входной и выходной алфавиты, а также состояния, получим следующие двоичные коды: 1) входной алфавит: а — 00, Ь вЂ” 01, 0 — 10, 1 — 11; 2) выходной алфавит: 0 — 00, 1 — 01, ? — 10, код 11 не используется; 3) множество состояний: ее — 00, е1 — 01, дз — 10, код 11 не используется.
Так как рассматриваемый автомат простой, мы сразу составим структурную таблицу (табл. 7.3). 562 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Таблица 7.3 Для частичных булевых Функций у1 = у1(х1,хз,и1,и2), у2 = = у2(х1зхз~и1зи2)~ 31 = 21(х1~хз,и1,и2), 22 = 22(х1,Х2,и1,и2) составим карты Кармо и найдем для каждой из них минимальную ДНФ. Для функции у1 карта Карно изображена на рис. 7.43.
Единственная склейка дает у1 = й1й2х1. 001х х11х 1х1х Рис. 7.44 Рис. 7.43 Для второй функции получим (рис. 7.44) у2 = изх1 Ч и1 х1 = х1(и1 Ч и2). Д.7.3. Конечные автоматы с выходом. Структурный синтез 563 х01х Охех х1хх 1ххх Рис. 7.4О Рис. 7.45 Для функции «1 имеем (рис. 7.45) минимальную ДНФ Наконец, для функции ез по карте Карно, изображенной на рис. 7.46, находим лз = из Ч й1й1. Структурная схема автомата представлена на рис. 7.47. Обратим внимание на то, что вместо инверторов для сигналов и1 и из мы используем сигналы, снимаемые с инверсных выходов триггеров Т1 и Тз.
Заметим также, что переменная хз оказалась Озинепиеной. Действительно, тип входного символа („буква", т.е. а или 6, и „цифра", т.е. О или 1) распознается по первому разряду входного вектора Х: при х1 = О имеем ебукву", а при х1 = 1 — „цифру". Наконец, следует заметить, что синтезированная „структурная схема", строго говоря, не являетсл графом (поскольку содержит, например, „кратные дуги", т.е.
допускает несколько Разных дуг между одной и той же парой вершин). Даже комбинационная часть этой схемы не может быть уже названа схемой иэ Функциональных элементов, так как в вершины, помеченные переменными и1,из, заходят некоторые дуги. Это будет, говоря неформально, схема из функциональных элементов, „вставленная" в некий более общий „графовый объект".
564 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Рмс. Т.4Т Строгая математическая теория таких „обобщенных графов" в атом учебнике не рассматривается'. Дополнение 7.3. Морфизмы и конечные подстановки Пусть У и $г' — некоторые алфавиты (в частности, К = = Ю). Жорбзизм — это произвольное отображение Ь: к'* -+ -а Ю', такое, что Ь(Л) = Л и (тк,у е к") (Ь(ху) = Ь(к)Ь(у)). "В литературе длл этих объектов также используютса термины „сеть", „гиперграф", „блок-схема" (смл Яблоксквб С.В.). Д.73. Морфеомы и конечные подстановки 565 Иначе говоря, морфизм (в данном контексте) — зто гомо,цорфиэи свободного моиоида т'* в свободный моноид тт" (см.
пример 2.7.д). Теорема 7.11. Любой морфнзм Ь: Ъ" -+ тФ'* однозначно определяетсл конечным отпображением ((а, Ь(а)): а Е К Ь(а) Е тт'). Обычно такое отображение задается в форме, напоминающей запись правил вывода порождающей грамматпики: а« -+ Ь(а«), ..., а„-+ Ь(а„), где т' = (ам..., ао).
Чтобы найти образ некоторого непустого слова х Е Ъ'+, достаточно вместо каждой буквы х(т) подставить слово Ь(х(«)) е Ит*. Например, если Ь задается в виде а -+ аЬсЬа, Ь -+ Ьа, с -+ Л, то Ь(аЬЬс) = аЬсЬаЬаЬа, Ь(Ь(аЬЬс) = Ь (аЬЬс) = Ь(аЬсЬаЬаБа) = = аЬсЬа Ьа Ба аЬсЬаБа аБсЬа Ьа аЬсЬа = = аЬс(Ьа) аЬс(Ьа) аЬс(Ба) аЬсЬа. Морфизм Ь называется Л-свободным мордтиэмом, если для всякого слова х ф Л Ь(х) ф Л.
Морфизм предыдущего примера не является Л-свободным. Если Ь: У' -+ тт'* — морфизм, то сооп«ветпстпвие Ь 1 (обратп"ое к Ь) из И1' в У* называют инверсным морд«измом (инверсией морфиэма, обратпиым мордтиэмом). Таким образом, из определений сразу следует, что Чр Е тт' (й) = (х: Ь(х) = у). Для рассмотренного выше примера Ь (аЬсЬаЬа) = (аБсп: т«> 01 = аЬс'.
566 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЭЫКИ Определение Т.11. Пусть Ь: У' -+ В' — морфизм. Тогда для языка Ь С У' язык Ь(Ь) = (у: у = Ь(х), х Е У"1 называют морфизмом языка Ь, а для языка К С Ю' язык Ь 1(К) = = 1х: Ь(х) Е Х, х Е У') — инверсным морфизмом языка Ь. Таким образом, язык Ь(о) есть не что иное, как образ языка Ь при о1пображении Ь, а Ь ~(К) — прообраз языка Х при отиображении Ь (см. 1.3). Соответствие о С У* х И~' называют конечной подстановкой, если: 1) о(Л) =1Л1; 2) для каждого а Е У множество о(а) конечно; 3) для любых цепочек х, у Е У* о(ху) = о(х)о(у) (т.е. множество слов о(ху) есть соединение языков о(х) и о(у)). Иначе говоря, конечная подстановка — зто своего рода многозначный морфизм, на любой букве алфавита принимающий лишь конечное множество значений.
Точно так же как и для морфизма, легко показать, что конечная подстановка полностью определяется своими значениями на буквах алфавита У и, следовательно, может быть задана, как и морфизм, в виде системы „правил замены", в которой одной и той же букве алфавита У сопоставляется, вообще говоря, несколько цепочек в алфавите И~. Например: а -+ абсЬа, а -+ ас, Ь-+Ьа, Ь-~ саЬ, с -+ аа, с -~ Л, с -+ ЬаЬ, или в более короткой записи: а-+абеба)ас, б-+Ьа~саб, с-+па)Л)баб, как мы записывали правила вывода грамматик и сисшемы команд конечных автиомашов. Для нашего примера о(аЬ) = (аЬсЬаба, абсбасаб, асба, ассаб).
567 Д. 7 3. Морфизиы и извечные иодотииовки Если а С У' х тт' — конечная подстановка, то обратное сооитветвсптвие гг ~ С тт"' х У' называется инверсной (обратной) конечной нодстпановкой (или инверсией конечной подстпановкн). Заметим, что для фиксированного у Е тт', согласно определеням обратного соответствия и сечения соответствия, о (у) = (х: (х,у) Е о') = (х: у Е о(х)) . Если Ь С т", о С т" х Ит' — конечная подстановка, то сг(Ь) = (у: (3х Е т ) у Е а(х)) .
Если же К С тт'", то гг ~(К) = 1х: (Зу Е К)у Е «т(х)) = 1х: о(х) й К ~ И~. Нетрудно заметить, что, согласно определению обласпти определения и областпи значения соогпветпсгввил, а(Ь) С В(гт), а о ~(Ь) С Р(гт) = В(о ~). Подчеркнем, что не все цепочки множества о(х) при х Е ст 1(К) содержатся в юыке К, но найдется хотя бы одна цепочка в а(х), которая принадлежит К. Формулируемая далее теорема связывает конечную подстановку с основными операциями над языками: объединением языков, соединением языков и итперанией языка. Теорема 7.12. Если К и Ь вЂ” языки в алфавите У, а о' С Ъ" х тт" — конечная подстановка, то 1) о(КОЛ) =сг(К)0о(Ь); 2) о(КЬ) = а(К)о(Ь); 3) гт(Ь') = (о(Ь))'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
