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

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

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

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


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

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


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


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

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


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


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

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


a_1\to h(a_1),\quad \ldots,\quad a_n\to h(a_n),

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


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


\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}

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


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


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


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

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


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


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


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

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


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


\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}

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


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


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


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


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

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


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


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


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


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


\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}


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


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


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


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

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


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


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


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


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

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


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


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


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

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

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


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


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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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