Словарный оператор, реализуемый автоматом

По определению автомата :

– состояние автомата, в которое он переходит из состояния , когда на его вход поступает символ ;

­ символ на выходе автомата, находящегося в состоянии , в момент, когда на его вход поступает символ .

Обе функции определены на множестве . Расширим область определения до , полагая, что на вход поступает не символ , а слово .

Формальное определение функций и можно дать индуктивно по длине слова.

Базис индукции. Полагаем , .

Индуктивный переход. Предположим, что функции и определены для всех слов , длина которых не превосходит . Рассмотрим произвольное слово длины с первой буквой , то есть . Определим и :

, (1)

. (2)

Из формул (1) и (2) следует, что функции и полностью определяются функциями и , задающими закон функционирования автомата, и являются суперпозициями этих функций. Например, для слова из (1):

.

Из формул (1) и (2) :

,

.

Будем считать, что в момент автомат находится в состоянии , которое будем называть начальным.

Словарным оператором, реализуемым автоматом , называется отображение

,

определяемое следующим образом:

. (3)

Поставим вопрос: каждое ли преобразование слов можно реализовать на автомате? Формально нужно проверить выполнение условия: .

Оказывается, что для выполнения этого условия необходимо, чтобы словарный оператор обладал следующими тремя свойствами.

1°. . Следует из (2) и (3).

2°. , где . Словарный оператор должен отображать слова с общим началом в слова с общим началом.

Словарный оператор , обладающий свойствами 1° и 2°, называется детерминированным.

3°. Пусть – детерминированный оператор, а – некоторое слово.

Остаточным оператором оператора , порожденным словом , называется словарный оператор , действующий по правилу:

, если . (4)

Корректность этого определения вытекает из свойства 2°. Правило (4) можно сформулировать так: чтобы найти образ слова при отображении , припишем к нему слева слово , найдем образ полученного слова при отображении и удалим в полученном слове букв.

Из определения (4) получим соотношение

. (5)

Действительно, из равенства по определению (4) следует

и .

При . Отсюда получаем (5).

Рассмотрим остаточный оператор для словарного оператора, реализуемого автоматом. Для множества слов, имеющих общее начало , имеем

.

Отсюда

.

Так как – одно из состояний автомата , то

.

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

Словарный оператор, обладающий свойствами 1°–3°, называется ограниченно-детерминированным.

Мы доказали следующую теорему.

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

Справедлива и обратная теорема.

Теорема. Для каждого ограниченно-детерминированного словарного оператора существует реализующий его конечный автомат.

Доказательство. Пусть – ограниченно-детерминированный словарный оператор. Обозначим через число различных остаточных операторов словарного оператора . Если , то – множество всех остаточных операторов словарного оператора (). Поскольку каждый остаточный оператор порождается некоторым словом , разобьем множество всех слов на классов:

, (6)

где . Обозначим класс, в который входит слово через . Имеем

.

Разбиение (6) обладает следующим свойством

. (7)

Построим автомат , реализующий оператор .

Так , то , . В качестве состояний автомата возьмем классы разбиения (6):

. (8)

Функция переходов:

. (9)

Соотношение (9) можно по индукции распространить на слова:

. (10)

Функция выходов:

. (11)

Покажем индукцией по длине слова, что , то есть

. (12)

.

Пусть (12) справедливо для всех слов длины . Рассмотрим произвольное слово длины с последней буквой :

.

По предположению индукции . На основании (10) . Тогда

.

Теорема доказана.