Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Конечные автоматы с выходом. Структурный синтез

Конечные автоматы с выходом. Структурный синтез


Пусть M=(V,Q,q_0,F,\delta) — детерминированный конечный автомат. Модифицируем метки его дуг, а именно фиксируем произвольно алфавит W, который назовем выходным (хотя он может и совпадать со входным алфавитом V конечного автомата M), его буквы назовем выходными символами и для каждой дуги e конечного автомата M проделаем следующее: каждому входному символу a, принадлежащему метке дуги е, сопоставим однозначно упорядоченную пару (a,b)\in V\times W.


Полученный таким образом размеченный ориентированный граф называют конечным автоматом с выходом.


Конечный автомат с выходом может быть определен и иначе, независимо от понятия детерминированного конечного автомата. Конечный автомат с выходом есть упорядоченная семерка


M=(V,W,Q,q_0,F,\delta,\mu),

где V — входной алфавит (его элементы — входные символы); W — выходной алфавит (его элементы — выходные символы); Q — конечное множество состояний конечного автомата с выходом; q_0 — выделенное состояние, называемое начальным состоянием конечного автомата с выходом; F — выделенное непустое подмножество состояний, каждый элемент которого называют заключительным состоянием конечного автомата с выходом; \delta\colon Q\times V\to Q — отображение, называемое функцией переходов конечного автомата с выходом; \mu\colon Q\times V\to W — отображение, называемое функцией выходов конечного автомата с выходом.


Графом (или диаграммой) конечного автомата с выходом M называют ориентированный граф, множество вершин которого совпадает с множеством состояний Q, а множество дуг определяется так: из вершины (состояния) q ведет дуга в вершину (состояние) r тогда и только тогда, когда r=\delta(q,a) для некоторого входного символа a (причем, поскольку \delta есть отображение, для каждой пары (q,a) указанное состояние r единственное).


Каждой дуге диаграммы конечного автомата с выходом M сопоставляется метка, являющаяся конечным множеством упорядоченных пар из V\times W, так, что пара (a,b) принадлежит метке дуги q\to r тогда и только тогда, когда \mu(q,a)=b.


Как видно, метка каждой дуги конечного автомата с выходом есть конечное соответствие, функциональное по второй компоненте (т.е. частичное отображение из V в W). Область определения этого соответствия называется входной меткой дуги, а область значений — выходной меткой дуги (диаграммы конечного автомата с выходом).


На рис. 7.37 показана диаграмма конечного автомата с выходом, у которого входной алфавит V=\{a,b\}, выходной алфавит W=\{0;1\}, множество состояний Q=\{q_0,q_1,q_2\} при начальном состоянии q_0 и заключительном — q_2. Функции переходов и выходов определяются метками дуг. Обычно при изображении диаграмм упорядоченная пара (i,0)\in V\times W записывается через косую черту: i/0.


Диаграмма конечного автомата с выходом, у которого входной алфавит V={a,b}

Можно показать, что два сформулированных выше определения конечного автомата с выходом равносильны и тем самым существует взаимно однозначное соответствие между конечными автоматами с выходом (в смысле второго определения) и ориентированными графами, дуги которых размечены над декартовым произведением двух алфавитов так, как это описано в первом определении. Исходя из этого, мы можем отождествить конечные автоматы с выходом и их диаграммы.


Таким образом, каждому конечному автомату с выходом M однозначно сопоставляется детерминированный конечный автомат M_V=(V,Q,q_0,F,\delta), метки дуг которого получаются "стиранием" всех выходных символов в упорядоченных парах, которыми помечены дуги исходного конечного автомата с выходом (на каждой дуге остается только ее входная метка). Этот детерминированный конечный автомат будем называть входной проекцией конечного автомата с выходом или V-проекцией конечного автомата с выходом M. Входная проекция конечного автомата с выходом, диаграмма которого изображена на рис. 7.37, показана на рис. 7.38.


Диаграмма входной проекции конечного автомата с выходом

Функцию выходов \mu конечного автомата с выходом M можно доопределить до некоторого отображения \mu^{\ast} из Q\times V^{\ast} в W^{\ast}. Для этого фиксируем произвольно состояние q и входную цепочку x\in V^{\ast}. Тогда в силу детерминированности конечного автомата M_V существует единственный путь в M_V (и, следовательно, в диаграмме M), ведущий из q в некоторое состояние r, на котором читается цепочка x. Пусть a\in V — входной символ, принадлежащий входной метке некоторой дуги, исходящей из r. Тогда положим \mu^{\ast}(q,x)=\lambda, если x=\lambda; \mu^{\ast}(q,xa)= \mu^{\ast}(q,x)\mu(r,a) (заметим, что при этом для любых q\in Q и a\in V имеется \mu^{\ast}(q,a)=\mu(q,a), т.е. функция выходов конечного автомата с выходом есть сужение функции \mu^{\ast} на подмножество Q\times V). В частности, для любой входной цепочки x, допускаемой конечным автоматом M_V, положим


f_M(x)=\mu^{\ast}(q_0,x).
(7.11)

функция f_M определенная выражением (7.11), называется функцией, вычисляемой конечным автоматом с выходом M.


Так, для конечного автомата на рис. 7.37 имеем, например, f_M(abba)=0110. Можно показать, что функция f_M, вычисляемая данным конечным автоматом, есть биекция регулярного языка (a+b)^{\ast}bb(a+b)^{\ast} в алфавите V=\{a,b\} на регулярный язык (0+1)^{\ast}11(0+1)^{\ast} в алфавите W=\{0;1\}, такая, что для каждой цепочки x первого языка цепочка f_M(x) получается заменой каждого вхождения символа a символом 0 и заменой каждого вхождения символа b символом 1.


Функция из V^{\ast} в W^{\ast} называется ограниченно детерминированной функцией (или ОД-функцией), если она вычисляется некоторым конечным автоматом с выходом.


Замечание 7.13. Термин "ограниченно детерминированная функция" связан с тем, что множество всех функций вида f\colon V^{\ast}\to W^{\ast}, вычисляемых конечными автоматами с выходом, есть собственное подмножество множества всех таких функций, которые вычисляются посредством так называемых машин Тьюринга. Машина Тьюринга является самой общей математической моделью "детерминированного преобразователя слов", т.е. моделью, с помощью которой может быть вычислена любая функция из множества слов в одном алфавите в множество слов в другом алфавите.




Входная и выходные ленты конечного автомата

Таким образом, каждый конечный автомат с выходом вычисляет некоторую ОД-функцию. С интуитивной точки зрения это значит, что конечный автомат с выходом работает как "детерминированный преобразователь" слов (цепочек) во входном алфавите в слова (цепочки) в выходном алфавите. В отличие от обычного конечного автомата, который является чистым "распознавателем", конечный автомат с выходом снабжен выходной лентой, на которую записывается выходная цепочка f_M(x) для заданной входной цепочки x (рис. 7.39).


Для конечных автоматов с выходом может быть поставлена задача структурного синтеза. Содержательно ее можно представить как задачу, аналогичную задаче реализации булевой функции или булева оператора схемой из функциональных элементов. Однако в отличие от СФЭ, реализующей булев оператор, "схема", которая реализует ОД-функцию (или, что то же, вычисляющий ее конечный автомат с выходом), должна помимо функциональных элементов, каждый из которых вычисляет некоторую булеву функцию из заданного конечного множества функций, содержать так называемые элементы задержки, позволяющие хранить информацию о текущем состоянии автомата.


Чтобы объяснить это, представим себе (на интуитивном уровне) процесс работы конечного автомата с выходом во времени.


В начальный момент времени (время дискретно) t=0 блок управления конечного автомата с выходом находится в начальном состоянии q(0)=q_0. Предположим, что в произвольный момент времени t\geqslant0 состояние есть q(t). Пусть в этот момент времени конечный автомат считывает с входной ленты символ x(t). Тогда в этот же момент времени t на выходной ленте появится выходной символ y(t), а его устройство управления перейдет в состояние q(t+1), в котором и останется до следующего момента времени t+1. При этом выполняются соотношения


\begin{cases}q(t+1)=\delta(q(t),x(t)),\\ y(t)=\mu(q(t),x(t)),\\ q(0)=q_0. \end{cases}
(7.12)

Эти соотношения называют каноническими уравнениями данного конечного автомата с выходом.


Блочная схема с комбинационной частью и запоминающей частью

Из канонических уравнений (7.12) вытекает, что "схема", реализующая конечный автомат с выходом, должна иметь " память" о состоянии устройства управления в предыдущий момент времени. Эта "память" реализуется с помощью так называемых элементов задержки, или триггеров.


Конструированию "схемы" предшествует двоичное кодирование входных и выходных символов, а также состояний устройства управления. Это значит, что каждому состоянию или символу однозначно сопоставляется булев вектор (набор) соответствующей размерности. В общем виде искомая "схема" должна содержать два блока: назовем их комбинационной частью (КЧ) и запоминающей частью (ЗЧ) (рис. 7.40). На вход комбинационной части поступают в каждый момент времени t двоичный код входного символа (булев вектор X(t)) и двоичный код состояния от запоминающей части (булев вектор U(t)), а с выхода комбинационной части снимается двоичный код выходного символа (булев вектор Y(t)) и двоичный код следующего состояния (булев вектор U(t+1)).


Если через F и G обозначить булевы операторы, сопоставленные в результате указанного выше двоичного кодирования функциям перехода и выхода соответственно, то канонические уравнения примут вид


\begin{aligned}Z(t)=F(U(t),X(t)),\\ Y(t)=G(U(t),X(t)),\\ U(t+1)=Z(t),\\ U(0)=U_0,\\ t\geqslant0. \end{aligned}
(7.13)

Таким образом, комбинационная часть строится как некая схема из функциональных элементов, реализующая булев оператор, определяемый первыми двумя уравнениями (7.13), тогда как запоминающая часть содержит необходимое число триггеров и реализует "задержку" U(t+1)=Z(t). Каждый триггер есть устройство преобразования "одноразрядного двоичного сигнала" (с математической точки зрения булева вектора размерности 1), состоящего в задержке этого сигнала "на один такт". Иначе говоря, если в момент времени t на вход триггера T поступает сигнал x(t), в момент (t+1) с выхода триггера снимается сигнал y(t+1)=x(t). Обычно рассматривают триггеры с двумя выходами: прямым и инверсным. Прямой выход работает так, как описано выше, а инверсный выдает сигнал, являющийся отрицанием сигнала прямого выхода (рис. 7.41).


Прямой выход блока

Теперь обсудим вопрос о размерности булевых векторов, кодирующих состояния и символы обоих алфавитов. Произвольное непустое конечное множество S=\{s_1,\ldots,s_p\} может быть "закодировано" двоичными числами таким образом: нумеруем элементы S от 0 до (p-1) и эти номера записываем в двоичной системе счисления. Нетрудно сообразить, что тогда разрядность этих чисел (или, что то же самое, размерность соответствующих булевых векторов) составит ]\log_{2}p[ (ближайшее целое, большее \log_{2}p). Так, если p=15, то для того, чтобы закодировать числа от 0 до 14, нужны четырехразрядные двоичные коды, поскольку ]\log_{2}15[=4. Заметим, что в общем случае, поскольку число ]\log_{2}p[ не будет целым, не все двоичные числа соответствующей разрядности будут использованы. Так, при p=15 не будет использовано число 1111 (двоичный код числа 15).


Тогда размерности булевых векторов X (кодов входных символов), Y (кодов выходных символов), U и Z (кодов текущего и нового состояний) соответственно будут равны:


n=]\log_{2}|V|[,\qquad m=]\log_{2}|W|[,\qquad k=]\log_{2}|Q|[.

Предлагается следующий алгоритм определения булевых операторов F и G в (7.13).


1. Составляется таблица для функций переходов и выходов исходного конечного автомата с выходом (табл. 7.1).


\begin{aligned}\mathit{Table~7.1}~&\\ \begin{array}{|c|c|c|c|} \hline \text{Current status} & \text{Input symbol}& \text{Output symbol}& \text{New status} \\\hline \vdots & \vdots & \vdots & \vdots \\\hline q& a& b=\mu(q,a)& r=\delta(q,a) \\\hline \vdots & \vdots & \vdots & \vdots \\\hline \end{array} &\end{aligned}

2. По составленной таблице (см. табл. 7.1) строят так называемую структурную таблицу (табл. 7.2), в которой каждый символ (входной и выходной) и каждое состояние заменяются их двоичным кодом, причем так, что если набор (u_1,\ldots,u_k) есть код текущего состояния q, набор (x_1,\ldots,x_n) есть код входного символа a, то


(y_1,\ldots,y_m)= G \bigl((u_1,\ldots,u_k),(x_1,\ldots,x_n)\bigr)

тогда и только тогда, когда набор (y_1,\ldots,y_m) есть код выходного символа b=\mu(q,a), a


(z_1,\ldots,z_k)= F \bigl((u_1,\ldots,u_k),(x_1,\ldots,x_n)\bigr)

тогда и только тогда, когда набор (z_1,\ldots,z_k) есть код состояния r=\delta(q,a).


\begin{aligned}\mathit{Table~7.2}~&\\ \begin{array}{|c|c|c|c|} \hline U& X& Y& Z \\\hline \vdots & \vdots & \vdots & \vdots \\\hline u_1,\ldots,u_k& x_1,\ldots,x_n & y_1,\ldots,y_m & z_1,\ldots,z_k \\\hline \vdots & \vdots & \vdots & \vdots \\\hline \end{array} &\end{aligned}

Структурная таблица есть не что иное, как таблица, задающая некоторый булев оператор (вообще говоря, частичный, так как не все векторы соответствующей размерности служат кодами элементов множеств V,W,Q) из \mathbb{B}^{k+n} в \mathbb{B}^{m+k}. Этот оператор может быть реализован некоторой схемой из функциональных элементов (как правило, над стандартным базисом). Вектор Z поступает (в некоторый момент времени t) на входы к триггеров, с прямых выходов которых (в момент времени t+1) снимается вектор U, то есть U(t+1)=Z(t). Таким образом, если в начальный момент времени t=0 с выхода запоминающей части снимается вектор U_0, код начального состояния q_0 и на вход комбинационной части поступит вектор X(0), то на вход запоминающей части в этот же момент времени поступит вектор Z(0)=F(U(0),X(0))=U(1) и триггеры запоминающей части будут хранить уже информацию о новом состоянии до момента времени t=1 и т.д.


В этом небольшом дополнении мы никак не можем сколько-нибудь подробно и строго обсуждать математическую теорию реализации ОД-функций "схемами" с элементами задержки. Разумеется, нет и речи о каких-либо доказательствах. Также мы не решаем "инженерно-технические" проблемы структурного синтеза, в частности проблемы "аппаратной реализации" триггеров. Наша цель здесь — показать в рамках самого элементарного изложения связь между теорией конечных автоматов и теорией булевых функций. Эта связь состоит в том, что теория булевых функций дает аппарат для структурного синтеза конечных автоматов (с выходом), т.е. для перехода от описания функции, вычисляемой конечным автоматом, к его структуре, реализующей его "схеме", построенной на функциональных элементах и элементах задержки.


В заключение разберем простой пример структурного синтеза.




Пример 7.14. Конечный автомат с выходом задан диаграммой, изображенной на рис. 7.42. С содержательной точки зрения этот автомат работает как простейший "лексический анализатор", распознавая все цепочки во входном алфавите V=\{a,a,0,1\}, которые начинаются с "буквы", т.е. с символа a или b, как "правильные", тогда как цепочки, начинающиеся с "цифры" (т.е. с 0 или 1), классифицируются как "неправильные", о чем выдается сообщение в виде выходного символа "?".


Конечный автомат с выходом, заданный диаграммой

Кодируя входной и выходной алфавиты, а также состояния, получим следующие двоичные коды:


1) входной алфавит: a-00,~ b-01,~0-10,~1-11;
2) выходной алфавит: 0-00,~1-01,~?-10, код 11 не используется;
3) множество состояний: q_0-00,~ q_1-01,~ q_2-10, код 11 не используется.

Так как рассматриваемый автомат простой, мы сразу составим структурную таблицу (табл. 7.3).


\begin{aligned}\mathit{Table~7.3}~&\\ \begin{array}{|cc|cc|cc|cc|} \hline u_1&u_2&x_1&x_2& y_1&y_2&z_1&z_2\\\hline 0&0&0&0&0&0&0&1\\ 0&0&0&1&0&0&0&1\\ 0&0&1&0&1&0&1&0\\ 0&0&1&1&1&0&1&0\\\hline 0&1&0&0&0&0&0&1\\ 0&1&0&1&0&0&0&1\\ 0&1&1&0&0&1&0&1\\ 0&1&1&1&0&1&0&1\\\hline 1&0&0&0&0&0&1&0\\ 1&0&0&1&0&0&1&0\\ 1&0&1&0&0&1&1&0\\ 1&0&1&1&0&1&1&0\\\hline \end{array}&\end{aligned}

Для частичных булевых функций


y_1=y_1(x_1,x_2,u_1,u_2),\quad y_2=y_2(x_1,x_2,u_1,u_2),\quad z_1=z_1(x_1,x_2,u_1,u_2),\quad z_2=z_2(x_1,x_2,u_1,u_2)

ставим карты Карно и найдем для каждой из них минимальную ДНФ.


Карта Карно для функции

Для функции y_1 карта Карно изображена на рис. 7.43. Единственная склейка дает y_1=\overline{u}_1\overline{u}_2x_1. Для второй функции получим (рис. 7.44) y_2=u_2x_1\lor u_1x_1= x_1(u_1\lor u_2). Для функции z_1 имеем (рис. 7.45) минимальную ДНФ z_1=u_1\lor x_1\overline{u}_2. Наконец, для функции z_2 по карте Карно, изображенной на рис. 7.46, находим z_2=u_2\lor\overline{x}_1\overline{u}_1.


Карта Карно для функции 2

Структурная схема автомата представлена на рис. 7.47. Обратим внимание на то, что вместо инверторов для сигналов u_1 и u_2 мы используем сигналы, снимаемые с инверсных выходов триггеров T_1 и T_2. Заметим также, что переменная x_2 оказалась фиктивной. Действительно, тип входного символа ("буква", т.е. а или Ь, и "цифра", т.е. 0 или 1) распознается по первому разряду входного вектора X: при x_1=0 имеем " букву", а при x_1=1 — "цифру".


Структурная схема автомата

Наконец, следует заметить, что синтезированная "структурная схема", строго говоря, не является графом (поскольку содержит, например, "кратные дуги", т.е. допускает несколько разных дуг между одной и той же парой вершин). Даже комбинационная часть этой схемы не может быть уже названа схемой из функциональных элементов, так как в вершины, помеченные переменными u_1,u_2 заходят некоторые дуги. Это будет, говоря неформально, схема из функциональных элементов, "вставленная" в некий более общий "графовый объект".


Строгая математическая теория таких "обобщенных графов" в этом курсе не рассматривается.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved