XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 88
Текст из файла (страница 88)
Конечный автомат с выходом есть упорядоченная семерка М = (т', тт', Ч, до, г', б, р), где т' — входной алфавит (его элементы — входные символы); Ж вЂ” выходной алфавит (его элементы — выходные символы); ц — конечное множество сосшолний конечного аешомаша с выходом; ое — выделенное состояние, называемое начальным состполнием конечного авшоматпа с выходом; г' — выделенное непустое подмножество состояний, каждый элемент которого называют эаключишельным сосшолнием конечного аетпомата с выходоМ б: чт х т -т чт — отпображение, называемое функцией переходов конечного аетпомаша с выходом; рэ ьт х т' -+ тт" — отображение, называемое функцией выходов конечного авшоматпа с выходом.
Графом (или диаграммой) конечного авшомаша с выходом М называют ориентированный граф, множество вершин которого совпадает с множеством состояний ьт, а множество дуг определяется так: иэ вершины (состояния) о ведетп дуга в вершину (состояние) г тогда и только тогда, когда Д.7.2. Коиечвые автоматы с выходом. Структурвыв синтез 553 ,. — 6(д,а) для некоторого входного символа а (причем, поскольку б есть отображение, для каждой пары (д,а) указанное состояние т единственное).
Каждой дуге диаграммы конечного автомата с выходом М сопоставляется метка, являющаяся конечным множеством упорядоченных пар из У х тУ, так, что пара (а, Ь) принадлежит метке дуги д ~ г тогда и только тогда, когда р(д,а) = Ь. Как видно, метка каждой дуги конечного автомата с выходом есть конечное соошвешсшвие, функциональное по вшорой номпоненше (т.е.
часшичное ошображение иэ У в ЬУ). Обласшс определенья этого соотпвешсшвил называется входной мешной дуги, а область значений — выходной меписой дуги (диаграммы конечного автомата с выходом). На рис. 7.37 показана диаграмма конечного автомата с выходом, у которого входной алфавит У = (а,Ь), выходной алфавит тУ = (О, Ц, множество состояний Я = (до,д1,дт) при начальном состоянии до и заключительном — дэ. Функции переходов и выходов определяются метками дуг. Обычно при иэображении диаграмм упорядоченная пара (я', 0) Е У х И/ записывается через косую черту: 1/О. а/О, Ь/1 а/О Рис. 7.37 Можно показать, что два сформулированньпс вьппе опреде. ления конечного автомата с выходом равносильны и тем самым существует взаимно однозначное соошвешсшвие между конечными автоматами с выходом (в смысле второго определения) и ориентированньпсн графами, дуги которых размечены над денаршовым произведением двух алфавитов так, как это описано первом определении.
Исходя иэ этого, мы можем отождествить конечные автоматы с выходом и их диаграммы. 554 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Таким образом, каждому конечному автомату с выходом М однозначно сопоставляется детерминированный конечный автомат Му = ( т', Я, де, г, 6), метки дуг которого получаются „стиранием" всех выходных символов в упорядоченных парах, которыми помечены дуги исходного конечного автомата с выходом (на каждой дуге остается только ее входная метка). Этот детерминированный конечный автомат будем называть входной проекцией конечноео автпоматпа с выходом вли 1Г-проекцией конечноео автпоматпа с выходом М. Входная проекция конечного автомата с выходом, диаграмма которого изображена на рис. 7.37, показана на рис.
7.38. а,Ь Рис. 7.38 Функцию выходов р конечного автомата с выходом М можно доопределить до некоторого отображения д* из ц х т" в тт'. Для этого фиксируем произвольно состояние д и входную цепочку х Е 'т'. Тогда в силу детерминированности конечного автомата Му существует единственнътй путвь в Му (и, следовательно, в диаграмме М), ведущий из д в некоторое состояние г, на котором читается цепочка х.
Пусть а Е т входной символ,принадлежащий входной метке некоторой дуги, исходящей из г. Тогда положим р'(д,х) = Л, если х = Л; р'(д,ха) = р'(т7,х)р(г,а) (заметим, что при этом для любых д Е Я и а Е У,ы'(д, а) = р(д, а), т.е. функция выходов конечного автомата с выходом есть сужение фрикции р' иа подмиожестиво т,т х У). В частности, для любой входной цепочки х, допускаемой конечным авитомаитом Мт, положим Д.у.2.
Ковечвые автоматы с выходом. Структурвыв сввтеэ 555 Функция ум, определенная выражением (7.11), называется ,ярнкцией, вычисляемой конечным автпоматпом с выходом М Так, для конечного автомата на рис. 7.37 имеем, например, тд~(аЬЬа) = 0110. Можно показать, что функция ум, вычисляемая данным конечным автоматом, есть бпекцвл регулярного языка (а + Ь)'6Ь(а + Ь)" в алфавите т' = (а, 6) на регулярный язык (0+ 1)'11(0+1)" в алфавите тт' = (О, Ц, такая, что для каждой цепочки х первого языка цепочка ум(х) получается заменой каждого вхождения символа а символом 0 и заменой каждого вхождения символа 6 символом 1. Функция из т" в ЬЬ" нззываетсл ограниченно детперминнрованной функцией (или ОД-ф1тнкцней), если она вычисляется некоторым конечным автоматом с выходом.
Замечание 7.13. Термин „ограниченно детерминированная функция" связан с тем, что множество всех функций вида 1: 'т' -+ тт', вычисляемых конечными автоматами с выходом, есть собственное подмножество множества всех таквх функций, которые вычисляются посредством так называемых машин Тьюринга. Машина Тьюринга является самой общей математической моделью „детерминированного преобразователя слов", т.е. моделью, с помощью которой может быть вычислена любая функция из множества слов в одном алфавите в множество слов в другом алфавите (см. Д.7.4). Таким образом, каждый конечный автомат с выходом вычисляет некоторую ОД-функцию. С интуитивной точки зрения зто значит, что конечный автомат с выходом работает как „детерминированный преобразователь" слов (цепочек) во входном алфавите в слова (цепочки) в выходном алфавите.
В отличие от обычного конечного автомата, который является чистым „распознавателем", конечный автомат с выходом снабжен выходной лентой, на которую записывается выходная цепочка ты(х) для заданной входной цепочки х (рис. 7.39). 556 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Входная лента Рис. 7.39 Для конечных автоматов с выходом может быть поставлена задача спьруктпурноео синпиеза. Содержательно ее можно представить как задачу, аналогичную задаче реализации булевой функции или булева оператпора схемой из функниональных злв,аеншов.
Однако в отличие от СФЭ, реализующей булев оператор, „схема", которая реализует ОД-функцию (или, что то же, вычисляющий ее конечный автомат с выходом), должна помимо функциональных элементов, каждый из которых вычисляет некоторую булеву функцию кз заданного конечного множества функций, содержать так называемые элементы задержки, позволяющие хранить информацию о текущем состоянии автомата. Чтобы объяснить это, представим себе (на интуитивном уровне) процесс работы конечного автомата с выходом во времени. В начальный моментвремени (время дискретно!) 8=0 блок управления конечного автомата с выходом находится в начальном состоянии д(0) = дв.
Предположим, что в произвольный момент времени $ > 0 состояние есть д($). Пусть в этот момент времени конечный автомат считывает с входной ленты символ х(1). Тогда в этот же момент времени Ф на выходной ленте появится выходной символ у(1), а его устройство управ- Длй. Кояечяые автоматы с еъпеолом. Структуовый святее 557 ленив перейдет в состояние д($+ 1), в котором и останется до следующего момента времени Ф+ 1. При этом выполняются соотношения д((+1) = б(д((),х(Ф)), у(() )ы(я(() х(Ф)) д(0) = Чо. (7.12) Эти соотношения называют каноническими уравнениями данного конечноео автпоматпа с выходом. Из канонических уравнений (7.12) вытекает, что „схема", реализующая конечный автомат с выходом, должна иметь „память" о состоянии устройства управления в предыдущий момент вРемени.
Эта епамлтьо РезлизУетсл с помощью так называемых элеменпюве эадерхскн, или тприеееров. Конструированию „схемы" предшествует двоичное кодирование входных и выходных символов, а также состояний устройства управления. Это значит, что каждому состоянию или символу однозначно сопоставляется булее ееншор (набор) соответствующей размерности.
В общем виде искомая „схема" должна содержать два блока: назовем их комбинационной частпью (КЧ) и эапоминаюн(еб частпью (ЗЧ) (рис. 7.40). На вход комбинационной части поступают в каждый момент времени ( двоичный код входного символа (булез вектор Х($)) и у(с) двончныи код состояния от эа; Щ поминающей части (булев век- КЧ ЗЧ тор У($) ), а с выхода комбинз У(0 ционной части снимается двоич- ный код выходного символа (булез вектор У(~) ) и двоичный код следующего состояния (булев вектор у((+1) ). Если через Р и се обозначить булевы операторы, сопоста- вленные в результате указанного выше двоичного кодирования 558 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ функциям перехода и выхода соответственно, то канонические уравнения примут вид Таким образом, комбинационная часть строится как некая схема нз функциональных элементов, реализующая булез оператор, определяемый первыми двумя уравнениями (7.13), тогда как запоминающал часть содержит необходимое число триггеров и релизует „задержку" У($+1) = Я($).
Каждый триггер есть устройство преобразования „одноразрядного двоичного сигнала" (с математической точки зрения булеза вектора размерности 1), состоящего в задержке этого сигнала „на один такт". Иначе говоря, если в момент времени $ на вход триггера Т поступает сигнал х(Ф), в момент Ф+ 1 с выхода триггера снимается сигнал у(8+ 1) = х(Ф).
Обычна рассматривают триг- геры с двумя выходами: нрлнььн и 11 т "О 11 инверсным. Прямой выход работает так, как описано выше, а инверсный рО+ П выдает сигнал, являющийся ошринани- ем сигнала прямого выхода (рис. 7.41). Рис. Т.41 Теперь обсудим вопрос о размерности булевых векторов, кодирующих состояния и символы обоях алфавитов. Произвольное непустое конечное множество о = (лм ..., лр) может быть „закодировано" двоичными числами таким образом: нумеруем элементы Я от 0 до р — 1 и эти номера записываем в двоичной системе счисления.
Нетрудно сообразить, что тогда разрядность этих чисел (или, что то же самое, размерность соответствующих булевых векторов) составит ] 1окзр( (ближайшее целое, большее 1обз р). Так, если р = 15, Д.у.2. Ковечвые автоматы с выходом. Струхтурвый святее 559 то для того, чтобы закодировать числа от 0 до 14, нужны четырехрвзрядные двоичные коды, поскольку ] 1ояз 15[ = 4. Заметим, что в общем случае, поскольку число 1оязр не будет целым, не все двоичные числа соответствующей разрядности будут использованы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
