Морфизмы и конечные подстановки

Пусть [cbm]V[/cbm] и [cbm]W[/cbm] — некоторые алфавиты (в частности, [cbm]V=W[/cbm] ). Морфизм — это произвольное отображение [cbm]h\colon V^{\ast}\to W^{\ast}[/cbm] , такое, что [cbm]h(\lambda)=\lambda[/cbm] и

[cbm](\forall x,y\in V^{\ast})\bigl(h(xy)=h(x)h(y)\bigr).[/cbm]

Иначе говоря, морфизм (в данном контексте) — это гомоморфизм свободного моноида [cbm]V^{\ast}[/cbm] в свободный моноид [cbm]W^{\ast}[/cbm] (см. пример 2.7,д).

Теорема 7.11. Любой морфизм [cbm]h\colon V^{\ast}\to W^{\ast}[/cbm] однозначно определяется конечным отображением

[cbm]\bigl\{(a,h(a))\colon\, a\in V,~h(a)\in W^{\ast}\bigr\}.[/cbm]

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

[cbm]a_1\to h(a_1),\quad \ldots,\quad a_n\to h(a_n),[/cbm]

где [cbm]V=\{a_1,\ldots,a_n\}[/cbm] . Чтобы найти образ некоторого непустого слова [cbm]x\in V^{+}[/cbm] , достаточно вместо каждой буквы [cbm]x(i)[/cbm] подставить слово [cbm]h(x(i))\in W^{\ast}[/cbm] .

Например, если [cbm]h[/cbm] задается в виде [cbm]a\to abcba,~b\to ba,~ c\to\lambda[/cbm] , то [cbm]h(abbc)=abcbababa[/cbm] и

[cbm]\begin{aligned}h(h(abbc))&= h^2(abbc)= h(abcbababa)=\\ &= abcba\, ba\,ba\, abcbaba\, abcba\, ba\,abcba=\\ &= abc(ba)^3abc(ba)^2abc(ba)^2abcba. \end{aligned}[/cbm]

Морфизм [cbm]h[/cbm] называется λ-свободным морфизмом, если Для всякого слова [cbm]x\ne\lambda[/cbm] есть [cbm]h(x)\ne\lambda[/cbm] . Морфизм предыдущего примера не является λ-свободным.

Если [cbm]h\colon V^{\ast}\to W^{\ast}[/cbm] — морфизм, то соответствие [cbm]h^{-1}[/cbm] (обратное к [cbm]h[/cbm] ) из [cbm]W^{\ast}[/cbm] в [cbm]V^{\ast}[/cbm] называют инверсным морфизмом (инверсией морфизма, обратным морфизмом).

Таким образом, из определений сразу следует, что [cbm]\forall y\in W^{\ast}[/cbm] имеется [cbm]h^{-1}(y)=\{x\colon\, h(x)=y\}[/cbm] . Для рассмотренного выше примера

[cbm]h^{-1}(abcbaba)= \{abc^n\colon\, n\geqslant0\}= abc^{\ast}.[/cbm]

Определение 7.11. Пусть [cbm]h\colon V^{\ast}\to W^{\ast}[/cbm] — морфизм. Тогда для языка [cbm]L\subseteq V^{\ast}[/cbm] язык [cbm]h(L)=\{y\colon\, y=h(x),~x\in V^{\ast}\}[/cbm] называют морфизмом языка [cbm]L[/cbm] , а для языка [cbm]K\subseteq W^{\ast}[/cbm] язык [cbm]h^{-1}(K)= \{x\colon\, h(x)\in K,~x\in V^{\ast}\}[/cbm] — инверсным морфизмом языка [cbm]L[/cbm] .

Таким образом, язык [cbm]h(L)[/cbm] есть не что иное, как образ языка [cbm]L[/cbm] при отображении [cbm]h[/cbm] , а [cbm]h^{-1}(K)[/cbm] — прообраз языка [cbm]K[/cbm] при отображении [cbm]h[/cbm] .

Соответствие а [cbm]\sigma\subseteq V^{\ast}\times W^{\ast}[/cbm] называют конечной подстановкой, если:

1) а(А) = {А};
2) для каждого [cbm]a\in V[/cbm] множество [cbm]\sigma(a)[/cbm] конечно;
3) для любых цепочек [cbm]x,y\in V^{\ast}[/cbm] имеем [cbm]\sigma(xy)=\sigma(x)\sigma(y)[/cbm] (т.е. множество слов [cbm]\sigma(xy)[/cbm] есть соединение языков [cbm]\sigma(x)[/cbm] и [cbm]\sigma(y)[/cbm] ).

Иначе говоря, конечная подстановка — это своего рода многозначный морфизм, на любой букве алфавита принимающий лишь конечное множество значений.

Точно так же как и для морфизма, легко показать, что конечная подстановка полностью определяется своими значениями на буквах алфавита [cbm]V[/cbm] и, следовательно, может быть задана, как и морфизм, в виде системы "правил замены", в которой одной и той же букве алфавита [cbm]V[/cbm] сопоставляется, вообще говоря, несколько цепочек в алфавите [cbm]W[/cbm] . Например:

[cbm]\begin{array}{lll}a\to abcba,&\qquad a\to ac,&\qquad \\ b\to ba,&\qquad b\to cab,&\qquad \\ c\to aa,&\qquad c\to\lambda,&\qquad c\to bab, \end{array}[/cbm]

или в более короткой записи: [cbm]a\to abcba\mid ac,~ b\to ba\mid cab,~ c\to aa\mid\lambda\mid bab[/cbm] , как мы записывали правила вывода грамматик и системы команд конечных автоматов.

Для нашего примера [cbm]\sigma(ab)=\{abcbaba, abcbacab, acba, accab\}[/cbm] .

Если [cbm]\sigma\subseteq V^{\ast}\times W^{\ast}[/cbm] — конечная подстановка, то обратное соответствие [cbm]\sigma^{-1}\subseteq W^{\ast}\times V^{\ast}[/cbm] называется инверсной (обратной) конечной подстановкой (или инверсией конечной подстановки).

Заметим, что для фиксированного [cbm]y\in W^{\ast}[/cbm] , согласно определениям обратного соответствия и сечения соответствия,

[cbm]\sigma^{-1}(y)= \{x\colon\, (x,y)\in\sigma\}= \{x\colon\, y\in\sigma(x)\}.[/cbm]

Если [cbm]L\subseteq V^{\ast},~ \sigma\subseteq V^{\ast}\times W^{\ast}[/cbm] — конечная подстановка, то [cbm]\sigma(L)=\{y\colon\,(\exists x\in L)y\in\sigma(x)\}[/cbm] .

Если же [cbm]K\subseteq W^{\ast}[/cbm] , то [cbm]\sigma^{-1}(K)= \{x\colon\, (\exists y\in K)y\in\sigma(x)\}= \{x\colon\, \sigma(x)\cap K\ne\varnothing\}[/cbm] .

Нетрудно заметить, что, согласно определению области определения и области значения соответствия, [cbm]\sigma(L)\subset R(\sigma)[/cbm] , a [cbm]\sigma^{-1}(L)\subseteq D(\sigma)= R(\sigma^{-1})[/cbm] . Подчеркнем, что не все цепочки множества [cbm]\sigma(x)[/cbm] при [cbm]x\in\sigma^{-1}(K)[/cbm] содержатся в языке [cbm]K[/cbm] , но найдется хотя бы одна цепочка в [cbm]\sigma(x)[/cbm] , которая принадлежит [cbm]K[/cbm] .

Формулируемая далее теорема связывает конечную подстановку с основными операциями над языками: объединением языков, соединением языков и итерацией языка.

Теорема 7.12. Если [cbm]K[/cbm] и [cbm]L[/cbm] — языки в алфавите [cbm]V[/cbm] , а [cbm]\sigma\subseteq V^{\ast}\times W^{\ast}[/cbm] — конечная подстановка, то

[cbm]\begin{aligned}&{\scriptstyle{\mathsf{1)}}}\quad \sigma(K\cup L)= \sigma(K)\cup \sigma(L);\\[2pt] &{\scriptstyle{\mathsf{2)}}}\quad \sigma(KL)= \sigma(K) \sigma(L);\\[2pt] &{\scriptstyle{\mathsf{3)}}}\quad \sigma(L^{\ast})= (\sigma(L))^{\ast}. \end{aligned}[/cbm]

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

Теорема 7.13. Если [cbm]L\subseteq V^{\ast}[/cbm] и [cbm]K\subseteq W^{\ast}[/cbm] — регулярные языки, [cbm]\sigma\subseteq V^{\ast}\times W^{\ast}[/cbm] — конечная подстановка, то [cbm]\sigma(L)[/cbm] и [cbm]\sigma^{-1}(K)[/cbm] — регулярные языки в алфавитах [cbm]W[/cbm] и [cbm]V[/cbm] соответственно.

Регулярность языка [cbm]\sigma(L)[/cbm] легко доказывается индукцией по построению регулярного выражения с привлечением теоремы 7.12, и детали этого доказательства нетрудно восстановить.

Доказательство регулярности языка [cbm]\sigma^{-1}(K)[/cbm] значительно труднее. Мы используем "технику буферов", которая оказывается полезной в теории формальных языков при доказательстве многих утверждений. Пусть [cbm]M=(Q,W,q_0,F,\delta)[/cbm] — конечный автомат, допускающий язык [cbm]K[/cbm] . Построим конечный автомат [cbm]M'=(Q',W,q_0,F',\delta')[/cbm] следующим образом.

1. [cbm]Q'=\{s_0\}\cup \bigl\{[q,x]\colon\, q\in Q,~ x\in W^{(k)}= W^0\cup W^1\cup \ldots\cup W^k\bigr\}[/cbm] , где [cbm]\mathop{k=\max_{\substack{y\in\sigma(a)\\ a\in W}}|y|,~s_0\notin Q}\limits^{\phantom{A}^{{}^{{}^{.}}}}[/cbm] .

С интуитивной точки зрения множество [cbm]Q'[/cbm] состояний конечного автомата [cbm]M'[/cbm] включает "новое" состояние [cbm]s_0[/cbm] и конечное множество упорядоченных пар из [cbm]Q\times W^{(k)}[/cbm] , где [cbm]k[/cbm] — наибольшая длина среди всех длин слов из образов букв алфавита [cbm]V[/cbm] по подстановке [cbm]\sigma[/cbm] . Образно говоря, каждое состояние нового автомата определяется состоянием старого автомата (допускающего [cbm]K[/cbm] ) и содержимым "буфера" конечной длины [cbm]k[/cbm] для слов из [cbm]W^{\ast}[/cbm] , длина которых не превышает [cbm]k[/cbm] .

2. [cbm]F'=\bigl\{[q_f,\lambda]\colon\,q_f\in F\bigr\}[/cbm] .

3. Система команд [cbm]\delta'[/cbm] содержит команды следующих видов:

[cbm](i)~ s_0a\to [q_0,x][/cbm] , [cbm]a\in V\cup\{\lambda\},~ x\in\sigma(a)[/cbm] ;
[cbm](ii)~ [q,ax]\to[p,x][/cbm] в том и только в том случае, когда [cbm]\delta[/cbm] содержит команду [cbm]qa\to p,~a\in W,~x\in W^{(k)}[/cbm] ;
[cbm](iii)~[q,\lambda]a\to [q,x][/cbm] , где [cbm]x\in\sigma(a),~ a\in V,~ q\in Q[/cbm] .

Неформально работа конечного автомата [cbm]M'[/cbm] может быть описана следующим образом.

Если входная цепочка [cbm]y=\lambda[/cbm] , то [cbm]M'[/cbm] допускает цепочку [cbm]\lambda\in\sigma^{-1}(\lambda)[/cbm] . Это соответствует команде вида [cbm](i)[/cbm] при [cbm]a=\lambda[/cbm] (при условии, конечно, что [cbm]q_0\in F[/cbm] , т.е. что [cbm]\lambda\in K[/cbm] ). Если [cbm]y\ne\lambda[/cbm] , то [cbm]M'[/cbm] прочитает символ [cbm]y(1)[/cbm] и по команде вида [cbm](i)[/cbm] "заполнит буфер" какой-то цепочкой из множества [cbm]\sigma(y(1))[/cbm] , т.е. перейдет в одно из состояний [cbm][q_0,x_1][/cbm] , где [cbm]x_1\in \sigma(y(1))[/cbm] . Далее [cbm]M'[/cbm] начинает "моделировать" работу конечного автомата [cbm]M[/cbm] (согласно командам вида [cbm](ii)[/cbm] ), "читая содержимое буфера" и не обращая внимания на вход, т.е. делая λ-такты. Исчерпав цепочку [cbm]x_1,~M'[/cbm] перейдет в состояние [cbm][r_1,\lambda][/cbm] , где [cbm]q_0\Rightarrow^{\ast}r_1[/cbm] в [cbm]M[/cbm] . Если [cbm]y=y(1)[/cbm] и [cbm]r_1\in F[/cbm] , то [cbm]\sigma(y)\cap K\ne\varnothing[/cbm] и [cbm]y\in\sigma^{-1}(K)[/cbm] . Иначе автомат может допустить другую цепочку из [cbm]\sigma(y(1))[/cbm] и т.д. В том случае, если ни из одного состояния [cbm][q_0,x_1][/cbm] нельзя попасть в состояние [cbm][q_f,\lambda],~q_f\in F[/cbm] , однобуквенная цепочка [cbm]y\notin\sigma^{-1}(K)[/cbm] и [cbm]M'[/cbm] "зависает" в незаключительном состоянии.

Если цепочка [cbm]y[/cbm] имеет второй символ [cbm]y(2)[/cbm] , то по команде вида [cbm](iii)[/cbm] будет обеспечена "подкачка буфера" некоторой цепочкой [cbm]x_2\in \sigma(y(2))[/cbm] v и [cbm]M'[/cbm] опять начнет работать за конечный автомат [cbm]M[/cbm] , читая буфер, и т.д.

Нетрудно видеть, что

[cbm][q_0,x_1]\Rightarrow^{\ast} [r_1,\lambda] \Rightarrow [r_1,x_2] \Rightarrow^{\ast} [r_2,\lambda] \Rightarrow \ldots\Rightarrow^{\ast} [r_m,\lambda],[/cbm]

[cbm]r_m\in F[/cbm] при [cbm]x_i\in\sigma(y(i))[/cbm] для всех [cbm]i=1,\ldots,m[/cbm] и [cbm]|y|=m[/cbm] тогда и только тогда, когда цепочка [cbm]x_1x_2\ldots x_m[/cbm] читается на некотором пути из [cbm]q_0[/cbm] в [cbm]r_m[/cbm] , т.е. когда [cbm]\sigma(y)\cap K\ne \varnothing[/cbm] и [cbm]y\in\sigma^{-1}(K)[/cbm] .

Строгое доказательство равенства [cbm]L(M')=\sigma^{-1}(K)[/cbm] основано на индукции по длине пути в графе автомата. Это доказательство мы не приводим.

Следствие 7.5. Если [cbm]L\subset V^{\ast}[/cbm] и [cbm]K\subset W^{\ast}[/cbm] — регулярные языки, [cbm]h\colon V^{\ast}\to W^{\ast}[/cbm] — морфизм, то [cbm]h(L)[/cbm] и [cbm]h^{-1}(K)[/cbm] — регулярные языки в алфавитах [cbm]W[/cbm] и [cbm]V[/cbm] соответственно.

С интуитивной точки зрения доказанные результаты означают "устойчивость" множества регулярных языков относительно преобразований, задаваемых конечными подстановками (в частности, морфизмами).

Источник

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

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: