6.3. Сети из автоматов

Автомат называется комбинационным, если для каждого входного символа а и любых состояний q_i и q_j: λ(q_i, a)= λ(q_j, a), иначе говоря, если выходной символ не зависит от состояния и определяется текущим входным символом. В таком автомате все состояния эквивалентны и, следовательно, минимальный комбинационный автомат имеет одно состояние. Функция переходов в нем вырождена; его поведение однозначно задается функцией выходов с одним аргументом: λ(a_i)=V_j.

Автомат называется логическим, если его входной алфавит состоит из 2^m двоичных наборов длины m, а выходной из 2ⁿ двоичных наборов длины n. Функция выходов логического комбинационного автомата – это просто система n логических функций от m переменных (i-я функция определяет значения i-ой компоненты в выходном векторе автомата).

6.4. Синхронные сети

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

Под состоянием сети из m одновременно работающих автоматов S₁, …, S_m (компонент сети) понимается вектор (q_i1, …, q_im), где q_ij – состояние автомата S_j. Поэтому, в общем случае число возможных состояний сети равно произведению чисел состояний составляющих ее компонент.

Вектор – состояние сети указывает, в каких состояниях находятся компоненты сети в один и тот же момент времени. Следовательно, при описании автоматных сетей, в отличие от абстрактных автоматов, необходимо вводить понятие времени. Существует два способа – синхронный и асинхронный. При синхронном способе вводится шкала времени, которая делится на отрезки одинаковой длины (такты), нумеруемые 0, 1, 2, …. Входное слово рассматривается как слово длины к, занимает к тактов. Его буквы можно считать функциями времени a(t) – буква, появившаяся в момент t. Автоматные функции δ и λ реализуются с задержкой. Время задержки функции равно единице: δ(q(t), a(t))=q(t+1); состояние определяется заранее. Время задержки λ обычно считают равным нулю: δ(q(t),a(t))=V(t).

Рассмотрим некоторые основные виды соединения автоматов:

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

а) С раздельными входами и алфавитами А₁ и А₂ (рис. 21а).

Здесь пару автоматов S₁ и S₂

S₁=( A₁, Q₁, V₁, δ₁, λ₁)

S₂=( A₂, Q₂, V₂, δ₂, λ₂)

можно рассматривать как один автомат S=(A, Q, V, δ, λ), определенный так: A=A₁xA₂, Q=Q₁·Q₂, V=V₁·V₂,

следовательно, входной символ автомата S – это пара символов а=(а₁, а₂), состояние S

q=(q¹, q²),

δ(q, a)=δ((q¹, q²), (а¹, а²))= (δ₁(q¹, q²), δ₂(а¹, а²)),

т.е. смена состояний происходит независимо и одновременно.

Аналогично

λ(q, a)= (λ ₁(q¹, q²), λ ₂(а¹, а²))= (V¹, V²).

Автомат S называется прямым произведением автоматов S₁ и S₂.

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

Этот автомат определяется аналогично, с той лишь разницей, что алфавиты А₁, А₂ и А совпадают, поэтому

δ(q, a)= (δ₁(q¹, а), δ₂(q², а)) и.т.д.

2. Последовательное соединение.

Эту сеть можно описать как автомат S=(A, Q, V, δ, λ), причем A=A₁, V=V₂, V₁=A₂. Как и прежде Q= Q₁·Q₂. Если задержка λ₁ равна нулю: λ ₁(q¹(t), a(t)) = V¹(t), то

q(t+1)=(q¹(t+1), q²(t+1)) = (δ₁(q¹(t), a(t), δ₂(q²(t), λ ₁(q¹(t), a(t)))).

Выражение в правой части зависит только от q(t) = (q¹(t), q²(t)) и a(t). Эта функция и есть функция δ для S: q(t+1) = δ(q(t), a(t)). Ее конкретная таблица зависит о таблиц δ₁, δ₂ и λ.

3. Обратная связь.

Заключается в том, что выход автомата S₁ присоединяется к одному из его входов.

Рассмотрим случай, когда S₁ – комбинационный автомат без задержки и предположим, что S₁ реализует логическую функцию .

Вход х₁ оставлен внешним, на вход х₂ подана замкнутая обратная связь. Пусть в момент t V=0, тогда x₂(t)=0 V(t)= =1, т.е. V(t) равен и нулю и единице в один и тот же момент, т.е. получаем противоречие. Этот пример показывает, что сеть из автоматов, содержащая контур обратной связи без задержек, может не иметь конкретной автоматной интерпретации.

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

Действительно, такая сеть для автомата с функциями q(t+1)=δ(q(t), a(t)), V(t)=λ(q(t), a(t)) приведена на схеме.

Здесь блок λ – комбинационный автомат с входным алфавитом AxQ и выходным алфавитом V; блок δ – комбинационный автомат с тем же входным алфавитом и выходным Q.

Блок D – блок, задерживающий поступающие на него сигналы на 1 такт. Он представляет собой автомат Мура, входной и выходной алфавиты которого совпадают и равны Q={q₁, …, q_n}, алфавит состояний R={r₁, …, r_n} имеет ту же мощность, что и Q, λ_D(r_i)=q_i, δ_D(r_i, q_j)=r_j для всех i, j=1, …, n.

Сеть Петри – математическая модель дискретной динамической системы, в т.ч. и информационной.

Сетью петри называется набор N=(T,P,F,M₀), где Т – конечное множество символов, называемых переходами; Р - конечное множество символов, называемых местами; РТ=; F – функция инцидентности.

F: TPPT{0;1},

M₀ – начальная разметка мест:

M₀: Р{0;1;2….}.

Неформально сеть Петри представляют размеченным ориентированным графом со множеством вершин ТР. Из вершины места рР, изображаемой кружком ведет дуга в вершину-переход tT, изображаемому прямоугольником, тогда и только тогда, когда

F(p,t)=1

(p - входное место перехода t; на рис 16 P={p₁, p₂, p₃}, T={a, b, c, d}). Из вершины-перехода t ведет дуга в вершину-место р тогда и только тогда, когда

F(p,t)=1

(p - входное место перехода t). Место р помечается разметкой M₀(p)0, часто изображаемой различным числом точек (фишек).

Динамика поведения моделируемой сети описывается в терминах функционирования сети Петри.

Сеть функционирует в дискретном времени, переходя от разметки к разметке. Конечная разметка – это функция: М: Р{0,1,2,…}; смена разметок происходит в результате срабатывания переходов сети. Переход tT может сработать при разметке М, если для любого рР:

M(p)-F(p,t)0,

т.е. если каждое его входное место имеет хотя бы одну фишку. В результате срабатывания t при разметке M последняя сменяется на M' по правилу: для любого рР

M'(p)= M(p)-F(p,t)+ F(t,p),

т.е. переход t изымает по фишке из каждого своего входного места и посылает по фишке в каждое свое выходное место. Если может срабатывать несколько переходов, то срабатывает один, любой из них. Сеть останавливается, если при некоторой разметке (тупиковая разметка) ни один из ее переходов не может срабатывать. При одной и той же начальной разметке сеть Петри может порождать, в силу недетерминированности ее функционирования, различные последовательности срабатывания ее переходов. Эти последовательности образуют слова в алфавите Т, а множество всевозможных слов, порождаемых сетью Петри, называется ее языком. Две сети Петри эквивалентны, если они порождают один и тот же язык.