Морфизмы и конечные подстановки
Пусть и — некоторые алфавиты (в частности, ). Морфизм — это произвольное отображение , такое, что и
Иначе говоря, морфизм (в данном контексте) — это гомоморфизм свободного моноида в свободный моноид (см. пример 2.7,д).
Теорема 7.11. Любой морфизм однозначно определяется конечным отображением
Обычно такое отображение задается в форме, напоминающей запись правил вывода порождающей грамматики:
где . Чтобы найти образ некоторого непустого слова , достаточно вместо каждой буквы подставить слово .
Например, если задается в виде , то и
Морфизм называется λ-свободным морфизмом, если Для всякого слова есть . Морфизм предыдущего примера не является λ-свободным.
Если — морфизм, то соответствие (обратное к ) из в называют инверсным морфизмом (инверсией морфизма, обратным морфизмом).
Таким образом, из определений сразу следует, что имеется . Для рассмотренного выше примера
Определение 7.11. Пусть — морфизм. Тогда для языка язык называют морфизмом языка , а для языка язык — инверсным морфизмом языка .
Таким образом, язык есть не что иное, как образ языка при отображении , а — прообраз языка при отображении .
Соответствие а называют конечной подстановкой, если:
1) а(А) = {А}; 2) для каждого множество конечно; 3) для любых цепочек имеем (т.е. множество слов есть соединение языков и ).
Иначе говоря, конечная подстановка — это своего рода многозначный морфизм, на любой букве алфавита принимающий лишь конечное множество значений.
Точно так же как и для морфизма, легко показать, что конечная подстановка полностью определяется своими значениями на буквах алфавита и, следовательно, может быть задана, как и морфизм, в виде системы "правил замены", в которой одной и той же букве алфавита сопоставляется, вообще говоря, несколько цепочек в алфавите . Например:
или в более короткой записи: , как мы записывали правила вывода грамматик и системы команд конечных автоматов.
Для нашего примера .
Если — конечная подстановка, то обратное соответствие называется инверсной (обратной) конечной подстановкой (или инверсией конечной подстановки).
Заметим, что для фиксированного , согласно определениям обратного соответствия и сечения соответствия,
Если — конечная подстановка, то .
Если же , то .
Нетрудно заметить, что, согласно определению области определения и области значения соответствия, , a . Подчеркнем, что не все цепочки множества при содержатся в языке , но найдется хотя бы одна цепочка в , которая принадлежит .
Формулируемая далее теорема связывает конечную подстановку с основными операциями над языками: объединением языков, соединением языков и итерацией языка.
Теорема 7.12. Если и — языки в алфавите , а — конечная подстановка, то
Основной результат, рассматриваемый в этом дополнении, составляет следующая теорема.
Теорема 7.13. Если и — регулярные языки, — конечная подстановка, то и — регулярные языки в алфавитах и соответственно.
Регулярность языка легко доказывается индукцией по построению регулярного выражения с привлечением теоремы 7.12, и детали этого доказательства нетрудно восстановить.
Доказательство регулярности языка значительно труднее. Мы используем "технику буферов", которая оказывается полезной в теории формальных языков при доказательстве многих утверждений. Пусть — конечный автомат, допускающий язык . Построим конечный автомат следующим образом. 1. , где .
С интуитивной точки зрения множество состояний конечного автомата включает "новое" состояние и конечное множество упорядоченных пар из , где — наибольшая длина среди всех длин слов из образов букв алфавита по подстановке . Образно говоря, каждое состояние нового автомата определяется состоянием старого автомата (допускающего ) и содержимым "буфера" конечной длины для слов из , длина которых не превышает .
2. .
3. Система команд содержит команды следующих видов:
, ; в том и только в том случае, когда содержит команду ; , где .
Неформально работа конечного автомата может быть описана следующим образом.
Если входная цепочка , то допускает цепочку . Это соответствует команде вида при (при условии, конечно, что , т.е. что ). Если , то прочитает символ и по команде вида "заполнит буфер" какой-то цепочкой из множества , т.е. перейдет в одно из состояний , где . Далее начинает "моделировать" работу конечного автомата (согласно командам вида ), "читая содержимое буфера" и не обращая внимания на вход, т.е. делая λ-такты. Исчерпав цепочку перейдет в состояние , где в . Если и , то и . Иначе автомат может допустить другую цепочку из и т.д. В том случае, если ни из одного состояния нельзя попасть в состояние , однобуквенная цепочка и "зависает" в незаключительном состоянии.
Если цепочка имеет второй символ , то по команде вида будет обеспечена "подкачка буфера" некоторой цепочкой v и опять начнет работать за конечный автомат , читая буфер, и т.д.
Нетрудно видеть, что
при для всех и тогда и только тогда, когда цепочка читается на некотором пути из в , т.е. когда и .
Строгое доказательство равенства основано на индукции по длине пути в графе автомата. Это доказательство мы не приводим.
Следствие 7.5. Если и — регулярные языки, — морфизм, то и — регулярные языки в алфавитах и соответственно.
С интуитивной точки зрения доказанные результаты означают "устойчивость" множества регулярных языков относительно преобразований, задаваемых конечными подстановками (в частности, морфизмами).
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|