13.Сети автоматов. Их анализ и синтез.

Автомат (Мили) называется комбинационным, если для любого входного символа aи любых состоянийq_iиq_jg(q_i,a)=g(q_j,a), иначе говоря, если выходной симовл не зависит от текущего состояния и определяется входным символом (все состояния автомата в данном случае эквивалентны, т.е. минимизированный автомат будет иметь всего одно состояние).

Автомат называется логическим, если его входной алфавит состоит из 2^mдвоичных наборов длиныm, а выходной алфавит – 2ⁿдвоичных наборов длиныn. Тогда функция выхода – набор изnлогических функций отmпеременных. Можно получать автоматные блок-схемы, например, схему, представленную на рис. 36.

Рис. 36. Схема автоматов.

Следует отметить, что автоматы в такой схеме должны уметь останавливаться.

Возможны различные случаи рассмотрения автоматных схем.

1. Если алфавиты автоматов не пересекаются. В этом случае действуют обычные правила минимизации для частичных автоматов, и для правильных последовательностей входных сигналов число суммарное состояний получаемого автомата – maxQ_i.

2. Если входные алфавиты исходных автоматов совпадают или включают друг друга, тогда множество состояний является объединением множества состояний исходных состояний, затем могут производиться эквивалентные преобразования автомата, в этом случае число состояний Q_i.

В любом случае блок-схема автоматов, работающих последовательно – конечный автомат S, значит, множество автоматов замкнуто относительно операции условного и безусловного перехода( следовательно, каждая программа является автоматом, и каждый алгоритм так же).

Синхронные сети автоматов.

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

Под состоянием сети из mавтоматовS₁,S₂,…,S_mпонимается вектор (q_i¹,,,,q_i^m), где каждоеq_i^jсостояние автоматаj. В общем случае число состояний автомата, полученного в результате построения сети – произведение числа состояний исходных автоматов.

Является ли полученная схема автоматом?

Один из способов введения времени – синхронный: такты, границы тактов нумеруются натуральными числами, начиная с 0.

Длина такта рассматривается как единица времени. Входное слово – временная последовательность сигналов (импульсов). Интервал между соседними импульсами – длина такта. Слово длины kбудет обрабатываться заkтактов. Входная информация -a(t).

Автоматные функции fиgреализуются с задержкой;f(q(t),a(t))=q(t+1),q(0) –задаётся отдельно,

g(q(t),a(t))=b(t) обычно, ( иногдаg(q(t),a(t))=b(t+1), тогда задаётсяb(0))

Виды соединения автоматов:

1. Параллельное соединение

   1. С разделительными входами и алфавитами А₁и А₂(рис. 37.а).S =<A, Q,V, q₀, F,G>

В этом случае входной алфавит A= А₁А₂, внутренний алфавитQ=Q₁Q₂, выходной алфавитV= V₁V₂.Sназывается прямым произведением автоматовS₁иS₂. В этом случаеa=(a¹,a²) (Здесь верхний индекс означает отнесение к соответствующему алфавиту).

f((q¹,q²), (a¹,a²))=(f₁(q¹,a¹),f₂(q²,a²)).

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

2. С общим входом и алфавитом А (рис. 37 б).

В этом случае f((q¹,q²),a)=(f₁(q¹,a),f₂(q²,a)). Определение выходов в обоих случаях очевидно.

Рис. 37 Параллельное соединение автоматов.

2. Последовательное соединение автоматов (рис.38).

S =<A, Q,V, q₀, F,G>, A=A₁, V=V₂, V₁=A₂, Q= Q₁Q₂. ДляFиGсущественна задержкаg₁. Если задержкаg₁равна 0, т.е.g₁(q¹(t),a(t))=v¹(t), тоq(t+1)=(q¹(t+1),q²(t+1))= (f₁(q¹(t),a(t)),f₂(q²(t),g₁(q¹(t),a(t))), т.е. зависимость существует только отq(t),a(t), при этом состояниеq(t+1)=f(q(t),a(t)), выходg((q¹,q²),a)=g₂(q²,g¹(q¹,a)).

Если же задержка g₁равна 1, т.е.g₁(q¹(t),a(t))=v¹(t+1), тоq(t+1= (f₁(q¹(t),a(t)),f₂(q²(t),g₁(q¹(t-1),a(t-1))), и такой простой зависимости, как для прошлого случая, нет.

Пример.

рассмотрим схему из двух элементов задержки, воспроизводящих вход через 1 такт. S₁иS₂имеют по одному состоянию, начальное значение выхода =0,S()=00_-2(отбрасываются два последних символа последовательности).

Таблица переходов автомата, реализующего задержку:

	q0	q1
0	q0, 0	q1, 1
1	q0, 0	q1, 1

Считаем, что если задержка gравна 0,g(q(t),a(t))=v(t)=g(t)

Обозначим состояние (q_i,q_j) черезij. Тогда таблица переходов/выходов результирующего автомата

	00	01	10	11
0	00,0	00,1	01,0	01,1
1	10,0	10,1	11,0	11,1

Т.о. цепь из двух элементов задержки описывается автоматом без задержки.

3. Соединение автоматов с обратной связью. Общая схема представлена на рис. 39

Рис.39 Схема соединения с обратной связью

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

Например, если s(x) функция Шеффера, иv(t)=0, тогдаx₂=0, значит,v(t)=1, а приx₁=1 это даётv(t)=0. Противоречие, т.е. в реальности состояние будет не определено.

Поэтому вводится задержка и схема автомата приобретает следующий вид (рис.40).

Рис.40 Общая схема автомата с обратной связью

Всякий автомат при синхронной интерпретации может быть реализован как сеть, составленная из комбинационных автоматов и элементов задержки.

На рис. 40 приведена схема для автомата с функциями

q(t+1)=f(q(t),a(t))

v(t)=g(q(t),a(t))

На рисунке g– комбинационный автомат с входным алфавитомAQи выходным алфавитомV,f– комбинационный автомат с входным алфавитомAQи выходным алфавитомQ,D– блок задержки (на 1 такт).

D– автомат Мура, входной и выходной алфавит которогоQ= {q₁,q₂,…,q_n}, множество состояний -R={r₁,r₂,…,r_n},RQ, функцииg(r_i)=q_i,f_D(r_i,q_j)=r_j.

Частный случай D– двоичный элемент задержки, когдаg1(t)=f(q(t),a(t))=q(t+1).

В важном частном случае, когда A,V,Qсостоят из двоичных наборов,fиg– логические комбинационные автоматы, двоичные входы которых в моментtявляются логическими функциями от двоичных переменных, образующих наборыa(t) иq(t),D– параллельное соединение элементов задержки. Число элементов задержки равно длине вектораQ, а число состоянийDравно мощности входного алфавитаQ= 2ⁿ.

Так как произвольные конечные алфавиты могут быть закодированы двоичными наборами, то получается

Теорема. Любой конечный автомат при любом двоичном кодировании может быть реализован синхронной сетью из логических комбинационных автоматов и двоичных задержек, причем число задержек не может быть меньше log₂Q.

Сеть из логических блоков и элементов задержки будем называть правильно построенной логической сетью (ППЛС), если

1. К каждому входу блока сети присоединён не более чем один выход блока сети (однако допускается присоединение выхода более чем к одному входу, т.е. допускается разветвление выходов)

2. В каждом контуре обратной связи, т.е. в каждом цикле, образованном блоками и соединениями между ними, имеется не менее одного элемента задержки.

Входами такой сети называются те входы блоков, к которым не присоединены никакие выходы, выходами сети называются те выходы блоков, которые не присоединены ни к каким входам (рис.41).

Рис. 41

Основные этапы проектирования автоматов

M_x- множество входных векторов,

M_z– множество выходных векторов,

M_y-- множество векторов, характеризующих входные каналы обратной связи (памяти),

M_y+- множество векторов, характеризующих выходные каналы обратной связи (памяти).

Каждый из каналов в случае k-значной логики может находиться в одном изkзначений из множества {0, 1,…,k-1}.

Правила вывода в грамматике, соответствующей автомату, можно определить как подстановку

XY⁺ Z Y^-, Y⁺(t=0)=Y₀⁺, Y⁺(t+)=Y^-(t).

Состояния каналов обратной связи будем называть внутренними состояниями автомата, а - временем перехода из одного состояния в другое, причёмможет быть постоянной для данного автомата или эже зависеть от измененияX. В первом случае автомат называется синхронным, во втором – асинхронным.

При заданном значении Y₀⁺последовательность входных векторовX(входная последовательность) однозначно определяет последовательность векторовZ(выходную последовательность).

Объём памяти автомата (число внутренних состояний автомата) обычно гораздо меньше объема памяти операционного автомата.

Общая структура автомата представлена на рис.42.

рис. 42. Общая схема автомата. Здесь

1 – преобразуемая информация,

2 – результат преобразования,

3 - управляющее воздействие, соответствующее реализуемому алгоритму,

4 - признаки, характеризующие результат

5 – сигнал, определяющий выполняемое преобразование и его начало,

6 – сигнал окончания операции.

!-2 – информационные каналы,

3-6- управляющие.

По Глушкову – ЭВМ – преобразователь информации, который целесообразно рассматривать как композицию пар автоматов (операционный+управляющий).

Общий порядок проектирования автоматов:

системное проектирование – логическое проектирование (логические блоки) – техническое проектирование.

Литература

1. Сергиевский Г.М. «Лингвистические модели», М., 1983

2. В.Дж.Рейуорд-Смит «Теория формальных языков», М., Радио и связь, 1988

3. О.П.Кузнецов, Г.М. Адельсон-Вельский «Дискретная математика для инженера», Энергоатомиздат, 1988

4. В.А. Горбатов «Основы дискретной математики», М., ВШ, 1986

5. В.А. Горбатов «Фундаментальные основы дискретной математики», М., Наука, 2000.

49