Графический способ

Табличный способ

При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Конечным автоматом Мили называется шестерка объектов:
A = <S, X, Y, s0, δ, λ>, где:
S - конечное непустое множество (состояний);
X - конечное непустое множество входных сигналов (входной алфавит)
Y - конечное непустое множество выходных сигналов (выходной алфавит)
s_0∈S - начальное состояние
δ∶S×X→S - функция переходов
λ∶S×X→Y - функция выходов

Таблицы…..

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца a_i и строки x_j в таблице переходов ставится состояние a_s = d[ a_i,x_j], в которое автомат перейдет из состояния a_i под воздействием сигнала x_j; а в таблице выходов – соответствующий этому переходу выходной сигнал y_g = l[ a_i,x_j].

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

Автомат Мура может быть определен как кортеж из 5 элементов, включающий:

· множество внутренних состояний S (внутренний алфавит);

· начальное состояние S ₀;

· множество входных сигналов X (входной алфавит);

· множество выходных сигналов Y (выходной алфавит);

· функция переходов Φ(z, x).

Таблица

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

Графический способ

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a_i и a_s соединяются дугой, направленной от a_i к a_s, если в автомате имеется переход из a_i в a_s, т.е. a_s = d(a_i, x_j). В автомате Мили дуга отмечается входным сигналом x_j, вызвавшим переход, и выходным сигналом y_g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

а) б)

Пусть . Состояния и автомата V называются отличимыми словом , если . В противном случае и называются неотличимыми словом. Конечный автомат, для которого все состояния отличимы друг от друга (т.е. невозможно отождествление состояний), называется приведенным конечным автоматом (или конечным автоматом приведенного вида).

Теорема. Состояния и конечного автомата неотличимы тогда и только тогда, когда они неотличимы словом длины не более

Пусть A ={a₁,..., a_m }, В = {b₁,..., b_n } – конечные алфавиты. Функция f: A^*®В^* называется детерминированной функцией ( д.функцией), если она удовлетворяет следующим условиям:

а) если a Î А^* и ïaï= 1, то ïf(a)ï = l,

b) если a₁ = а(1)... a(k), a₂ = а'(1)... a'(k'), k' £ k, f(a₁) = b(l)... b(k), f(a₂) = b'(l)... b'(k'), и а(1) = а'(1),..., a(s) = a'(s) при не­котором s, 1 s k', то b(l) = b'(l),..., b(s) = b'(s).

Такие функции могут быть использованы для описания дискрет­ных устройств, изменяющих свои состояния в дискретные моменты t = 1, 2, …. Слово aÎА* рассматривается как последовательность вход­ных сигналов, а слово b Î В* – как последовательность сигналов на выходе устройства. Тогда свойство b) означает, что каждый очередной выходной сигнал определяется однозначно последовательностью ранее поступивших входных сигналов и не зависит от того, какие сигналы будут поступать на вход устройства в последующие моменты времени.

Для изучения детерминированных функций удобно задавать их посредством инфор­мационных деревьев.

Информационное дерево в алфавитах А, В, где ôАô = m, это бес­конечный ори­ентированный граф G, каждому ребру которого приписа­на пара вида (а,b), где а Î A, b Î В, и выполнены следующие условия:

1). Существует вершина v₁ (корень информационного дерева), из которой достижимы все остальные вершины графа G. Для каждой вер­шины v графа G существует единственный путь, ведущий от корня v₁, к вершине v.

2). Из каждой вершины v графа G выходит ровно m ребер, кото­рым сопоставлены m пар вида (а₁, b_i1),..., (а_m, b_im), {i₁,..., i_m}Í {1,...,n}, где А = {а₁,..., а_m}, b_js Î В, s = 1,..., m.

На рис.1 приведен фрагмент информационного дерева в алфави­тах А ={0,1}, В = {0,1,2}.

Пусть G – информационное дерево в алфавитах А, В. v₁ – корень этого дерева, и v – произвольная вершина. Подграф графа G, образо­ванный всеми вершинами, достижимыми из v (включая v), сам являет­ся информационным деревом.

Два информационных дерева g₁и g₂ в алфавитах А, В назовем изоморфными, если существует такое взаимно-однозначное отображе­ние q₁ множества вершин дерева g₁ на множество вершин дерева g₂, и взаимно-однозначное отображение q₂ множества ребер дерева g₁ на множество ребер дерева G₂, для которых выполнены условия:

а) если р – ребро, ведущее от вершины v дерева g₁ к вершине v^¢ этого дерева, то ребро q₂ (р) ведет от вершины q₁(v) дерева g₂к вершине q₁ (v^¢) дерева g₂;

б) если ребру р дерева g₁сопоставлена пара (а, b), то ребру q₂ (р) дерева G₂ также сопоставлена пара (а, b).

Отношение изоморфизма разбивает множество поддеревьев G(v) информационного дерева G на классы эквивалентности. Обозначим эти классы Q₁, Q₂, Q₃ .... Если множество Q = { Q₁, Q₂, Q₃ ...} конечно и ½Q½ = s, то д.функция называется ограниченно-детерминированной функцией (о.д. функцией) веса s.

О.д.функция f является конечно автоматной функцией, т.е. функцией, реализуемой инициальным конечным автоматом (A, Q, В, j, y, ). Верно, очевидно, и обратное: каждая конечно автоматная функция является о.д.функцией.

С каждым инициальным автоматом (A, Q, В, j, y, q₀) можно связать о.д.функцию F: А* ® В*, F_v (a)= y(q₀,a). Для произвольных конечных алфавитов A, Q, В можно рассмотреть их коды и считать, что А = {0,1}ⁿ, Q = (0,1}^r, В = (0,1}^m для каких-то n, r, m, т.е. коды букв из одного и того же алфа­вита имеют одинаковую длину. Для простоты будем считать, что m=1.

Итак, пусть о.д.функция f(x₁,...,х_n) вычисляется автоматом V = ({0,l}ⁿ, (0,1}^r, {0,1}, j, y, q₀), где

j ((q₁,..., q_r), (а₁,..., а_n)) = (q₁',..., q_r'),

y ((q₁,…, q_r), (а₁,..., a_n)) = b, (1)

а_j,q_i, q_i', b Î { 0,1 }, j = 1,..., n, i = 1,..., r.

Если ввести параметр t, интерпретируемый как номер такта вре­мени или номер очередной буквы, подаваемой на вход автомата, то для описания функционирования автомата можно использовать систему канонических уравнений:

q(1) = q₀

q(t+1) = j (q(t), x(t))

b(t) = y (q(t), x(t))

Здесь x(t), q(t), b(t) – соответственно входной символ, состояние и выходной символ автомата в момент t.

Дата добавления: 2015-08-13