Технические дисциплины - ПППСМ

2. АВТОМАТЫ С ПАМЯТЬЮ

2.1. Абстрактные автоматы

Термин «автомат» в обычном понимании – это устройство, выполняющее некоторые функции без участия человека. В этом смысле ЭВМ является автоматом. Но, с другой стороны, мы рассматриваем автомат (его называют абстрактным автоматом) как некоторую математическую модель для описания реальных технических автоматов. Далее будем рассматривать абстрактный автомат (АА).

АА S как математическая модель имеет один вход Z и выход W. Рассмотрим его работу в некотором идеализированном дискретном времени.

 

Z

S

W

 

Для этого на шкале времени t выделяют дискретные моменты времени: 0, 1, 2

Особенности сигналов Z и W АА: в каждый момент времени на вход устройства S поступает входной сигнал zf; zf называют еще буквой множества (алфавита) z. Причем каждой букве zf соответствует один единственный двоичный код, например, 0011.

Аналогично на входной сигнал zf автомат вырабатывает выходной сигнал wg. Ее также называют буквой из множества (алфавита) w. wg соответствует свое единственное двоичное слово (0001).

Пример:

Z = {z1, z2, z3};

W = {w1, w2, w3, w4}.

Пусть автомат такой, что в ответ на буквы zf он формирует на выходе wg следующим образом:

Дискретное время t:    0      1     2     3     4     5

Вход z(t):                      z2 z1 z1 z3 z2 z2 (1)

Выход w(t):                  w1 w3 w4 w2 w1 w3

Как видно из (1), реакция автомата на одну и туже букву может быть различной.

Сигнал wg на выходе автомата с памятью в каждый момент времени t зависит не только от входного сигнала zf в этот же момент времени, но и от предыстории. Т.е. в таком автомате должна быть память о том, какое слово поступило на его вход до рассматриваемого момента времени. Это и есть автомат с памятью.

Автомат называется комбинационным, если некоторой букве входа алфавита z независимо от t соответствует одна и та же буква выходного алфавита.

 

Пример:

Дискретное время t:    0      1     2     3     4     5

Вход z(t):                      z1 z2 z2 z3 z1 z2 (2)

Выход w(t):                  w3 w1 w1 w2 w3 w1

Характерной особенностью автомата с памятью является то, что во время работы он переходит из одного своего внутреннего состояния в другое. Состояние автомата в момент времени t будем обозначать am, а множество состояний (алфавита) множеством  A = {a1, a2,…, am,…, aM}, где a1 – начальное состояние.

Состояние автомата am в момент времени t запоминается в памяти. Отсюда название: автомат с памятью.

 

 

2.2.Определение (задание) абстрактного автомата.

При задании АА не учитывают физической природы входных и выходных сигналов, а рассматривают их как буквы некоторого алфавита, считают, что автомат функционирует в некотором идеализированном дискретном времени t = 0, 1, 2… При этих условиях автомат S определяется как 6-компонентный картеж (вектор).

 

Z

S

W

 

S = (A, Z, W, δ, λ, a1)

Z = {z1, z2,…, zf,…, zF} – множество входных сигналов или входной алфавит.

W = {w1, w2,…, wg,…, wG} - множество выходных сигналов или выходной алфавит.

A = {a1, a2,…, am,…, aM} - множество состояний.

δ - функция переходов. Определяет следующее состояние автомата as = a(t+1) в момент времени (t+1) в зависимости от текущего состояния am и в момент времени t. Т.е. функция перехода δ каждой паре zf состояния автомата am ставит в соответствие новое as в момент времени (t+1), в который он переходит из af.

Функцию  можно описывать следующим образом:

am, zfas

as = δ (am, zf)     или     a(t+1) = δ (am, zf)

a1 – начальное состояние.

λ – функция выхода. Вид ее приводит к разделению автомата на классы:

- автомат Мили;

- автомат Мура.

 

В автомате Мили функция выходов λ ставит в соответствие паре состояний am - zf выходной сигнал wg.

wg = λ (am, zf) - функция выхода для автомата Мили.

В автомате Мура функция выходов λ каждому состоянию автомата am ставит в соответствие выходной сигнал wg.

wg = λ (am) - функция выхода для автомата Мура.

Автомат называется конечным, если множество Z, W и А является конечным.

КС описывается тройкой (вектором) S следующего вида:

S = (Z, W, λ), т.е. задается вектором

Z, W - входной и выходной алфавит,

λ - функция выходов, которая представляет собой описание ПФ.

wg = λ (zf)

КС рассматривается как автомат с одним состоянием.

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

Автоматы Мили и Мура получили наибольшее распространение на практике. Они отличаются способом определения выходного сигнала wg .

Автомат Мили описывается следующими выражениями:

a(t+1) = δ (am, zf)

wg = λ (am, zf)

Состояние в следующий момент времени a(t+1) = as зависит от состояния автомата am и сигнала zf, взятых в момент времени t.

am = am (t);

zf = zf (t);

wg = wg (t).

Чтобы далее не писать значения сигнала в момент времени t, например, am (t), будем просто обозначать эти сигналы без t - am.

Выходной сигнал wg в автомате Мили зависит от состояния автомата am и значения входного сигнала zf в текущий момент времени.

Автомат Мура описывается как:

а (t+1) = δ (am, zf) - функция перехода.

wg = λ (am) - функция выхода.

В автомате Мура в отличие от автомата Мили выходной сигнал wg зависит только от текущего состояния am, но не зависит от zf.

 

Автомат называется полностью определенным, если область определения функций δ и λ содержит все возможные пары (am, zf). Если δ и λ определены не на всех парах (am, zf), то такой автомат называется неполностью определенным (частичным).

 

 



 

Добавить комментарий


Защитный код
Обновить