Пред. страница   . След. страница   Раздел   Содержание

________________________________________________________________________________________________________

4.4. Автоматные преобразователи

4.4.1. Определение и работа автоматного преобразователя

Определение. Если задан перевод С, то преобразователем или транслятором назовем устройство, которое по заданной цепочке αÎ Lвх, находит цепочку ρÎ Lвх, такую что (α, ρ) Î С.

Простейшим преобразователем является конечный автоматный преобразователь (А- преобразователь). Он отличается от автомата без выходов тем, что в каждом такте работы он может создавать на выходы в общем случае цепочку выходных символов. Схему такого преобразователя можно изобразить так:

Рис. 4.1. Модель автоматного преобразователя.

А-преобразователь A определяется следующей совокупностью объектов:

A = {P, S, s₀, F, W, φ},

где P - входной алфавит, состоящий из символов, записываемых на входную ленту,

S - множество состояний автомата,

s₀- начальное состояние из множества S,

F - множество конечных или заключительных состояний, представляющих собой подмножество S,

W - выходной алфавит, содержащий символы, записываемые на выходную ленту,

φ - функция переходов, которая в общем случае задает отображение.

φ: P ´ S ® S ´ W*,

которое в функциональной форме можно записать так:

φ(s, p)=(s', g),

где p Î P, s,s' Î S, g Î W*.

В частном случае

φ: P ´ S ® S ´ W.

В функциональной форме отображение имеет вид:

φ q(s, p)=(s',w),

где p Î P, s,s' Î S, w Î W. Этот частный случай соответствует определению конечного автомата с выходами.

Работу КП удобно описывать с помощью смены конфигураций. Как обычно назовем конфигурацией тройку:

(s, a, g),

где s Î S, a Î P* и g Î W*.

Если такт работы КП определяется конфигурацией (s, ab, g) и определена функция переходов φ(s, a)=(s', m), то происходит смена такта, которая заключается в переходе к новой конфигурации

(s', b, gm).

Смену конфигураций обозначим так:

(s', b, gm) |¾ (s', b, gm).

Последовательности сменяющих друг друга конфигураций, как обычно, будем обозначать символом |¾*.

Определение. Цепочку g назовем выходом входной цепочки a, если существует последовательность конфигураций (s₀, a, $) |¾* (s', $, g)

для некоторого s' Î F.

Определение. Множество пар, состоящих из входных и соответствующих им выходных цепочек, назовем переводом, определяемым преобразователем A и обозначим C(A).

C(A) = { (a, g)|(s0, a, $) |¾ (s', $, g) & sÎ F }.

Утверждение. Для каждой простой СУ-схемы T={V_A, V_твх, V_твых, I, Q}, у которой входная и выходная грамматики являются автоматными, можно построить конечный преобразователь A, такой что С(A)=С(Т).

Построение преобразователя A по заданной СУ-схеме Т начнем с того, что примем P = V_твх, W = V_твых, S = V_A, s ₀= I.

Затем введем дополнительный нетерминальный символ Z для обозначения конечного состояния и примем F=Z.

Входная и выходная грамматики заданной СУ - схемы являются А - грамматиками, поэтому правила СУ - схемы должны иметь вид <A> ® a<B>, b<B> или <A> ® a, b.

Функцию переходов определим так:

(1) для каждого правила <A> ® a<B>, b<B>, принадлежащего

Q построим команду q(A,a)=(B,b).

(2) для каждого правила <A> ® a,b построим правило вида

<A> ® a<Z>,b<Z>, где Z - заключительное состояние и

команду q(A,a)=(Z,b).

Графически такое построение означает, что правилу

<A> ®a<B>,b<B> ставится в соответствие фрагмент графа автомата.

Рис.4.2. Фрагмент автомата, соответствующий правилу <A> ®a<B>,b<B> СУ - схемы

Построение аналогично построению распознавателя и отличается от него только тем, что переходам приписываются выходные символы.

Построенный преобразователь по заданной на входной ленте цепочке строит соответствующую ей выходную цепочку, если эта цепочка является допустимой. Если же входная цепочка не является допустимой, преобразователь останавливается, не достигнув конечного состояния.

4.4.2. Автоматные модели, используемые для построения цифровых устройств.

Для описания поведения и проектирования цифровых устройств применяют модели конечных автоматов (А - преобразователей) без входной и выходной лент. Входные символы подаются на вход таких автоматов из внешней среды последовательно в дискретные моменты времени, которые определяются генератором тактовых сигналов. Предполагается, что такой генератор существует во внешней среде (вне автомата). Если на вход автомата подается входной сигнал в момент времени t, то к моменту подачи следующего входного сигнала t+1, автомат изменяет свое состояние и вырабатывает новый выходной сигнал.

Работа автоматов рассматриваемого вида описывается с помощью двух функций: функции переходов и функции выходов. Функция переходов j(s_i,p_n)=s_l определяет новое состояние. в которое переходит автомат. Функция выходов задает символ, вырабатываемый на выходе автомата. При этом функция выходов может быть представлена в одном из двух видов. Так, функция выходов может зависеть только от состояния автомата y(s_i). В этом случае автомат называется автоматом Мура. Если же функция выходов зависит от состояния и входного символа y(s_i,p_n), то автомат называется автоматом Мили.

Использование двух функций для описания работы автомата позволяет представить его структуру в виде двух блоков: автомата без выходов( А – распознавателя) и .выходного преобразователя. На рисунке 4.3а.a показана структурная схема автомата Мура, а на рисунке 4.3b - структурная схема автомата Мили. Следует отметить, что структурные схемы автоматов Мили и Мура отличаются только видом выходного преобразователя.

a)

b)

Рис.4.3. Структурные схемы автоматов: a) Мура, b) Мили

Функции переходов и выходов обычно задают в виде таблиц или диаграмм переходов. Например, таблица 4.1 определяет функции переходов автомата Мура, входной алфавит которого состоит из двух символов íp₁,p₂ý, выходной алфавит – из трех символов íw₀,w₁,w₂ý, а алфавит состояний - из четырех символов ís₀,s₁,s₂,s₃ý. Каждому состоянию в таблице приписан определенный выходной символ. Диаграмма переходов, соответствующая этой таблице, показана на рисунке 4.4а.

Таблица 4.1

w		P0	P1
W1	S0	S3	S2
W0	S1	-	-
W1	S2	S2	S1
W2	S3	S0	S1

Таблица 4.2

	P0	P1
S0	S3 , W2	S2 , W1
S1	-	-
S2	S2, W1	S1, W0
S3	S0, W1	S1, W1

Функции переходов и выходов автомата Мили, имеющие те же алфавиты, что и рассмотренный выше автомат Мура, показана в таблице 4.2. В каждой клетке этой таблицы размещаются два символа (значения), разделенные запятой: состояние, в которое переходит автомат, и выходной сигнал, вырабатываемый при этом переходе. Диаграмма переходов, соответствующая этой таблице, показана на рисунке 4.4.б. В общем случае диаграмма переходов автоматов Мили и Мура отличаются тем, что выходные сигналы в автомате Мура приписываются состояниям, а в автомате Мили – переходам, т.е. располагаются на дугах.

Несмотря на то, что автоматы Мили и Мура используют разные выходные преобразователи, они связаны отношением эквивалентности, которое определяется следующим образом.

Определение. Если при подаче одного и того же входного слова на вход автоматов А₁ и А₂, находящихся в начальных состояниях, на выходах автоматов вырабатываются одинаковые выходные слова, то такие автоматы называются эквивалентными.

Используя определение эквивалентности, можно сформулировать следующее утверждение.

Утверждение. Для каждого автомата Мура можно построить эквивалентный ему автомат Мили и, наоборот, для каждого автомата Мили можно построить эквивалентный ему автомат Мура.

Справедливость этого утверждения покажем с помощью описания способов построения автомата эквивалентного заданному автомату.

Вначале рассмотрим способ построения эквивалентного автомата Мили для заданного автомата Мура. Проще всего такое построение выполняется путем преобразования диаграмм переходов, которое заключается в том, что выходной символ, приписанный состоянию автомата Мура, переносится на дуги, входящие в это состояние. В результате такого переноса получаем диаграмму автомата Мили. Формально такой перенос выходных символов соответствует построению новой функции выходов. Если в исходном автомате Мура имеем

j(s_k,p_i)=s_l и y(s_l)=w_r,

то после перестановки в функцию выходов получаем суперпозицию функции

y(s_l)= y(j(s_k,p_i)) =w_r,

которую можно рассматривать, как новую функцию выходов автомата Мили

y’(s_k,p_i) =w_r.

Пример преобразования диаграммы переходов автомата Мура в эквивалентную диаграмму автомата Мили показан на рисунке 4.4.

a) b)

Рис. 4.4. Диаграммы переходов автомата Мура (a) и эквивалентного ему автомата Мили (b).

Если построение автомата Мили, эквивалентного заданному автомату Мура, не приводит к изменению числа состояний и функций переходов, то при преобразовании автомата Мили в автомат Мура может происходить увеличение числа состояний и усложнение функции переходов искомого автомата Мура. Увеличение числа состояний происходит в случае, когда в одно состояние автомата входят несколько дуг, отмеченных разными выходными символами, как это показано на рисунке 4.5a. В вершину, помеченную состоянием sl, входят три дуги, помеченные выходными символами w_t, w_h, w_q. Простое перенесение выходных символов с дуг на вершину в этом случае невозможно, поскольку каждому состоянию должен быть приписан только один выходной символ. Решение этой проблемы заключается в расщеплении состояния s_l на три состояния, каждому из которых приписывается определенный выходной символ, как это показано на рисунке 4.5.б.

a)

b)

Рис. 4.5. Преобразование фрагмента автомата Мили (a) в автомат Мура (b)

Формально преобразование фрагмента на рисунке 4.5. можно описать следующим образом. Если в заданном автомате Мили имеется состояние s_l, такое что

j(s_k,p₁)=s_l y(s_k,p₁)=w_t,

j(s_r,p₂)=s_l y(s_r,p₂)=w_h,

j(s_m,p₃)=s_l y(s_m,p₃),=w_q,

то для построения автомата Мура состояние s_l надо заменить тремя состояниями: s_lt, s_lh, s_lq. При этом первый индекс нового состояния показывает, какому состоянию исходного автомата Мили это состояние соответствует, а второй индекс показывает, какой выходной сигнал должен вырабатываться автоматом в этом состоянии:

y(s_lt) = w_t, y(s_lh) = w_h, y(s_lq) = w_q.

Кроме того, для каждого нового состояния искомого автомата Мура необходимо определить функцию переходов из этого состояния. Такая функция переходов должна соответствовать переходам исходного автомата Мили. Для рассматриваемого фрагмента функция переходов имеет вид:

j(s_lt,p₄) = su, j(s_lh,p₄) = s_u, j(s_lq,p₄) = s_u.

Если в автомате Мура состояние s_u, в свою очередь, заменить несколькими состояниями, то необходимо добавить переходы из каждого состояния s_li в состояния s_uj.

В общем случае для преобразования заданного автомата Мили в автомат Мура необходимо каждое состояние исходного автомата, в которое есть переходы, отмеченные различными выходными символами, заменить несколькими состояниями. Затем для каждого состояния определить функции переходов и выходов.

Итак, в случае рассматриваемого преобразования число состояний искомого автомата Мура может увеличиваться. При этом число состояний не может превысить величину n´m, где m - число состояний исходного автомата, а n – число символов входного алфавита.

В качестве иллюстрации описанного способа построим автомат Мура для автомата Мили, заданного табл. 4.3.

Таблица 4.3

	p0	p1
s0	s0 , w0	s1 , w1
s1	s0 , w1	s0 , w0

Диаграмма переходов этого автомата показана на рисунке 4.6а. Из диаграммы видно, что имеется три перехода из состояния s_0, которые отмечены двумя выходными символами w₀ и w₁. Следовательно, в искомом автомате это состояние нужно заменить двумя состояниями s₀₀ и s₀₁. Выполняя замену состояния s₀ и добавляя переходы для новых состояний, как описано выше, получаем диаграмму переходов автомата Мура в виде, изображенном на рисунке 4.6.б. Этой диаграмме соответствует таблица переходов 4.4.

a)

b)

Рис. 4.6. Диаграммы переходов автомата Мили (a) и эквивалентного ему автомата Мура (b).

Таблица 4.4

w		p0	p1
w0	s00	s00	s11
w0	s01	s00	s11
w1	s11	s00	s01

В заключении отметим, что на практике наряду с рассмотренными автоматами Мили и Мура используют автоматы с двумя выходными преобразователями, один из которых вырабатывает выходные сигналы, зависящие только от состояния, а второй – выходные сигналя, зависящие как от состояния, так и от входного сигнала. Структурная схема автомата такого типа приведена на рисунке 4.7. В таких автоматах часть переходов может вырабатывать выходные сигналы, зависящие от входа, а другая часть переходов выполняется только для перехода в состояния автомата, вырабатывающие выходные сигналы.

Рис 4.7. Схема автомата с двумя выходными преобразователями.

_____________________________________________________________________________

Пред. страница   . След. страница   Раздел   Содержание