Модель абстрактного автомата

Понятие "состояние" используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и/или слов выходного языка от символов и/или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата qÎQ и для каждого символа xÎX в момент дискретного времени [t] на выходе устройства генерируется символ yÎY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата qÎQ и для каждого символа xÎX в момент дискретного времени [t] автомат переходит в очередное состояние qÎQ. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (q_1[[1]q₂[2]q₃[3]...) и последовательности выходных символов (y₁[1]y₂[2]y₃[3]...), которые для последовательности символов (x₁[1]x₂[2]x₃[3]...) разворачиваются в моменты дискретного времени t = 1,2,3,.... В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках - последовательности символов алфавитов X, Y и Q.

Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и Q, а операциями - две функции j и y:

M = á X; Y; Q; y; jñ, (1.1)

Так как области определения функций переходов и выходов совпадают, то обобщенный оператор поведения автомата можно представить так:

(y;j): (QÄX) ® (QÄY). (1.2)

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:

(1.3)

Если на входе автомата имеем слово a = (x₁x₂x₃...x_s), то, считывая последовательно символы этого слова, на выходе автомата генерируется последовательность символов слова b по следующей схеме:

b[1]=(j(q[1];x₁[1]));

b[2]=(j(q[1];x₁[1])j(q[2];x₂[2])) = (j(q[1];x₁[1])j(q[1];(x₁[1]x₂[2])));

…………………………………………….. (1.4)

b[s] = (j(q[1];x₁[1])j(q[2];x₂[2]) ... j(q[s];x_s[s])) =

= (j(q[1];x₁[1])j(q[1];(x₁[1]x₂[2])) ... j(q[1];(x₁[1]x₂[2] ... x_s[s])));

Так как на каждом i-ом такте к слову длины (i-1) приписывается справа очередной символ j(q[1];x₁[1]x₂[2]...x_i[i]), то последовательность символов выходного слова можно записать так:

b = (j(q;x₁)j(q;(x₁x₂))...j(q;(x₁x₂...x_s)))=(j(q;a)). (1.5 )

Если считывание символов входного слова a выполняется последовательно слева направо, то всегда найдется такая последовательность (x₁x₂...x_s-1)=g, для которой

a = ((x₁x₂...x_s-1)x_s) =(gx_s), (1.6)

где g =(x₁x₂...x_s-1) - "голова" слова a;

x_s - "хвост" слова a.

Поэтому если входное слово a = (gx_s), то выходное слово b можно записать так:

b = j(q;a ) = j(y(q;g );x_s). (1.7)

Это означает, что последний символ слова b есть результат работы автомата, начавшего работу в состоянии q и считавшего последний символ слова a, но значение этого символа зависит от всей входной последовательности.

Длина выходного слова всегда равна длине входного слова.

Изменение состояний автомата для последовательности символов слова a = (x₁x₂x₃...x_s) может быть описано следующей схемой:

q[2] = y(q[1];x₁[1]);

q[3] = y(q[2];x₂[2]) = y(y(q[1];(x₁[1]);x₂[2])); (1.8)

..................................................................................................................................

q[s+1] = y(q[s];x_s[s]) = y(y... (y(y(y(q[1];x₁[1]);x₂[2]);x₃[3]);...x_s-1[s-1]);x_s[s]),

где q[1] -начальное состояние автомата.

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

q[s+1] = y(y... (y(y(y(q;x₁);x₂);x₃)...x_s-1);x_s). (1.9)

Если входное слово a = (gx_s), то изменение состояния автомата может быть описано так:

q[s+1] = y(y(q;g );x_s). (1.10 )

Это означает, что q[s+1] есть последнее состояние автомата, начавшего работу в состоянии q и считавшего последний символ слова a в момент дискретного времени s.

Функциональная схема абстрактного автомата представлена на рис.1.2.

Рис.1.2 Функциональная схема абстрактного автомата.

Если функции переходов и выходов однозначно определены для каждой пары (q;x)Î(QÄX), то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определенным.

Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.

Если у автомата задано начальное состояние q=q₀ÎQ, в котором он находится всегда до приема первого символа входного слова, то автомат называют инициальным. В этом случае модель автомата записывают так:

M = á X;Y;Q;y;j;q₀ñ, (1.11)

Последовательность символов в слове b и последовательность состояний автомата q однозначно определяются начальным состоянием автомата q=q₀ и последовательностью символов во входном канале a. Поэтому отображение входного слова a на выходное слово b чаще называют автоматным отображением, то есть b = М(q₀;a), а М – автоматным оператором.

Автоматное отображение обладает свойствами:

1) входное и выходное слова имеют одинаковую длину (свойство сохранения длины);

2) y_i-ый символ выходного слова зависит от всей последовательности символов входного слова, до x_i-го включительно; кроме того если a=a₁a₂, то b=b₁b_2..

Контрольные вопросы

1) Каковы особенности автоматов с бесконечной памятью?

2) Какие операции свойственны алгебре автоматов?

3) Что такое детерминированный автомат?

4) Что такое недетерминированный автомат?

5) Объясните содержание оператора поведения автомата.

6) Что является "головой" и "хвостом" последовательности символов?

Дата добавления: 2015-07-26; просмотров: 193; Нарушение авторских прав

Мы поможем в написании ваших работ!