7.2.2. Табличное задание автоматов

Поскольку множества A, B и Q автомата  присутствуют в определениях функций перехода и выхода, то для задания  достаточно определить только сами эти функции.

Поскольку области определения  и   конечные множества, то простейший способ представления функций  табличный. В таком способе функции представляются своими графиками. Отображения  и  задаются в виде двух таблиц, одна из которых определяет , а другая  .Эти таблицы имеют строки, соответствующие символам входного алфавита, и столбцы, соответствующие состояниям автомата A.

Элемент таблицы для , лежащий на пересечении i-й строки и j-го столбца, равен (a_i, q_j). Аналогичный элемент таблицы для отображения  равен (a_i, q_j).

 q_j  q_j

. . . .

. . . .

a_i . . . (a_i, q_j) . . . a_i . . . (a_i, q_j) . . .

. . . .

. . . .

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

7.2.3. Канонические уравнения

Пусть для автомата задано фиксированное состояние q₀, в котором он всегда начинает свою работу в начальный момент времени t₀. Тогда, если отображения  и  могут быть записаны в виде формульных выражений, то функционирование такого автомата во времени представляет следующая система соотношений, называемых каноническими уравнениями:

q(t0) = q0;	(1)
q(t+1) = (x(t), q(t));	(2)
y(t) = (x(t), q(t)).	(3)

Здесь q(t) обозначает состояние автомата в момент t, а x(t) и y(t)  это соответственно символ на входе и символ на выходе этого автомата в момент времени t.

Уравнение (1) задает начальное состояние , уравнение (2)  состояние  в следующий момент времени, а уравнение (3)  символ на выходе  в момент t.

Очевидно, что если в последовательные моменты времени

t₀, t₀ + 1, . . . , t₀ + k, . . .

на вход автомата A поступают символы a_i1, ... , a_ik, то с помощью уравнений (1)  (3) можно определить последовательность символов на выходе автомата в процессе переработки указанных входных символов, а также последовательность состояний автомата в процессе работы.

7.3. Функции конечных автоматов

Пусть A = {a₁, ... , a_m}  некоторый алфавит. Словом в этом алфавите называется всякая конечная последовательность: a_i1, ... , a_ik , все элементы которой являются символами из A.

Введем в рассмотрение пустое слово, которое не содержит символов, и обозначается как .

Длиной произвольного слова называется количество символов в нем. Длина произвольного слова обозначается как | |.

Для обозначения множества слов в алфавите A применяется обозначение A^*.

Пусть ,  A^*. Тогда запись обозначает слово, получаемое последовательным выписыванием сначала символов слова , а затем символов . Слово называется сцеплением слов и .

Если  = (A, B, Q, , )  это некоторый автомат, то всякое слово A^* называется входным словом для .

ОПРЕДЕЛЕНИЕ

Пусть A и B являются алфавитами. Тогда отображение f: A^*  B^* называется словарной функцией.

Возьмем произвольное непустое входное слово = a_i1, ..., a_ik. Пусть в начальный момент времени t₀ автомат  находится в состоянии q_r и в моменты времени t₀, t₀+1, . . . , t₀+k  1 на его вход поступают символы a_i1, . . . , a_ik.

В процессе работы автомата в эти же моменты времени на выходе  появляются символы выходного алфавита b_j1, . . . , b_jk, образующие слово , которое называется выходным словом автомата.

Будем говорить, что  из начального состояния q_r перерабатывает слово в слово .