![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Словарный оператор, реализуемый автоматом
По определению автомата
Обе функции определены на множестве Формальное определение функций Базис индукции. Полагаем Индуктивный переход. Предположим, что функции
Из формул (1) и (2) следует, что функции
Из формул (1) и (2)
Будем считать, что в момент Словарным оператором, реализуемым автоматом
определяемое следующим образом:
Поставим вопрос: каждое ли преобразование слов можно реализовать на автомате? Формально нужно проверить выполнение условия: Оказывается, что для выполнения этого условия необходимо, чтобы словарный оператор 1°. 2°. Словарный оператор 3°. Пусть Остаточным оператором оператора
Корректность этого определения вытекает из свойства 2°. Правило (4) можно сформулировать так: чтобы найти образ слова Из определения (4) получим соотношение
Действительно, из равенства
При Рассмотрим остаточный оператор для словарного оператора, реализуемого автоматом. Для множества слов, имеющих общее начало
Отсюда
Так как
Таким образом, Словарный оператор, обладающий свойствами 1°–3°, называется ограниченно-детерминированным. Мы доказали следующую теорему. Теорема. Словарный оператор, реализуемый конечным автоматом, является ограниченно-детерминированным. Справедлива и обратная теорема. Теорема. Для каждого ограниченно-детерминированного словарного оператора существует реализующий его конечный автомат. Доказательство. Пусть
где
Разбиение (6) обладает следующим свойством
Построим автомат Так
Функция переходов:
Соотношение (9) можно по индукции распространить на слова:
Функция выходов:
Покажем индукцией по длине слова, что
Пусть (12) справедливо для всех слов длины
По предположению индукции
Теорема доказана.
|