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

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

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

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

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


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

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


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


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


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


[math]M=(V,W,Q,q_0,F,\delta,\mu),[/math]

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


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


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


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


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


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

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


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


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

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


[math]f_M(x)=\mu^{\ast}(q_0,x).[/math]
(7.11)

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


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


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


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




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

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


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


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


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


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

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


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

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


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


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


[math]\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}[/math]
(7.13)

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


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

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


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


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

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


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


[math]\begin{array}{|c|c|c|c|}\multicolumn{4}{r}{\mathit{Table~7.1}}\\\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}[/math]

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


[math](y_1,\ldots,y_m)= G \bigl((u_1,\ldots,u_k),(x_1,\ldots,x_n)\bigr)[/math]

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


[math](z_1,\ldots,z_k)= F \bigl((u_1,\ldots,u_k),(x_1,\ldots,x_n)\bigr)[/math]

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


[math]\begin{array}{|c|c|c|c|}\multicolumn{4}{r}{\mathit{Table~7.2}}\\\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}[/math]

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


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


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




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


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

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


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

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


[math]\begin{array}{|cc|cc|cc|cc|}\multicolumn{8}{r}{\mathit{Table~7.3}} \\\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}[/math]

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


[math]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)[/math]

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


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

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


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

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


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

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


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


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


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

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