Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Словарные операторы

 

Рассмотрим конечный алфавит, составленный из букв:.

Элементы декартового произведения называют словами длины в алфавите:. При имеем пустое слово, которое обозначается. Множество всех слов в алфавите обозначается:.

Длину слова обозначим. Например,,.

Пусть и – произвольные слова из алфавита. Приписывание слова к слову называется конкатенацией. Полученное при этом слово обозначается:.

Операция конкатенации обладает следующими свойствами:

а) ассоциативность:;

б) существование нейтрального элемента:.

Очевидно, что эта операция некоммутативна.

Пусть и – два алфавита, и – соответствующие им множества слов. Отображение

 

называется словарным оператором.

Рассмотрим примеры словарных операторов для двоичных алфавитов.

Пример 1. Оператор сопоставляет каждому слову его первую букву:

.

Пример 2. Оператор производит в слове-аргументе замену каждого нуля на единицу и каждой единицы на нуль:

.

Пример 3. Оператор переписывает каждое слово слева направо:

.

Пример 4. Оператор определяется следующим образом:

,

где

,

,

.

 

 

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

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

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

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

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

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

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

, (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). Тогда

.

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

 




Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 721; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.