Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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

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


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


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

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


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

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


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


[math]\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}[/math]

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


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


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


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

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


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


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


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

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


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


[math]\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}[/math]

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


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


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


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


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

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


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


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


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


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


[math]\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}[/math]


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


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


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


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

1. [math]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\}[/math], где [math]\mathop{k=\max_{\substack{y\in\sigma(a)\\ a\in W}}|y|,~s_0\notin Q}\limits^{\phantom{A}^{{}^{{}^{.}}}}[/math].


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


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


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


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

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


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


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


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

[math][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],[/math]

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


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


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


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved