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

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

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

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

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


Алгебраические свойства КС-языков

Алгебраические свойства КС-языков


В этой лекции мы рассмотрим некоторые операции над КС-языками, относительно которых множество всех КС-языков замкнуто. Напомним, что множество всех регулярных языков (в произвольно фиксированном алфавите) замкнуто относительно операций (конечного) объединения, соединения, пересечения, дополнения (до универсального языка) и итерации. В этом разделе мы докажем прежде всего что множество КС-языков замкнуто относительно операций объединения, соединения и итерации. Потом мы увидим, что пересечение двух КС-языков, вообще говоря, не является КС-языком, но можно доказать более слабое утверждение: пересечение КС-языка с регулярным языком есть КС-язык.


Суперпозиция языков


Начнем с определения новой операции над языками — операции суперпозиции.


Пусть [math]V=\{a_1,\ldots,a_n\}[/math] — произвольный алфавит, каждой букве [math]a_i[/math] которого сопоставлен однозначно некоторый алфавит [math]V_{a_i}[/math] (не исключено, что все алфавиты [math]V,V_{a_1},\ldots,V_{a_n}[/math] совпадают); в алфавите [math]V[/math] фиксируем произвольно язык [math]L\subseteq V_{a_i}^{\ast}[/math], а в каждом из алфавитов [math]V_{a_i}[/math] — язык [math]L_{a_i}\subseteq V_{a_i}^{\ast}[/math].


Рассмотрим множество всех таких цепочек в объединении алфавитов [math]V_{a_1}\cup\ldots\cup V_{a_n}[/math], которые могут быть получены из цепочек языка [math]L[/math] следующим образом: берем произвольную цепочку [math]b_1\ldots b_k\in L[/math] и каждую букву [math]b_j[/math] в ней заменяем произвольной цепочкой [math]x_j\in L_{b_j}\colon[/math]


[math]\begin{array}{cccc}b_1&\quad b_2&\quad \ldots&\quad b_k\\ \downarrow&\quad \downarrow&\quad &\downarrow\\ x_1&\quad x_2&\quad \ldots&\quad x_k \end{array}[/math]

в результате чего получаем цепочку [math]x_1x_2\ldots x_k[/math].


Множество всех цепочек вида [math]x_1x_2\ldots x_k[/math], получаемых описанным выше способом, называют суперпозицией (или подстановкой) языков [math]L_{a_1},\ldots,L_{a_n}[/math] в язык [math]L[/math] и обозначают [math]\mathcal{S}(L,L_{a_1},\ldots,L_{a_n})[/math]. При этом полагают, что если пустая цепочка [math]\lambda[/math] принадлежит языку [math]L[/math], то она принадлежит суперпозиции [math]\mathcal{S}(L,L_{a_1},\ldots,L_{a_n})[/math].


При определении суперпозиции на алфавиты [math]V,V_{a_1},\ldots,V_{a_n}[/math] не накладывается никаких ограничений. Они могут и попарно не пересекаться, а могут и все совпадать. В любом случае суперпозиция [math]\mathcal{S}(L,L_{a_1},\ldots,L_{a_n})[/math] есть язык в алфавите [math]V_{a_1}\cup\ldots\cup V_{a_n}[/math]. Точно так же среди языков [math]L_{a_i}[/math], "подставляемых" в язык [math]L[/math], может оказаться и сам язык [math]L[/math], т.е. язык можно подставлять сам в себя, причем многократно.


Заметим, что если язык [math]L[/math] не содержит пустую цепочку, суперпозиция [math]\mathcal{S}(L,L_{a_1},\ldots,L_{a_n})[/math] может ее содержать. Это возможно, если каждый язык [math]L_{a_i}[/math] содержит пустую цепочку. Тогда, беря произвольно [math]x\in L[/math] и заменяя каждый ее символ пустой цепочкой, получаем пустую цепочку как элемент суперпозиции. Если же пустая цепочка принадлежит [math]L[/math], то, по определению, суперпозиция обязана ее содержать.


Еще заметим, что для разных вхождений одной и той же буквы [math]b_j[/math] цепочки [math]x\in L[/math] совершенно не обязательно заменять эту букву одной и той же цепочкой языка [math]L_{b_j}[/math]: каждому вхождению может быть сопоставлена своя цепочка этого языка.




Пример 8.18. Зададим язык [math]L[/math] в алфавите [math]V=\{a,b,c\}[/math] как множество [math]\{a^nb^nc^n\colon n\geqslant1\}[/math]. Букве [math]a[/math] алфавита [math]V[/math] сопоставим алфавит [math]V_a=\{0;1\}[/math], выбрав в качестве языка [math]L_a[/math] множество [math]\{0^n1^n\}_{n\geqslant0}[/math]. Букве [math]b\in V[/math] сопоставим алфавит [math]V_b=\{a\}[/math] и в этом алфавите — язык [math]L_b=\{a^{n^2}\colon n\geqslant0\}[/math]. Наконец, букве [math]c[/math] алфавита [math]V[/math] сопоставим алфавит [math]V_c=\{a,b,c\}=V[/math] и в качестве языка [math]L_c[/math] возьмем язык [math]L[/math], пополненный пустой цепочкой, т.е. [math]L_c=\{a^nb^nc^n\colon n\geqslant0\}[/math].


Возьмем цепочку [math]aabbcc\in L[/math] и первый символ а заменим цепочкой [math]0011\in L_a[/math], второй символ [math]a[/math] — цепочкой [math]01\in L_a[/math], первый символ [math]b[/math] — цепочкой [math]a^{729}\in L_a[/math] (при [math]n=27[/math]), второй символ [math]b[/math] — пустой цепочкой, первый символ [math]c[/math] — пустой цепочкой, второй символ — цепочкой [math]abc\in L_c[/math]. В результате получим следующую цепочку, принадлежащую суперпозиции [math]\mathcal{S}(L,L_a,L_b,L_c)\colon[/math]


[math]001101a^{729}abc= 001101\underbrace{aaa\ldots aa}_{729\,\text{times}} abc.[/math]

Проделывая аналогичные действия с любой другой цепочкой языка [math]L[/math] или же производя другие замены символов той же самой цепочки, будем получать все новые цепочки определенной выше суперпозиции. В данном случае будем иметь [math]\lambda\in \mathcal{S}(L,L_a,L_b,L_c)[/math], так как каждый из языков [math]L_a,\,L_b[/math] и [math]L_c[/math] содержит пустую цепочку.


Пример 8.19. Пусть алфавит [math]V[/math] есть русский алфавит {A,Б,..,Э,Ю,Я}, а язык [math]L[/math] — множество всех слов русского языка. Каждой букве русского алфавита сопоставим язык, состоящий из единственной однобуквенной цепочки [math]\alpha[/math], которая стоит рядом с указанной русской буквой на клавиатуре компьютера. Так, [math]L_A=\{F\},~ L_B=\{<\}[/math] и т.д. Все эти языки можно считать языками в латинском алфавите, дополненном определенными специальными символами, такими, как [math][,],\{,\},<,<[/math] и т.п. Тогда, если мы в качестве исходной цепочки языка [math]L[/math] возьмем слово УЧЕБНИК, то получим такую цепочку в суперпозиции [math]\mathcal{S}(L,L_A,\ldots)\colon\, EXT<YBR[/math].


Разобранные примеры показывают, что суперпозицию можно рассматривать как своего рода "кодирование" цепочек языка [math]L[/math] с заменой в них каждой буквы цепочкой другого языка. Действительно, такая замена является одним из простейших способов "шифровки" текстов.


Замечание 8.11. Суперпозицию можно определить через соответствие. Введем соответствие [math]\sigma\subseteq V\times \{L_{a_1}\cup\ldots\cup L_{a_n}\}[/math] так, что для каждого [math]i=\overline{1,n}[/math] упорядоченная пара [math](a_i,y)[/math] принадлежит а тогда и только тогда, когда [math]y\in L_{a_i}[/math]. В этом случае


[math]\mathcal{S}(L,L_{a_1},\ldots,L_{a_n})= \bigcup\limits_{x\in L\setminus \{\lambda\}} \sigma\bigl(x(1)\bigr)\ldots \sigma\bigl(x(k)\bigr)\cup (\{\lambda\}\cap L)[/math], где [math]x=x(1)\ldots x(k)[/math].

В терминах суперпозиции могут быть представлены такие операции над языками как объединение, соединение и итерация.




Объединение языков


Пусть [math]L_1[/math] и [math]L_2[/math] — два произвольных языка в каком-то алфавите [math]W[/math]. Возьмем произвольный двухбуквенный алфавит [math]V=\{a,b\}[/math] и язык [math]L[/math] зададим как [math]L=V[/math] (т.е. язык [math]L[/math] состоит из двух однобуквенных цепочек [math]a[/math] и [math]b[/math]). Рассмотрим суперпозицию [math]\mathcal{S}(L,L_a,L_b)[/math], где [math]L_a=L_1,~L_b=L_2[/math]. Докажем, что эта суперпозиция совпадает с объединением [math]L_1\cup L_2[/math]. Действительно, если мы возьмем цепочку [math]a\in L[/math], то ее единственную букву мы можем, согласно определению суперпозиции, заменить любой цепочкой языка [math]L_1[/math]. Точно так же, строя суперпозицию, вместо цепочки [math]b\in L[/math] получим все цепочки языка [math]L_2[/math]. Итак,


[math]L_1\cup L_2=\mathcal{S}\bigl(\{a,b\},L_1,L_2\bigr).[/math]



Соединение языков


Снова фиксируем произвольно в произвольном алфавите [math]W[/math] языки [math]L_1[/math] и [math]L_2[/math]. Опять-таки произвольно выберем двухбуквенныи алфавит [math]\{a,b\}[/math], определив язык [math]L=\{ab\}[/math]. Положим, как и выше, [math]L_a=L_1,~L_b=L_2[/math]. Тогда суперпозиция [math]\mathcal{S}(L,L_a,L_b)= \mathcal{S}(\{ab\},L_a,L_b)[/math] совпадет с соединением [math]L_1L_2[/math]. В самом деле, символ [math]a[/math] единственной цепочки [math]ab[/math] языка [math]L[/math] можно при построении суперпозиции заменять любой цепочкой языка [math]L_1[/math], а символ [math]b[/math] — любой цепочкой языка [math]L_2[/math]. В результате записанная выше суперпозиция совпадет с множеством всех цепочек, представимых как соединение [math]xy[/math], где [math]x\in L_1,~y\in L_2[/math]. Но это и есть соединение [math]L_1L_2[/math]. Итак,


[math]L_1L_2=\mathcal{S}\bigl(\{ab\},L_1,L_2\bigr).[/math]



Итерация языков


Рассуждая аналогично, можно показать, что итерация [math]L^{\ast}[/math] языка [math]L[/math] равна


[math]L^{\ast}=\mathcal{S}(a^{\ast},L)[/math], а позитивная итерация [math]L^{+}=\mathcal{S}(a^{+},L)[/math]

(для любых алфавита [math]W[/math], языка [math]L\subseteq W^{\ast}[/math] и однобуквенного алфавита [math]V=\{a\}[/math]).


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


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

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